爱奇艺2018.9.28笔试 清雨的自助餐_n种食物,排成一排,可以选择若干种,但是不能选择-程序员宅基地

技术标签: 笔试题  

题目描述

有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次后,则到达递归终点。

注意此代码的思想是:每选择一个位置后,下一个位置只能在上一个选择位置之后选择;每次选择位置,要注意给剩余位置留足够多的空位置(一个空格一个食物)。

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/anlian523/article/details/82912815

智能推荐

编译android源码报错:build/envsetup.sh: 1: Syntax error: "(" unexpected_./envsetup.sh: 1: syntax error: "(" unexpected-程序员宅基地

文章浏览阅读1.1k次。编译android源码报错:build/envsetup.sh: 1: Syntax error: "(" unexpected编译android源码时报错:build/envsetup.sh: 1: Syntax error: "(" unexpected解决方法:执行$sudo dpkg-reconfigure dash命令,并选择“否”_./envsetup.sh: 1: syntax error: "(" unexpected

2021-07-02 swift大礼包-程序员宅基地

文章浏览阅读5.5k次,点赞3次,收藏5次。全面的Swift学习资料整理_walkerwqp的博客-程序员宅基地 全面的Swift学习资料整理 ...

ImageView 使用详解-程序员宅基地

文章浏览阅读1.7w次,点赞3次,收藏82次。极力推荐文章:欢迎收藏Android 干货分享本篇文章主要介绍Android开发中的部分知识点,通过阅读本篇文章,您将收获以下内容:一、ImageView 的继承关系二、ImageView 常用方法三、ImageView 背景 间距属性设置四、使用Bitmap 类型动态设置ImageView 资源五、ImageView 图片倒影实现六、ImageV..._imageview

目前市场上的电脑一体机从计算机种类,一体机电脑与普通电脑的区别-程序员宅基地

文章浏览阅读639次。现在,市场上开始流行一体机电脑了,很多网友可能会对一体机电脑感兴趣。下面,本文针对市场上的一体机电脑优劣作一个简要说明。一、一体机电脑的好处由于一体机电脑,所有的设备都封装在同一个容器内,就连显示屏都和电脑的设备融为一体了。因此,一体电脑的放置、携带,是相当的方便。它的好处就是方便放置,放哪里都行,因为不占空间。二、一体机电脑的弊端由于一体机电脑把传统的机箱内的所有设备和显示屏,都合为一体了,可见..._企业版一体机与普通一体机的区别

Ubuntu 11.04 CUDA4.0的安装与编译_ubuntu cuda11.4安装编译样例时一直不停止-程序员宅基地

文章浏览阅读729次。出差的时候网上查了查相关的资料,回来用了早上的空余时间编译通了,主要的参考网址有两个:中文:http://topic.csdn.net/u/20110809/13/281a50dc-605f-4b32-92bf-4193eeebf7ec.html英文:http://forums.nvidia.com/index.php?showtopic=198030 Now, let's go._ubuntu cuda11.4安装编译样例时一直不停止

基于最小二乘、迭代和相位梯度校正的解包裹算法实例分析_精确最小二乘法解相位包裹-程序员宅基地

文章浏览阅读1.8k次,点赞3次,收藏7次。基于最小二乘、迭代和相位梯度校正的解包裹算法(CPILSI)实例_精确最小二乘法解相位包裹

随便推点

台大李宏毅《机器学习》2021课程撒花完结!除了视频、PPT,还有人汇编了一本答疑书...-程序员宅基地

文章浏览阅读530次。点击 机器学习算法与Python学习 ,选择加星标精彩内容不迷路机器之心报道今年 2 月末,「精灵宝可梦大师」李宏毅的《机器学习》最新一期课程正式开课。对于想要入门机器学习的同学来说,这是..._李宏毅ppt机器学习书

YOLOv5(ultralytics) 训练自己的数据集,VOC2007为例_ultralytics能训练sam吗-程序员宅基地

文章浏览阅读3.8k次,点赞4次,收藏40次。官方教程:https://github.com/ultralytics/yolov5/wiki/Train-Custom-DataVOC格式数据1.在yolov5目录下创建VOC2007文件夹,有VOC2007 …Annotations # 存放图片对应的xml文件 …JPEGImages # 存放图片 …ImageSets/Main #之后会在Main文件夹内自动生成train.txt,val.txt,test.txt和trainval.txt四个文件,存放训练集、验证集、测试集图片的名_ultralytics能训练sam吗

单词薄-java程序设计课程-成功-derby安装_apache derby安装-程序员宅基地

文章浏览阅读619次,点赞2次,收藏6次。http://www.mamicode.com/info-detail-1597112.html一、首先按照这个网址,干了一遍。下载了derby。设置了环境变量和系统变量。————————————————————————————1,首先下载Derbyhttp://db.apache.org/derby/derby_downloads.html技术分享下载最新版本 db-derb..._apache derby安装

GameFramework框架详解之 框架总览_gameformwork讲解-程序员宅基地

文章浏览阅读1.5w次,点赞23次,收藏73次。一.前言目前市场上有很多优秀个开源框架,比如ET,GameFramework,DBFramework,StrangeIOC,Loxodon-Framework,KSFramework,xluaFramework等等。其中要说规范的话,不得不说GameFramework还是不错的,当然很多新手看到后会觉的有点复杂,写一个小小的功能,不得不套用一堆东西,继承一堆接口,感觉不知所措,不能随心所欲的去撸代码。其实这个框架就是为了约束新手的行为的,让我们面向接口编程,遵循“开闭”的设计原则来写代码,方便后期的扩_gameformwork讲解

分布式之数据库和缓存双写一致性方案解析_java 延时双写-程序员宅基地

文章浏览阅读126次。为什么写这篇文章?首先,缓存由于其高并发和高性能的特性,已经在项目中被广泛使用。在读取缓存方面,大家没啥疑问,都是按照下图的流程来进行业务操作。 但是在更新缓存方面,对于更新完数据库,是更新缓存呢,还是删除缓存。又或者是先删除缓存,再更新数据库,其实大家存在很大的争议。目前没有一篇全面的博客,对这几种方案进行解析。如果想学习Java工程化、高性能及分布式、深入浅出。微服务、Sp..._java 延时双写

推荐文章

热门文章

相关标签