NOIP实用算法 教程 系列的第 2 篇 （本系列共13篇）
NOIP实用算法 教程

1.模拟方法
a.用数学量和图形描述问题
b.模拟计算过程
c.模拟时的优化
d.高精度计算算法

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 |                                  1 |  42 21 | 2 ——整除
  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[])，从末位起相加，注意是否进位。

显然，减法作为加法的逆运算，也很容易实现。另一种聪明的办法是，对减数每一位取补码，在做加法即可。请读者自行实现高精度减法。
高精度乘法困难一些。我推荐的方法是，先考虑多位高精度数乘一位高精度数的过程。多位高精度数乘多位高精度数可以转化为多位高精度数乘另一高精度数每一位，再将结果相加的过程。下面给出多位高精度数乘一位高精度数的源代码：

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

习题
模拟方法的习题 ——感谢 深蓝评测系统 提供习题

附件：高精度计算算法C源文件（包括加、减、乘、输入、输出）
抱歉，只有对本站任何文章发表过评论才能阅读隐藏内容。

本文由 最后的叶子 创作，转载或引用前请联系我们。

相关文章：

  1. NOIP实用算法 6.常用数学方法
  2. NOIP实用算法 7.分治
  3. 寻找满分单词
  4. NOIP实用算法 3.搜索
  5. NOIP实用算法 2.排序算法与算法时空复杂度

2009年7月5日 星期天

30条评论

留下您的足迹

2009 f(Program,Poet)=Programet.
Powered by Wordpress. Theme by Pharmacy Drugs and LastLeaf.