人工智能机器人课程：实用算法之模拟方法

 

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”。