1、J I A N G S U U N I V E R S I T Y算法設計與分析課程設計設計分析測試報告 題目： 求兩個數的最大公因數專業班級： J軟件工程1 姓 名： 高陽 學 號： 4121169020 指導教師：茍建平 2014年 12月程序算法設計說明書一、 前言1. 問題描述最大公因數。編寫一個完整的程序，計算任意兩個整數a, b 的最大公因數，其中0a, b10100。（要求：禁止網上下載大數類實現；10 分鐘內輸出結果）2. 程序編制環境相關說明系統：WINDOWS 8.1編制環境：visual studio 2013二、 程序主要算法設計分析說明算法設計思路：用取模來加速計算，

2、但大數不能用數值類型來存儲，得用字符串或數組來運算，我下面是用字符串來實現的。用字符串來進行計算，從低位到高位計算。當數很大時，因為輾轉相除法是用減法來做的，數太大，所需時間過長，不滿足10分鐘內輸出結果，所以算法需要加速。所以假設更大的那個數的長度是len1，更小的是len2，取模，關鍵算法就是把小的數擴大10*（len1-len2-1）倍，相減之后相當于一下子減了小數10*（len1-len2-1）次。三、 程序模塊說明1. 總體設計說明程序采用自己定義的a來存取第一個輸入的數。定義一個b來記錄第二個輸入的數。11為a長度。12為b長度比較11和12。lena存放a的的數長度。lenb存放

3、b的數的長度。用ca一一存放a的的字符。用經過比較處理的b作為結果輸出。2.模塊說明：采用3個函數，Compare函數，來比較a，b里存放數的大小，長度來確定a和b的順序（字符多的放a）。Subtract函數來實現相減的功能。Main函數里實現輸入和輸出，以及比較。時間復雜度為O（n）。4、 總結（含主函數設計說明）這次課程設計的題目有點復雜，一開始看到這個題目時，還不知道要怎么下手解決。后來在網上搜索了一下求最大公因數問題及算法。發現將數轉換為字符來算就簡單了。算法解決了，接下來具體用什么數據結構，用數組最簡單。確定兩個數組，程序就基本定下來了，算法解決了，接下來具體用什么數據結構實現也是個

4、問題。最后還是覺得直接用數組最簡潔。確定了用char數組，以及比較的方法。為實現程序循環，開始就用了while，后由用戶自己輸入數字。總結這次課程設計，雖然程序的實現并不難，也不復雜。但是實現程序的算法卻難倒了我。這也讓我深刻地體會到了算法的力量。在以后的學習中，我一定會注意自己的薄弱環節，好好補充知識。五、 時間復雜度：O（n）程序及算法測試報告一、 前言1. 測試目的及采用的主要測試方法目的：測試該程序能否成功求出兩數的最大公因數，以及速率。測試方法：用不同的數據測試，判斷是否有誤。代碼：using System;using System.Collections.Generic;using

5、 System.Linq;using System.Text;namespace 大數最大公因數 class Program static void Main(string args) string a, b; while (true)/控制程序循環 Console.WriteLine("Please input 0 to exit!");/開關 Console.WriteLine("輸入第一個數: "); a = Console.ReadLine();/a記錄第一個數 if (a = "0") break; Console.Writ

6、eLine("輸入第二個數： "); b = Console.ReadLine();/b記錄第二個數 Compare(ref a, ref b);/比較ab是否一樣 while (a != "0") Compare(ref a, ref b); string bb = b; int l1 = a.Length, l2 = b.Length;/記錄a，b的長度 if (l1 - l2 > 1)/若a大于b for (int i = 0; i < l1 - l2 - 1; i+) bb += "0" while (a.Leng

7、th > bb.Length) Subtract(ref a, ref bb); Subtract(ref a, ref b); Console.WriteLine("The greatest common divisorb is:n0", b); Console.Read(); static void Compare(ref string a, ref string b) int lena = a.Length;/a長度 int lenb = b.Length;/b長度 if (lena > lenb) return; else if (lena < l

8、enb) string temp = a; a = b; b = temp; return; else int i = 0, j = 0; while (true) if (ai > bi) return; else if (ai < bi) string temp = a; a = b; b = temp; return; else i+; j+; if (i = a.Length) return; static void Subtract(ref string a, ref string b) S Compare(ref a, ref b); char ca=a.ToCharA

9、rray();/把輸入的a一一放入char數組里 char cc=new chara.Length;/定義一個長度為a長度的cc數組 int i = a.Length - 1, j = b.Length - 1; while (j >= 0) if (cai >= bj) cci = Convert.ToChar(cai - bj + 48);/轉換長度 else cci = Convert.ToChar(cai + 10 - bj + 48); cai - 1 = Convert.ToChar(cai - 1 - 1); i-; j-; while (i >= 0)/i為長

10、度 if (!(cai >= '0' && cai <= '9') cci = Convert.ToChar(cai + 10); cai - 1 = Convert.ToChar(cai - 1 - 1); else cci = cai; i-; i = 0; while (i<cc.Length) if (cci = '0') i+; else break; if (i = cc.Length) a = "0" else a = new string(cc, i, cc.Length - i); 2. 測試環境說明系統：WINDOW