有人抱怨：算法太枯燥、乏味了，看到公式就头晕，无法学下去了。你肯定选择了一条充满荆棘的路。选对方法，你会发现这里是一条充满鸟语花香和欢声笑语的幽径，在这里，你可以和高德纳聊聊，同爱因斯坦喝杯咖啡，与歌德巴赫和角谷谈谈想法，Dijkstra也不错。与世界顶级的大师进行灵魂之交，不问结果，这一过程已足够美妙！

如果这本书能让多一个人爱上算法，这就足够了！

趣味故事1-3：马克思手稿中的数学题

马克思手稿中有一道趣味数学问题：有30个人，其中有男人、女人和小孩，这些人在一家饭馆吃饭花了50先令；每个男人花3先令，每个女人花2先令，每个小孩花1先令；问男人、女人和小孩各有几人？

（1）问题分析

设 x 、 y 、 z 分别代表男人、女人和小孩。按题目的要求，可得到下面的方程：

x + y + z =30　①

3 x +2 y + z =50 ②

两式相减，②-①得：

2 x + y =20　③

从式③可以看出，因为 x 、 y 为正整数， x 最大只能取9，所以 x 变化范围是1～9。那么我们可以让 x 从1到9变化，再找满足①②两个条件 y 、 z 值，找到后输入即可，答案可能不止一个。

（2）算法设计

按照上面的分析进行算法设计，见算法1-11。

//算法1-11
#include<iostream> 
int main() 
{ 
  int x,y,z,count=0; //记录可行解的个数
  cout<<" Men，Women，Children"<<endl; 
  cout<<"........................................"<<endl; 
  for(x=1;x<=9;x++) 
  { 
    y=20-2*x;  //固定x值然后根据式③求得y值 
    z=30-x-y;  //由式①求得z值 
    if(3*x+2*y+z==50)  //判断当前得到的一组解是否满足式②
      cout<<++count<<"  "<<x<<y<<z<<endl; //打印出第几个解和解值x，y，z
    } 
}

（3）算法分析

算法完全按照题中方程设计，因此正确性毋庸置疑。那么算法复杂度怎样呢？从算法1-11中可以看出，对算法时间复杂度贡献最大的语句是for(x=1;x<=9;x++)，该语句的执行次数是9，for循环中3条语句的执行次数也为9，其他语句执行次数为1，for语句一共执行36次基本运算，时间复杂度为 О (1)。没有使用辅助空间，空间复杂度也为 О (1)。

（4）问题的进一步讨论

为什么让 x 变化来确定 y 、 z 值？让 y 变化来确定 x 、 z 值会怎样呢？让 z 变化来确定 x 、 y 值行不行？有没有更好的算法降低时间复杂度？

趣味故事1-4：爱因斯坦的阶梯

爱因斯坦家里有一条长阶梯，若每步跨2阶，则最后剩1阶；若每步跨3阶，则最后剩2阶；若每步跨5阶，则最后剩4阶；若每步跨6阶，则最后剩5阶。只有每次跨7阶，最后才正好1阶不剩。请问这条阶梯共有多少阶？

（1）问题分析

根据题意，阶梯数 n 满足下面一组同余式：

n ≡1(mod2)

n ≡2(mod3)

n ≡4(mod5)

n ≡5(mod6)

n ≡0(mod7)

注意： 两个整数 a 、 b ，若它们除以整数 m 所得的余数相等，则称 a 、 b 对于模 m 同余，记作 a ≡ b (mod m )，读作 a 同余于 b 模 m ，或读作 a 与 b 关于模 m 同余。那么只需要判断一个整数值是否满足这5个同余式即可。

（2）算法设计

按照上面的分析进行算法设计，见算法1-12。

//算法1-12
#include<iostream> 
int main() 
{ 
  int n=1; //n为所设的阶梯数 
  while(!((n%2==1)&&(n%3==2)&&(n%5==4)&&(n%6==5)&&(n%7==0))) 
      n++;      //判别是否满足一组同余式
  cout<<"Count the stairs= "<<n<<endl;  //输出阶梯数
}

（3）算法分析

算法的运行结果：

Count the stairs =119

因为 n 从1开始，找到第一个满足条件的数就停止，所以算法1-12中的while语句运行了119次。有的算法从算法本身无法看出算法的运行次数，例如算法1-12，我们很难知道while语句执行了多少次，因为它是满足条件时停止，那么多少次才能满足条件呢？每个问题具体的次数是不同的，所以不能看到程序中有 n ，就简单地说它的时间复杂度为 n 。

我们从1开始一个一个找结果的办法是不是太麻烦了？

（4）算法改进

因为从上面的5个同余式来看，这个数一定是7的倍数 n ≡0(mod 7)，除以6余5，除以5余4，除以3余2，除以2余1，我们为什么不从7的倍数开始判断呢？算法改进见算法1-13。

//算法1-13
#include<iostream> 
int main() 
{ 
  int n=7; //n为所设的阶梯数 
  while(!((n%2==1)&&(n%3==2)&&(n%5==4)&&(n%6==5)&&(n%7==0))) 
  n=n+7;      //判别是否满足一组同余式
  cout<<"Count the stairs="<<n<<endl;  //输出阶梯数
}

算法的运行结果：

Count the stairs =119

算法1-13中的while语句执行了119/7=17次，可见运行次数减少了不少呢！

（5）问题的进一步讨论

此题算法还可考虑求1、2、4、5的最小公倍数 n ，然后令 t = n -1，判断 t ≡0(mod 7)是否成立，若不成立则 t = t + n ，再进行判别，直到选出满足条件的 t 为止。

1、2、4、5的最小公倍数 n =20。

t = n -1=19， t ≡0(mod 7)不成立；

t = t+n =39， t ≡0(mod 7)不成立；

t = t+n =59， t ≡0(mod 7)不成立；

t = t+n =79， t ≡0(mod 7)不成立；

t = t+n =99， t ≡0(mod 7)不成立；

t = t+n =119， t ≡0(mod 7)成立。

我们可以看到这一算法判断6次即成功，但是，求多个数的最小公倍数需要多少时间复杂度，是不是比上面的算法更优呢？结果如何请大家动手试一试。

趣味故事1-5：哥德巴赫猜想

哥德巴赫猜想：任一大于2的偶数，都可表示成两个素数之和。

验证：2000以内大于2的偶数都能够分解为两个素数之和。

（1）问题分析

为了验证哥德巴赫猜想对2000以内大于2的偶数都是成立的，要将整数分解为两部分（两个整数之和），然后判断分解出的两个整数是否均为素数。若是，则满足题意；否则重新进行分解和判断。素数测试的算法可采用试除法，即用2，3，4，…， 去除 n ，如果能被整除则为合数，不能被整除则为素数。

（2）算法设计

按照上面的分析进行算法设计，见算法1-14。

//算法1-14
#include<iostream>
#include<math.h> 
int prime(int n); //判断是否均为素数
int main() 
{ 
  int i,n; 
  for(i=4;i<=2000;i+=2) //对2000大于2的偶数分解判断，从4开始，每次增2
  {
    for(n=2;n<i;n++)  //将偶数i分解为两个整数，一个整数是n，一个是i-n
      if(prime(n))    //判断第一个整数是否均为素数 
         if(prime(i-n))   //判断第二个整数是否均为素数 
         { 
            cout<< i <<"=" << n <<"+"<<i-n<<endl;  //若均是素数则输出 
            break; 
         } 
     if(n==i) 
        cout<<"error "<<endl; 
  } 
} 
int prime(int i) //判断是否为素数 
{ 
  int j; 
  if(i<=1) return 0; 
  if(i==2) return 1; 
  for(j=2;j<=(int)(sqrt((double)i);j++) 
    if(!(i%j)) return 0; 
  return 1;  
}

（3）算法分析

要验证哥德巴赫猜想对2000以内大于2的偶数都是成立的，我们首先要看看这个范围的偶数有多少个。1～2000中有1000个偶数，1000个奇数，那么大于2的偶数有999个，即 i =4，6，8，…，2000。再看偶数分解和素数判断，这就要看最好情况和最坏情况了。最好的情况是一次分解，两次素数判断即可成功，最坏的情况要 i -2次分解（即 n =2，3，…， i -1的情况），每次分解分别执行2～sqrt( n )次、2～sqrt( i - n )次判断。

这个程序看似简单合理，但存在下面两个问题。

1）偶数分解存在重复。

• i =4：分解为（2，2），（3，1），从 n =2，3，…， i -1分解，每次得到一组数（ n ， i - n ）。
• i =6：分解为（2，4），（3，3），（4，2），（5，1）。
• i =8：分解为（2，6），（3，5），（4，4），（5，3），（6，2），（7，1）。

除了最后一项外，每组分解都在 i /2处对称分布。最后一组中有一个数为1，1既不是素数也不是合数，因此去掉最后一组，那么我们就可以从 n =2，3，…， i /2进行分解，省掉了一半的多余判断。

2）素数判断存在重复。

• i =4：分解为（2，2），（3，1），要判断2是否为素数，然后判断第二个2是否为素数。判断成功，返回。
• i =6：分解为（2，4），（3，3），（4，2），（5，1），要判断2是否为素数，然后判断4是否为素数，不是继续下一个分解。再判断3是否为素数，然后判断第二个3是否为素数。判断成功，返回。

每次判断素数都要调用prime函数，那么可以先判断分解有可能得到的数是否为素数，然后把结果存储下来，下次判断时只需要调用上次的结果，不需要再重新判断是否为素数。例如（2，2），第一次判断结果2是素数，那第二个2就不用判断，直接调用这个结果，后面所有的分解，只要遇到这个数就直接认定为这个结果。

（4）算法改进

先判断所有分解可能得到的数是否为素数，然后把结果存储下来，有以下两种方法。

1）用布尔型数组 flag[2..1998]记录分解可能得到的数（2～1998）所有数是不是素数，分解后的值作为下标，调用该数组即可。时间复杂度减少，但空间复杂度增加。

2）用数值型数组data[302]记录2～1998中所有的素数（302个）。

• 分解后的值，采用折半查找（素数数组为有序存储）的办法在素数数组中查找，找到就是素数，否则不是。
• 不分解，直接在素数数组中找两个素数之和是否为 i ，如果找到，验证成功。因为素数数组为有序存储，当两个数相加比 i 大时，不需要再判断后面的数。

（5）问题的进一步讨论

上面的方法可以写出3个算法，大家可以尝试写一写，然后分析时间复杂度、空间复杂度如何？哪个算法更优一些？是不是还可以做到更好？ 48wtYsyOkFQy/zek2l78MsjcUnlBnBqUlb+ErKhcb52vBgWrwnPx34uoRu6wf6qf