数学三角形

DFS

#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;

int num[15];
int vis[15];
int n,sum;

void dfs(int k)
{
  if(k>=n)                        //凑齐四个数搭建数字三角形
  {
    int copy[15];                 //创建临时空间计算数字三角形
    for(int i=0;i<n;i++)          //将num[]放进copy[]
      copy[i]=num[i];

    for(int i=n-1;i>=1;i--)       //计算三角形顶角数字
      for(int j=0;j<i;j++)
        copy[j]+=copy[j+1];
    if(copy[0]==sum)             //判断数字是否满足
    {
      for(int i=0;i<n;i++)
        printf("%d%s",num[i],i<n-1?" ":"\n");
      exit(0);
    }
    return;
  }

  for(int i=1;i<=n;i++)          //a1，a2，a3，a4，正序挨个尝试：1234，1243.....4321
  {
    if(!vis[i])
    {
      vis[i]=1;                  //锁上
      num[k]=i;                  //1~n数字排列放进mun[]
      dfs(k+1);
      vis[i]=0;                  //解锁
    }
  }
}

int main() {
  scanf("%d%d", &n, &sum);       //层数、顶点
  dfs(0);
  return 0;
}

笔记：按照题意枚举所有全序列，n越大耗费的时间越长，没有经过剪枝的处理，肯定超时

DFS+剪枝

#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;

int num[15];
int vis[15];
int n,sum;

int yh[15][15];
void init()                                      //杨辉三角
  {
    for(int i=1;i<=13;i++)                       //从1开始
    {
      yh[i][0]=1;                                //从0开始
      for(int j=1;j<i;j++)
        yh[i][j]=yh[i-1][j-1]+yh[i-1][j];
    }
  }


void dfs(int k, int ans)                          //k：最初序列 ans：顶点
{
  if(k>=n)                                        //序列长度满足最初序列
  {
    //for(int i=0;i<n;i++)                          //遍历打印序列
      //printf("%d%s",num[i],i<n-1?" ":"\n");
    if(ans==sum)                                  //顶点数与sum相等
    {
      for(int i=0;i<n;i++)                        //遍历打印序列
        printf("%d%s",num[i],i<n-1?" ":"\n");
      exit(0);
    }
    return;
  }

  for(int i=1;i<=n;i++)
  {
    if(!vis[i])
    {
      if(ans+i*yh[n][k]>sum)                     //大剪枝：顶点超过sum
        break;                                   //不用继续递归

      if( k>n/2 && i<num[n-1-k])                 //小剪枝：后面的数字，不能比前面的数字大
        continue;                                //因为对称性，所以1234遍历过那4321就不需要遍历了

      vis[i]=1;
      num[k]=i;
      dfs(k+1, ans+i*yh[n][k]);                  //杨辉三角系数
      vis[i]=0;
    }
  }
}

int main()
{
  init();
  scanf("%d%d",&n,&sum);
  dfs(0, 0);
  return 0;
}

笔记：剪枝可以将没必要递归的分叉修剪掉，大剪枝是修建一片分叉，小剪枝根据杨辉三角的对称性，和题意输出的要求，修剪掉已经遍历的最小序列

版权声明：

本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。本文链接：https://blog.csdn.net/qq_43290318/article/details/102131328