过河问题python实现

2024年4月21日 17:42 by wst

算法实践

---

今天媳妇考我一道题，肯定不能难住我，经过一番探索，最终解决。

题目

30个人坐一条船，结果超载了，需要有15个人下船。下船规则：

大家排成一队，排队位置即为它们的编号。

从1开始报数，数到9的人下船。

如此循环，直到船上仅剩15人。

问：都有哪些编号的人下船了？

分析

为了解决这个问题，假设所有人在一个数组lis中，编号为1到30；然后假设一个数组aim存储要下船的人的下标。seqs存储数数的序列，每到9个的时候就清空，重新往里入。假设i是数数的下标，解决方法如下：

1. 判断aim中的人数是否到15个人了，否则就执行下面的循环；

2. 判断i是否(结尾)等于30，如果是则让i=0;

3. 判断i是否在aim中，如果在则忽略i, 同时让i=i+1， 转到步骤1。

4. 如果i不在aim中，则把i放入seqs中；同时判断seqs的长度是否为9，如果是则清空seqs，把i放入aim中；

5. 执行i=i+1,为下一次循环做准备（转到步骤1）;

代码

lis = list(range(1, 31))    # 开始所有的人

aim = []    # 要下船的人的下标

seqs = []   # 数数的序列

i = 0       # 当前数到的人的下标

while len(aim)<15:    
    if i==30:
        i = 0 
    print("i:", i)      # debug
    if i in aim:
        print("被跳过了")
        i = i + 1
        continue
    seqs.append(i)
    if len(seqs) == 9:
        seqs = []
        aim.append(i)
    i = i + 1

    # print("seqs:", seqs)    # debug
    # print("aim:", aim)      # debug


rest = [x for idx,x in enumerate(lis) if idx not in aim]  # 留在船上的人

aim_person = [x+1 for x in aim]    # 下标加1为编号

print("下船的人的编号：", aim_person)

输出结果：

下船的人的编号： [9, 18, 27, 6, 16, 26, 7, 19, 30, 12, 24, 8, 22, 5, 23]

总结

如果更好的方法，欢迎评论！

后记

经过和媳妇讨论，更简单的实现诞生了：

lis = {key:1 for key in range(1,31)}

i = 1  # 数到的人的编号
j = 0  # 数到第几个人
k = 0  # 下船的人的个数

while k < 15:
    if i == 31:
        i = 1
    if lis[i] == 1:
        j += 1
        if j == 9:
            k += 1
            lis[i] = 0
            j = 0
    i += 1

print("要下船的人：", [k for k in range(1,31) if lis[k]==0])

输出结果：

要下船的人： [5, 6, 7, 8, 9, 12, 16, 18, 19, 22, 23, 24, 26, 27, 30]

 

---