acm程序設(shè)計(jì)算法講解

1、ACM程序設(shè)計(jì)算法講解1目錄1.河內(nèi)之塔...............................................................................................................................................32.AlgithmGossip:費(fèi)式數(shù)列....................................

2、...........................................................................43.巴斯卡三角形.......................................................................................................................................5

3、4.AlgithmGossip:三色棋...................................................................................................................65.AlgithmGossip:老鼠走迷官（一）.............................................................

4、..................................86.AlgithmGossip:老鼠走迷官（二）.............................................................................................107.AlgithmGossip:騎士走棋盤.............................................

5、............................................................118.AlgithmGossip:八皇后.................................................................................................................149.AlgithmGossip:八枚銀幣....

6、.........................................................................................................1610.AlgithmGossip:生命游戲............................................................................................

7、...............1811.AlgithmGossip:字串核對(duì)...........................................................................................................2112.AlgithmGossip:雙色、三色河內(nèi)塔................................................

8、...........................................2313.AlgithmGossip:背包問(wèn)題（KnapsackProblem）.....................................................................2714.AlgithmGossip:蒙地卡羅法求PI.........................................

9、....................................................3215.AlgithmGossip:Eratosthenes篩選求質(zhì)數(shù)...................................................................................3316.AlgithmGossip:超長(zhǎng)整數(shù)運(yùn)算（大數(shù)運(yùn)算）..................

10、.........................................................3517.AlgithmGossip:長(zhǎng)PI.................................................................................................................3718.AlgithmGossip:最大公因數(shù)、最小公

11、倍數(shù)、因式分解...........................................................4019.AlgithmGossip:完美數(shù)...............................................................................................................4320.AlgithmGossip:阿姆

12、斯壯數(shù).......................................................................................................4621.AlgithmGossip:最大訪客數(shù)..........................................................................................

13、.............4822.AlgithmGossip:中序式轉(zhuǎn)后序式（前序式）...........................................................................5023.AlgithmGossip:后序式的運(yùn)算............................................................................

14、.......................5324.AlgithmGossip:洗撲克牌（亂數(shù)排列）...................................................................................5525.AlgithmGossip:Craps賭博游戲.........................................................

15、.........................................5726.AlgithmGossip:約瑟夫問(wèn)題（JosephusProblem）..................................................................5927.AlgithmGossip:排列組合.................................................

16、..........................................................6128.AlgithmGossip:格雷碼（GrayCode）......................................................................................6329.AlgithmGossip:產(chǎn)生可能的集合..................

17、.............................................................................6530.AlgithmGossip:m元素集合的n個(gè)元素子集............................................................................6831.AlgithmGossip:數(shù)字拆解.............

18、..............................................................................................7032.AlgithmGossip:得分排行.......................................................................................................

19、....7333.AlgithmGossip:選擇、插入、氣泡排序...................................................................................7534.AlgithmGossip:Shell排序法改良的插入排序....................................................................79

20、35.AlgithmGossip:Shaker排序法改良的氣泡排序..................................................................8236.排序法改良的選擇排序..........................................................................................................

21、....8437.AlgithmGossip:快速排序法（一）...........................................................................................8838.AlgithmGossip:快速排序法（二）.......................................................................

22、....................9039.AlgithmGossip:快速排序法（三）...........................................................................................92ACM程序設(shè)計(jì)算法講解31.河內(nèi)之塔河內(nèi)之塔說(shuō)明說(shuō)明河內(nèi)之塔(TowersofHanoi)是法國(guó)人M.Claus(Lucas)于1883年從泰國(guó)帶至法國(guó)的，河內(nèi)

23、為越戰(zhàn)時(shí)北越的首都，即現(xiàn)在的胡志明市；1883年法國(guó)數(shù)學(xué)家EdouardLucas曾提及這個(gè)故事，據(jù)說(shuō)創(chuàng)世紀(jì)時(shí)Benares有一座波羅教塔，是由三支鉆石棒（Pag）所支撐，開(kāi)始時(shí)神在第一根棒上放置64個(gè)由上至下依由小至大排列的金盤（Disc），并命令僧侶將所有的金盤從第一根石棒移至第三根石棒，且搬運(yùn)過(guò)程中遵守大盤子在小盤子之下的原則，若每日僅搬一個(gè)盤子，則當(dāng)盤子全數(shù)搬運(yùn)完畢之時(shí)，此塔將毀損，而也就是世界末日來(lái)臨之時(shí)。解法解法如果柱子標(biāo)為

24、ABC，要由A搬至C，在只有一個(gè)盤子時(shí)，就將它直接搬至C，當(dāng)有兩個(gè)盤子，就將B當(dāng)作輔助柱。如果盤數(shù)超過(guò)2個(gè)，將第三個(gè)以下的盤子遮起來(lái)，就很簡(jiǎn)單了，每次處理兩個(gè)盤子，也就是：AB、AC、BC這三個(gè)步驟，而被遮住的部份，其實(shí)就是進(jìn)入程式的遞回處理。事實(shí)上，若有n個(gè)盤子，則移動(dòng)完畢所需之次數(shù)為2^n1，所以當(dāng)盤數(shù)為64時(shí)，則所需次數(shù)為：2641=18446744073709551615為5.05390248594782e16年，也就是約500

25、0世紀(jì)，如果對(duì)這數(shù)字沒(méi)什幺概念，就假設(shè)每秒鐘搬一個(gè)盤子好了，也要約5850億年左右。#includevoidhanoi(intnABC)if(n==1)printf(“Movesheet%dfrom%cto%cn“nAC)elsehanoi(n1ACB)printf(“Movesheet%dfrom%cto%cn“nAC)hanoi(n1BAC)intmain()intnprintf(“請(qǐng)輸入盤數(shù)：“)scanf(“%d“hanoi(n