爱奇艺2018.9.28笔试清雨的自助餐

今天药忘吃喽~ 2022-05-09 04:38 233阅读 0赞

# 题目描述 #

有N种食物，排成一排，选择里面的若干食物，但不能选择相邻的食物。一个也不选也是一种选择的方法。  
问有多少种选择的方法？  
**输入：**  
一个整数n  
**输出：**  
一个正整数表示答案  
**样例输入：**  
3  
**样例输出：**  
5  
**提示：**  
方法有1、2、3、1和3、不选。共5种。

# 斐波那契 #

n从1开始，  
f(1)=2  
f(2)=3  
f(3)=5  
…

n = eval(input())
    
    li = [0]*3
    li[1]=2
    li[2]=3
    
    for i in range(3,n+1):
        li[i%3] = li[(i-1)%3] + li[(i-2)%3]
    print(li[n%3])

数组大小为3即可。写出前几种情况，就可以发现此题是斐波那契。

# 递归 #

n = eval(input())
    
    result = n+1#选一个食物和不选
    li = []
    
    def solve(num):#当前方法的食物个数num
        #手动设置递归起点
        global li
        for i in range(1,n-(num-1)*2+1):
            li.append(i)
            recur(i,num,num-1)
            li.remove(i)
        
    def recur(current,num,last):
        #current当前选择的食物的位置
        #num当前方法的食物个数，递归中不变
        #last剩余需要选择的食物的个数
        global li
        global result
        if last == 0:
            result += 1
            print(li)#此句可屏蔽
            return
        tempLast = last -1
        for i in range(current+2, n-tempLast*2+1):
            li.append(i)
            recur(i,num,tempLast)
            li.remove(i)
    
    if(n>=3):
        #大于3就有两个或者更多位置的选择方法
        #最少可以选两个位置
        #最大情况如下
        maxnum = n-1 if n%2 == 0 else n#最多位置的选择方法中，位置间隔一个空格的最短长度
        #比如n为5，最多选3个位置，3个位置位置间隔空格就是5；比如n为6，最多还是选3个位置
        maxnum = (maxnum+1)//2
        for i in range(2,maxnum+1):
            solve(i)
    
    print(result)

首先注意此代码为错误代码，因为时间复杂度太高，如果说题意要求打印出每种选择的方法，那么此代码为正确代码。

整个程序思想是递归。

首先是确认下来选择的方法中，要选几个食物。范围是\[2,maxnum\]，maxnum的计算方法见注释。

确定下来当前方法的食物个数num后，依次选择每个食物的位置，选择num次。注意每次选择时也有个范围，**范围开始是上一次选择的位置加2，范围结束则要注意给后面留足够多的空位（比如选第一个位置时，要注意给后面留(num-1)\*2个位置，因为刚好后面是一个空格一个食物、一个空格一个食物这样的排列）**。当选择了num次后，则到达递归终点。

注意此代码的思想是：**每选择一个位置后，下一个位置只能在上一个选择位置之后选择；每次选择位置，要注意给剩余位置留足够多的空位置（一个空格一个食物）。**