那些很难想到的算法

40 条评论 学习笔记

　　首先，题目不难，简单的循环求值。为：求X^Y的最后三位数，一般情形下可取值然后取模搞定。

　　解析：一般情况下，求X^Y很简单，使用pow(x,y)瞬间搞定，然后对其模1000，最后三位就搞定了。事实上，没这么简单，想想4151784^9941241次方算出来等于多少，估计你自己的电脑很难搞定，所以得变通一下。

　　看看那些意想不到的算法，甚至很难弄清楚其中的数学原理。简单点说，想不出来就是数学没学好。为什么别人能想到用最后三位相乘数字依旧能保持不变呢，看来水还很深。

//引用的别人的代码，莫怪
#include "stdio.h"
int main(void){
    int i,x,y,z = 1; //x，y为x^y,z为最后三位数
    printf("请输入两个数：\n");
    scanf("%d%d",&x,&y); //输入底数和幂数
    for (i = 1;i <= y;i++){ //底数每乘一次就取其后三位数
        z = z*x % 1000; //仔细看这里
    }
    if (z > 100){
        printf("最后三位数为：%d\n",z);
    }
    else if(z < 10){
        printf("最后三位数为：00%d\n",z);
    }else{
        printf("最后三位数为：0%d\n",z);
    }
    return 0;
}

　　最后，我们应该可以发现一个问题，那就是每次计算之时始终保持数字为一个三位数的状态就是最后三位。取模的结果相乘并不影响最后的结果，应该是可信的。如果谁能附上证明最好。

40条评论在“那些很难想到的算法”

写下你最简单的想法