红色部分怎么理解??

C语言 码拜 6年前 (2015-05-11) 333次浏览 0个评论

给你三个数X(1<=X<=10^100)、Y(1<=Y<=10^8)、Z(1<=Z<=10^4),你能计算出X^Y%Z的值吗?

Description
输入三个如上所描述的数X、Y、Z。多组输入。

Input
输出X^Y%Z的值。

Output
2 3 5
12345 2345 345
123456789123456789 19234321 2341
Sample Input
3
240
1825
#include<stdio.h>
#include<string.h>
int main()
{
void res(char str[],int y,int a);
char str[1000];
int y,z;
while(scanf(“%s%d%d”,str,&y,&z)!=EOF)
{
res(str,y,z);
}
return 0;
}
void res(char str[],int y,int z)
{
int len=strlen(str);
int Value=0,i;
i=0;
while(i<len)
{
while(Value<100000 && i<len)
{
Value=Value*10+str[i]-“”0″”;
i++;
}
Value %= z;
}
int result=1;
while(y>0)
{
if(y%2!=0)
result=(result*Value)%z;
Value=(Value*Value)%z;
y /= 2;
}

printf(“%d\n”,result);
}

x^y = x^(y/2) y为偶数
x^y = x * x^(y/2) y为奇数
40分
红色部分,其是是想求value的y次方除以z取余。
一步一步来思考:
第一步就是 result = result * value % z, 循环y次,就得出结果

但是这样做是不是还能再优化呢?答案是肯定的。我们先用递归的思路思考一下:
比如 已经得到 result = result * value %z
那么 如果y是2 的话 那利用上面的 result 就可以得到 result = result * result %z
如果y是 4的话,再利用上一步的result,可以得到result = result * result %z
如果y是8的话,继续利用上一步的result,可以得到:result = result * result %z
……

其实红色的部分就是要把上述的递归部分转化成循环的方法来实现。
具体红色那样做对不对呢?我现在还不想给你结论!(其实我还没优化到那一步,不许揭穿我!)

————————
个人见解。

引用 2 楼 henuyx 的回复:

红色部分,其是是想求value的y次方除以z取余。
一步一步来思考:
第一步就是 result = result * value % z, 循环y次,就得出结果

但是这样做是不是还能再优化呢?答案是肯定的。我们先用递归的思路思考一下:
比如 已经得到 result = result * value %z
那么 如果y是2 的话 那利用上面的 result 就可以得到 result = result * result %z
如果y是 4的话,再利用上一步的result,可以得到result = result * result %z
如果y是8的话,继续利用上一步的result,可以得到:result = result * result %z
……

其实红色的部分就是要把上述的递归部分转化成循环的方法来实现。
具体红色那样做对不对呢?我现在还不想给你结论!(其实我还没优化到那一步,不许揭穿我!)

————————
个人见解。

说得有道理.
其实就跟2进制一样,从低位到高位这样跌起来.有1就加起来.

把%z去掉就是快速冪的算法,
引用 2 楼 henuyx 的回复:

红色部分,其是是想求value的y次方除以z取余。
一步一步来思考:
第一步就是 result = result * value % z, 循环y次,就得出结果

但是这样做是不是还能再优化呢?答案是肯定的。我们先用递归的思路思考一下:
比如 已经得到 result = result * value %z
那么 如果y是2 的话 那利用上面的 result 就可以得到 result = result * result %z
如果y是 4的话,再利用上一步的result,可以得到result = result * result %z
如果y是8的话,继续利用上一步的result,可以得到:result = result * result %z
……

其实红色的部分就是要把上述的递归部分转化成循环的方法来实现。
具体红色那样做对不对呢?我现在还不想给你结论!(其实我还没优化到那一步,不许揭穿我!)

————————
个人见解。

2楼的朋友,,谢了哈,懂了一些,,,红色那里是对的


CodeBye 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权 , 转载请注明红色部分怎么理解??
喜欢 (0)
[1034331897@qq.com]
分享 (0)

文章评论已关闭!