难道C语言对待如此简单的小学生都会做的算术问题都束手无策吗？倒也不是这样，办法是有的，但需要你自己去想。编程的乐趣大抵在此。
由于本题目问题的核心在于两个较大的数相乘超过了int类型的范围，所以可以考虑把乘数拆成较小的数。比如
123456×654321=（123×103+456）×（654×103+321）
=123×103×（654×103+321）+ 456×（654×103+321）
=123×103×654×103+123×103×321+ 456×654×103+ 456×321
=123×654×106+123×321×103+ 456×654×103+ 456×321
=（123×654）×106+（123×321+ 456×654）×103+ 456×321
如果能分别求出（123×654）、（123×321+ 456×654）、456×321，问题不就解决了吗？而（123×654）、（123×321+ 456×654）、456×321，可以确信，是可以用int类型表示的。
在这种情况下，用一个int变量存储123456或654321是不行的，需要两个，一个用来记录123456或654321的前三位，另一个记录后三位。这种对数据的组织和安排方式，就是所谓的数据结构。尽管这里的还只是一种很粗糙的数据结构。此外还可以发现，设计数据结构首先涉及到的问题恰恰是选择合适的数据类型。
在这种数据结构下的算法就是：首先求出（123×654）、（123×321+ 456×654）、456×321。可以断定积的最后三位是456×321对1000求余的结果，最前面几位是（123×654）+（123×321+ 456×654）/103，中间三位的值为（123×321+ 456×654）%103+456×321/1000。（这些示意性的东西叫伪代码（Pseudocode））
从对算法的描述中还可以发现，积最好用三个int来表示。
所以，所谓的算法无非就是对操作步骤的描述。描述算法的方式有很多，其中之一就是使用自然语言来描述。用C语言描述的算法和数据结构就是C代码。
- /*编程求123456*654321*/
- #include <stdio.h>
- #include <stdlib.h>
- #define CS1 123456 //乘数1
- #define CS2 654321 //乘数2
- #define YQ 1000 //一千
- int main(void)
- {
- int cs1_q3w,cs1_h3w,cs2_q3w,cs2_h3w;//乘数1、乘数2的前3位和后3位
- int ji_q,ji_z,ji_h; //积的前、中、后三个部分
-
- cs1_q3w = CS1 / YQ ;
- cs1_h3w = CS1 % YQ ;
-
- cs2_q3w = CS2 / YQ ;
- cs2_h3w = CS2 % YQ ;
- //求出（123×654）、（123×321+ 456×654）、456×321
- ji_q = cs1_q3w * cs2_q3w ;
- ji_z = cs1_q3w * cs2_h3w + cs1_h3w * cs2_q3w ;
- ji_h = cs1_h3w * cs2_h3w ;
- //进位处理,注意：次序很重要
- ji_q = ji_q + ji_z / YQ ;
- ji_z = ji_z % YQ + ji_h / YQ ;
- ji_h = ji_h % YQ ;
- //输出
- printf("%d×%d == %d%d%d\n" , CS1 , CS2 , ji_q , ji_z ,ji_h );
- system("PAUSE");
- return 0;
- }
程序输出
123456×654321 == 80779853376
与程序代码3-5的输出相比，这个结果至少可以说可信度很高，尽管我们还无法确信。
增强对程序正确性信心的方法只有通过测试。由于这段代码对于两个不多于6位的十进制数都应该成立，所以可以选择易于验算的情况运行程序，比如把123456改为100000再运行程序。
然而，很遗憾，程序求100000×654321的结果竟然是
100000×654321 == 654321000
造成这个错误的原因是，代码中ji_z、ji_h表示的都是三位的十进制数，但当它们的值为0时，%d这种格式只输出1个0而不是3个0。改进的办法是把它们对应的%d改成%03d。其中3表示输出三位，0表示如果前面有空格则填充0（可以自己上机对比一下%03d、%3d和%d之间的区别）。
把输出改写为
printf("%d×%d == %d%03d%03d\n" , CS1 , CS2 , ji_q , ji_z ,ji_h );
之后，可以发现程序求100000×654321的结果是正确的。如果还不放心，可以再找一些数据进行测试。
免费注册
楼主: DNFCF
发表于 2011-04-28 22:03
发表于 2011-04-28 22:37
