C语言用递归算法实现:整数模幂运算 x的r次模p.用循环控制比较简单,但是自己用递归写了个运行时结果不

问题描述:

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).
此方法为数论中的方法,上面描述的问题希望用此方法用递归调用实现,
1个回答 分类:综合 2014-10-27

问题解答:

我来补答
需要输入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);
}
 
 
展开全文阅读
剩余:2000