WaWa的难题

水深无声 2022-04-01 03:14 191阅读 0赞

###  ###

题目描述

HaHa和WaWa是好朋友，他们在临近期末的这段时间一起宅在图书馆学习。  
今天HaHa在书上看到一个排列组合题目，思考很久后，仍然找不出其中的规律。  
于是他把题目叙述给了WaWa。  
题目：  
————————————————————————  
一个长度为N的排列，由数字1~N组成，它满足两个条件。  
1、数字1永远在第一位。  
2、任意两个相邻数字之差小于等于2。  
现在给出一个N，  
你能知道能组成多少个符合条件的排列吗？。  
例如：  
N=4  
1 2 3 4  
1 2 4 3  
1 3 2 4  
1 3 4 2  
所以答案为4  
————————————————————————  
WaWa听后也是一脸懵逼。  
现在WaWa想求助于你们，WaWa给出一个正整数N，问你用1~N能组成多少个符合题意的排列。

输入

多组数据。  
每组数据输入一个正整数N(1<=N<=100)。

输出

输出符合题意的排列个数

样例输入 Copy

2  
4

样例输出 Copy

1  
4

##### 分析： #####

本题的基本思路是dfs，不过时间超限。但我们运用dfs看结果的时候会发现规律。

#include"stdio.h"
    #include"string.h"
    int main()
    {
        long long a[101];
        long long i,j,k;
        long long N;
        a[1]=1;a[2]=1;a[3]=2;
        for(i=4;i<101;i++)
            a[i]=a[i-1]+a[i-3]+1;
       while(~scanf("%lld",&N))
       {
           printf("%lld\n",a[N]);
       }
    }

BFS代码：

#include"stdio.h"
    #include"string.h"
    long long count;
    long long vis[101];
    long long a[101],N;
    void dfs(long long mark)
    {
        int i,j,k;
        if(mark==N+1)
            {count++;
    
            }
        else
         {
             for(i=2;i<=N;i++)
               {//注意题目，是差，并未说谁大。
                   if(vis[i]==1&&abs(i-a[mark-1])<=2)
                      {
                          vis[i]=0;
                          a[mark]=i;
                          dfs(mark+1);
                          vis[i]=1;
                      }
               }
         }
    
    
    }
    int main()
    {
        long long i;
        while(~scanf("%lld",&N))
        {
            for(i=1;i<=N;i++)
              vis[i]=1;
            a[1]=1;
            count=0;
            dfs(2);
            printf("%lld\n",count);
        }
    }