最近在学习Python、算法和一些数学知识,希望自己能够在理解世界、抽象、建模方面能再有所前进,持续建设和完善自己。
倒水趣题:
有两个水瓶,一个的容量是9升,另一个的容量是4升。问如何才能从河中打出6升水?
分析过程:
设,9升的水瓶容量为A,4升的水瓶容量为B,6升水容量为C。
这道题的本质是,计算并判断,C能否被A和B来进行度量。求A和B的最大公因数(或称:最大公约数、最大公度)gcm(greatest common measure),进而判断出C能否被gcm度量。
C如果能够被A和B的gcm度量,那么这道题就可解,进而继续使用循环、以及合理的分支,进行处理逻辑的设计,最后编码实现,测试验证。最后再用大O表示法,判断一下最糟糕情况下的运行时间,看看能否进行算法优化。
解题过程:
环境:Windows 11 专业版,64 位操作系统;Python 3.11.1
代码测试及调试方式:IDLE Shell 3.11.1 终端(或Visual Studio Code终端),输入代码,按回车即可
一、首先判断C能否被A和B的gcm进行度量
(一)求A和B的最大公因数gcm:
1、辗转相除法
def calc_gcm(a, b):
while b != 0:
a, b = b, a % b
return a
2、递归法(自己调用自己)
def calc_gcm(a, b):
if b == 0:
return a
else:
return calc_gcm(b, a % b)
(二)判断C能否被A和B的最大公因数gcm进行度量,即整除
def judge_c(ab, c):
if c % ab == 0:
return 'ture'
else:
return 'false'
进行判断:
judge_c(calc_gcm(9, 4), 6)
得到的结果是:'ture'
二、算法设计、编码实现(要记得增加必要的注释哦,让未来的自己还能读懂它,这很重要)
辗转相减的解决方案:
import numpy as np
import csv
def pour(in1, in2, in3):
b = np.array([0, 0])
i = np.array([in1, in2])
d = in3
# 循环条件
while b[0] >= 0 and b[1] >= 0 and i[0] >= i[1] and i[0] >= d and b[0] != d:
if b[0] == 0:
# print(b)
"""给第一个桶,加满水"""
b[0] = i[0]
print('为A桶,加满水')
print(b)
else:
# b[0] > 0
if b[1] == i[1]:
"""第二个桶,水满,需倒空"""
b[1] = 0
print('B桶,水满,需倒空')
print(b)
elif b[1] == 0:
if b[0] >= i[1]:
"""第二个桶,空桶,第一个桶,可以为第二个桶倒满水"""
b[0] = b[0] - i[1]
b[1] = i[1]
print('A桶为空桶B加满水')
print(b)
elif b[0] < i[1]:
"""第二个桶,空桶,第一个桶,不可以为第二个桶倒满水"""
b[1] = b[1] + b[0]
b[0] = 0
print('A桶为空桶B加水')
print(b)
elif b[1] > 0 and b[1] < i[1]:
if b[0] < (i[1] - b[1]):
"""第二个桶,不是空桶,第一个桶不可以为第二个桶倒满水"""
b[1] = b[1] + b[0]
b[0] = 0
print('A桶为非空桶B加水')
print(b)
elif b[0] > (i[1] - b[1]):
"""第二个桶,不是空桶,第一个桶可以为第二个桶倒满水"""
b[0] = b[0] - (i[1] - b[1])
b[1] = i[1]
print('A桶为非空桶B加满水')
print(b)
print('结束')
print(b)
测试执行:
pour(9, 4, 6)
执行结果:
>>> pour(9, 4, 6)
为A桶,加满水
[9 0]
A桶为空桶B加满水
[5 4]
B桶,水满,需倒空
[5 0]
A桶为空桶B加满水
[1 4]
B桶,水满,需倒空
[1 0]
A桶为空桶B加水
[0 1]
为A桶,加满水
[9 1]
A桶为非空桶B加满水
[6 4]
结束
[6 4]
好啦,倒水趣题的每一步骤,都被很好的展示出来了,接下来,需要根据大O表示法,考虑一下算法优化了,等我再多学一些处理手段,再更新倒水趣题的新算法哈
补充知识:
如果遇到下载numpy模块失败的情况,需要使用国内的源,通过pip开展numpy模块安装
环境:Windows 11 专业版,64 位操作系统;Python 3.11
1、安装numpy模块:
pip install numpy -i https://pypi.tuna.tsinghua.edu.cn/simple
2、升级pip:
首先,打开【文件资源管理器】--访问【Python安装目录 D:\Program Files\Python\Python311\ 】
而后,在目录位置,输入其中的命令 【cmd】
输入其中的命令,升级pip到25.3 【python.exe -m pip install --upgrade pip==25.3 -i https://pypi.tuna.tsinghua.edu.cn/simple】
3、添加信任主机:
输入其中的命令,添加信任主机 【python -m pip install --trusted-host pypi.org --trusted-host files.pythonhosted.org numpy】