C语言用递归算法实现：整数模幂运算 x的r次模p.用循环控制比较简单,但是自己用递归写了个运行时结果不算法思想如下,希望用递归实现：(1) a←x,b←r ,c←1(2)若b=0,则输出c,结束．(3)若b是正的
来源：学生作业帮助网 编辑：六六作业网 时间：2024/11/25 15:21:42
C语言用递归算法实现：整数模幂运算 x的r次模p.用循环控制比较简单,但是自己用递归写了个运行时结果不算法思想如下,希望用递归实现：(1) a←x,b←r ,c←1(2)若b=0,则输出c,结束．(3)若b是正的
C语言用递归算法实现：整数模幂运算 x的r次模p.用循环控制比较简单,但是自己用递归写了个运行时结果不
算法思想如下,希望用递归实现：
(1) a←x,b←r ,c←1
(2)若b=0,则输出c,结束．
(3)若b是正的偶数,则b← b/2,a ← a2 mod p,转(3)
否则,转(4).
(4) b←b-1,c ←a*c mod p ,转(2).
此方法为数论中的方法,上面描述的问题希望用此方法用递归调用实现,
C语言用递归算法实现：整数模幂运算 x的r次模p.用循环控制比较简单,但是自己用递归写了个运行时结果不算法思想如下,希望用递归实现：(1) a←x,b←r ,c←1(2)若b=0,则输出c,结束．(3)若b是正的
需要输入x,r,p
#include
void Run(int x,int r,int p,int t)
{
int a,b,c;
a=x;b=r;c=t;
if(b==0)
{
printf("%d",c);
return;
}
if((b>0)&&(b%2==0))
{
b=b/2;
a=(a*a)%p;
}
else
{
b=b-1;
c=(a*c)%p;
}
Run(a,b,p,c);
}
void main()
{
int x,r,p,t=1;
printf("please enter x :");
scanf("%d",&x);
printf("please enter r :");
scanf("%d",&r);
printf("please enter p :");
scanf("%d",&p);
Run(x,r,p,t);
}