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