当前位置：网站首页>递归递推之Fighting_小银考呀考不过四级

递归递推之Fighting_小银考呀考不过四级

2022-08-10 12:36:00 【51CTO】

题目大概：

一行有n个座位，每两个人之间至少空两个座位，求至少一个人的情况下的作为的做法。

思路：

a[n]为n个座位有的所有做法。假设前面的作为已经排好，第n个座位有两种情况，有人做和没人做，当有人做时，n-1和n-2一定没人做，所以和坐法和a[n-3]的数量时一样的，当没人坐时，那就和a[n-1]上的坐法是一样的，但还有一种情况，即当只有一个人坐时，a[n]上坐一人也算一种情况，故得出公式a[n]=a[n-1]+a[n-3]+1。

感想：

这个题有些难想，但不难想到要用公式能递推出所有的坐法，并且一般后面的数据于前面的有联系，但最后的加一容易忘掉，但调试的时候会发现每个数都会小1，再仔细回想就会发现错误。

代码：

       
       #include <iostream> 
       
using namespace std ; 
       
int main () 
       
{ int n ; 
       
int a [ 46 ]; 
       
a [ 1 ]= 1 ;a [ 2 ]= 2 ;a [ 3 ]= 3 ; 
       
for ( int i = 4 ;i < 46 ;i ++) 
       
{a [i ]=a [i -1 ]+a [i -3 ]+ 1 ; 
       
} 
       
while (cin >>n ) 
       
{cout <<a [n ]<<endl ; 
       
} 
       
    return 0 ; 
       
} 
       
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.