第21課計(jì)算水仙花數(shù)第21課計(jì)算水仙花數(shù)11.尋找水仙花數(shù)。水仙花數(shù)是指這樣的三位整數(shù)，其各個(gè)位上的數(shù)之立方和恰好等于該數(shù)自己，例如371，是水仙花數(shù)，因?yàn)?71=33+73+13,設(shè)計(jì)一個(gè)算法尋找出所有的水仙花數(shù)。

2.尋找玫瑰花數(shù)。玫瑰花數(shù)是指這樣的四位整數(shù)，其各個(gè)位上的數(shù)之4次方和恰好等于該數(shù)自己，例如1634，1634=14+64+34+44,設(shè)計(jì)一個(gè)算法尋找出所有的玫瑰花數(shù)。

3.尋找勾股數(shù)。“勾股數(shù)”指滿足勾股定理關(guān)系的一組整數(shù)，也就是直角三角形三邊長恰好都取整數(shù)值的特殊情況，3，4，5就是一組勾股數(shù)大家都知道32+42=52，輸出50以內(nèi)能夠組成勾股數(shù)。

4.“百錢買百雞”問題。中國古代數(shù)學(xué)家張丘建在《張丘建算經(jīng)》中提出一個(gè)問題。“雞翁一，值錢五，雞母一，值錢三，雞雛三，值錢一。百錢買百雞。問雞翁、母、雛各幾何？”。1.尋找水仙花數(shù)。水仙花數(shù)是指這樣的三位整數(shù)，其各個(gè)位上的數(shù)2枚舉算法枚舉算法的基本思想是把問題所有的可能解一一地羅列出來，并對每一個(gè)可能解進(jìn)行判斷，以確定這個(gè)可能解是否是問題的真正解。

在設(shè)計(jì)枚舉算法時(shí)，必須注意的是：

（1）不能遺漏任何一個(gè)真正解，這是問題本身所要求的；

（2）盡可能地使可能解的羅列范圍最小，這是為了提高解決問題的效率。枚舉算法枚舉算法的基本思想是把問題所有的可3實(shí)踐活動(dòng)尋找水仙花數(shù)。水仙花數(shù)是指這樣的三位整數(shù)，其各個(gè)位上的數(shù)之立方和恰好等于該數(shù)自己，例如371，是水仙花數(shù)，因?yàn)?71=33+73+13,設(shè)計(jì)一個(gè)算法尋找出所有的水仙花數(shù)。

（1）.算法分析（點(diǎn)擊打開算法分析）：

水仙花數(shù)是三位整數(shù)，從100到999共900種可能，羅列出問題所有可能的解并判斷每個(gè)位上數(shù)字的3次方之和是否恰好等于它自己，使用運(yùn)算符MOD和\對每個(gè)整數(shù)進(jìn)行分解，分別得到百位上的數(shù)字、十位上的數(shù)字和個(gè)位上的數(shù)字。

實(shí)踐活動(dòng)尋找水仙花數(shù)。水仙花數(shù)是指這樣的4算法分析i<1000？輸出一個(gè)水仙花數(shù)i結(jié)束Na←百位上的數(shù)字開始i←100b←十位上的數(shù)字c←個(gè)位上的數(shù)字是否是水仙花數(shù)？a3+b3+c3=i?Yi←i+1NY算法分析i<1000？輸出一個(gè)水仙花數(shù)i結(jié)束Na←百位上的數(shù)5（2）.分析并編寫程序代碼：

①程序界面設(shè)計(jì)：（2）.分析并編寫程序代碼：

①程序界面設(shè)計(jì)：6控件屬性值的設(shè)置參考如下表對象名屬性名屬性值Form1Caption水仙花數(shù)List1（用繪制而成）list空白Command1Caption計(jì)算控件屬性值的設(shè)置參考如下表對象名屬性名屬性值Form1Ca7②分析算法流程，編寫代碼；

PrivateSubCommand1_Click()

DimsumAsInteger

Dimi,a,b,cAsInteger

List1.Clear

Fori=100To999

a=i\100‘求得百位上的數(shù)字a

b=i\10Mod10'求得十位上的數(shù)字b

c=iMod10'求得個(gè)位上的數(shù)字c

Ifa^3+b^3+c^3=iThen'判斷是否滿足條件

List1.AddItem(Str(i))

sum=sum+1

EndIf

Nexti

Label1.Caption="個(gè)數(shù)："+Str(sum)

EndSub

③運(yùn)行調(diào)試程序;

②分析算法流程，編寫代碼；

PrivateSubComm8課堂練習(xí)1.尋找水仙花數(shù)問題，請將劃線處填寫完整：

PrivateSubCommand1_Click()

DimsumAsInteger

DimaAsInteger,bAsInteger,kAsInteger

List1.Clear

Fora=1To9

Forb=0To9

Fork=0To9

If__________________________________Then‘(1)List1.AddItem(Str(100*a+10*b+k))

sum=sum+1

EndIf

Nextk

Nextb

_____________________’(2)

Label1.Caption="個(gè)數(shù)："+Str(sum)

EndSuba^3+b^3+k^3=100*a+10*b+kNexta課堂練習(xí)1.尋找水仙花數(shù)問題，請將劃線處填寫完整：

Priv92.把一個(gè)兩位數(shù)的個(gè)位數(shù)字與其十位數(shù)字交換后得到一個(gè)新數(shù)，它與原數(shù)相加，結(jié)果恰好是一個(gè)自然數(shù)的平方，這樣的兩位數(shù)有多少？請將下面代碼中的劃線處填寫完整：

PrivateSubCommand1_Click()

Dims1AsInteger,s2asInteger

DimaAsInteger,bAsInteger

List1.Clear

Fora=1To9

Forb=aTo9'假設(shè)b≥a,避免重復(fù)

s1=10*a+b

____________________________‘(1)If__________________________ThenList1.AddItem(str(s1))‘(1)尋找滿足條件的方案

Nextb

Nexta

EndSub

s2=10*b+a

int(sqr(s1+s2))^2=s1+s2

2.把一個(gè)兩位數(shù)的個(gè)位數(shù)字與其十位數(shù)字交換后得到一個(gè)新數(shù)，10算法的效率（一）評價(jià)一個(gè)算法的效率主要是考察算法執(zhí)行時(shí)間的情況。可以在相同的規(guī)模下，根據(jù)執(zhí)行時(shí)間的長短來評價(jià)一個(gè)算法的優(yōu)劣。一個(gè)算法的好壞對計(jì)算機(jī)的效能影響有多大呢？我們來做這樣一個(gè)比較，假設(shè)有兩臺計(jì)算機(jī)分別是計(jì)算機(jī)A和計(jì)算機(jī)B，計(jì)算機(jī)A的運(yùn)算處理速度比計(jì)算機(jī)B大約快50倍。以求解“百錢買百雞”（“雞翁一，值錢五，雞母一，值錢三，雞雛三，值錢一。百錢買百雞。問雞翁、母、雛各幾何？”）為例子，設(shè)雞翁為x只，雞母為y只，雞雛為z只。算法A：把公雞、母雞、小雞的枚舉范圍都是1～100；算法B：經(jīng)粗略計(jì)算公雞的枚舉范圍為1～20，母雞的枚舉范圍為1～33，而小雞的枚舉范圍應(yīng)是100－x－y。在計(jì)算機(jī)A上運(yùn)行算法A程序，在計(jì)算機(jī)B上運(yùn)行算法B程序，兩臺計(jì)算機(jī)誰先把結(jié)果運(yùn)算出來呢？

算法的效率（一）評價(jià)一個(gè)算法的效11算法A的程序代碼如下：

Forx=1To100

Fory=1To100

Forz=1To100

If(x+y+z=100)And(5*x+3*y+z/3=100)Then

List1.AddItemStr(x)+“”+Str(y)+“”+Str(z)

EndIf

Nextz

Nexty

Nextx

算法B程序代碼如下：

Forx=1To20

Fory=1To33

Z=100-x-y

If5*x+3*y+z/3=100Then

List1.AddItemStr(x)+“”+Str(y)+“”+Str(z)

EndIf

Nexty

Nextx算法A的程序代碼如下：

Forx=1To12運(yùn)算結(jié)果是計(jì)算機(jī)B先把結(jié)果運(yùn)算出來。為什么會這樣呢？我們來分析一下，算法A需要執(zhí)行100×100×100=1000000次內(nèi)循環(huán)，而算法B只需要執(zhí)行20×33=660次內(nèi)循環(huán)，雖然計(jì)算機(jī)A比計(jì)算機(jī)B快50多倍，但還是計(jì)算機(jī)B先求得計(jì)算結(jié)果。

一個(gè)好的算法可以算得更快。什么樣的算法是好算法呢？通常從時(shí)間復(fù)雜度和空間復(fù)雜度兩方面來評價(jià)，在這里我們主要討論時(shí)間復(fù)雜度。通常我們把算法的基本操作執(zhí)行的次數(shù)作為算法的時(shí)間量度T(n)=O(f(n))，表示隨著規(guī)模n的增大，算法執(zhí)行時(shí)間的增長率和f(n)的增長率相同，稱時(shí)間復(fù)雜度，估算時(shí)按該算法對各種輸入情況的平均值來考慮。在最壞情況下的復(fù)雜度和平均情況下的復(fù)雜度是評估算法兩種衡量標(biāo)準(zhǔn)。運(yùn)算結(jié)果是計(jì)算機(jī)B先把結(jié)果運(yùn)算出來。為131.尋找水仙花數(shù)。水仙花數(shù)是指這樣的三位整數(shù)，其各個(gè)位上的數(shù)之立方和恰好等于該數(shù)自己，例如371，是水仙花數(shù)，因?yàn)?71=33+73+13,設(shè)計(jì)一個(gè)算法尋找出所有的水仙花數(shù)。

算法流程圖

程序代碼設(shè)計(jì)

示例程序

1.尋找水仙花數(shù)。水仙花數(shù)是指這樣的三位整數(shù)，其各個(gè)位上的142.尋找玫瑰花數(shù)。玫瑰花數(shù)是指這樣的四位整數(shù)，其各個(gè)位上的數(shù)之4次方和恰好等于該數(shù)自己，例如1634，1634=14+64+34+44,設(shè)計(jì)一個(gè)算法尋找出所有的玫瑰花數(shù)。

算法流程圖

程序代碼設(shè)計(jì)

示例程序

2.尋找玫瑰花數(shù)。玫瑰花數(shù)是指這樣的四位整數(shù)，其各個(gè)位上的數(shù)153.尋找勾股數(shù)。“勾股數(shù)”指滿足勾股定理關(guān)系的一組整數(shù)，也就是直角三角形三邊長恰好都取整數(shù)值的特殊情況，3，4，5就是一組勾股數(shù)大家都知道32+42=52，輸出5