递归与分治思想

最新推荐文章于 2025-05-27 21:52:10 发布

一匹小羊驼

最新推荐文章于 2025-05-27 21:52:10 发布

阅读量132

点赞数

分类专栏：数据结构与算法文章标签：算法数据结构

本文链接：https://blog.csdn.net/happy_programer/article/details/128537996

版权

数据结构与算法专栏收录该内容

11 篇文章

订阅专栏

本文展示了递归在解决经典算法问题中的应用，包括斐波那契数列的迭代和递归实现，汉诺塔问题的递归解决方案，以及使用分治策略解决八皇后问题。这些示例突显了递归和分治在计算机科学中的重要性。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

递归

斐波那契数列的迭代实现

#include<stdio.h>

int main()
{
    int i;
    int a[40];
    a[0]=0;
    a[1]=1;
    printf("%d %d ",a[0],a[1]);
    for(i=2;i<40;i++){
        a[i]=a[i-1]+a[i-2];
        printf("%d ",a[i]);
    }
    return 0;
}

递归实现

int factorial(n)
{
    if(n==0) return 1;
    else return n*factorial(n-1);
}

汉诺塔问题

#include<stdio.h>

//将n个盘子从x借助y移动到z
void move(itn n,char x,char y,char z)
{
    if(n == 1)
    {
        printf("%c-->%c\n",x,z);
    }
    else{
        move(n-1,x,z,y);  //将n-1个盘子从x借助z移动到y上
        printf("%c-->%c\n",x,z);  //将第n个盘子从x移到z上
        move(n-1,y,x,z);  //将n-1个盘子从y借助x移到z上
    }
    
}

int main()
{
    int n;
    printf("请输入汉诺塔的层数：");
    scanf("%d",&n);
    printf("移动的步骤如下：\n");
    move(n,'x','y','z');
}

分治

八皇后问题

#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)
        {
            flag1 = 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表示列数
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(row==8)
    {
        printf("第%d种",count+1);
        for(i=0;i<8;i++)
        {
            for(j=0;j<8;j++)
            {
                printf("%d ",*(*(chess2+i)+j));
            }
            printf("\n");
        }
        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\n",count);
    return 0;
}