176-607978-[趣味拓展]多重循环的优化_鸡兔同笼.sy.md

show	version	enable_checker
step	1.0	true

二重循环

回忆

• 上次研究了二重循环之上的多重循环
  • 三重循环
  • 四重循环
• 说白了就是循环套循环

• 从五运六气到年、月、日
• 再到时、分、秒
• 其实循环嵌套无处不在
• 计算机中的多重循环可以优化吗？🤔

我们再看一个例子

• 再看一个经典的例子
  • 鸡兔同笼
  • 先不要翻篇

• 自己做做看

鸡兔同笼

• 最简单的思路
• 穷举法

heads = eval(input("how many heads?"))
legs = eval(input("how many legs?"))
find_flag = False
for cock in range(heads+2):
    print(list(range(heads+4)))
    if find_flag == True:
        break;
    for rabbit in range(legs//2):
        print("cock:",cock,",rabbits:",rabbit)
        print("cock+rabbit:",cock+rabbit,"2cock+4rabbit:",cock*2+4*rabbit)
        print(cock+rabbit==heads)
        print(cock*2+rabbit*4==legs)
        if ((cock+rabbit)==heads) and ((2*cock+4*rabbit)==legs):
            print("cock:",cock,",rabbits:",rabbit,"yes got the answer")
            find_flag = True
            break;

• 上述代码演示了跳出两层循环的办法
• 那就立一个 flag
• 这个 flag 就像一个哨兵
• 一旦发现符合要求的数值
• 直接跳出两层循环
• 但是目前循环的复杂度和腿数与头数的乘积成正比
• 能否优化一些呢？

优化程序

• 其实一重循环就够了
• 如果兔子数量固定
• 那么鸡的数量就是头数减去兔子的数量

heads = eval(input("how many heads?"))
legs = eval(input("how many legs?"))
find_flag = False
for cock in range(heads+2):
    print(list(range(heads+2)))
    rabbit = heads - cock
    print("cock:",cock,",rabbits:",rabbit)
    print("cock+rabbit:",cock+rabbit,"2cock+4rabbit:",cock*2+4*rabbit)
    print(cock*2+rabbit*4==legs)
    if ((2*cock+4*rabbit)==legs):
        print("cock:",cock,",rabbits:",rabbit,"yes got the answer")
        break

• 这样从两重循环变成了一重循环
• 复杂度从和头数与腿数的成绩成正比
• 变成了和头数成正比
• 但是还可以再简化么？

再优化

heads = eval(input("how many heads?"))
legs = eval(input("how many legs?"))
rabbit = legs//2 - heads
cock = 2*heads - legs//2
print("cock:",cock,"rabbit",rabbit)

• 其实这个东西就连一重循环都不需要
• 一万个腿都能搞定
• 完全直接计算就可以得到
• 我们陷入循环的时候
• 必须要思考一下
• 是不是有循环的必要
• 千万不要现在习惯的思路里面！

• 错也要错得不一样！
• 不找出路那就太自恋了！
• 像水仙花一样
• 掉水里就淹死了！

雉兔同籠

• 方法之外

• 用概念、数量之类的方式去抽象
  • 是很理性的
• 但
  • 也是很容易陷入概念的

总结

• 这次研究了雉兔同笼
• 其实我们很容易
  • 陷入循环
  • 陷入概念
  • 陷入抽象数字的陷阱
• 怎么样跳出循环
• 直击本质
• 确实是很难的事情
• 计算机程序不怕循环
• 计算机文件遍历也依赖循环
• 如何写程序去遍历文件？？🤔
• 下次再说 👋