阿克曼子数组求解方案无法处理大数问题排查

程序需求：

• 接收两个输入：<数字> <检查数>
• 遍历该数字的所有连续子数字串（将数字的每一位视为数组元素，子数组即连续的若干位），计算子串各位数字之和，若和≤检查数则计数+1
• 最终输出总计数 + 该计数的阿克曼数
• 阿克曼数定义：对于N，是满足“X层2的幂塔（2²…^2，共X个2）严格大于N”的最小正整数X
• 要求不能使用数组，仅通过%和/截断数字实现

当前问题：代码对常规数字处理正常，但处理极大数字（如11111111111111111或93875190871098170）时失效，已改用unsigned long long int仍无效果。

原代码 #

#include <stdio.h>
#include <math.h>

int main () {
    unsigned long long int number; int checknum;
    int count = 0;
    scanf("%llu %d", &number, &checknum);
    
    int size = (int)log10(number) + 1;
    
    for (int left = 0; left < size; left++) {
        unsigned long long int dummy = number % (unsigned long long int)pow(10, size-left);
        int dummysize = (int)log10(dummy) + 1;
        for (int right = 0; right < dummysize; right++) {
            unsigned long long int dummydummy = dummy / (int)pow(10, right);
            int dummydummysize = (int)log10(dummydummy) + 1;
            int sum = 0;
            for (int i = 0; i < dummydummysize; i++) {
                int digit = (int)dummydummy%10;
                sum = sum + digit;
                dummydummy = dummydummy/10;
            }
            if (sum <= checknum) {count++;}
        }
    }
    int num = 2;
    for (int i = 1; i < 100; i++){
        if (num > pow(2,count)) {printf("%d", count + i); break;}
        num = pow(2, num);
    }
    
    return 0;
}

核心问题分析 #

1. log10与pow的精度丢失

   • unsigned long long的最大值是18446744073709551615（20位），但double类型仅能精确表示53位以内的整数，对于超过16位的整数，log10计算出的位数会出现偏差，导致size、dummysize等变量错误。
   • pow(10, k)返回的double值转成整数时，可能因精度问题得到错误结果（比如pow(10,16)实际计算值可能略小于真实的10^16），导致number % ...或dummy / ...的截断逻辑完全错误。

2. 子串遍历的冗余与错误
   原代码每次通过截断数字获取子串，再重新计算各位和，不仅效率低下，还会因截断错误导致子串范围错误。

3. 阿克曼数计算的溢出与精度问题

   • pow(2, count)当count较大时，double无法精确表示结果，导致比较逻辑失效。
   • 幂塔增长极快（3层是16，4层是65536，5层是2^65536），远超过unsigned long long的范围，直接用pow计算会溢出成无效值，导致循环逻辑错误。

修正后的代码 #

#include <stdio.h>
#include <limits.h>

// 计算数字的位数（避免log10精度问题）
int get_digit_count(unsigned long long num) {
    if (num == 0) return 1;
    int cnt = 0;
    while (num > 0) {
        cnt++;
        num /= 10;
    }
    return cnt;
}

// 计算N的阿克曼数
int calc_ackerman(int n) {
    if (n < 2) return 1; // 1层幂塔2>1，满足条件
    unsigned long long tower = 2;
    int x = 1;
    while (1) {
        if (tower > n) {
            return x;
        }
        // 若当前幂塔已接近ULLONG_MAX，下一层必然超过n
        if (tower > 63) { // 2^63是ULLONG_MAX的一半，2^64溢出
            return x + 1;
        }
        unsigned long long next_tower = 1;
        int overflow = 0;
        for (int i = 0; i < tower; i++) {
            if (next_tower > ULLONG_MAX / 2) {
                overflow = 1;
                break;
            }
            next_tower *= 2;
        }
        if (overflow) {
            return x + 1;
        }
        tower = next_tower;
        x++;
    }
}

int main() {
    unsigned long long number;
    int checknum;
    int count = 0;
    scanf("%llu %d", &number, &checknum);

    int size = get_digit_count(number);
    unsigned long long suffix = number;

    // 遍历所有起始位置的后缀，计算每个后缀的所有前缀和
    for (int left = 0; left < size; left++) {
        int current_sum = 0;
        unsigned long long s = suffix;
        while (s > 0) {
            int digit = s % 10;
            current_sum += digit;
            if (current_sum <= checknum) {
                count++;
            }
            s /= 10;
        }
        // 去掉当前后缀的最左一位，得到下一个后缀
        suffix /= 10;
    }

    int ack = calc_ackerman(count);
    printf("%d\n", count + ack);

    return 0;
}

修正说明 #

• 用循环除法替代log10计算数字位数，彻底避免精度问题。
• 换一种子串遍历方式：对每个起始位置的后缀，逐位累加和并判断，无需截断整个数字，逻辑更可靠且效率更高。
• 阿克曼数计算改用整数循环，加入溢出判断，避免浮点数精度问题和无效溢出。

内容的提问来源于stack exchange，提问作者mxchi16