亲爱的，我征求你的意见。
我在PHP中有以下代码/ for循环
$number= 123
$counter = 0;
$digitsum = 6 /* This is calculated by another function */
for($i=1;$i<=$number-1;$i++) {
if(array_sum(preg_split('//',$i)) == $digitsum){
$counter++;
}
}
echo $counter;
所以基本上我的循环计算给定数字以下有多少数字具有相同的数字总和，然后显示有多少。尽管它可以完美地处理 5 位数字并在 1 秒内计算循环数，但我需要它来处理 18 位数字并在 1 秒内完成计数。
这甚至有可能实现吗？还是我应该寻求其他解决方案？
这是一个非常快速的解决方案。它仍然无法在 1 秒内处理 18 位数字，但它可以在 2 毫秒内完成 @Edakos (6, 12345) 的答案中的示例。
function count_numbers_with_digit_sum( $sum, $max ) {
if($sum < 0 || $max <= 0) {
return 0;
}
$count = 0;
$greatest_piece = (int) str_pad(1, strlen($max.""), "0");
$first_digit = (int) substr($max, 0, 1);
if( $max <= 9 && $sum <= 9 ) {
$count++;
}
else {
$count_to = max(1, ($sum > $first_digit) ? $first_digit : $sum );
for( $i = 0; $i < $count_to; $i++ ) {
$count += count_numbers_with_digit_sum( $sum - $i, $greatest_piece - 1 );
}
$count += count_numbers_with_digit_sum( $sum - $count_to, $max % $greatest_piece );
}
return $count;
}
$start = microtime(true);
echo count_numbers_with_digit_sum( 6, 12345);
echo "<br/>";
echo (int)((microtime(true) - $start)*1000) )." ms";
一些示例运行：
count_numbers_with_digit_sum( 9, 100 ) = 10 0 ms
count_numbers_with_digit_sum( 6, 123 ) = 10 0 ms
count_numbers_with_digit_sum( 6, 12345 ) = 130 2 ms
count_numbers_with_digit_sum( 23, 12345 ) = 530 40 ms
count_numbers_with_digit_sum( 34, 582973 ) = 13923 2287 ms
count_numbers_with_digit_sum( 9, 984930 ) = 2001 39 ms
这是它的工作原理。让我们称其S(x,y)数字之和等于 的不同正整数的数量小于或y等于x。例如，S(3,25) = 3（3、12、21）。我们可以做以下逻辑。为简单起见，我们只看 x=6 和 y=123，就像在您的原始示例中一样。 S将是我们不“使用”第一个（数百）位的整数数量，加上我们使用的整数数量。在这种情况下，百位的最大值为 1，所以...
S(6,123) = S(6,99) + S(5,23)
查看十位数字，我们可以使用 0 到 6 之间的任何值，所以：
S(6,99) = S(6,9) // single digits
+ S(5,9) // 10-19
+ S(4,9) // 20-29
+ S(3,9) // 30-39
+ S(2,9) // 40-49
+ S(1,9) // 50-59
+ S(0,9) // 60
这非常适合递归。对于给定的y，我们查看所有最左边的数字都是 0（即未使用）的场景，例如 S(x,9)、S(x,99)、S(x,999) 等，然后我们看看“最大化”最左边的数字。例如，
S(34, 12345) = S(34, 9999) + S(34, 999) + S(34, 99) + S(34, 9) + S(33, 2345)
= 10 + 0 + 0 + 0 + S(33, 2345)
= 10 + S(33, 999) + S(33, 99) + S(33, 9) + S(31, 345)
= 10 + 0 + 0 + 0 + S(31, 345)
= 10 + S(31, 99) + S(31, 9) + S(31, 45)
= 10 + 0 + 0 + 0
= 10
上面的函数实现了这个递归。您可以轻松地调整此函数以将大“数字”用作字符串值：
function count_numbers_with_digit_sum_string( $sum, $max ) {
return count_numbers_with_digit_sum_string_inner( $sum."", $max."" );
}
function count_numbers_with_digit_sum_string_inner( $sum, $max ) {
if($sum < 0 || $max <= 0) {
return 0;
}
$count = 0;
$strlenmax = strlen($max);
$strlensum = strlen($sum);
$nines_less_than_max = (int) str_pad("", $strlenmax-1, "9");
$first_digit = (int) substr($max, 0, 1);
$last_two_digits_sum = (int) substr($sum, -2);
if( $strlenmax <= 1 && $strlensum <= 1 ) {
$count++;
}
else {
$count_to = max( 1, ($strlensum > 1 || $sum > $first_digit) ? $first_digit : ( (int) $sum ) );
for( $i = 0; $i < $count_to; $i++ ) {
$count += count_numbers_with_digit_sum_string_inner( substr($sum, 0, -2) .($last_two_digits_sum - $i), $nines_less_than_max );
}
$count += count_numbers_with_digit_sum_string_inner( substr($sum, 0, -2) .($last_two_digits_sum - $count_to), substr($max, 1));
}
return $count;
}
$start = microtime(true);
echo count_numbers_with_digit_sum_string( 34, 12345);
echo "<br>".( (int)((microtime(true) - $start)*1000) )." ms";
这个版本大约是上面纯数字版本的两倍。
您可以通过预先计算和缓存值来大大加快速度。正如您在上面看到的，有很多诸如S(x, 999),S(x,9999)等的术语。只有 10 个 x (0..9) 值在 y = 9 时“起作用”，19 个值 (0..18) 对 y 起作用= 99, 28 (0..27) 表示 y = 999 等。如果你想缓存 1,558 个值（9、99、999 中 y 的 S(x,y) 的所有组合，最多 999,999,999,999,999,999） ，您可以减少大量的递归并节省大量时间。有了足够大的缓存，我相信您可以将 18 位数字的时间缩短到一秒。这很容易做到，通过建立它（缓存 9 个值，然后是 99，然后是 999，等等）。如果以后有时间，我将发布概念证明。
希望有帮助！
（编辑澄清缓存计算，修复 $count_to 中的计算错误）
这应该更快，因为它不使用正则表达式：
<?php
$number = 123;
$counter = 0;
$digitsum = 6; /* This is calculated by another function */
for($i=1;$i<=$number-1;$i++) {
if(array_sum(str_split($i)) == $digitsum) {
$counter++;
}
}
echo $counter;
您可以尝试以下选项 C：
选项A：（你的尝试）
$number = 12345;
$counter = 0;
$digitsum = 6;
$start = microtime();
for ($i = 1; $i <= $number - 1; $i++) {
if (array_sum(preg_split('//', $i)) == $digitsum) {
$counter++;
}
}
echo (int)((microtime() - $start)*1000); // ~ 42 miliseconds at writecodeonline.com
选项B：（从这里）
$start = microtime();
$i = 0;
while ($i++ < $number) {
if (array_sum(str_split($i)) == $digitsum) {
$counter++;
}
}
echo (int)((microtime() - $start)*1000); // ~ 19 miliseconds at writecodeonline.com
选项C：（从这里）
$start = microtime();
$i = 0;
while ($i++ < $number) {
$sum = 0;
$n = $i;
do {
$sum += $n % 10;
} while ($sum <= $digitsum and $n = (int) $n / 10);
if ($sum == $digitsum) {
$counter++;
}
}
echo (int)((microtime() - $start)*1000); // ~ 5 miliseconds at writecodeonline.com
也许这就是你想要的
function foo($digits, $digitsum) {
$sum = 0;
if(!empty($digits)) {
if($digitsum > 1) {
$current = array_shift($digits);
if(count($digits) > 0) {
if($digitsum >= $current) {
$sum += foo($digits, $digitsum - $current);
for($i = 0; $i < $current; $i++) {
$sum += foo(array_fill(0, count($digits), 9), $digitsum - $i);
}
} else {
for($i = 0; $i <= $digitsum; $i++) {
$sum += foo(array_fill(0, count($digits), 9), $digitsum - $i);
}
}
} elseif($current >= $digitsum) {
$sum += 1;
}
} elseif($digitsum == 1) {
$sum += count($digits);
} else {
$sum += 1;
}
}
return $sum;
}
$number = 123;
$digitsum = 6;
$digit = strlen($number);
$digits = str_split($number);
$counter = foo($digits, $digitsum);
var_dump($counter);