CodeChef入门题CIELRCPT递归实现异常：单输入结果正确但多测试用例仅输出前两个

我帮你梳理下代码里的问题，以及对应的修复方案：

核心错误点 #

1. 错误的程序终止逻辑：
   在main函数的for循环里，当检测到p是2的幂时，你直接用return 0终止了整个程序，而不是仅结束当前测试用例的处理。比如第一个测试用例如果是2，程序会直接退出，后面的所有测试用例都不会被执行——这是多测试用例只输出前几个结果的核心原因。

2. 递归函数的返回路径不完整：
   你的menus函数中，当premaining != 0时调用递归，但调用后没有返回递归的结果，也没有确保函数所有分支都有return语句。这会导致函数执行到末尾时没有返回值，属于未定义行为，返回的结果可能是随机的错误值。

3. 浮点数精度问题：
   使用pow(2,j)计算2的幂是不安全的，因为pow是浮点数函数，可能会出现精度误差（比如pow(2,11)可能返回2047.999999999，转成long后变成2047），导致后续计算错误。

修复后的代码 #

我重新整理了递归逻辑，去掉了全局变量，用整数运算替代浮点数，修复了所有错误：

#include <iostream>
using namespace std;

// 递归计算所需菜单数量
int menus(int premaining) {
    if (premaining >= 2048) {
        // 先处理2048的倍数，剩余部分递归计算
        return (premaining / 2048) + menus(premaining % 2048);
    }
    // 找到小于等于当前值的最大2的幂
    int k = 1;
    while (k * 2 <= premaining) {
        k *= 2;
    }
    // 如果当前值就是2的幂，直接返回1；否则递归处理剩余部分，计数+1
    return (premaining == k) ? 1 : 1 + menus(premaining - k);
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        int p;
        cin >> p;
        cout << menus(p) << endl;
    }
    return 0;
}

修复说明 #

• 移除全局变量：改用递归返回值累加计数，彻底避免了全局变量在多测试用例和递归过程中的副作用。
• 替换浮点数运算：用整数乘法k *= 2计算2的幂，完全消除了精度问题。
• 修正程序终止逻辑：去掉了main函数中错误的return 0，所有测试用例都会被完整处理。
• 完善递归返回路径：所有分支都有明确的return语句，避免未定义行为，确保返回结果正确。

额外优化提示 #

其实这个问题本质上是计算p的二进制表示中1的个数（因为每个2的幂对应二进制的一个1），所以最简便的写法是直接用位运算统计1的个数，比如：

#include <iostream>
using namespace std;

int main() {
    int t;
    cin >> t;
    while (t--) {
        int p;
        cin >> p;
        cout << __builtin_popcount(p) + (p / 2048) << endl;
    }
    return 0;
}

这里__builtin_popcount(p)是GCC内置函数，统计二进制中1的个数，加上2048的倍数（因为2048是2^11，相当于二进制的第12位），就是最终的结果，比递归写法更高效简洁。

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