递归程序对大输入不起作用

提问者：小点点

递归程序对大输入不起作用

我试着从这个网站上写一个问题的答案--https://main2.edu.pl/C/kurs-podstaw-algorytmiki-druga-e/p/kro/

这是关于递归的补充，所以我想出了一个使用它的代码。它应该显示(a+1)^B模10000余数。不幸的是，对于小的数字，我的程序可以工作，但是当它达到更大的数字时，它就。。。不-例如:

a=1
b=4
输出为16，正确。

a=2
b=3
输出为27，正确。

a=2
b=100
它给出的输出是-8495，这是完全不正确的。

我试着去寻找，但是我没有找到解决问题的办法，因为我真的不知道发生了什么事。我在想，可能是因为数据类型太小，但是把int改为long int，并没有改变什么。

下面是我的代码:

#include <iostream>
using namespace std;

int pot(int a, int b){
    if (b == 1)
        return a;
    if (b % 2 == 0) //test for even number
        return pot(a, b / 2) * pot(a, b / 2);
    else //make it even number
        return a * pot(a, b - 1);
}

main(){
    int a, b;
    int P;
    cin>>P;
    for(int i = 1; i<=P; i++){
        a = 0;
        b = 0;
        cin>>a;
        cin>>b;
        cout<<endl<<(pot(a+1, b))%10000;
    }
}

共1个答案

匿名用户

不要只取最终结果的余数，而应该在每次pot返回值时取余数。结果应该是正确的，因为您只是将结果乘以数，对于正的x，y和m，(x*y)%m应该等于(x%m)*(y%m))%m。

请尝试以下操作:

int pot(int a, int b){
    int r;
    if (b == 1)
        r = a;
    else if (b % 2 == 0) //test for even number
        r = pot(a, b / 2) * pot(a, b / 2);
    else //make it even number
        r = a * pot(a, b - 1);
    return r % 10000;
}

另外，在第二种情况下，您正在复制pot(a，b/2)的计算，这将大大减慢计算速度。您应该更改:

r = pot(a, b / 2) * pot(a, b / 2);

致:

r = pot(a, b / 2);
r *= r;

（当然还要加上花括号。）那应该快多了。

更新:我刚刚更正了我的答案，为第二种情况包含了else，这在原始代码中是不存在的。在原始代码中不需要它，但在我的更改之后需要它。