21 - 猜女神的零食

鱼C-小师妹

在线讲解：



叮咚～热心市民小由鱼又收到了女神的短信：

小由鱼鸽鸽，来玩个游戏，你要是能猜出我们吃了多少包薯片，我就请你喝奶茶，猜错了，你请我喝～

提示如下：我们宿舍买了一箱薯片，第一天吃掉了其中一半后又多吃了一包(且不存在吃半包的情况)，第二天照此方法吃完剩下的一半后又多吃一包，每天如此，直到第 10 天早上，发现只剩下一包薯片了。

收到女神的短信，一向不爱喝奶茶的小由鱼，虎躯一震，让我请，绝无可能！



先来假设一箱有 10 包吧，那么按照女神的提示：

• 第一天有 10 包。
• 第二天就要吃掉第一天的一半就是 5 包，然后额外加 1 包，就是吃了 6 包，还剩 4 包
• 第三天就要吃掉第二天剩下中的一半就是 2 包，然后额外加 1 包，就是吃了 3 包，还剩 1 包
• 这样第四天就会发现只剩 1 包
  

如果正面按照女神的提示，一个一个数字去试，找到符合上面算法，且第 10 天刚好为 1 的数就是答案了～

很明显女神这里给自己挖了一个“坑”，正面攻破会很麻烦～

哼哼，你有张良计，我有过墙梯～

女神这次的奶茶，喝定了，反面突围，采用递归～

二话不说，开撸代码，先将女神的问题抽象成数学表达式。

假设 Ai 为第 i 天吃完后剩下的薯片包数。

那么第一天刚开始吃的薯片总包数就是 A0，显然，女神题目就是要求是 A0。

那么根据问题描述，前后相邻两天之间的薯片数应存在如下关系：

1. A(i+1)=Ai-(Ai/2+1)

复制代码

左右等式进一步可转换为：

1. Ai=2A(i+1)+2=2(A(i+1)+1)

复制代码

哼哼，公式有了，离解决问题还远吗？！

按照该公式，代数进去递推一下：

A0 = 2×(A1+1)    A1：第1天吃完后剩下的薯片数
A1 = 2×(A2+1)    A2：第2天吃完后剩下的薯片数
……
A8 = 2×(A9+1)    A9：第9天吃完后剩下的薯片数
A9 = 1

因为我们从 0 开始，那么 A9 其实就代表第 10 天。

没问题，由于第 9 天吃完后剩下的薯片数是已知的。

因此根据上述递推式子可以推出第 8 天的薯片总数。

根据第 8 天吃完后剩下的薯片数又可以推出第 7 天的薯片总数……

重复进行下去，就可以推出第 1 天摘下的薯片总数。

上面的公式用循环结构和递归都可以实现。

如果用循环就要正面攻破：

第 1 天的薯片数是第 2 天薯片数加 1 后的 2 倍

我们创建变量 x 表示后一天的，y 表示前一天。

还需要创建 day 表示日期，直接用 while 循环递减就可以：

1. day = 9
   
2. x = 1
   
3. while day > 0:
   
4.     y = (x + 1) * 2
   
5.     x = y
   
6.     day -= 1
   
7. print(f"女神共吃了{y}包薯片")

复制代码

结果：



看到结果，小由鱼内心 OS：

太呐，女神和她舍友们也太能吃了吧！！

不过转念一想，哈哈哈，能吃是福也挺好～

用递归就假设第 n 天吃完后剩下的薯片数为 A(n)，第 n+1天 吃完后剩下的薯片数为 A(n+1)。

这样代码也直接出来了：

游客，如果您要查看本帖隐藏内容请回复

结果还是一样，问题解决了，赶紧回信息！

否则女神还以为我算不出来，这样请奶茶，怕是要破产！

哈哈哈哈哈哈哈，人间真实·小由鱼去回信息啦，递归完整代码就留给你们当课后作业咯～

用了两次递归了，童鞋们应该或多或少对递归感觉了，小师妹就来带你们总结一下：

递归三定律：

• 必须有一个结束条件
• 必须能改变状态向结束条件推进
• 必须调用自身
  

童鞋们好好去参悟吧～

好的，下课！

源码： P21.py.zip (322 Bytes, 下载次数: 9, 售价: 6 鱼币)

2021-8-22 20:03 上传

点击文件名下载附件

柿子饼同学

沙发~

hornwong

小薛王

学习学习

gjc2010gys

算出来了！有3070包！代码如下：

1. def jisuan():
   
2.     global chip
   
3.     chip = chip - ((chip / 2) + 1)
   
4.     return chip
   
5. 
   
6. for chip in range(1,10000):
   
7.     t_chip = chip
   
8.     for i in range(0,10):
   
9.         jisuan()
   
10.     if chip == 1:
    
11.         break
    
12. else:
    
13.     print(False)
    
14. 
    
15. print(t_chip)

复制代码

睦ちゃん她爹

鱼C-小师妹

gjc2010gys 发表于 2021-8-16 11:00
算出来了！有3070包！代码如下：

厉害了！！！

年少的梦想

沙发, 好熟悉,上次吃的是桃

冰清玉洁丸

请问小由鱼和小甲鱼的关系

pests

鱼C-小师妹

冰清玉洁丸 发表于 2021-8-18 10:48
请问小由鱼和小甲鱼的关系

Java 和 JavaScript

airsnowman

1. nums = 1
   
2. 
   
3. for i in range(10):
   
4.     nums += 1
   
5.     nums *= 2
   
6. 
   
7. print(nums)
   

复制代码

鱼C-小师妹

airsnowman 发表于 2021-8-19 16:47

再想想

冰清玉洁丸

鱼C-小师妹 发表于 2021-8-18 18:38
Java 和 JavaScript

懂了

老甲鱼真黄

Jave和JaveScript是什么意思

cheerlye

这个有点复杂

小甲鱼头号迷弟

gjc2010gys 发表于 2021-8-16 11:00
算出来了！有3070包！代码如下：

厉害！

1. #666

复制代码

小甲鱼头号迷弟

老甲鱼真黄 发表于 2021-8-20 11:20
Jave和JaveScript是什么意思

难道不是Java 和 JavaScript吗
两个完全不搭边的编程语言

一阵三十六

'''请女神喝秋一奶'''
# i》天数
# n》当天持有的薯片总数
# 利用公式 Ai = 2*(A(i+1) + 1)
n = 1
for i in range(9,-1,-1):
    if i >=0 :
        n = 2*(n+1)
        continue
print('计算完毕！')
print('买了',n,'包！',sep='')
print('A0 =',n)

非凡

从公式来看，是要递归无疑了

1. def goddess(x):
   
2.     if x == 1:
   
3.         return 1
   
4.     else:
   
5. 
   
6.         return (goddess(x-1)+1)*2
   
7. 
   
8. >>>goddess(10)
   
9. >>>1534
   

复制代码

一共是1534包，我也要奶茶
每天只吃一半，不是可以一直吃下去？干嘛要每天吃一半多一包呢？


但是~~
Ai是第i天吃完后剩下的薯片，从题目上理解来看，第九天吃完一半，加一包。第10天早上起来，发现只剩一包了。这时小姐姐刚起床肯定是都还没刷牙呢~所以第9天吃完后，就已经剩下 1包了。第10天都还没开始吃。

所以Ai = 2 怎么来的呢？

总共1534包
第一天吃  767 +1 包剩下766包
第二天吃  383 +1 包剩下382包
第三天吃  191 +1 包剩下190包
第四天吃  95 +1 包剩下94包
第五天吃  47 +1 包剩下46包
第六天吃  23 +1 包剩下22包
第七天吃  11 +1 包剩下10包
第八天吃  5 +1 包剩下4包
第九天吃  2 +1 包剩下1包
第10天没吃，发现只剩1包