難道C語言對待如此簡單的小學(xué)生都會做的算術(shù)問題都束手無策嗎？倒也不是這樣，辦法是有的，但需要你自己去想。編程的樂趣大抵在此。
由于本題目問題的核心在于兩個較大的數(shù)相乘超過了int類型的范圍，所以可以考慮把乘數(shù)拆成較小的數(shù)。比如
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的前三位，另一個記錄后三位。這種對數(shù)據(jù)的組織和安排方式，就是所謂的數(shù)據(jù)結(jié)構(gòu)。盡管這里的還只是一種很粗糙的數(shù)據(jù)結(jié)構(gòu)。此外還可以發(fā)現(xiàn)，設(shè)計數(shù)據(jù)結(jié)構(gòu)首先涉及到的問題恰恰是選擇合適的數(shù)據(jù)類型。
在這種數(shù)據(jù)結(jié)構(gòu)下的算法就是：首先求出（123×654）、（123×321+ 456×654）、456×321�？梢詳喽ǚe的最后三位是456×321對1000求余的結(jié)果，最前面幾位是（123×654）+（123×321+ 456×654）/103，中間三位的值為（123×321+ 456×654）%103+456×321/1000。（這些示意性的東西叫偽代碼（Pseudocode））
從對算法的描述中還可以發(fā)現(xiàn)，積最好用三個int來表示。
所以，所謂的算法無非就是對操作步驟的描述。描述算法的方式有很多，其中之一就是使用自然語言來描述。用C語言描述的算法和數(shù)據(jù)結(jié)構(gòu)就是C代碼。
- /*編程求123456*654321*/
- #include <stdio.h>
- #include <stdlib.h>
- #define CS1 123456 //乘數(shù)1
- #define CS2 654321 //乘數(shù)2
- #define YQ 1000 //一千
- int main(void)
- {
- int cs1_q3w,cs1_h3w,cs2_q3w,cs2_h3w;//乘數(shù)1、乘數(shù)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 ;
- //進(jìn)位處理,注意：次序很重要
- 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的輸出相比，這個結(jié)果至少可以說可信度很高，盡管我們還無法確信。
增強(qiáng)對程序正確性信心的方法只有通過測試。由于這段代碼對于兩個不多于6位的十進(jìn)制數(shù)都應(yīng)該成立，所以可以選擇易于驗算的情況運(yùn)行程序，比如把123456改為100000再運(yùn)行程序。
然而，很遺憾，程序求100000×654321的結(jié)果竟然是
100000×654321 == 654321000
造成這個錯誤的原因是，代碼中ji_z、ji_h表示的都是三位的十進(jìn)制數(shù)，但當(dāng)它們的值為0時，%d這種格式只輸出1個0而不是3個0。改進(jìn)的辦法是把它們對應(yīng)的%d改成%03d。其中3表示輸出三位，0表示如果前面有空格則填充0（可以自己上機(jī)對比一下%03d、%3d和%d之間的區(qū)別）。
把輸出改寫為
printf("%d×%d == %d%03d%03d\n" , CS1 , CS2 , ji_q , ji_z ,ji_h );
之后，可以發(fā)現(xiàn)程序求100000×654321的結(jié)果是正確的。如果還不放心，可以再找一些數(shù)據(jù)進(jìn)行測試。
免費注冊
樓主: DNFCF
發(fā)表于 2011-04-28 22:03
發(fā)表于 2011-04-28 22:37
