亲爱的，我征求你的意见。
我在 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)等。 x （0..9） 只有 10 个值"工作"，其中 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,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;
也许这就是你想要的
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);
您可以从以下选项中尝试选项 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