【正文】 3】 變量計數(shù)之二 ? (1) x=1； ? (2) for(i=1； i=n； i++) ? (3) for(j=1； j=i； j++) ? (4) for(k=1； k=j； k++) ? (5) x++； ? 該算法段中頻度最大的語句是 (5)，從內(nèi)層循環(huán)向外層分析語句 (5)的執(zhí)行次數(shù)： ? 復(fù)雜度： O(n3) 2020/9/16 35 算法的描述方法 ⑴ 自然語言 優(yōu)點：容易理解 缺點：冗長、二義性 使用方法：粗線條描述算法思想 注意事項：避免寫成自然段 2020/9/16 36 ① 輸入 m 和 n； ② 求 m除以 n的余數(shù) r； ③ 若 r等于 0， 則 n為最大公約數(shù) ， 算法結(jié)束； 否則執(zhí)行第 ④ 步； ④ 將 n的值放在 m中 ， 將 r的值放在 n中； ⑤ 重新執(zhí)行第 ② 步 。 + + + = + + + = + + = + = L 2020/9/16 45 通用分治遞推式 大小為 n的原問題分成若干個大小為 n/b的子問題，其中 a個子問題需要求解，而 k是合并各個子問題的解需要的工作量。 2020/9/16 51 【 輸出 】 ? 對每一個測試數(shù)據(jù)只會有一行輸出。Z39。它的函數(shù)聲明形式（函數(shù)原型）如下： istreamamp。 2020/9/16 61 OJ評測 原理 Input 1 5 2 6 10 20 111 111 321 123 Output 6 8 30 222 444 2020/9/16 62 Rightmost Digit（ hdu1061） ? Problem Description ? Given a positive integer N, you should output the most right digit of N^N. ? Input ? The input contains several test cases. The first line of the input is a single integer T which is the number of test cases. T test cases follow. Each test case contains a single positive integer N(1=N=1,000,000,000). 2020/9/16 63 ? Output ? For each test case, you should output the rightmost digit of N^N. ? Sample Input ? 2 ? 3 ? 4 ? Sample Output ? 7 ? 6 2020/9/16 64 ? Hint ? In the first case, 3 * 3 * 3 = 27, so the rightmost digit is 7. In the second case, 4 * 4 * 4 * 4 = 256, so the rightmost digit is 6. 2020/9/16 65 直接做 int i,n,tmp,sum。n)。 ? 如果通過求 nn的最后結(jié)果再求最高數(shù)位的數(shù)字，方法簡單，但是存在問題，就是 n較大時候， nn太大而無法用程序存儲，需要設(shè)計大數(shù)的存儲方案，且?guī)砹擞嬎氵^程中的難度而且消耗大量內(nèi)存空間和時間。 ? } ? return 0。 ? 頭文件沒啥變化，就是 2020/9/16 87 qsort 方法 ? 格式： ? qsort ( 數(shù)組名 ，元素個數(shù)，元素占用的空間 (sizeof)，比較函數(shù) ) ? 說明：要寫比較函數(shù) ? 頭文件：在 2020/9/16 88 比較函數(shù)的寫法 ? int pare(const void *a,const void *b) { return *(int*)b*(int*)a。amp。 ? if (data[i]==1amp。i++) ? { ? data[i]=(a*data[i1]+b*data[i2])%7。i++) ? { ? data[i]=(a*data[i1]+b*data[i2])%7。 降序： sort(begin,end,greaterdatatype()). 2020/9/16 86 ? 升序： ? Sort(a,a+20,lessint())。 ? x = (int)pow(10,x)。 ? printf(%ld\n,(int)sum+1)。num)。\n39。 ? 而 getchar函數(shù)每次只接受 一個 字符，經(jīng)常c=getchar()這樣來使用。amp。 3. 結(jié)束行：單獨的一行 “ END” 。 ?關(guān)鍵：根據(jù)遞歸過程建立遞推關(guān)系式 ， 然后求解這個遞推關(guān)系式 。 ? (1) x=0； =0； ? (2) for(k1； =n； ++) ? (3) x++； ? (4) for(i=1； =n； ++) ? (5) for(j=1； j=n； ++) ? (6) y++； ? 該算法段的時間復(fù)雜度為 T(n)=Ο(n2)。 例如： for(i=1。 2020/9/16 25 和算法執(zhí)行時間相關(guān)的因素 ： 1）問題中數(shù)據(jù)存儲的數(shù)據(jù)結(jié)構(gòu) 2）算法采用的數(shù)學(xué)模型 3）算法設(shè)計的策略 4）問題的規(guī)模 5）實現(xiàn)算法的程序設(shè)計語言 6）編譯算法產(chǎn)生的機器代碼的質(zhì)量 7）計算機執(zhí)行指令的速度 2020/9/16 26 算法效率的衡量方法 ? 通常有兩種衡量算法效率的方法 : ? 1）事后統(tǒng)計法（有缺點，較少使用） ? 2）事前分析估算法 ? 算法的時間效率是問題規(guī)模的函數(shù)。j=n。 歐幾里德算法 2020/9/16 37 ⑵ 流程圖 優(yōu)點：流程直觀 缺點：缺少嚴(yán)密性、靈活性 使用方法：描述簡單算法 注意事項：注意抽象層次 2020/9/16 38 N 開始 輸入 m和 n r=m % n r=0 m=n； n=r 輸出 n 結(jié)束 Y 歐幾里德算法 2020/9/16 39 ⑶ 程序設(shè)計語言 優(yōu)點：能由計算機執(zhí)行 缺點：抽象性差，對語言要求高 使用方法：算法需要驗證 注意事項：將算法寫成子函數(shù) 2020/9/16 40 include int CommonFactor(int m, int n) { int r=m % n。 ? ? ? + = = 1 ) ( 1 ) ( n b n aT n c n T k ? ? ? ? ? = = k k k b