Python算法——经典算法问题
经典算法问题 Python 实现合集
在编程学习中，算法是永恒的主题。今天给大家带来一系列经典算法问题的 Python 实现，涵盖了数学问题、游戏策略、数据结构等多个领域。每个案例都配有详细的分析和代码实现，非常适合算法初学者和面试备考的同学。
1. 五猴分桃问题
问题描述：海滩上有一堆桃子，五只猴子来分。第一只猴子把桃子分成五份，多了一个，它吃掉多的一个并拿走一份；第二只猴子把剩下的桃子又分成五份，也多了一个，它也吃掉多的一个并拿走一份；以后每只猴子都如此操作。问原来至少有多少个桃子？
def show(n):
for i in range(1, 6):
t = (n - 1) / 5
print('%d. 总数%d个, 第%i只猴吃一个, 拿走%s个。' % (i, n, i, t))
n = 4 * t
def fun():
k = 1
while True:
t = k
for i in range(4):
t = 5 * t + 1
if t % 4: break
t /= 4
else:
print(5 * t + 1)
show(5 * t + 1)
break
k += 1
fun()
算法思路：采用逆向递推，从最后一只猴子往前推，找到满足条件的最小整数解。
2. 三色旗问题
问题描述：有一个包含红、白、蓝三种颜色的数组，要求通过最少次数的交换，将数组排列成红、白、蓝的顺序。
import random
def fun(l):
count = 0
a = l.count(0)
b = a + l.count(1)
k1 = a
k2 = len(l) - 1
# 把第一个区域全部交换成白
for i in range(a):
if l[i] == 0:
continue
if l[i] == 1:
while l[k1] != 0: k1 += 1
k = k1
elif l[i] == 2:
while l[k2] != 0: k2 -= 1
k = k2
l[k] = l[i]
l[i] = 0
count += 1
# 把第二个区域全部交换成红
k = len(l) - 1
for i in range(a, b):
if l[i] == 2:
while l[k] != 1: k -= 1
l[k] = l[i]
l[i] = 1
count += 1
return count
t = [random.choice([0, 1, 2]) for i in range(30)]
print(t)
steps = fun(t)
print(t, steps)
算法思路：设置三个指针，分别指向白区、红区和蓝区，一次遍历完成交换。
3. 约瑟夫环问题
问题描述：n个人围成一圈，从第一个人开始报数，数到k的人出列，下一个人继续从1开始报数，求最后剩下的人。
class Node():
def __init__(self, value, next=None):
self.value = value
self.next = next
def createLink(n):
if n <= 0:
return False
if n == 1:
return Node(1)
else:
root = Node(1)
tmp = root
for i in range(2, n+1):
tmp.next = Node(i)
tmp = tmp.next
tmp.next = root
return root
def josephus(n, k):
if k == 1:
print('survive:', n)
return
root = createLink(n)
tmp = root
while True:
for i in range(k-2):
tmp = tmp.next
print('kill:', tmp.next.value)
tmp.next = tmp.next.next
tmp = tmp.next
if tmp.next == tmp:
break
print('survive:', tmp.value)
if __name__ == '__main__':
josephus(10, 4)
算法思路：使用循环链表模拟报数过程，每次删除第k个节点。
4. 过桥问题
问题描述：有n个人要过桥，每次最多两人，过桥需要手电筒，每个人过桥时间不同，两人一起过按时间长的算，求最短过桥时间。
def fun(arr, time=0):
ll = len(arr)
if ll == 1:
return arr[0]
if ll == 2:
return arr[1] + time
if ll == 3:
return arr[0] + arr[1] + arr[2] + time
x = 2 * arr[0] + arr[-1] + arr[-2]
y = arr[0] + 2 * arr[1] + arr[-1]
if x < y:
return fun(arr[0:ll-2], time + x)
else:
return fun(arr[0:ll-2], time + y)
arr = [2, 5, 6, 9, 13]
print(fun(arr))
算法思路：贪心策略，每次选择两种方案中较优的一种。
5. 取火柴游戏
问题描述：有21根火柴，两人轮流取，每次可取1-4根，取到最后一根者胜。实现一个AI对手。
import random
def fun(match):
idx = 0
while match > 1:
idx += 1
if idx % 2 == 1:
gamer = 'A'
choice = random.choice(range(1,5)) if match >= 5 else random.choice(range(1, match+1))
else:
gamer = 'B'
if match > 5:
for x in range(1, 5):
if (match - x) % 5 == 1:
choice = x
break
else:
choice = match - 1
match -= choice
print(gamer, choice, match)
another = 'A' if gamer == 'B' else 'B'
loser = gamer if match == 0 else another
print('%s 胜利!' % loser)
fun(21)
算法思路：利用数学规律，保持剩余火柴数为5的倍数加1。
6. 年龄问题
问题描述：四个人年龄成等差数列，年龄和为26，乘积为880，求各自的年龄。
def sum(a, k, n):
s = a
for i in range(1, n):
s += a + i * k
return s
def mul(a, k, n):
s = a
for i in range(1, n):
s *= a + i * k
return s
for a in range(1, 26 // 4):
find = False
k = 1
while True:
t = sum(a, k, 4)
if t >= 26:
if t == 26 and mul(a, k, 4) == 880:
find = True
break
k += 1
if find:
for i in range(20):
print(a + i * k)
算法思路：枚举首项和公差，检查是否满足和与积的条件。
7. 三色球问题
问题描述：红、黄、蓝三种球，红球最多3个，黄球最多3个，蓝球最少2个，总数为8个，求所有可能的组合。
print('red\tyellow\tblue')
for red in range(0, 4):
for yellow in range(0, 4):
for green in range(2, 7):
if red + yellow + green == 8:
print(red, '\t', yellow, '\t', green)
算法思路：三重循环枚举所有可能，检查总数条件。
8. 鸡兔同笼问题
问题描述：经典的鸡兔同笼问题，输入脚的总数和头的总数，计算鸡和兔各有多少只。
while True:
try:
sum = eval(input("请输入鸡和兔子脚的总数: "))
head = eval(input("请输入鸡和兔子头的总数: "))
if sum < 6:
print("输入鸡和兔子脚的总数错误请重新输入>>>")
elif head < 2:
print("输入鸡和兔子头的总数错误请重新输入>>>")
else:
j = 0
t = 0
flag = False
while j < head:
j += 1
t = head - j
if (sum == (j * 2 + t * 4)):
print("有鸡 %d只，兔子 %d只" % (j, t))
except:
print("能不能好好玩？")
算法思路：枚举鸡的数量，计算兔的数量，检查脚数是否匹配。
9. 井深问题
问题描述：五个人用绳子测井深，每个人测量的方式不同，求井深和各人绳长。
def fun():
e = 0
while True:
e += 4
a = 0
while True:
a += 5
d = e + a / 5
c = d + e / 4
if c % 2 != 0 or d % 3 != 0:
continue
b = c + d / 3
if b + c / 2 < a:
break
if b + c / 2 == a:
deep = 2 * a + b
print('a--> %d, b--> %d, c--> %d, d--> %d, e--> %d, deep--> %d' % (a, b, c, d, e, deep))
return a, b, c, d, e, deep
print(fun())
算法思路：根据方程组推导，满足整除条件求解。
10. 金鱼问题
问题描述：某人卖金鱼，第一次卖掉总数的一半加1/2条，第二次卖掉剩下的1/3加1/3条，依次类推，最后剩下11条，求原来有多少条。
n = 11
while True:
x = n
for i in range(2, 5+1):
x = x - (x/i + 1/i)
if x == 11:
print(n)
x = n
for i in range(2, 5+1):
m = x/i + 1/i
x = x - m
print('%d: mai-->%d shend-->%d' % (i-1, m, x))
break
n = n + 1
算法思路：逆向递推，从最后结果往前推算初始值。
11. 借书问题
问题描述：5本书借给3个人，每人最多借一本，求所有可能的借法。
count = 0
print("假设五本书分别为1，2，3，4，5，主要借法有")
for a in range(1, 6):
for b in range(1, 6):
if a != b:
for c in range(1, 6):
if c != a and c != b:
count += 1
print("第%d种：A分到书%d,B分到书%d,C分到书%d" % (count, a, b, c))
算法思路：三重循环枚举，确保三个人拿到的书不同。
12. 分椰子问题
问题描述：海滩上有一堆椰子，五个人分，每次分成5份多一个，求原来至少有多少个椰子。
def xf(n):
a = 1
b = a
while 1:
for i in range(n-1):
a = (a-1)/n*(n-1)*1.0
if (a-1) % n == 0:
return b
b += 1
a = b
print(xf(5))
算法思路：类似五猴分桃问题，逆向推导。
13. 传教士与野人过河问题
问题描述：n个传教士和n个野人过河，船最多载m人，任何一边传教士人数不能少于野人（除非该边没有传教士），求过河方案。
n = 3 # n个传教士、n个野人
m = 2 # 船能载m人
x = [] # 一个解
is_found = False
def get_states(k):
if k % 2 == 0:
s1, s2 = n - sum(s[0] for s in x), n - sum(s[1] for s in x)
else:
s1, s2 = sum(s[0] for s in x), sum(s[1] for s in x)
for i in range(s1 + 1):
for j in range(s2 + 1):
if 0 < i + j <= m and (i * j == 0 or i >= j):
yield [(-i, -j), (i, j)][k % 2 == 0]
def conflict(k):
if k > 0 and x[-1][0] == -x[-2][0] and x[-1][1] == -x[-2][1]:
return True
if 0 < n - sum(s[0] for s in x) < n - sum(s[1] for s in x):
return True
if 0 < sum(s[0] for s in x) < sum(s[1] for s in x):
return True
return False
def backtrack(k):
global is_found
if is_found: return
if n - sum(s[0] for s in x) == 0 and n - sum(s[1] for s in x) == 0:
print(x)
is_found = True
else:
for state in get_states(k):
x.append(state)
if not conflict(k):
backtrack(k + 1)
x.pop()
backtrack(0)
算法思路：状态空间搜索，使用回溯法，每次生成合法的船载状态，检查两岸是否满足约束条件。
总结
以上13个经典算法问题涵盖了数学推理、贪心策略、回溯搜索、链表操作等多种算法思想。通过实现这些案例，不仅可以加深对Python语言的理解，还能提升解决实际问题的能力。每个问题都有其独特的思维亮点，建议读者亲自运行代码，观察输出结果，理解算法背后的数学原理。
