实验01:吃鸡蛋问题
创始人
2024-06-04 00:03:38
0

1.实验目的

通过实验理解算法的概念、算法的表示、算法的时间复杂度和空间复杂度分析;初步学会递归算法和非递归算法的转换。

2.实验内容

为庆祝三八女生节,学校发给女老师老王发放了n\ge2 个鸡蛋 。老王计划每天吃 2 至 n 个,连续若干天吃完,问老王有多少种吃法。

说明:本题只是数学题,不考虑实际生活中老师的食量 😄。

: 如果有3个鸡蛋,只有1种正确吃法,因为

$$
\begin{array}{|c|} \hline 吃法 & 第1天 & 第2天 & 第3天 & 正确与否 \\ \hline 1 & 3个 & / & / & 正确\\ 2 & 2个 & 1个 & / & 错误\\ 3 & 1个 & 2个 &/ & 错误\\ 4 & 1个 & 1个 & 1个 & 错误\\ \hline \end{array}
$$  

程序输入输出示例

输入(鸡蛋个数):3

输出(正确吃法数):1

3.实验要求

编制程序并对其时间复杂度和空间复杂度进行分析,实现递归版本非递归版本

\square 基础性实验 \square 综合性实验 \boxtimes 设计性实验


实验报告正文

一、问题分析(模型、算法设计和正确性证明等)

设老王吃完n个鸡蛋的方法有f(n)种,则有递归式:

f(n)=\left\{ \begin{array}{ll} 0, & {if \quad n=1}\\ 1, & {if \quad n=2}\\ f(n-2) + f(n-1), & {if \quad n>2} \end{array} \right.

情况1:n=1

不符合题意所以无合法吃法。

情况2:n=2

老王每天至少吃2个鸡蛋所以只有一种吃法。

情况3:n>2

老王吃完鸡蛋的情形可分为以下两种:

  1. 最后一天吃了2个鸡蛋

  2. 最后一天吃了3个及以上鸡蛋

对于情形1,只考虑剩下n-2个鸡蛋的吃法即可,即f(n-2)。

对于情形2,因为最后一天吃的鸡蛋数\geq 3个,所以减少1个也是合法的吃法,所以该情形的吃法有f(n-1)种。

二、算法设计复杂度分析(伪代码,不要粘贴源码)

  1. 递归算法

 

 

下求解递归算法的时间复杂度,设规模为n问题所需的计算时间为T(n),则有:

$$
T(n)=\left\{ \begin{array}{ll} O(1), & {if \quad n=1||n=2}\\ T(n-2) + T(n-1), & {if \quad n>2} \end{array} \right.
$$

通过微分方程法求得方程的解:

$$
T(n) \in \theta(f(n))=\theta(\frac{1}{\sqrt{5}}(\frac{1+\sqrt5}{2})^n-\frac{1}{\sqrt 5}(\frac{1-\sqrt{5}}{2})^n)
$$

下讨论递归算法的空间复杂度,每次返回函数本身都会开辟新的栈空间,故递归树的高度即为该算法所用空间。递归出口为1和2,递归树高度为n-1,所以空间复杂度为\theta (n)。

  1. 非递归算法

  2.  

    下讨论非递归算法的时间复杂度,设规模为n的问题所需的计算时间为T(n),则有:

    $$
    T(n)\in \theta(n-2)=\theta(n)
    $$  

    下讨论非递归算的空间复杂度,该算法仅使用两个整型变量(伪代码中a,b)辅助运算,故空间复杂度为\theta(1)。

三、实验结果记录和分析(测试向量的测试时间运行结果)

  1. 递归算法

    鸡蛋数(个)结果(种)运行时间(ms)
    210.0003
    780.0003
    12890.0015
    179870.0149
    22109460.1275
    271213930.8093
    3213462698.9908
    371493035214.5162
    421655801411106.4063

 

  1. 非递归算法

    鸡蛋数(个)结果(种)运行时间(ms)
    210.0002
    780.0001
    12890.0001
    179870.0001
    22109460.0002
    271213930.0001
    3213462690.0001
    37149303520.0002
    421655801410.0002
    1012189229958345552000000.0004
    10012.686381002448534e2080.0028

 

四、总结(可描述出现的问题和解决方法、经验和反思等)

此问题应与整数划分区别开,整数划分(最小数不少于2)只计算划分数即可,本问题还需计算每个划分种不同排列,例如n=7时,\{2,2,3\}是一种合法的整数划分,而\{2,2,3\},\{2,3,2\},\{3,2,2\}都是合法的吃鸡蛋方式,记3种,故两者并不相同。

递归算法的思路更加接近我们思考一个问题的方式,结构清晰,可读性强。可用数学归纳等方法证明其正确性,设计算法及调试很方便。但是效率很低,时间空间复杂度都高于非递归算法。

本次实验中可将递归算法写作以下非递归算法:

memo = dict({1:0,2:1});
def f(n):if n in memo:return memo[n]else:memo[n] = f(n-1) + f(n-2);return memo[n]

时间复杂度为O(n^2),空间复杂度为O(n),但是本实验中采用进一步优化的迭代算法改善算法效率。

相关内容

热门资讯

喜欢穿一身黑的男生性格(喜欢穿... 今天百科达人给各位分享喜欢穿一身黑的男生性格的知识,其中也会对喜欢穿一身黑衣服的男人人好相处吗进行解...
发春是什么意思(思春和发春是什... 本篇文章极速百科给大家谈谈发春是什么意思,以及思春和发春是什么意思对应的知识点,希望对各位有所帮助,...
网络用语zl是什么意思(zl是... 今天给各位分享网络用语zl是什么意思的知识,其中也会对zl是啥意思是什么网络用语进行解释,如果能碰巧...
为什么酷狗音乐自己唱的歌不能下... 本篇文章极速百科小编给大家谈谈为什么酷狗音乐自己唱的歌不能下载到本地?,以及为什么酷狗下载的歌曲不是...
华为下载未安装的文件去哪找(华... 今天百科达人给各位分享华为下载未安装的文件去哪找的知识,其中也会对华为下载未安装的文件去哪找到进行解...
怎么往应用助手里添加应用(应用... 今天百科达人给各位分享怎么往应用助手里添加应用的知识,其中也会对应用助手怎么添加微信进行解释,如果能...
家里可以做假山养金鱼吗(假山能... 今天百科达人给各位分享家里可以做假山养金鱼吗的知识,其中也会对假山能放鱼缸里吗进行解释,如果能碰巧解...
一帆风顺二龙腾飞三阳开泰祝福语... 本篇文章极速百科给大家谈谈一帆风顺二龙腾飞三阳开泰祝福语,以及一帆风顺二龙腾飞三阳开泰祝福语结婚对应...
美团联名卡审核成功待激活(美团... 今天百科达人给各位分享美团联名卡审核成功待激活的知识,其中也会对美团联名卡审核未通过进行解释,如果能...
四分五裂是什么生肖什么动物(四... 本篇文章极速百科小编给大家谈谈四分五裂是什么生肖什么动物,以及四分五裂打一生肖是什么对应的知识点,希...