那些很难想到的算法

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条评论在“那些很难想到的算法”

  1. 证明：设任何一个数的任何次幂表示为 a^b;其中a表示十进制数为an…a1;b表示十进制数为bn…b1;
    首先证明任何两个数相加的最后结果的最后三位数只与这个两个数的最后三位数有关系。
    即需要证明an…a1 + bn…b1相加结果的最后三位数与a3a2a1 + b3b2b1的最后三位数相同。
    an …a3 a2 a1 a3 a2 a1
    + bn…b3 b2 b1 b3 b2 b1
    ————————————————————————————————————
    C3 C2 C1 C3 C2 C1
    根据竖式加法显然是成立的。
    又因为任何n个数相加都可以拆分为每次两个数相加得到最后的结果(加法的结合律)
    a^b表示的意义是a^b-1个a相加；由以上结论可以推得任何一个数的任何次幂最后结果的最后三位数，只与每次底数相乘的最后三位数有关系。

    回复

      1. 都很基础的东西，只不过用字符来表示任何数而已了。我感觉理解这个问题最核心的还是乘法怎么来的就明白了。

        回复

          1. 是的，有些东西还是经验的积累。向这个问题，我之前没有做过，但是想过类似的问题，结果的最后一位只与乘数的最后一位有关系。当初没有深入拓展，今天看到博主的文章，研究了一下。

            回复

            1. 对的，类似的算法还有蛮多的，如果有时间可以刷刷算法题，对于自身能力提升还是有一定空间的

              回复

写下你最简单的想法