0.問題 (黑體,15)
一個N位的十進制正整數,如果它的每個位上的數字的N次方的和等於這個數本身,則稱其為花朵數。 (宋體,15,Arial)
例如:
當N=3時,153就滿足條件,因為 1^3 + 5^3 + 3^3 = 153,這樣的數字也被稱為水仙花數(其中,“^”表示乘方,5^3表示5的3次方,也就是立方)。
當N=4時,1634滿足條件,因為 1^4 + 6^4 + 3^4 + 4^4 = 1634。
當N=5時,92727滿足條件。
實際上,對N的每個取值,可能有多個數字滿足條件。
程序的任務是:求N=21時,所有滿足條件的花朵數。注意:這個整數有21位,它的各個位數字的21次方之和正好等於這個數本身。如果滿足條件的數字不只有一個,請從小到大輸出所有符合條件的數字,每個數字占一行。因為這個數字很大,請注意解法時間上的可行性。要求程序在3分鐘內運行完畢。
1.用C語言表達問題
/*0_問題.h*/#ifndef WENTI_H
#define WENTI_H
#define CESHI //進行測試
//#define QIUJIE //求解21位問題
#ifdef CESHI //測試
#define JINZHI 10 //十進制
#define WEISHU 3 //3位花朵數
#define N WEISHU //冪次==位數
#endif //CESHI
#ifdef QIUJIE //求解
#define JINZHI 10 //十進制
#define WEISHU 21 //位數
#define N WEISHU //冪次==位數
#endif //QIUJIE
#endif // WENTI_H
編寫代碼首先要提出問題,理解問題,並用C語言表達問題。
這裡的符號常量就是C語言對問題的描述。盡管不可能完全描述,但卻充分地表現了問題的特征。由於對問題進行了抽象,使得代碼可以具有更廣的適應范圍。即不但適合求解21位花朵數,同樣適合求解其他位數的花朵數問題;不但適合求解十進制問題,也適合其他進制問題。
把問題中的常數寫成符號常量同時也是為了測試的需要。沒有人敢開一輛沒有測試過的汽車,但是很奇怪,人們卻敢於使用沒有經過充分測試的軟件,實際上後者往往更危險。
測試的必要性還體現在,稍具規模的代碼幾乎絕對不可能一氣呵成地一次性寫正確,測試在這裡實際上也是開發的有力助手。
在開始寫代碼時並不清楚究竟有沒有21位花朵數,如果有的話,同樣也不清楚這個花朵數是多少。如果希望對自己的代碼有點信心,那麼這種信心只能來自測試。然而對21位花朵數的測試幾乎沒有可能,這時只能測試規模較小的同類問題。較小規模問題測試通過後,我們才能對較大的問題的解產生一些自信。
這裡的“#define CESHI //進行測試”就如同一個開關一樣,如果把CESHI改成QIUJIE,不用修改代碼,只要重新編譯,就可以得到求解21位問題的程序。
2.開始求解
首先寫main()。由於在代碼編寫過程中涉及到測試,所以寫了兩個main()。
/*1_MAIN.c*/
/*
Name:花朵數問題
Author:鍵盤農夫
Date:2011,5,30
Description:
*/
#include "1_MAIN.h"
#ifdef CESHI //測試
int main( void )
{
system("PAUSE");
return 0;
}
#endif //CESHI
#ifdef QIUJIE //求解
int main( void )
{
system("PAUSE");
return 0;
}
#endif //QIUJIE
與之對應的,還有一個
/*1_MAIN.h*/
#ifndef MAIN_H
#define MAIN_H
#include "0_問題.h"
/**************************類型定義**************************/
/**************************函數原型**************************/
#include <stdlib.h> //system()
#endif // MAIN_H
這是聯系“0_問題.h”和main()的紐帶,同時也以備以後補充類型定義和函數原型。
3.解決方案
回顧問題不難發現,問題的全部要求可分為“求解”和“輸出”兩個步驟。
搜索一下自己的數學知識,並沒有什麼神奇的定理對解決這個問題有所幫助。沒辦法,只好用最笨的辦法——窮舉。窮舉只能在窮舉的過程中對所枚舉的各種可能進行驗算,因此main()改寫為
#ifdef QIUJIE //求解
int main( void )
{
//求解:窮舉<=>驗算<=>記錄結果
//輸出
system("PAUSE");
return 0;
}
#endif //QIUJIE
“記錄結果”而不是立即輸出的原因是問題要求“從小到大輸出”。
編譯通過,運行正常!收工。
4.完成第一個自定義函數框架的過程
至少有四個函數需要寫,首先從“窮舉”入手。步驟:
1.在main()中寫出函數調用,qiongju();
2.緊接著在原地描述這個函數的原型,void qiongju( void );
#ifdef QIUJIE //求解
int main( void )
{
//求解:窮舉<=>驗算<=>記錄結果
qiongju();//void qiongju( void );
//輸出
system("PAUSE");
return 0;
}
#endif //QIUJIE
3.考慮這個函數定義的位置,由於這個函數可能比較復雜,所以把這個函數安排在另外一個源文件“2_窮舉.c”中,添加“2_窮舉.c”和“2_窮舉.h”
4.在"1_MAIN.h"中加入 #include "2_窮舉.h" 預處理命令
5.將main()中的qiongju()的函數原型移動到“2_窮舉.h”的函數原型部分,並修改為
extern void qiongju( void );
/*2_窮舉.h*/ #ifndef QIONGJU_H#define QIONGJU_H /**************************類型定義**************************//**************************函數原型**************************/ extern void qiongju( void );#endif // QIONGJU_H 6.在"2_窮舉.c"中寫出空的qiongju()函數定義,順便把main()中的一部分注釋移過來
/*2_窮舉.c*/
#include "2_窮舉.h"
extern void qiongju( void )
{//<=>驗算<=>記錄結果} 把 0_問題.h 中的 #define CESHI 中的CESHI改成QIUJIE,編譯通過,運行正常!收工。
(未完待續)