经典算法（1）

河内塔（又称汉诺塔）

河内之塔(Towers of Hanoi)是法国人M.Claus(Lucas)于1883年从泰国带至法国的，河内为越战时北越的首都，即现在的胡志明市；1883年法国数学家Edouard Lucas曾提及这个故事，据说创世纪时Benares有一座波罗教塔，是由三支钻石棒（Pag）所支撑，开始时神在第一根棒上放置64个由上至下依由小至大排列的金盘（Disc），并命令僧侣将所有的金盘从第一根石棒移至第三根石棒，且搬运过程中遵守大盘子在小盘子之下的原则，若每日仅搬一个盘子，则当盘子全数搬运完毕之时，此塔将毁损，而也就是世界末日来临之时。

如果柱子标为ABC，要由A搬至C，在只有一个盘子时，就将它直接搬至C，当有两个盘子，就将B当作辅助柱。有n个盘子时，先将前 n-1 个移动到B，然后将最后一个移动到C，再将A作为辅助盘，将 n-2 移动到A，然后把B上的最后一个移动到C······以此循环，具体代码如下：

#include <stdio.h>
void hanoi(int n ,char a, char b, char c)
{
    if(n == 1)
    {
        printf("move sheet %d from %c to %c\n",n,a,c);
    }
    else
    {
        hanoi(n-1,a,c,b);
        printf("move sheet %d from %c to %c\n",n,a,c);
        hanoi(n-1,b,a,c);
    }
    
}

int main()
{
    int i = 0;
    printf("请输入盘子数量：");
    scanf("%d",&i);

    hanoi(i,'A','B','C');

    return 0;
}
C

费式数列

Fibonacci为1200年代的欧洲数学家，在他的着作中曾经提到：「若有一只免子每个月生一只小免子，一个月后小免子也开始生产。起初只有一只免子，一个月后就有两只免子，二个月后有三只免子，三个月后有五只免子（小免子投入生产）……。注意新生的小免子需一个月成长期才会投入生产，类似的道理也可以用于植物的生长，这就是Fibonacci数列，一般习惯称之为费氏数列，例如以下： 1、1 、2、3、5、8、13、21、34、55、89……

根据规律可以得出，从第三个月开始(2),兔子的数目都为前两个月之和，算法如下：

#include <stdio.h>

int fibonacci(int n)
{
    int sum;
    if(n == 0 || n == 1)
    {
        sum = 1;
    }
    else
    {
        sum = fibonacci(n-1) + fibonacci(n-2);
    }
    return sum;
}

int main()
{
    int i = 0;
    printf("起初只有一只小兔子，请输入时间（月）：");
    scanf("%d",&i);
    int sum = fibonacci(i);
    printf("共有%d只兔子\n",sum);   
} 
C

杨辉三角

杨辉三角，是二项式系数在三角形中的一种几何排列。在欧洲，这个表叫做帕斯卡三角形。帕斯卡（1623—-1662）是在1654年发现这一规律的，比杨辉要迟393年，比贾宪迟600年。杨辉三角是中国古代数学的杰出研究成果之一，它把二项式系数图形化，把组合数内在的一些代数性质直观地从图形中体现出来，是一种离散型的数与形的结合。

三角形的前提是：每行端点与结尾的数为1。
可以根据以下性质来进行代码编写：

• 每个数字等于上一行的左右两个数字之和。可用此性质写出整个杨辉三角。即第n+1行的第i个数等于第n行的第i-1个数和第i个数之和，这也是组合数的性质之一。即 C(n+1,i)=C(n,i)+C(n,i-1)。

#include <stdio.h>
long combi(int r,int i)
{
    if(r == 1 || i == 1 || i == r)
    {
        return 1;
    }
    else
    {
        return combi((r-1),(i-1)) + combi((r-1),(i));
    }
    
} 

int main()
{
    int num = 0;
    int i;
    int j;
    int k;
    printf("请输入杨辉三角的层数：");
    scanf("%d",&num);

    for(i = 1; i <= num; i++)
    {
        for (k = 1; k <= (num-i)*2; k++)
        {
            printf(" ");
        }
        
        for (j = 1; j <= i; j++)
        {
            printf("%ld  ",combi(i,j));
        }
        printf("\n");
    }
}
C

三色棋

三色旗的问题最早由E.W.Dijkstra所提出，他所使用的用语为Dutch Nation Flag(Dijkstra为荷兰人)，而多数的作者则使用Three-Color Flag来称之。

假设有一条绳子，上面有红、白、蓝三种颜色的旗子，起初绳子上的旗子颜色并没有顺序，您希望将之分类，并排列为蓝、白、红的顺序，要如何移动次数才会最少，注意您只能在绳子上进行这个动作，而且一次只能调换两个旗子。

遇到蓝色就放到数组前面，遇到红色放到数组末尾，中间自然就全部是白色了，代码如下：

#include <stdio.h>
enum{
    READ =  0,
    WHITE,
    BLUE,
};

int main()
{
    int i = 0;
    int flags[] = {0,1,2,0,1,2,0,1,2,0,1,2,0,1,2,0,1,2,0,1,2,0,1,2,0,1,2,0,1,2};
    int lens = sizeof(flags)/sizeof(flags[0]);
    int begin = 0;
    int end = lens - 1;

    for (i = 1; i < lens; i++)
    {
        while (flags[i] != WHITE)
        {
            if(flags[i] == BLUE)
            {
                flags[i] = flags[begin];
                flags[begin] = BLUE;
                begin++;
            }
            if(flags[i] == READ)
            {
                flags[i] = flags[end];
                flags[end] = READ;
                end--;
            }
        }
        
        if(i == end-1)
        {
            break;
        }
    }

    for (i = 0; i < lens; i++)
    {
        printf("%d  ",flags[i]);
    }
    printf("\n");

    return 0;
}
C