algorithm - 由 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 和 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 in S, s - s % 10^floor(log10(s)))。

不过你做对了，因为

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

长话短说，您需要做的就是申请用户 גלעד ברקן's approach下面修复你的代码。它将导致 O(xyz(x+y+z)) 算法，并且可以通过看到 SUM(i = 0 to t-1, 10^i) = (10^t - 1) 改进为 O(xyz) )/9，所以只需更改代码中的一行:

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

还有一个非常简单的 O(xyz) 时间 + 空间方法，它使用动态规划，只使用最少的数学和组合学:设 g(x, y, z) 为元组 (count, sum)，其中 count 是由 正好 x 个四、y 个五和 z 个六组成的 4-5-6 个数。 sum 是他们的总和。那么我们有如下的重现:

using ll=long long;
pair<ll, ll> g(int x, int y, int z) {
    if (min(x,min(y,z)) < 0)
        return {0,0};
    if (max(x,max(y,z)) == 0)
        return {1,0};
    pair<ll, ll> result(0, 0);
    for (int d: { 4, 5, 6 }) {
        auto rest = g(x - (d==4), y - (d==5), z - (d==6));
        result.first += rest.first;
        result.second += 10*rest.second + rest.first*d;
    }
    return result;
}

int main() {
    ll res = 0;
    // sum up the results for all tuples (i,j,k) with i <= x, j <= y, k <= z
    for (int i = 0; i <= x; ++i)
        for (int j = 0; j <= y; ++j)
            for (int k = 0; k <= z; ++k)
                res += g(i, j, k).second;
    cout << res << endl;
}

我们可以将内存添加到 g 以避免两次计算结果，从而产生多项式时间算法而不需要组合洞察力。

对于可以使用超过 3 个数字的情况，这很容易概括，如 gen-y-s's answer 所示。 .它也可以推广到您对数字的形状有更复杂限制的情况。如果你想对给定范围内的数字求和，它甚至可以被概括，通过组合它 with another generic DP approach .

编辑:还有一种方法可以直接描述您的函数f(x, y, z)，即包含的4-5-6 个数字的总和>至多 x 四、y 五和 z 六。你需要包含 - 排除。例如，对于计数部分，我们有

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)

求和稍微复杂一些。