解题思路：题意很明确，就是让求满足条件：1、第一个数必须是1；2、相邻两个数之差不大于2 的排列的种数。

可以得出递推公式：f[i]=f[i-1]+f[i-3]+1，其中 f[n]即为所求。

 1 #include<iostream>

 2 #include<cstdio>

 3 

using 

namespace std;

 4 

 5 

int main()

 6 {

 7     

int i,n,f[

60];

 8     f[

1]=

1;

 9     f[

2]=

1;

10     f[

3]=

2;

11     

for(i=

4;i<

60;i++)

12         f[i]=f[i-

1]+f[i-

3]+

1;

13     

while(cin>>n)

14     {

15         cout<<f[n]<<endl;

16     }

17     

return 

0;

18 }