Question

C语言的一道题 求指点

#include <stdio.h>

int main()
{
unsigned short a,b;
unsigned n;
double c;
scanf("%d",&n);
for(;n>=1;n--)
{
scanf("%hd%hd",&a,&b);
for(c=0.001;b>=1;b--)
{
c=c*a;
if(c>=1)
{
c=c-(int)(c);
}
}
printf("%d\n",(int)(c*1000));
}
}

题目描述

求A^B的最后三位数表示的整数（1<=A,B<=1000）

输入

n个测试实例，每个实例给出两个正整数A,B

输出

输出A^B的最后三位（没有前导0）
样例输入
2
2 3
12 6

样例输出
8
984

这道题我觉得我的算法没毛病啊，为什么提交总是提示错误！流泪！求解析一下我的答案及正确答案应该是？

而且！#include <stdio.h>

int main()
{
unsigned short a,b,d,p;
unsigned n;
int c;
scanf("%d",&n);
for(;n>=1;n--)
{
scanf("%hd%hd",&a,&b);
p=a;
for(c=1;b>=1;b--)
{
c=c*a;
d=c%1000;
}
printf("%d\n",d);
}
}这段是错的，但是
#include <stdio.h>

int main()
{
unsigned short a,b,d;
unsigned n;
int c;
scanf("%d",&n);
for(;n>=1;n--)
{
scanf("%hd%hd",&a,&b);
for(c=1;b>=1;b--)
{
c=c%1000;
c=c*a;
}
printf("%d\n",c%1000);
}
}

就对了！！！求解！流泪！

Answer 1

第一个代码, 你需要知道double每个数字都是近似存储的,虽然有前若干位是准确数字的说法,但实际上除了恰好是2^n组合的加法情况,其他的多少都会有一些近似.
这样在大量计算累积下来就会导致精度丢失的扩大. 最终导致结果错误.
第二个代码.
如果把c改成int应该是可以过的.
现在c是short 这样在做c=c*a; 的时候就可能会溢出.
比如 a=999; 计算第二次的时候 c=998001, 但最大值只是32767,所以实际上得到的c值是14961 取余后结果是961,明显和正确答案001差太多了.

追问

可是第二段的代码中的c是int型的啊

追答

正确的代码,c在乘之前做了模除 ,控制了范围,所以不会溢出.
关于这个修改,刚看错了, 这里还是必须通过加一个模除,来限制范围,即
c=c*a%1000;
不然a不断的累乘到c上, 就算int也会溢出的.

追问

非常感谢！！！

Answer 2

#include <stdio.h>
int main()
{int n,a,b,c;
scanf("%d",&n);
for(;n>=1;n--)
{
scanf("%d%d",&a,&b);
for(c=1;b>=1;b--)
  c=c*a%1000;
printf("%d\n",c);
}
return 0;
}