《资讯科学的逻辑思考演算法培训课件》由会员分享，可在线阅读，更多相关《资讯科学的逻辑思考演算法培训课件（33页珍藏版）》请在金锄头文库上搜索。
1、1,資訊科學的邏輯思考-演算法,楊昌彪 教授兼系主任 中山大學資訊工程學系 http:/www.cse.nsysu.edu.tw,2,2000年全國大專電腦軟體設計競賽(60隊),排名 隊伍編號 學校 答對題數時間 1A011台灣大學 4517 2A027清華大學 4578 3A030交通大學 4742 4A034交通大學 4748 5A028清華大學 4791 6A010台灣大學 4 1194 7A013台灣大學 3367 8A014台灣大學 3437 9A025清華大學 3561 10A039逢甲大學 3563 11A047中正大學 3565 12A024清華大學 3568 13A054中
2、山大學 3766 14A009台灣大學 3806 15A007 台灣師範大學 2230 16A031交通大學 2266 17A001長庚大學 2273 18A035交通大學 2317 19A012台灣大學 2325 20A015海洋大學 2361,排名 隊伍編號 學校 答對題數時間 21A023 台灣科技大學 2462 22A006 台灣師範大學 1 56 23A053中山大學 1 62 24A056中山大學 1115 25A033交通大學 1126 26A032交通大學 1146 27A048 崑山科技大學 1194 27A055中山大學 1194 28A026清華大學 1195 29A00
3、8 台灣師範大學 1206 30A036暨南大學 1220 31A029清華大學 1252 32A037暨南大學 1269 33A017 台北科技大學 1304 34A052 和春技術學院 1308 35A019 台灣師範大學 1348 36 其餘隊伍 0 0,3,2000 ACM亞洲區台北賽區大學程式設計競賽(48隊),RankTeam NameSchool NameProblemsSolved Penalty 1DoodoongSeoul National University 5735 2Gold MedalNational Taiwan University 4714 3Apple C
4、ar MovieNational Taiwan University 3291 3God of PowerNational Taiwan University 3439 3CUHK Mars The Chinese Univ. of Hong Kong 3817 4D.N.A. National Taiwan University 2263 4super SLPNational Taiwan University 2298 4eagleNational Tsing-Hua University 2302 5Roasted WingNational Chiao-Tung University 2
5、303 5NCTU JPN LABNational Chiao-Tung University 2421 5CSIE DragonNational Chiao-Tung University 2460 6SealNational Sun Yat-sen University 2477 6CUHK Mercury The Chinese Univ. of Hong Kong 2597 7Ocean StarNational Taiwan Ocean Univ. 2600 8CSIE SnakeNational Chiao-Tung University 1 48 8Funky Family IX
6、National Taiwan University 1136 8AntsNational Tsing-Hua University 1142 8The Seven WondersNational Taiwan University 1153 8ICE WorldNational Taiwan Normal Univ. 1156 9ICE SnowNational Taiwan Normal Univ. 1186 9cloverNational Taiwan Normal Univ. 1194 9ICE StormNational Taiwan Normal Univ. 1256 9CSIE
7、TigerNational Chiao-Tung University 1278 9EustisNational Tsing-Hua University 1289 9BravesNational Tsing-Hua University 1297 9ilantechNational I-Lan Institute of Tech. 1316 10ICE 007National Taiwan Normal Univ. 1359,4,1998 ACM大學程式設計競賽世界總決賽(54隊),Place University Solved Minutes 1 Charles U - Prague 6
8、919 2 St. Petersburg Univ. 6 1021 3 U Waterloo 6 1026 4 U Umea - Sweden 6 1073 5 MIT 6 1145 6 Melbourne U 6 1153 7 Tsing Hua U - Beijing 5 743 8 U Alberta 5 758 9 Warsaw U 5 780 10 Politehnica U Bucharest 5 813 11 UC Berkeley 5 11 Nanyang TU - Singapore 5 11 St. Petersburg IFMO 5 11 Duke University
9、5 11 Virginia Tech 5 11 Shanghai Jiaotong U. 5 17 McGill Poutines 4 17 National Taiwan U 4 17 Sofia University 4 17 Moscow State U 4 17 U Texas - Austin 4 17 Caltech 4 17 Ural State TU 4,Place University Solved 24 Case Western 3 24 BUET, Bangladesh 3 24 Stanford U 3 24 PUC Rio de Janeiro 3 24 Shangh
10、ai Univ. 3 29 Comenius U 2 29 University of Ulm 2 29 U Auckland 2 29 Harding University 2 29 Florida Tech 2 29 U Missouri-Rolla 2 29 U. Minnesota - Morris 2 29 Binus U.-Indonesia 2 29 U Central Florida 2 29 Darmstadt UT 2 29 NTNU - Taiwan 2 29 ITESM 2,6,邏輯思考,邏輯思考乃解決所有事務之基礎(不論是否使用電腦) 從小至大，每天均在累積邏輯思考的
11、實力，但求學期間增進較多 數學課程是邏輯思考的基礎,7,資訊科學(資訊工程)與數學,數學在計算上有其實用性 數學在深入的研究領域上可能較抽象 離散數學為資訊科學的數學基礎 資訊科學是數學的一個應用領域 資訊科學需設計實際可行的軟硬體,8,何謂演算法,Algorithm 解決問題的方法。將抽象的解法變成實際具體可行的方法或程式。 利用電腦解決問題的步驟 Step 1: 明確定義問題（將其模式化） Step 2: 設計演算法，並估計所需時間 Step 3: 撰寫程式，並加以測試,9,解決問題範例,問題：計算大學聯考英文之頂標 明確定義：計算所有考生中前25%英文成績之平均 演算法： Step 1:
12、 將所有考生英文成績排序（由高至低） Step 2: 將排名在前面1/4的成績資料相加後， 再除以1/4的人數 撰寫程式： .,10,各種排序演算法所需時間比較,CPU: K6-2 350時間單位：秒,11,何時學習演算法,課程順序 程式設計 資料結構 離散數學 演算法 事實上，開始學習程式設計，即已開始學習演算法,12,演算法範例,【問題】將50元硬幣換成等值的1元、5元、10元 硬幣的方法共有多少種？ 【方法-1】 採用窮舉法，每種硬幣可能的個數如下： i (10元):0,1,2,3,4,5 j (5 元):0,1,2,10 k (1 元):0,1,2,50 假設 i, j, k 分別代表
13、10元、5元、1元的個數， 則我們可以嘗試各種組合，並利用下面的判斷式： i*10 + j*5 + k = 50 6 * 11 * 51 = 3366,13,main() int loop = 0, number = 0; int i, 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種,執行迴圈%d次n,number,loop); 【執行結果】 共36種,執行迴圈3366次,14,【方法-
14、2】 若 k 不為 5 之倍數，根本不可能轉換，所以只需 考慮 k 為 5 之倍數的情況。 i (10元):0,1,2,3,4,5 j (5 元):0,1,2,10 k (1 元):0,5,10,50 6 * 11 * 11 = 726,15,main() int loop = 0, number = 0; int i, 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種,執行迴圈%d次
15、n,number,loop); 【執行結果】 共36種,執行迴圈726次,16,【方法-3】 當 i*10 + j*5 + k = 50時，應立即跳出最內 層迴圈，因為再變化 k 之值，i*10 + j*5 + k 均已大於 50。 491,17,main() int loop = 0, number = 0; int i, 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種,執行迴圈%d次n,number,loop); 【執行結果】 共36種,執行迴圈491次,18,【方法-4】 當 i 和 j 之值固定後，k 之值只有唯一的選擇， 因此不必考慮 k 的變化情形。 i=0,j可能為 0,1,2,10 (50-i*10)/5=10 i=1,j可能為 0,1,2,8 (50-i*10)/5=8 i=2,j可能為 0,1,2,6 (50-i*10)/5=6 . . . i=5,j可能為 0 (50-i*10)/5=0 36,19,main() int loop = 0, number = 0; int i, j
