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

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