C語言求高次方數的尾數代碼解析

問題描述

求13的13次方的最後三位數。

問題分析

許多初學者看到本題最容易想到的方法就是：將13累乘13次後截取最後三位即可。但是計算機中存儲的整數有一定的範圍，超出某範圍將不能正確表示，所以用這種算法不可能得到正確的結果。實際上，題目僅要求後三位的值，完全沒有必要把13的13次方完全求出來。

算法設計

手工計算13的13次方的步驟如下：

研究乘法的規律會發現：乘積的最後三位的值只與乘數和被乘數的後三位有關，與乘數和被乘數的高位無關。利用這一規律，在計算下一次的乘積時，我們只需用上次乘積的後三位來參與運算（即在求第三次乘積時，上次的乘積2197並不需要都參與運算，只取其後三位197再次與13相乘即可）。求某數的後三位的算法用某數對1000取模。編程過程中，將累乘得到的積存儲到變量last中，在進行下一次相乘之前先截取last的後三位再相乘，即：last%1000*13，將結果存儲到last中：last=last*x（x的值為13）%1000。 因第一次相乘時用到變量last的初值，故在定義時給last賦初值，或在參與計算之前給last賦初值1。
下面是完整的代碼：

#include <stdio.h>
int main()
{
    int i, x, y, last=1;  /*變量last保存求得的x的y次方的部分積的後三位*/
    printf("輸入 x 和 y:\n");
    scanf("%d %d", &x, &y);
    for(i=1; i<=y; i++)  /*x自乘的次數y*/
        last = last * x % 1000;  /*將last乘x後對1000取模，即求積的後三位*/
    printf("最後三位數是:%d\n", last);
 
    return 0;
}

運行結果：

linuxidc@linuxidc:~/www.linuxidc.com$ ./linuxidc.com
輸入 x 和 y :
12 12
最後三位數是:256
linuxidc@linuxidc:~/www.linuxidc.com$ ./linuxidc.com
輸入 x 和 y :
8 8
最後三位數是:216
linuxidc@linuxidc:~/www.linuxidc.com$ ./linuxidc.com
輸入 x 和 y :
13 13
最後三位數是:253

Linux公社的RSS地址：https://www.linuxidc.com/rssFeed.aspx

本文永久更新連結地址：https://www.linuxidc.com/Linux/2019-01/156341.htm

喜歡我就支持我