人工智能機器人課程：實用算法之模擬方法

1.模擬方法

a.用數學量和圖形描述問題

計算機處理的是數學量。若要用計算機解決實際問題，需要把實際問題抽象為數學量，或者數字。比如，

記事本把文字按 ASCII 碼錶轉換為數字儲存起 來，極品飛車把賽車的性能表示為數字，來權衡賽車的

好壞。一個漂亮的算法，需要用數學量表示出來。

任務：現有兩個軟件工程的製作任務，你的團隊可以接手其中任意一個。現要在兩個中選擇一個，需要

考慮製作成本，製作成功的可能性，可獲得經濟收益的 多少，對你的團隊知名度的影響等等因素。你

如何量化地分析和解決這個問題？

提示：需要把每一項都轉化為數值，必要時加入權值、計算期望。如果只考慮以上四個因素，可以得到

以下數學式

綜合收益=製作成功的概率*[(可獲得經濟收益-製作成本)*經濟效益的權值+團隊知名度的影響*社會

效益的權值]

其中概率和兩個權值是需要估計的值。

有時，我們需要用更直觀的圖形來描述實際問題。

圖論就是一個絕佳的方法。圖是一種表示離散量間關係的形式，它也是一種思想，常被用於建模。同時，

前人也為我們提供了很多現成的圖論算法，能夠解決很多常 見問題，這些將在之後被提到。

矩陣也是一種常見的方法。有時矩陣被表示成三角形的形式，比如“楊輝三角”。矩陣常常和數學有關，

在計算機計算時常常利用矩陣的遞推式。這也將在後面被提 到。

b.模擬計算過程

模擬方法是最常見、最直接的算法構建方法。

任務：編程實現歐幾里得算法（輾轉相除法，求兩個數的最大公約數 gcd(a,b)）

提示：

歐幾里得算法原理：gcd(a,b)=gcd(b,a mod b)

歐幾里得算法的圖形描述——

| 168 63 |

| 168 63 | 2

|

42

|

1.寫下兩個數 2.將兩數相除，餘數寫在較大的數下面

| 168 63 | 2

| 168 63 | 2

1 | 42 21 | 2 ——整除

1 | 42 21 |

3.將每列最下面的數相除，餘數寫在被除數下面 4.重複步驟3直至整除，此時最後寫下的餘數即為

開始時兩數的最大公約數

這是一個簡單的模擬算法，實際過程中，量間的關係往往比這複雜得多，因而，模擬算法可以是很複雜

的。

有些模擬算法還涉及到圖形和其他複雜的數據結構，這需要我們熟練地運用語言，巧妙地把其他關係轉

化為數學量間關係。

c.模擬時的優化

如果處理不當，模擬方法寫出的程序會非常長。這要求我們在模擬是將相似的步驟合為一體，適時利用

函數簡化程序。

以上面的歐幾里得算法為例：

/*實現時，若將左邊一列數最下面的記為 L[1000]、右邊一列數記為 R[1000]，顯然是不明智的，因

為只有每列最後一個數會在以後的計算中用到*/

/*實現方法一：及每一列最後一個數分別為 L、R。輸入即可是 L、R，返回 gcd(L,R)*/

int Euclid_1(int L,int R)

{

for(;;)

{

L=L%R;

if(L==0)return R;

R=R%L;

if(R==0)return L;

}

}

/*我們發現有兩步是相似的。因而我們可以把它簡化為實現方法二*/

int Euclid_2(int L,int R)

{

int t;

for(;;)

{

t=R; R=L%R; L=t;

if(R==0)return L;

}

}

/*甚至我們可以寫成遞歸形式。以下是實現方法三*/

int Euclid_3(int L,int R)

{

if(L%R==0)return R;

else return Euclid_3(R,L%R);

}

這個實例主要體現模擬算法的簡化過程。雖然在這樣小的程序段中，這樣的簡化作用不大，但遇到複雜

的模擬問題，這種利用相似性的簡化便非常有用了。應 當重視這樣的代碼優化。

d.高精度計算算法

競賽中經常會用上一些很大的數，超出長整型的數值範圍。這時我們需要使用高精度計算算法。這種算

法可以把數值範圍增加到我們想要的程度。

高精度函數往往包括加、減、乘、輸入、輸出五種。

實現高精度計算時，常常使用模擬算法——模擬小學豎式運算。我們把一個高精度數表示為一個數組 H[]，

數組中的某一個數相當於高精度數的某一位。

要注意的是，輸出時往往要求以十進制形式輸出。因而，高精度數每一位都應便於直接輸出。這樣，每

一位上的最大數都應是10^n-1。簡單地說，若把 H[] 定為 unsigned 型，高精度數每一位上最大數

最好為9999。這樣既能儘量利用儲存空間，又便於輸出。

另外，高精度數有時會用到負數。在補碼的體系中，仍然可以按正數的方法處理負數，但是要特別注意

輸出時的問題，和對溢出的防止。

任務：實現高精度運算加法

提示：設計函數 unsigned *HAdd(unsigned N1[],unsigned N2[],unsigned Ans[])，從末

位起相加，注意是否進位。

顯然，減法作為加法的逆運算，也很容易實現。另一種聰明的辦法是，對減數每一位取補碼，在做加法

4

即可。請讀者自行實現高精度減法。

高精度乘法困難一些。我推薦的方法是，先考慮多位高精度數乘一位高精度數的過程。多位高精度數乘

多位高精度數可以轉化為多位高精度數乘另一高精度數每一 位，再將結果相加的過程。下面給出多位

高精度數乘一位高精度數的源代碼：

#define H_Bit 256 /*定義常數：高精度數位數*/

unsigned *HTimesInt(unsigned N1[],int N2,unsigned Ans[]) /*N1[]為多位高精度數，

N2為高精度數的一位，Ans[]為另一高精度數，用於儲存結果*/

/*這裡允許 N1與 Ans 相同*/

{

unsigned i,up=0;

unsigned long temp;

for(i=H_Bit-1;i<=H_Bit;i--)

{

temp=N1[i]*N2+up;

up=temp/10000;

Ans[i]=(unsigned)(temp%10000);

}

return Ans;

/*函數返回作為答案的高精度數首地址，這樣更便於高精度運算函數的使用，例如連乘可以寫成

HTimesInt(HTimesInt(N1[],N2,Ans[]),N3,Ans[])*/

}

高精度數的輸入輸出需要專門的函數。針對不同語言的不同特點，可以比較容易地寫出這兩個函數。但

要注意輸出非首位數位上的“0”。

"

人工智能機器人課程：實用算法之模擬方法

1.模擬方法

a.用數學量和圖形描述問題

計算機處理的是數學量。若要用計算機解決實際問題，需要把實際問題抽象為數學量，或者數字。比如，

記事本把文字按 ASCII 碼錶轉換為數字儲存起 來，極品飛車把賽車的性能表示為數字，來權衡賽車的

好壞。一個漂亮的算法，需要用數學量表示出來。

任務：現有兩個軟件工程的製作任務，你的團隊可以接手其中任意一個。現要在兩個中選擇一個，需要

考慮製作成本，製作成功的可能性，可獲得經濟收益的 多少，對你的團隊知名度的影響等等因素。你

如何量化地分析和解決這個問題？

提示：需要把每一項都轉化為數值，必要時加入權值、計算期望。如果只考慮以上四個因素，可以得到

以下數學式

綜合收益=製作成功的概率*[(可獲得經濟收益-製作成本)*經濟效益的權值+團隊知名度的影響*社會

效益的權值]

其中概率和兩個權值是需要估計的值。

有時，我們需要用更直觀的圖形來描述實際問題。

圖論就是一個絕佳的方法。圖是一種表示離散量間關係的形式，它也是一種思想，常被用於建模。同時，

前人也為我們提供了很多現成的圖論算法，能夠解決很多常 見問題，這些將在之後被提到。

矩陣也是一種常見的方法。有時矩陣被表示成三角形的形式，比如“楊輝三角”。矩陣常常和數學有關，

在計算機計算時常常利用矩陣的遞推式。這也將在後面被提 到。

b.模擬計算過程

模擬方法是最常見、最直接的算法構建方法。

任務：編程實現歐幾里得算法（輾轉相除法，求兩個數的最大公約數 gcd(a,b)）

提示：

歐幾里得算法原理：gcd(a,b)=gcd(b,a mod b)

歐幾里得算法的圖形描述——

| 168 63 |

| 168 63 | 2

|

42

|

1.寫下兩個數 2.將兩數相除，餘數寫在較大的數下面

| 168 63 | 2

| 168 63 | 2

1 | 42 21 | 2 ——整除

1 | 42 21 |

3.將每列最下面的數相除，餘數寫在被除數下面 4.重複步驟3直至整除，此時最後寫下的餘數即為

開始時兩數的最大公約數

這是一個簡單的模擬算法，實際過程中，量間的關係往往比這複雜得多，因而，模擬算法可以是很複雜

的。

有些模擬算法還涉及到圖形和其他複雜的數據結構，這需要我們熟練地運用語言，巧妙地把其他關係轉

化為數學量間關係。

c.模擬時的優化

如果處理不當，模擬方法寫出的程序會非常長。這要求我們在模擬是將相似的步驟合為一體，適時利用

函數簡化程序。

以上面的歐幾里得算法為例：

/*實現時，若將左邊一列數最下面的記為 L[1000]、右邊一列數記為 R[1000]，顯然是不明智的，因

為只有每列最後一個數會在以後的計算中用到*/

/*實現方法一：及每一列最後一個數分別為 L、R。輸入即可是 L、R，返回 gcd(L,R)*/

int Euclid_1(int L,int R)

{

for(;;)

{

L=L%R;

if(L==0)return R;

R=R%L;

if(R==0)return L;

}

}

/*我們發現有兩步是相似的。因而我們可以把它簡化為實現方法二*/

int Euclid_2(int L,int R)

{

int t;

for(;;)

{

t=R; R=L%R; L=t;

if(R==0)return L;

}

}

/*甚至我們可以寫成遞歸形式。以下是實現方法三*/

int Euclid_3(int L,int R)

{

if(L%R==0)return R;

else return Euclid_3(R,L%R);

}

這個實例主要體現模擬算法的簡化過程。雖然在這樣小的程序段中，這樣的簡化作用不大，但遇到複雜

的模擬問題，這種利用相似性的簡化便非常有用了。應 當重視這樣的代碼優化。

d.高精度計算算法

競賽中經常會用上一些很大的數，超出長整型的數值範圍。這時我們需要使用高精度計算算法。這種算

法可以把數值範圍增加到我們想要的程度。

高精度函數往往包括加、減、乘、輸入、輸出五種。

實現高精度計算時，常常使用模擬算法——模擬小學豎式運算。我們把一個高精度數表示為一個數組 H[]，

數組中的某一個數相當於高精度數的某一位。

要注意的是，輸出時往往要求以十進制形式輸出。因而，高精度數每一位都應便於直接輸出。這樣，每

一位上的最大數都應是10^n-1。簡單地說，若把 H[] 定為 unsigned 型，高精度數每一位上最大數

最好為9999。這樣既能儘量利用儲存空間，又便於輸出。

另外，高精度數有時會用到負數。在補碼的體系中，仍然可以按正數的方法處理負數，但是要特別注意

輸出時的問題，和對溢出的防止。

任務：實現高精度運算加法

提示：設計函數 unsigned *HAdd(unsigned N1[],unsigned N2[],unsigned Ans[])，從末

位起相加，注意是否進位。

顯然，減法作為加法的逆運算，也很容易實現。另一種聰明的辦法是，對減數每一位取補碼，在做加法

4

即可。請讀者自行實現高精度減法。

高精度乘法困難一些。我推薦的方法是，先考慮多位高精度數乘一位高精度數的過程。多位高精度數乘

多位高精度數可以轉化為多位高精度數乘另一高精度數每一 位，再將結果相加的過程。下面給出多位

高精度數乘一位高精度數的源代碼：

#define H_Bit 256 /*定義常數：高精度數位數*/

unsigned *HTimesInt(unsigned N1[],int N2,unsigned Ans[]) /*N1[]為多位高精度數，

N2為高精度數的一位，Ans[]為另一高精度數，用於儲存結果*/

/*這裡允許 N1與 Ans 相同*/

{

unsigned i,up=0;

unsigned long temp;

for(i=H_Bit-1;i<=H_Bit;i--)

{

temp=N1[i]*N2+up;

up=temp/10000;

Ans[i]=(unsigned)(temp%10000);

}

return Ans;

/*函數返回作為答案的高精度數首地址，這樣更便於高精度運算函數的使用，例如連乘可以寫成

HTimesInt(HTimesInt(N1[],N2,Ans[]),N3,Ans[])*/

}

高精度數的輸入輸出需要專門的函數。針對不同語言的不同特點，可以比較容易地寫出這兩個函數。但

要注意輸出非首位數位上的“0”。

"