首页 > 代码库 > NYOJ469

NYOJ469

题目连接:http://acm.nyist.net/JudgeOnline/problem.php?pid=469

思路:很明显这是一道找规律的题 可是这个规律怎么找

那么就要看n的位置放在哪里了   

举个例子  比如说n等于5 求f(5);

第二位是2时:后面的四个数正好是2   3  4  5 所以这个排列的个数为 f(5-1);

第二位是3时:第三位可以是2那么后面两位是4   5  所以这个排列的个数为  f(5-3)

                   第三位是4的时候无结果

                   第三位是5的时候   只能有一个序列   1    3     5     4     2

综上所述:f(n) = f(n - 1) + f(n - 3) + 1;

下面看代码:

#include<stdio.h>int main(){    int n,a[59] = {0,1,1,2,4};  //数组一定要声明大于55    for(int i = 5;i < 56;i++)    {        a[i] = a[i - 1] + a[i - 3] + 1;    }    while(~scanf("%d",&n))    {        printf("%d\n",a[n]);    }    return 0;}//代码很简单   但是需要注意细节

 

NYOJ469