我试图计算范围A到B之间的整数,其数字和为s(假设s=60)。
A和B的范围是1到10^18。
设x为一个数,直到y,我们必须计算整数。
x=x1 x2…xn-1 xn和y=y1 y2…图1,其中XI和易是x和Y.的十进制数字。
左边是最小的一个,有十一个字。如果不存在这样的I,我们将LeftMistStLo定义为n+1,类似地,我们将LeftMoStHyHi定义为与Xi>i最小的I,否则N+1为1。
函数count返回属性为x≤y且x具有数字和60的整数x的f(y)。
根据上面的定义,n是y的位数,y[i]是y的第i位小数。下面的递归算法解决了这个问题:

    count(i, sum_so_far, leftmost_lo, leftmost_hi):
       if i == n + 1:
       # base case of the recursion, we have recursed beyond the last digit
       # now we check whether the number X we built is a valid solution
        if sum_so_far == 60 and leftmost_lo <= leftmost_hi:
          return 1
        else:
          return 0
     result = 0
     # we need to decide which digit to use for x[i]
     for d := 0 to 9
        leftmost_lo' = leftmost_lo
        leftmost_hi' = leftmost_hi
        if d < y[i] and i < leftmost_lo': leftmost_lo' = i
        if d > y[i] and i < leftmost_hi': leftmost_hi' = i
       result += count(i + 1, sum_so_far + d, leftmost_lo', leftmost_hi')
    return result






Compute the number f(Y) of integers X with the property X ≤ Y and X has the digit sum 60

现在我们有f(y)=count(1,0,n+1,n+1),我们已经解决了这个问题。
对于此特定实现为o(n^4)。
我从这个环节理解这个概念。
How to count integers between large A and B with a certain property?
但不知道如何优化。
现在我该如何优化这个问题的o(n)解决方案。
有人能帮我吗?

最佳答案

编辑哦天哪!就在我承认我的回答漏掉了重点之后,它被接受了。我把原来的答案原封不动地留下了,并解释了我的算法背后的想法,以及在折叠后它如何不如原来的解决方案。
这个特殊的问题应该被视为“18位的所有整数”,而不是“1到10^18之间的所有整数”。(对于数字和,小于18位的数字可以被视为带前导零的18位数字。)
然后你可以使用一个从下往上扩散的算法,就像埃拉托内斯的筛子在所有非素数上扩散一样。
从表示0的数字1到9的数字计数dig数组开始,即所有零。(零的数量可以计算为18 - sum(dig)。然后可以这样递归:

recurse(dig[], pos) {
    if (digitsum(dig) > 60) return;

    if (digitsum(dig) == 60) {
        count += poss(dig)
    } else {
        if (pos < 9) recurse(dig, pos + 1);
        if (sum(dig) < 18) {
            dig[pos]++;
            recurse(dig, pos);
            dig[pos]--;
        }
    }
}

这样你就可以处理所有数字计数的组合,如果超过60则返回。当您正好达到60时,必须计算与该数字计数相对应的可能数字的数目:
poss(dig) = 18! / prod(dig[i]!)

阶乘的乘积prod(dig[i]!)必须包含零的阶乘。(当然,还有0! == 1
这种方法应该足够快,如果你跟踪和到目前为止,并预先计算的阶乘。如果你想计算50到5000000000之间60位数字和的所有数字,它就不起作用。
补遗链接到的框架可以处理从a到b的任何范围。这里,让我们重点讨论从0到10^n的范围,即n位数字,其中位数较少的数字被认为具有前导零。
我的算法不是枚举所有的数字,而是考虑数字的计数。例如,如果我的数字是数字9的5倍,数字5的3倍,那么数字和就是60。现在我们要找出有多少个18位数的数字满足这个条件。59005005090900099就是这样一个数,但是这个数的所有唯一置换也是有效的。这个数字有18-(5+3)=10个零,因此这个组合有
N(5x9, 3x5) = 18! / (5! * 3! * 10!)

排列。
算法必须枚举所有置换。它跟踪数组中的枚举,dig
     ^ count
     |
2x   ...  ...  ...  ...  ...  ...  ...  ...  ...

1x   ...  ...  ...  ...  ...  ...  ...  ...  ...

0x   ...  ...  ...  ...  ...  ...  ...  ...  ...

     ---------------------------------------------> pos
      1    2    3    4    5    6    7    8    9

上面的例子是
dig == [0, 0, 0, 0, 3, 0, 0, 0, 5]

为了达到这个目的,它以之字形传播。当前数字称为pos。它既可以通过将当前数字的计数增加一个来垂直移动,也可以通过考虑下一个数字来水平移动。如果数字和达到或超过s或pos超过9,则递归停止。每次我们击中s,我们都会进行排列计算,如上图所示。
因为数组是通过引用传递的,并且实际上是整个过程中的同一个数组,所以我们必须在递增之后将其递减:我们必须在回溯之后进行清理。
该算法工作正常,能在一秒钟内找到所有18位数字的数字和为60的答案。
但它不可伸缩,因为它的运行时间呈指数增长。也因为你可以计算18的阶乘!有64位整数,但在20位之后!你需要大整数运算。(然而,一个聪明的实现将能够通过简化分数而得到更进一步的结果。)
现在想想你发布的代码。我已经删除了计算范围的所有内容。最简单的版本是:
ds_count(i, sum)
{
    if (sum > 60) return 0;

    if (i == 18) {
        if (sum == 60) return 1;
        return 0;
    }

    result = 0;
    for (d = 0; d < 10; d++) {
        result += ds_count(i + 1, sum + d);
    }

    return result;
}

这将枚举所有18位值。当总数超过60时,它就停止了,但就这样了。这并不比暴力解决方案好多少。
但这个解决方案有助于回忆。它经常会以相同的值调用,很容易理解原因。例如,调用N! / prod(dig[i]!)将从ds_count(2, 5)05...14...23...32...41...50...调用。(这让我想起了卡坦定居者的棋盘游戏中不同大小的数字筹码,它们占了两个骰子卷的总和。)
如果你能确定其中一个值,你可以保存它并有效地将5个调用缩短到16位。所以:
ds_count(i, sum)
{
    if (sum > 60) return 0;

    if (i == 18) {
        if (sum == 60) return 1;
        return 0;
    }

    if (defined(memo[i, sum])) return memo[i, sum];

    result = 0;
    for (d = 0; d < 10; d++) {
        result += ds_count(i + 1, sum + d);
    }

    memo[i, sum] = result;
    return result;
}

这是非常快的,没有像阶乘解那样的硬限制。它也更容易推动,因为它的核心是递归枚举。
有趣的是,我的解决方案不适合记忆。(除了记住阶乘,但这不是这里的限制因素)之字形计数集生成的重点是只进行唯一的递归调用。还有一种状态,即数字集,这使得记忆变得更加困难。

08-03 19:45
查看更多