人工智能機器人課程:實用算法之模擬方法
人工智能機器人課程:實用算法之模擬方法
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.模擬時的優化
如果處理不當,模擬方法寫出的程序會非常長。這要求我們在模擬是將相似的步驟合為一體,適時利用
函數簡化程序。
以上面的歐幾里得算法為例:
人工智能機器人課程:實用算法之模擬方法
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”。