不容易系列2 （C语言代码）递推

参考代码：AC（递推，思路借鉴题号1117，“递推”）

#include <stdio.h>

int main()
{
    int i, n;
    long long res[21];
    while (scanf("%d", &n) != EOF)
    {
        res[2] = 1;
        res[3] = 2;
        res[4] = 9;
        if (n<=4)
        {
            printf("%d\n", res[n]);
            continue;
        }
        else
        {
            for (i=5;i<=n;i++)
                res[i]=(res[i-1]+res[i-2])*(i-1);//根据规律可知
            printf("%lld\n",res[n]);
        }
    }
    return 0;
}

参考代码：输出超限（DFS）

#include <stdio.h>
#include <stdlib.h>

int cnt,n;
int *num,*vis;

void dfs(int i)
{
    if(i==n+1)
    {
        cnt++;return;
    }
    int t;
    for(t=1;t<=n;t++)
    {
        if(!vis[t]&&t!=i)
        {
            num[i]=t;
            vis[t]=1;
            dfs(i+1);
            vis[t]=0;
        }
    }
    return;
}

int main()
{
    int i;
    while(scanf("%d",&n))
    {
        cnt=0;
        num=(int *)malloc(sizeof(int)*(n+1));
        vis=(int *)malloc(sizeof(int)*(n+1));
        for(i=0;i<=n;i++) {num[i]=i;vis[i]=0;}
        dfs(1);
        printf("%d\n",cnt);
        free(num);
    }
    return 0;
}

参考代码: 输出超限（全排列，类似题号1163，“排队买票”问题） 

#include <stdio.h>
#include <stdlib.h>
int cnt,n;
int *num;

void pmut(int i)
{
    int j,t,tmp;
    if(i<n)
    {
        for(j=i;j<=n;j++)
        {
            tmp=num[j];
            for(t=j;t>i;t--)
                num[t]=num[t-1];
            num[i]=tmp;

            pmut(i+1);

            for(t=i;t<j;t++)
                num[t]=num[t+1];
            num[j]=tmp;
        }
    }
    else
    {
        int flag=1;
        for(j=1;j<=n;j++)
            if(num[j]==j) {flag=0;break;}
        if(flag) cnt++;
    }
}


int main()
{
    int i;
    while(scanf("%d",&n))
    {
        cnt=0;
        num=(int *)malloc(sizeof(int)*(n+1));
        for(i=0;i<=n;i++) num[i]=i;
        pmut(1);
        printf("%d\n",cnt);
        free(num);
    }
    return 0;
}