由4 5 6组成的数字的总和

Question

我们给出三个整数x,y和z.你必须找到所有数字的总和,其数字仅由4,5和6组成,十进制表示最多为x四,十进制表示最多为y五,十进制表示最多为z六

我正在使用Describe Here这个概念

我的代码:

// fact[i] is i!
    for(int i=0;i<=x;i++)
        for(int j=0;j<=y;j++)
            for(int k=0;k<=z;k++){

           int t = i+j+k;
           if(t==0) continue;
           long ways = fact[t-1];
           long pow = (long) Math.pow(10,t-1);
           long rep=0;
           if(i!=0){
               rep = fact[j]*fact[k];
               if(i>0) rep*=fact[i-1];

              o+= 4*pow*(ways/rep); 
           }

           if(j!=0){
               rep = fact[i]*fact[k];
               if(j>0) rep*=fact[j-1];

              o+= 5*pow*(ways/rep); 
           }

           if(k!=0){
               rep = fact[i]*fact[j];
               if(k>0) rep*=fact[k-1];

              o+= 6*pow*(ways/rep); 
           }

        }

但我得到了错误的答案x=1 , y=1 and z=1我得到3315,而正确答案是3675.

请帮我找出错误.

4+5+6+45+54+56+65+46+64+456+465+546+564+645+654=3675

Answer 1

问题不在于您的代码，而在于您的逻辑：让S为仅由数字4、5和6组成的数字集。您要计算SUM（S）。但是，由于您只考虑这些数字的前几位，因此实际上是在计算SUM（以S为单位，s-s％10 ^ floor（log10（s）））。

不过您做得正确，因为

4 + 5 + 6 + 40 + 50 + 50 + 60 + 40 + 60 + 400 + 400 
  + 500 + 500 + 600 + 600 = 3315

长话短说，您需要做的就是申请用户？下面的方法可修复您的代码。这将导致O（xyz（x + y + z））算法，并且可以通过看到SUM（i = 0到t-1，10 ^ i）=（10 ^ t-1来改进为O（xyz） ）/ 9，因此只需在代码中更改一行即可：

4 + 5 + 6 + 40 + 50 + 50 + 60 + 40 + 60 + 400 + 400 
  + 500 + 500 + 600 + 600 = 3315

还有一种使用动态编程的非常简单的O（xyz）时间+空间方法，该方法仅使用最少的数学和组合运算：令g（x，y，z）为元组（count，sum），其中count是4的数量-5--6数正好由 x个4，y个5和z个6个组成。总和就是他们的总和。然后我们有以下重复发生：

// was: long pow = (long) Math.pow(10,t-1);
long pow = (long) (Math.pow(10,t)-1) / 9;

我们可以在g上添加备注，以避免两次计算结果，从而产生了多项式时间算法，而无需组合见解。

如gen-ys的答案所示，对于您可以使用3个以上数字的情况，这很容易推广。它也可以推广到对数字形状有更复杂限制的情况。如果您想将给定范围内的数字相加，甚至可以将其与另一种通用DP方法结合使用，将其通用化。

编辑：还有一种方法可以直接描述函数f（x，y，z），最多包含4个x 4，y个5个和z个6 个数的4-5-6数之和。为此，您需要包含/排除。例如，对于计数部分，我们有

c（x，y，z）= c（x-1，y，z）+ c（x，y-1，z）+ c（x，y，z-1）-c（x-1，y- 1，z）-c（x-1，y，z-1）-c（x，y-1，z-1）+ c（x-1，y-1，z-1）

总和稍微复杂一点。