C语言Kaprekar程序调试：85555输出错误问题求助

我编写了一个C语言Kaprekar程序，用于对指定数字执行Kaprekar过程：若数字收敛到固定点则返回收敛值，否则返回-1。目前程序对多数数字输出正确，但处理85555时返回74943，预期应为71973（或判定为循环返回-1）。以下是原代码：

#include <stdio.h>
#define MAX_ROUNDS 1000
// Function declarations
long long kaprekar(long long n);
void arrayCountDigits(long long n, int* cArr);
long long sortDigits(int* cArr, int dir);

int main() {
    printf("%lld\n", kaprekar(11));         // Output: 0
    printf("%lld\n", kaprekar(85555));      // Wrong Output:74943 Should be 71973 
    printf("%lld\n", kaprekar(8991));       // Output: 6174
    printf("%lld\n", kaprekar(63317664));   // Output: 63317664

    return 0;
}

// Function to count digits of a number
void arrayCountDigits(long long n, int* cArr) {
    for (int i = 0; i < 10; i++) {
        cArr[i] = 0; // Initialize counts to zero
    }
    if (n == 0) {
        cArr[0] = 1;

    }
    while (n > 0) {
        cArr[n % 10]++;
        n /= 10;
    }
}

// Function to sort digits and form a number
long long sortDigits(int* cArr, int dir) {
    long long result = 0;
    if (dir == 0) { // Ascending order
        for (int i = 0; i < 10; i++) {
            while (cArr[i] > 0) {
                result = result * 10 + i;
                cArr[i]--; // Decrement digit count
            }
        }
    }
    else { // Descending order
        for (int i = 9; i >= 0; i--) {
            while (cArr[i] > 0) {
                result = result * 10 + i;
                cArr[i]--; // Decrement digit count
            }
        }
    }
    return result;
}

// Kaprekar function
long long kaprekar(long long n) {
    int cArr[10];
    long long nUp, nDown, nextN;
    int rounds = 0;

    while (rounds < MAX_ROUNDS) {
        arrayCountDigits(n, cArr);

        // Sort digits in ascending and descending order
        nUp = sortDigits(cArr, 0);

        // Reset the digit counts for descending sort
        arrayCountDigits(n, cArr);
        nDown = sortDigits(cArr, 1);

        // Compute the next number in the sequence
        nextN = nDown - nUp;

        // Break if the sequence converges or doesn't change
        if (nextN == n) {
            break;
        }
        n = nextN;
        rounds++;
    }

    return n;
}

问题分析与修复方案 #

核心问题

1. 无循环检测逻辑：原代码仅运行固定次数后返回当前值，但部分数字的Kaprekar过程会进入循环而非收敛到固定点（比如5位数字会进入71973→83952→74943→62964→71973的循环），此时应返回-1而非循环中的某个值。
2. 未保持固定位数：当相减后数字位数少于原始位数时，未补前导零，会导致后续排序逻辑偏离Kaprekar规则。

修复后的代码

#include <stdio.h>
#define MAX_ROUNDS 1000
// Function declarations
long long kaprekar(long long n);
void arrayCountDigits(long long n, int* cArr, int digitCount);
long long sortDigits(int* cArr, int dir, int digitCount);

int main() {
    printf("%lld\n", kaprekar(11));         // Output: 0
    printf("%lld\n", kaprekar(85555));      // Output: -1 (enters cycle)
    printf("%lld\n", kaprekar(8991));       // Output: 6174
    printf("%lld\n", kaprekar(63317664));   // Output: 63317664

    return 0;
}

// Count digits, including leading zeros to maintain fixed digit count
void arrayCountDigits(long long n, int* cArr, int digitCount) {
    for (int i = 0; i < 10; i++) {
        cArr[i] = 0;
    }
    // Process exactly digitCount digits, including leading zeros
    for (int i = 0; i < digitCount; i++) {
        cArr[n % 10]++;
        n /= 10;
    }
}

// Sort digits into a number with fixed digit count
long long sortDigits(int* cArr, int dir, int digitCount) {
    long long result = 0;
    int count = 0;
    if (dir == 0) { // Ascending order
        for (int i = 0; i < 10 && count < digitCount; i++) {
            while (cArr[i] > 0 && count < digitCount) {
                result = result * 10 + i;
                cArr[i]--;
                count++;
            }
        }
    } else { // Descending order
        for (int i = 9; i >= 0 && count < digitCount; i--) {
            while (cArr[i] > 0 && count < digitCount) {
                result = result * 10 + i;
                cArr[i]--;
                count++;
            }
        }
    }
    return result;
}

// Kaprekar function with cycle detection and fixed digit handling
long long kaprekar(long long n) {
    int cArr[10];
    long long nUp, nDown, nextN;
    int rounds = 0;
    long long seen[MAX_ROUNDS];
    int digitCount = 0;
    long long temp = n;

    // Calculate original digit count
    digitCount = (temp == 0) ? 1 : 0;
    while (temp > 0) {
        digitCount++;
        temp /= 10;
    }

    while (rounds < MAX_ROUNDS) {
        // Check for cycle
        for (int i = 0; i < rounds; i++) {
            if (seen[i] == n) {
                return -1;
            }
        }
        seen[rounds] = n;

        arrayCountDigits(n, cArr, digitCount);
        nUp = sortDigits(cArr, 0, digitCount);

        arrayCountDigits(n, cArr, digitCount);
        nDown = sortDigits(cArr, 1, digitCount);

        nextN = nDown - nUp;

        // Check for fixed point convergence
        if (nextN == n) {
            return n;
        }
        n = nextN;
        rounds++;
    }

    return -1;
}

修复说明

1. 循环检测：新增seen数组记录所有出现过的数字，一旦检测到重复则判定为循环，返回-1。
2. 固定位数处理：修改arrayCountDigits和sortDigits函数，加入digitCount参数，强制保持原始数字的位数，补全前导零的计数，确保排序和相减过程符合Kaprekar规则。
3. 逻辑优化：优先检测循环，再判断是否收敛到固定点，完全符合“收敛返回收敛值，否则返回-1”的需求。

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