递归思想的应用

1. 编写一个递归函数，实现将输入的任意长度的字符串反向输出的功能。例如输入字符串ABC，则输出字符串CBA。
   代码实现：

void print(){
    char a;
    scanf("%c", &a);
    if(a != '#') print();
    if(a != '#') printf("%c", a);
}

2. 汉诺塔问题
   一位法国数学家曾编写过一个印度的古老传说：在世界中心贝拿勒斯的圣庙里，一块黄铜板上插着三根宝时针。印度教的主神梵天在创造世界的时候，在其中一根针上从下到上地穿好了由大到小的64片金片，这就是所谓的汉诺塔。不论白天黑夜，总有一个僧侣在按照下面的法则移动这些金片：一次只移动一片，不管在那根针上，小片必须在大片上面。
   僧侣们语言，但所有的金片都从梵天穿好的那根针上移到另外一根针时，世界就将在一声霹雳中消灭，而梵塔，庙宇和众生也都将同归于尽。

图片.png

问题的实现主要考虑下面三个步骤：

• 先将前63个盘子移动到Y上，确保大盘在小盘下。
• 再将最底下的64个盘子移动到Z上。
• 最后将Y上的63个盘子移动到Z上。
  代码实现如下：

#include <stdafx.h>
#include <stdio.h> 
void hannuotai(int n, char A, char B, char C) {
    /*
    如果是1个盘子
        直接将A柱子上的盘子从A移动到C
    否则
        将A柱子上的n-1个盘子借助C移动到B
        直接将A柱子上的盘子从A移动到C
        最后将B柱子上的n-1个盘子借助A移动到C
    */
    if (1 == n)
    {
        printf("将编号为%d的盘子直接从%c柱子移动到%c柱子\n", n, A, C);
    }
    else
    {
        hannuotai(n - 1, A, C, B);
        printf("将编号为%d的盘子直接从%c柱子移动到%c柱子\n", n, A, C);
        hannuotai(n - 1, B, A, C);
    }
}
int main(void) { 
    char ch1 = 'A';
    char ch2 = 'B';
    char ch3 = 'C';
    int n;
    printf("请输入要移动盘子的个数:");
    scanf_s("%d", &n);
    hannuotai(n, 'A', 'B', 'C');
    getchar();
    getchar();
    return 0;
}

3. 八皇后问题
   这个问题是十九世纪著名的数学家高斯1850年提出：
   在8x8格的国际象棋上摆放八个皇后，使其不能互相攻击，即在任意两个皇后都不能处于同一行，同一列或同一斜线上，问有多少种摆法。
   正确答案是92种摆法。
   其中一种解法如下：

图片.png

代码实现：

#include<stdafx.h>
#include<stdio.h>

int count = 0;

int notDanger(int row, int j, int(*chess)[8]) {
    
    int i, k, flag1 = 0, flag2 = 0, flag3 = 0, flag4 = 0, flag5 = 0;
    //判断列方向
    for (i = 0; i < 8; i++)
    {
        if (*(*(chess + i) + j) != 0)
        {
            flag1 = 1;
            break;
        }
    }
    //判断左上方
    for (i = row, k = j; i >= 0 && k >= 0; i--, k--)
    {
        if (*(*(chess + i) + k) != 0)
        {
            flag2 = 1;
            break;
        }
    }
    //判断右下方
    for (i = row, k = j; i < 8 && k < 8; i++, k++)
    {
        if (*(*(chess + i) + k) != 0)
        {
            flag3 = 1;
            break;
        }
    }
    //判断右上方
    for (i = row, k = j; i >= 0 && k < 8; i--, k++)
    {
        if (*(*(chess + i) + k) != 0)
        {
            flag4 = 1;
            break;
        }
    }
    //判断左上方
    for (i = row, k = j; i < 8 && k >= 0; i++, k--)
    {
        if (*(*(chess + i) + k) != 0)
        {
            flag5 = 1;
            break;
        }
    }

    if (flag1 || flag2 || flag3 || flag4 || flag5)
    {
        return 0;
    }
    else
    {
        return 1;
    }
    
}

//参数row：表示起始行
//参数n:表示列数
//参数(*chess)[8]：表示指向棋盘每一行的指针
void EightQueen(int row, int n, int(*chess)[8]) {
    int chess2[8][8], i, j;
    for (i = 0; i < 8; i++)
    {
        for (j = 0; j < 8; j++)
        {
            chess2[i][j] = chess[i][j];
        }
    }
    if (8 == row)
    {
        printf("第 %d 种", count + 1);
        for (i = 0; i < 8; i++)
        {
            for (j = 0; j < 8; j++)
            {
                printf("%d", *(*(chess2 + i) + j));
            }
            printf("\n"); 
        }
        count++;
    }
    else
    {
        //判断这个位置是否有危险
        //如果没有危险？继续往下判断
        for (j = 0; j < n; j++)
        {
            if (notDanger(row, j, chess)) {//判断这个位置是否有危险
                for (i = 0; i < 8; i++)
                {
                    *(*(chess2 + row) + i) = 0;
                }
                *(*(chess2 + row) + j) = 1;
                EightQueen(row + 1, n, chess2);
            }
        }
    }

}

int main() {

    int chess[8][8], i, j;
    for (i = 0; i < 8; i++)
    {
        for (j = 0; j < 8; j++)
        {
            chess[i][j] = 0;
        }
    }
    EightQueen(0, 8, chess);

    printf("总共有%d种解决方法!\n", count);

    getchar();
    return 0;
}