資訊科學(xué)的邏輯思考--演算法楊昌彪

教授兼系主任中山大學(xué)資訊工程學(xué)系.tw12000年全國大專電腦軟體設(shè)計競賽(60隊)排名隊伍編號學(xué)校答對題數(shù) 時間

1 A011 臺灣大學(xué) 4 5172 A027 清華大學(xué) 4 5783 A030 交通大學(xué) 4 7424 A034 交通大學(xué) 4 7485 A028 清華大學(xué) 4 7916 A010 臺灣大學(xué) 411947 A013 臺灣大學(xué) 3 3678 A014 臺灣大學(xué) 3 4379 A025 清華大學(xué) 3 56110 A039 逢甲大學(xué) 3 56311 A047 中正大學(xué) 3 56512 A024 清華大學(xué) 3 56813 A054 中山大學(xué) 3 76614 A009 臺灣大學(xué) 3 80615 A007臺灣師範(fàn)大學(xué) 2 23016 A031 交通大學(xué) 2 26617 A001 長庚大學(xué) 2 27318 A035 交通大學(xué) 2 31719 A012 臺灣大學(xué) 2 32520 A015 海洋大學(xué) 2 361排名隊伍編號學(xué)校答對題數(shù) 時間21 A023臺灣科技大學(xué) 2 46222 A006臺灣師範(fàn)大學(xué) 1 5623 A053 中山大學(xué) 1 6224 A056 中山大學(xué) 1 11525 A033 交通大學(xué) 1 12626 A032 交通大學(xué) 1 14627 A048崑山科技大學(xué) 1 19427 A055 中山大學(xué) 1 19428 A026 清華大學(xué) 1 19529 A008臺灣師範(fàn)大學(xué) 1 20630 A036 暨南大學(xué) 1 22031 A029 清華大學(xué) 1 25232 A037 暨南大學(xué) 1 26933 A017臺北科技大學(xué) 1 30434 A052和春技術(shù)學(xué)院 1 30835 A019臺灣師範(fàn)大學(xué) 1 34836其餘隊伍0022000ACM亞洲區(qū)臺北賽區(qū)大學(xué)程式設(shè)計競賽(48隊)Rank TeamName SchoolName Problems SolvedPenalty 1 Doodoong Seoul NationalUniversity 5 735 2 GoldMedal NationalTaiwanUniversity 4 714 3 AppleCarMovie NationalTaiwanUniversity 3 291 3 GodofPower NationalTaiwanUniversity 3 439 3 CUHKMarsTheChineseUniv.ofHongKong 3 817 4 D.N.A. NationalTaiwanUniversity 2 263 4 superSLP NationalTaiwanUniversity 2 298 4 eagle NationalTsing-HuaUniversity 2 302 5 RoastedWing NationalChiao-TungUniversity 2 303 5 NCTUJPNLAB NationalChiao-TungUniversity 2 421 5 CSIEDragon NationalChiao-TungUniversity 2 460 6 Seal NationalSunYat-senUniversity 2 477 6 CUHKMercuryTheChineseUniv.ofHongKong 2 597 7 OceanStar NationalTaiwanOceanUniv. 2 600 8 CSIESnake NationalChiao-TungUniversity 1 48 8 FunkyFamilyIX NationalTaiwanUniversity 1 136 8 Ants NationalTsing-HuaUniversity 1 142 8 TheSevenWonders NationalTaiwanUniversity 1 153 8 ICEWorld NationalTaiwanNormalUniv. 1 156 9 ICESnow NationalTaiwanNormalUniv. 1 186 9 clover NationalTaiwanNormalUniv. 1 194 9 ICEStorm NationalTaiwanNormalUniv. 1 256 9 CSIETiger NationalChiao-TungUniversity 1 278 9 Eustis NationalTsing-HuaUniversity 1 289 9 Braves NationalTsing-HuaUniversity 1 297 9 ilantech NationalI-LanInstituteofTech. 1 316 10 ICE007 NationalTaiwanNormalUniv. 1 359 31998ACM大學(xué)程式設(shè)計競賽世界總決賽(54隊)PlaceUniversitySolvedMinutes1CharlesU-Prague69192St.PetersburgUniv.610213UWaterloo610264UUmea-Sweden610735MIT611456MelbourneU611537TsingHuaU-Beijing57438UAlberta57589WarsawU578010PolitehnicaUBucharest581311UCBerkeley511NanyangTU-Singapore511St.PetersburgIFMO511DukeUniversity511VirginiaTech511ShanghaiJiaotongU.517McGillPoutines417NationalTaiwanU417SofiaUniversity417MoscowStateU417UTexas-Austin417Caltech417UralStateTU4PlaceUniversitySolved

24CaseWestern324BUET,Bangladesh324StanfordU324PUCRiodeJaneiro324ShanghaiUniv.329ComeniusU229UniversityofUlm229UAuckland229HardingUniversity229FloridaTech229UMissouri-Rolla229U.Minnesota-Morris229BinusU.-Indonesia229UCentralFlorida229DarmstadtUT229NTNU-Taiwan229ITESM2

4邏輯思考邏輯思考乃解決所有事務(wù)之基礎(chǔ)(不論是否使用電腦)從小至大，每天均在累積邏輯思考的實力，但求學(xué)期間增進較多數(shù)學(xué)課程是邏輯思考的基礎(chǔ)6資訊科學(xué)(資訊工程)與數(shù)學(xué)數(shù)學(xué)在計算上有其實用性數(shù)學(xué)在深入的研究領(lǐng)域上可能較抽象離散數(shù)學(xué)為資訊科學(xué)的數(shù)學(xué)基礎(chǔ)資訊科學(xué)是數(shù)學(xué)的一個應(yīng)用領(lǐng)域資訊科學(xué)需設(shè)計實際可行的軟硬體7何謂演算法Algorithm解決問題的方法。將抽象的解法變成實際具體可行的方法或程式。利用電腦解決問題的步驟Step1:明確定義問題（將其模式化）Step2:設(shè)計演算法，並估計所需時間Step3:撰寫程式，並加以測試8解決問題範(fàn)例問題：計算大學(xué)聯(lián)考英文之頂標(biāo)明確定義：計算所有考生中前25%英文成績之平均演算法：Step1:將所有考生英文成績排序（由高至低）Step2:將排名在前面1/4的成績資料相加後， 再除以1/4的人數(shù)撰寫程式：…...9各種排序演算法所需時間比較CPU:K6-2350 時間單位：秒10何時學(xué)習(xí)演算法課程順序程式設(shè)計資料結(jié)構(gòu)離散數(shù)學(xué)演算法事實上，開始學(xué)習(xí)程式設(shè)計，即已開始學(xué)習(xí)演算法11演算法範(fàn)例【問題】將50元硬幣換成等值的1元、5元、10元硬幣的方法共有多少種？【方法-1】採用窮舉法，每種硬幣可能的個數(shù)如下：i(10元):0,1,2,3,4,5j(5元):0,1,2,…,10k(1元):0,1,2,…,50假設(shè)i,j,k分別代表10元、5元、1元的個數(shù)，則我們可以嘗試各種組合，並利用下面的判斷式：

i*10+j*5+k=50

<執(zhí)行迴圈次數(shù)>

6*11*51=336612main(){

intloop=0,number=0;

inti,j,k;for(i=0;i<=5;i++)for(j=0;j<=10;j++)for(k=0;k<=50;k++){loop++;if(i*10+j*5+k==50)number++;}

printf("共%d種,執(zhí)行迴圈%d次\n",number,loop);}【執(zhí)行結(jié)果】

共36種,執(zhí)行迴圈3366次13【方法-2】若k不為5之倍數(shù)，根本不可能轉(zhuǎn)換，所以只需考慮k為5之倍數(shù)的情況。i(10元):0,1,2,3,4,5j(5元):0,1,2,…,10k(1元):0,5,10,…,50

<執(zhí)行迴圈次數(shù)>

6*11*11=72614main(){

intloop=0,number=0;

inti,j,k;for(i=0;i<=5;i++)for(j=0;j<=10;j++)for(k=0;k<=50;k+=5){loop++;if(i*10+j*5+k==50)number++;}

printf("共%d種,執(zhí)行迴圈%d次\n",number,loop);}【執(zhí)行結(jié)果】

共36種,執(zhí)行迴圈726次15【方法-3】當(dāng)i*10+j*5+k=50時，應(yīng)立即跳出最內(nèi)層迴圈，因為再變化k之值，i*10+j*5+k均已大於50。

<執(zhí)行迴圈次數(shù)>

49116main(){

intloop=0,number=0;

inti,j,k;for(i=0;i<=5;i++)for(j=0;j<=10;j++)

for(k=0;k<=50;k+=5){loop++;if(i*10+j*5+k==50){number++;break;}}

printf("共%d種,執(zhí)行迴圈%d次\n",number,loop);}【執(zhí)行結(jié)果】

共36種,執(zhí)行迴圈491次17【方法-4】當(dāng)i和j之值固定後，k之值只有唯一的選擇，因此不必考慮k的變化情形。i=0,j可能為0,1,2,…,10(50-i*10)/5=10i=1,j可能為0,1,2,…,8(50-i*10)/5=8i=2,j可能為0,1,2,…,6(50-i*10)/5=6...i=5,j可能為0(50-i*10)/5=0

<執(zhí)行迴圈次數(shù)>

3618main(){

intloop=0,number=0;

inti,j;for(i=0;i<=5;i++)

for(j=0;j<=(50-i*10)/5;j++){loop++;number++;

}

printf("共%d種,執(zhí)行迴圈%d次\n",number,loop);}【執(zhí)行結(jié)果】

共36種,執(zhí)行迴圈36次19【方法-5】由上一個方法知，當(dāng)i的值固定後，j的變化情形只有(50-i*10)/5種，因此只需對i做迴圈。

<執(zhí)行迴圈次數(shù)>

6main(){intloop=0,number=0;inti;for(i=0;i<=5;i++){loop++;number+=(50-i*10)/5+1;}printf("共%d種,執(zhí)行迴圈%d次\n",number,loop);}【執(zhí)行結(jié)果】

共36種,執(zhí)行迴圈6次20【方法-6】我們計算的值其實是一個等差級數(shù)，即11+9+7+…+1=6*(11+1)/2=36將等差級數(shù)的公式寫成程式即可計算。main(){intnumber=0,a,b,n=50;a=n/5+1;if(a%2==0)b=2;elseb=1;number=(a+b)*((a-b)/2+1)/2;

printf("共%d種\n",number);}【執(zhí)行結(jié)果】

共36種21上課教室與圖形著色課程ABCDE8:0018:00區(qū)間圖形著色問題(intervalgraphcoloring)：C1C1C2C3C2C1：第一個顏色C2：第二個顏色C3：第三的顏色ABDCE22問題難易度容易的問題：在多項式時間(polynomialtime)可 解決的問題如：排序，找最大值困難的問題：NP-complete，NP-hard如：分割問題(PartitionProblem) 推銷員問題(TravelingSalespersonProblem)不可解的問題：用演算法無法解決的問題如：停止問題(HaltingProblem)23我想不出好方法，我可能太笨了！24我想不出好方法，

因為不可能有這種好方法！25我想不出好方法，

因為這些名人專家也不會！26環(huán)球旅遊與推銷員問題

平面上給予n個點，從某一點出發(fā)，經(jīng)過每個點一次，再回到出發(fā)點，而其總長度為最短

此為NP-complete問題27職棒比賽與分割問題

給予一個正整數(shù)的集合A={a1,a2,…,an}，是否可以將其分割成兩個子集合，而此兩個子集合的個別總和相等。

例：A={1,3,8,4,10}可以分割：{1,8,4}及{3,10} 此為NP-complete問題28股票投資與0/1knapsack問題

有n個東西，每個東西有其個別價值(value)與重量(weight)另有一個袋子，其容量為M，如何選取某些東西，使其總重要不超過M，而其總價值為最高。例：

M=14最佳(optimal)解法：P1、P2、P3、P50/1knapsack問題為NP-complet