难道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的结果是正确的。如果还不放心,可以再找一些数据进行测试。