论文部分内容阅读
“群牛问题”在古希腊科学家阿基米德的研究课题中比较特别,是以诗句的形式出现在给埃拉托塞尼的一封信中。虽然其真实性有待考证,因为“群牛问题”大概很早以前就已存在,阿基米德只是重新研究而已,但历史上对这个问题的研究,却丰富了初等数论的内容。
下面我们也来分析一下群牛问题,并用Python求解验证。
太阳神有一牛群,由白、黑、花、棕四种颜色的公、母牛组成。
在公牛中,白牛数多于棕牛数,多出之数相当于黑牛数的1/2+1/3;黑牛数多于棕牛数,多出之数相当于花牛数的1/4+1/5;花牛数多于棕牛数,多出之数相当于白牛数的1/6+1/7。
在母牛中,白牛数是全体黑牛数的1/3+1/4;黑牛数是全体花牛数1/4+1/5;花牛数是全体棕牛数的1/5+1/6;棕牛数是全体白牛数的1/6+1/7。
问这牛群是怎样组成的?
通过了解知名数学难题的解题思路,并将其用于Python编程,提高我们的数学和编程水平。在我搜索的“100个数学难题”中第一个问题就是“群牛问题”,经过分析和研究,自觉颇有收获。
这是一道解不定方程组问题,有8个未知数,7个方程,有无数组解,我们可以求出最小正整数解。这个解数值较大,即使通过Python求最小正整数解也不容易。
按照编程解方程的惯性思路,方程的解可以使用枚举法去求。结果当Python程序运行后却没有输出结果(所有程序后面给出)。分析原因发现是因为解的数值过大,必须寻求更好的求解方法。
最普通的思路,不需要过多考虑,用枚举法一个个去测试(图1)。
测试1万个数的时间复杂度是10的12次方,需要运行30多个小时。通过搜索已知最小正整数解的值很大,枚举法获得结果的时间过长,必须去寻找更简捷的方法。
(1)验证解出错
在网上搜索到了群牛问题的一组正整数解,代入方程直接验证,运行结果后面4个全部为“False”(图2)。
False表示解并不符合原題目的这项条件(图3)。
(2)验证另一组带n的解也出错
搜索到的另一组解是带n的,代入方程验证结果更奇怪(图4)。
当n=1时,有两个“False”(图5)。
当n=5时,有1个“False”(图6)。
为什么我把搜到的答案拿来验证都没法通过,问题出在哪里呢?为什么不同的解验算的“False”数目还不一样?
在分析这些问题产生的原因过程中,我发现了一个库函数Sympy,它可以帮我解决问题!
(1)SymPy库简介
SymPy库函数是一个符号计算的Python库。它的目标是成为一个全功能的计算机代数系统,同时保持代码简洁、易于理解和扩展。它完全由Python写成,不依赖于外部库。SymPy支持符号计算、高精度计算、模式匹配、绘图、解方程、微积分、组合数学、离散数学、几何学、概率与统计、物理学等方面的功能。
SymPy的安装和使用这里不做介绍,我只分析它求解方程的方法SymPy.solve()。Solve()是一个数学术语,主要是用来求解代数方程(多项式方程)的符号解析解。
(2)方程求解:先看个简单例子(图7)。运行就可以直接求出方程的解{x: -1, y: 4},感觉到Python的强大了吗?
(3) 群牛问题求解方程
下面我们也来分析一下群牛问题,并用Python求解验证。
(一)群牛问题
太阳神有一牛群,由白、黑、花、棕四种颜色的公、母牛组成。
在公牛中,白牛数多于棕牛数,多出之数相当于黑牛数的1/2+1/3;黑牛数多于棕牛数,多出之数相当于花牛数的1/4+1/5;花牛数多于棕牛数,多出之数相当于白牛数的1/6+1/7。
在母牛中,白牛数是全体黑牛数的1/3+1/4;黑牛数是全体花牛数1/4+1/5;花牛数是全体棕牛数的1/5+1/6;棕牛数是全体白牛数的1/6+1/7。
问这牛群是怎样组成的?
(二)创意来源
通过了解知名数学难题的解题思路,并将其用于Python编程,提高我们的数学和编程水平。在我搜索的“100个数学难题”中第一个问题就是“群牛问题”,经过分析和研究,自觉颇有收获。
这是一道解不定方程组问题,有8个未知数,7个方程,有无数组解,我们可以求出最小正整数解。这个解数值较大,即使通过Python求最小正整数解也不容易。
(三)设计思路
按照编程解方程的惯性思路,方程的解可以使用枚举法去求。结果当Python程序运行后却没有输出结果(所有程序后面给出)。分析原因发现是因为解的数值过大,必须寻求更好的求解方法。
(四)程序设计过程
1.枚举法
最普通的思路,不需要过多考虑,用枚举法一个个去测试(图1)。
测试1万个数的时间复杂度是10的12次方,需要运行30多个小时。通过搜索已知最小正整数解的值很大,枚举法获得结果的时间过长,必须去寻找更简捷的方法。
2.对已知答案验证出错
(1)验证解出错
在网上搜索到了群牛问题的一组正整数解,代入方程直接验证,运行结果后面4个全部为“False”(图2)。
False表示解并不符合原題目的这项条件(图3)。
(2)验证另一组带n的解也出错
搜索到的另一组解是带n的,代入方程验证结果更奇怪(图4)。
当n=1时,有两个“False”(图5)。
当n=5时,有1个“False”(图6)。
为什么我把搜到的答案拿来验证都没法通过,问题出在哪里呢?为什么不同的解验算的“False”数目还不一样?
在分析这些问题产生的原因过程中,我发现了一个库函数Sympy,它可以帮我解决问题!
3.SymPy库函数
(1)SymPy库简介
SymPy库函数是一个符号计算的Python库。它的目标是成为一个全功能的计算机代数系统,同时保持代码简洁、易于理解和扩展。它完全由Python写成,不依赖于外部库。SymPy支持符号计算、高精度计算、模式匹配、绘图、解方程、微积分、组合数学、离散数学、几何学、概率与统计、物理学等方面的功能。
SymPy的安装和使用这里不做介绍,我只分析它求解方程的方法SymPy.solve()。Solve()是一个数学术语,主要是用来求解代数方程(多项式方程)的符号解析解。
(2)方程求解:先看个简单例子(图7)。运行就可以直接求出方程的解{x: -1, y: 4},感觉到Python的强大了吗?
(3) 群牛问题求解方程