问题描述
如果一个序列满足下面的性质，我们就将它称为摆动序列：
. 序列中的所有数都是不大于k的正整数；
. 序列中至少有两个数。
. 序列中的数两两不相等；
. 如果第i – 1个数比第i – 2个数大，则第i个数比第i – 2个数小；如果第i – 1个数比第i – 2个数小，则第i个数比第i – 2个数大。
比如，当k = 3时，有下面几个这样的序列：
一共有8种，给定k，请求出满足上面要求的序列的个数。
输入格式
输入包含了一个整数k。（k<=）
输出格式
输出一个整数，表示满足要求的序列个数。
样例输入 样例输出
记:
注意题目给的条件(当数字大于2时的条件判断,不满足时立即跳出)
AC代码:
#include <stdio.h>
#define N 20 int k;
int count = ;
int use[N+] = {}; /*数据存储*/
int vis[N+] = {}; /*访问标记*/ void dfs(int x)
{
int i,j;
int flag;
if (x >= )
{
count ++;
} if (x > k)
{
return ;
} for (i = ; i <= k ; i ++)
{
if (!vis[i])
{
flag = ;
use[x] = i;
for (j = x ; j >= ; j --)
{
if (use[j-]>use[j-] && use[j]>use[j-])
{
flag = ;
break;
}
else if (use[j-]<use[j-] && use[j]<use[j-])
{
flag = ;
break;
}
}
if (flag)
continue;
vis[i] = ;
dfs(x+);
vis[i] = ;
}
} return ;
} int main(void)
{
scanf("%d",&k);
dfs();
printf("%d",count); return ;
}