趣味算法题大全附详细解法

• 趣味算法题
  • 1000 桶水，其中一桶有毒，猪喝毒水后会在 15 分钟内死去，想用一个小时找到这桶毒水，至少需要几头猪？
  • 有一栋 100 层高的大楼，给你两个完全相同的玻璃球。假设从某一层开始，丢下玻璃球会摔碎。那么怎么利用手中的两个球，用什么最优策略知道这个临界的层是第几层?
  • 汉诺塔问题
  • 一个人爬楼梯，每次只能爬 1 个或 2 个台阶，假设有 n 个台阶，那么这个人有多少种不同的爬楼梯方法？
  • 斐波那契数列

趣味算法题

1000 桶水，其中一桶有毒，猪喝毒水后会在 15 分钟内死去，想用一个小时找到这桶毒水，至少需要几头猪？

提示: 转为多维问题。在轮次中存活的猪可以同时喝水

题解

扩展题:

1. 多桶有毒的情况？所有参数皆为可变参数的时候，如何来处理？ TODO

有一栋 100 层高的大楼，给你两个完全相同的玻璃球。假设从某一层开始，丢下玻璃球会摔碎。那么怎么利用手中的两个球，用什么最优策略知道这个临界的层是第几层?

提示：动态规划. 平均每种情况下的次数。

题解

扩展思路：

1. 多个球时，如何采用最优策略？
2. 如果 2 球时采用 10*10 = 100, 10 次作为间隔，最差 17 次, 最好 8 次. 如果 90 层没有碎，后面可以采用中分法来减少次数。如果 90 层碎了，则最坏情况为 9 + 8 = 17 次

汉诺塔问题

汉诺塔问题：古代有一个梵塔，塔内有三个座 A、B、C，A 座上有 64 个盘子，盘子大小不等，大的在下，小的在上。有一个和尚想把这个盘子从 A 座移到 B 座，但每次只能允许移动一个盘子，并且在移动过程中，3 个座上的盘子始终保持大盘在下，小盘在上。

题解

提示: 迭代法

一个人爬楼梯，每次只能爬 1 个或 2 个台阶，假设有 n 个台阶，那么这个人有多少种不同的爬楼梯方法？

提示: 迭代法

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

# 类似于 斐波那契数列
# 0 1 1 2 3 5 8 13 21

# 迭代法
def fun(n):
    if n == 1:
        return 1
    if n == 2:
        return 2
    return fun(n-1) + fun(n-2)

# 动态规划 存储计算中值，减少计算量
def fun(n):
    if n == 1:
        return 1
    if n == 2:
        return 2

    a = 1
    b = 2
    tmp = a + b
    for i in range(3, n):
        tmp = a + b
        a = b
        b = tmp
    return tmp

print(fun(6))

斐波那契数列

斐波那契数列的 5 种 python 实现写法