您现在的位置是：首页 >技术杂谈 >刷题刷题。网站首页技术杂谈

自然数拆分

---

利用step记录组合情况，只用sum不能判断组合情况

1.选择dfs原因：产生排列组合，和为7，step为8，其中7个空位，第8个step为输出；

    参量的设置sum，step (进入下一层）;

2.终止条件：sum>7  剪枝干    (此时最终step不一定为8)！！！！！

3.输出条件：sum==7，注意最后的值和前面的值输出形式不同；

4.dfs递归--for循环的设置：i为（1-7）需要放入每层的值；

5.注意：标记问题：同一数可以重复使用

              组合问题：i 从上一层的值开始递增7结束i=a[step-1]，同时注意a[0]边界

              回溯问题：sum+=i;   dfs（step+1);   sum-=i;    等价于   dfs（sum+i，step+1）

              因为这一层的sum没有改变

#include<stdio.h>
#include<string.h>
int n;
int a[1000];
void dfs(int sum,int step)
{
    if(sum>n) return ;  //注意！！！！！边界情况
    if(sum==n)
    {
        for(int i=0;i<=step-2;i++)
        printf("%d+",a[i]);
        printf("%d
",a[step-1]);
        return ;
    }
    //组合,可重复，从上一层最小值开始
    //同时注意初始边界值a[step-1]
    for(int i=a[step-1];i<n;i++)
    {
        a[step]=i;     //放入
        dfs(sum+i,step+1); //递归
        //这里无需标记，组合可重复使用
    }
}
int main()
{
    scanf("%d",&n);
    a[0]=1;
    dfs(0,1);
    return 0;
}

 八皇后

---

1.解题关键：横竖斜只有1个皇后；斜：横纵坐标之和，横纵坐标之差

2.dfs参数设置：step，不用调用每层x，y，不是迷宫探险类，只用check二维数组上每一点

3.for循环设置：check，该step层皇后是否满足check；

4.终止条件：step==n+1；

注意：i 行，a[ i ]列  

#include<stdio.h>
int n,a[20];                 //i表示行，a[i]表示列；
int cnt=0;
int check(int x,int y)      //n皇后是否成立，check游戏标准：横竖斜仅有一个皇后；
{
    for(int i=1; i<=x; i++)         //无需讨论行==情况，每次放step都是一行一行放的
    {
        if(a[i]==y)return 0;       //皇后位置和其他皇后列==（×）
        if(i+a[i]==x+y)return 0;   //皇后位置和其他皇后对角线1（×）
        if(i-a[i]==x-y)return 0;   //皇后位置和其他皇后对角线2（×）
    }
    return 1;
}
void dfs(int step)         //表示第step个皇后放在何处
{
    if(step==n+1)          //dfs最后一层为输出
    {
        cnt++;             //解的个数
        if(cnt<=3)
        {
            for(int i=1; i<=n; i++)
            {
                printf("%d ",a[i]);     
                if(i%n==0)printf("
");
            }
 
        }
        return ;
    }
    for(int j=1; j<=n; j++) //共1-8列
    {
        if(check(step,j))   //check第step行的皇后是否能放在j列上
        {
            a[step]=j;      //放在j列，标记；
            dfs(step+1);    //进入下一层，放下一个皇后；
            a[step]=0;     //取消标记
        }
    }
}
int main()
{
    scanf("%d",&n);
    dfs(1);              //第一层开始
    printf("%d",cnt);   
    return 0; 
}