程式的時間與空間 Time and Space in Programming 國立中山大學 資訊工程學系 平行處理實驗室 林必祥 李協彥 2017/11/18

TLE 在CPE評判系統中，若程式執行過久(約超過3秒)，會直接判定不通過 Why ? 如果沒有時間的限制，每道題目都超超超超暴力解，就能找到正確解答  人人都能解 7 題 !!

降低運算時間 刪除不必要的判斷、運算  要有好的算法，而不是傻傻的算 如果有重複的計算，可以將運算結果存起來，之後就不必再重新算  用空間來換取時間 !!

問題：將50元硬幣換成等值的1元、5元、10元硬幣的方法共有多少種？ + + + + + + + +

問題：將50元硬幣換成等值的1元、5元、10元硬幣的方法共有多少種？ 方法-1： 假設用了 i 個10元、 j 個5元、 k 個1元，每種硬幣可能的個數如下 i ( 10 元 ) : 0, 1, 2, 3, 4, 5 j ( 5 元 ) : 0, 1, 2, 3, …… , 9, 10 k ( 1 元 ) : 0, 1, 2, 3, ………… , 49, 50 採用窮舉法，嘗試各種(i, j, k)的組合，並利用下面的判斷式： 10i + 5j + k = 50 ? 便能計算出所有硬幣的組合。

問題：將50元硬幣換成等值的1元、5元、10元硬幣的方法共有多少種？ 方法-1： int i , j , k , ans = 0 , loop = 0; 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 ) ans++; } printf(“共 %d 種，迴圈執行了 %d 次\n”, ans , loop ); 共 36 種，迴圈執行了 3366 次

問題：將50元硬幣換成等值的1元、5元、10元硬幣的方法共有多少種？ 方法-2： 如果k不是5的倍數，便不可能轉換，因此可以排除掉那些情況 i ( 10 元 ) : 0, 1, 2, 3, 4, 5 j ( 5 元 ) : 0, 1, 2, 3, …… , 9, 10 k ( 1 元 ) : 0, 5, 10, 15, 20, ………… , 45, 50 ------------------------------------------------------------------- for( i = 0 ; i <= 5 ; i++) for( j = 0 ; j <= 10 ; j++) for( k = 0 ; k <= 50 ; k+=5) 共 36 種，迴圈執行了 726 次

問題：將50元硬幣換成等值的1元、5元、10元硬幣的方法共有多少種？ 方法-3： 當 i * 10 + j * 5 + k == 50 時，應立即跳出k的迴圈，因為再增加k值 也不會是解了。 if ( i * 10 + j * 5 + k == 50 ) { ans++; break; } 共 36 種，迴圈執行了 491 次

問題：將50元硬幣換成等值的1元、5元、10元硬幣的方法共有多少種？ 方法-4： 當 i 和 j 的值固定之後，k的值只有一種選擇，因此不必考慮 k 的變化情形 當 i = 0, j 可能為0, 1, 2, 3, ......, 10  ( 50 – i * 10 ) / 5 = 10 當 i = 1, j 可能為0, 1, 2, 3, ...., 8  ( 50 – i * 10 ) / 5 = 8 當 i = 2, j 可能為0, 1, 2, 3, ..., 6  ( 50 – i * 10 ) / 5 = 6 ... 當 i = 5, j 可能為0  ( 50 – i * 10 ) / 5 = 0

問題：將50元硬幣換成等值的1元、5元、10元硬幣的方法共有多少種？ 方法-4： for( i = 0 ; i <= 5 ; i++) for( j = 0 ; j <= (50-i*10)/5 ; j++) { loop++; ans++; } printf(“共 %d 種，迴圈執行了 %d 次\n”, ans , loop ); 共 36 種，迴圈執行了 36 次

問題：將50元硬幣換成等值的1元、5元、10元硬幣的方法共有多少種？ 方法-5： 由上個方法得知，當 i 的質固定後，j 的變化情形只有 (50-i*10)/5種， 0 ~ (50-i*10)/5 中，每個值都是一種換硬幣的組合。 因此只需要對 i 作迴圈，就能加總出答案。 for ( i = 0 ; i <= 5; i++ ) { loop++; number += (50 – i * 10 ) / 5 + 1 ; } 共 36 種，迴圈執行了 6 次

問題：將50元硬幣換成等值的1元、5元、10元硬幣的方法共有多少種？ 方法-6： 我們所計算的值，其實是一個等差級數，即 11 + 9 + 7 + 5 + 3 + 1 = 6 * ( 11+1) / 2 = 36 ------------------------------------------------------ int number = 0, a, b, n = 50 ; a = n / 5 + 1 ; if( a % 2 == 0 ) b = 2 ; else b = 1 ; number = ( a + b ) * ( ( a – b ) / 2 + 1 ) / 2 ; printf(“共 %d 種\n”, number ) ; 共 36 種

程式執行時間的差異 問題：將50元硬幣換成等值的1元、5元、10元硬幣的方法共有多少種？ 方法 運算執行次數 1 3366 2 726 3 491 4 36 5 6

用空間來換取時間 問題：若給你一個整數𝑝 ( 1<𝑝<1000000 )，請判斷這個數是否為質數？ 方法：從2到 𝑝 ，每個數字都檢查能不能整除 𝑝，如果都不行， 那 𝑝 就是質數。 int i , p , prime=1; for ( i = 2; i <= sqrt(p) ; i++ ) if( p % i == 0 ) prime=0; 𝑝 是質數 1 prime 𝑝 不是質數 迴圈執行： 𝑝 −1 次

問題：在陣列p中存有 10 個整數( 1<𝑝[𝑖]<1000000 )，請判斷這個陣 列中，哪些數字為質數？ 方法：對於每個數字𝑝[𝑖]，一樣從2 ~ 𝑝 ，每個數字都檢查能不能整 除 𝑝[i]，如果都不行，那 𝑝[𝑖] 就是質數。 int p[10], i , j , prime; for ( i = 0 ; i <10 ; i++ ) { prime=1; for ( j = 2; j <= sqrt( p[i] ) ; j++ ) if( p % j == 0 ) prime=0; } 𝑝[𝑖] 是質數 1 prime 𝑝[𝑖] 不是質數 迴圈執行：10∗( 𝑝 −1) 次

假設今天會給你100,000個數，每個數的值差不多10,000 用剛剛的方法，迴圈執行的次數約為 100000 * 100 = 10000000次。 這麼多次的運算，等程式執行完天都黑了。 如果可以建出一個清單，列出數字範圍內中哪些數是質數， 那麼每次讀取一個數只需要核對這個清單，就能知道是不是質數了！

質數表 對於一個數字 N ， 我們可以建出一張表來標示 1~N 中每個數字分別為 質數或合數。 建立的方法： 篩法。

質數表建立：篩法 窮舉所有的合數，並標記這些合數， 最後沒被標記到的便是質數！ example : 1.刪掉2的倍數 : 4, 6, 8, 10, ...... 直到超過N 2.找到下一個還沒被刪的數，是3 刪掉3的倍數：6,9,12,..... 直到超過N 3.找到下一個還沒被刪的數，是5  刪掉5的倍數：10,15,20,...直到超過N .... n.直到N之前都檢查過為止

範例 假設我們要建一個 N = 20 的質數表 (bool prime[21];) index value 1 false 2 true 3 4 5 6 7 8 9 10 index value 11 true 12 13 14 15 16 17 18 19 20

範例 從2開始，標記2的倍數直到20為止。 index value 1 false 2 true 3 4 5 6 7 8 9 10 11 true 12 13 14 15 16 17 18 19 20

範例 從2開始，標記2的倍數直到20為止。 index value 1 false 2 true 3 4 5 6 7 8 9 10 11 true 12 false 13 14 15 16 17 18 19 20

範例 找到下個沒被找過的數字：3，於是標記3的倍數 index value 1 false 2 true 3 4 5 6 7 8 9 10 11 true 12 false 13 14 15 16 17 18 19 20

範例 找到下個沒被找過的數字，是3，於是標記3的倍數 index value 1 false 2 true 3 4 5 6 7 8 9 10 11 true 12 false 13 14 15 16 17 18 19 20

範例 找到下個沒被找過的數字，是5，於是標記5的倍數 index value 1 false 2 true 3 4 5 6 7 8 9 10 11 true 12 false 13 14 15 16 17 18 19 20

範例 找到下個沒被找過的數字，是5，於是標記5的倍數 index value 1 false 2 true 3 4 5 6 7 8 9 10 11 true 12 false 13 14 15 16 17 18 19 20

範例 依此類推，直到找到20為止，就建出一個質數表了！ index value 1 false 2 true 3 4 5 6 7 8 9 10 index value 11 true 12 false 13 14 15 16 17 18 19 20

範例 如果我要知道13是不是質數，只需 要看質數表中第13個值為何： true 代表這個數是質數。 false 代表這個數是合數。 上述的查表動作，只需要 1 個運算 就能達成，而不用重新檢查每個數 字是否能整除13。 index value 1 false 2 true 3 4 5 6 7 8 9 10 index value 11 true 12 false 13 14 15 16 17 18 19 20

質數表建立：程式碼 bool prime[1000] ; void build_table( ) { for( int i = 0; i < 1000; i++ ) prime[ i ] = true; prime[ 0 ] = prime[ 1 ] = false; for(int i = 2; i < 1000; i++ ) if( prime[ i ] ) for( int j= i * 2; j < 1000; j = j + i ) prime[ j ] = false; } 初始化 刪除質數 i 的倍數 j = i 的所有倍數

質數表有比較好嗎 質數表的價值： 雖然一開始在建表的時候會花些時間，但後來在判斷是否為質數時， 就能節省大量的時間。 當你的測資很過分，都是很多而且很大的數字，此時查質數表遠比每個數 字都慢慢算還快許多！

題目演練 題目：UVA 543 題目敘述：「任何大於4的偶數，都可以寫成兩個質數相加。」 需要你寫一個程式來驗證上述的定理是否成立！ 輸入測資：不定數量的整數，每個整數範圍為6≤𝑛<1000000。 輸出答案：如果定理成立，便印出 n = a + b，其中a,b為質數，且b-a 是最大值。反之如果不成立，印出 Goldbach’s conjecture is wrong.

題目演練-UVA543

題目演練-UVA543 解法： 先建出大小為1,000,000質數表，再針對每個讀進來的整數n， 從3開始檢查是否有兩個質數a , b 可以達成n = a + b。 for ( i = 3 ; i < n ; i++ ) { if ( prime [ i ] && prime [ n – i ]) // true = 質數 找到答案囉  }

題目演練-UVA543 i index value 1 false 2 true 3 4 5 6 7 8 9 10 11 12 Example : n = 12 當 i = 3 確認 3 和 12 – 3 是否都是質數  12 – 3 = 9 不是質數 i

題目演練-UVA543 i index value 1 false 2 true 3 4 5 6 7 8 9 10 11 12 Example : n = 12 當 i = 4 確認 4 和 12 – 4 是否都是質數  4和12 – 4 = 8 都不是質數 i

題目演練-UVA543 i index value 1 false 2 true 3 4 5 6 7 8 9 10 11 12 Example : n = 12 當 i = 5 確認 5 和 12 – 5 是否都是質數  5和12 – 5 = 7 都是質數 !! 找到答案囉  print 12 = 5 + 7 i

UVA_543 部分程式碼 build_table( ); while( scanf(“%d”, &n ) && n ) { for( i = 3; i <= n / 2 ; i++ ) if( prime [ i ] && prime [ n – i ] ) printf(“%d = %d + %d\n”, n , i , n – i ); break; } if( i > n / 2 ) // i > n / 2 代表沒有找到解 printf(“Goldbach’s conjecture is wrong.\n”);

Q & A