国王的婚姻

来自计算思维百科
跳转至: 导航搜索
国王的婚姻.png

从前,有一个酷爱数学的年轻国王向邻国一位美丽聪明的公主求婚。公主出了这样一道题:求出48 770 428 433 377 171的一个真因子。若国王能在一天之内求出答案,公主便接受他的求婚?那么国王最后有没有跟公主结婚呢?

解决方案

真因子:能够整除正整数的不是1也不是正整数本身的正整数。求48 770 428 433 377 171的一个真因子,显然国王可以从2到48 770 428 433 377 170,用每个数去除48 770 428 433 377 171看是不是能够整除,这种方式是穷举法,体现机械式的思维方式。

更好的方法是将问题分解成小问题,同时让多人帮国王计算,这就体现了分解的计算思维。

方案一:穷举法

国王回去后立即开始逐个数地进行计算,他从早到晚,共算了3万多个数,最终还是没有结果。如果要一个一个算,要从2算到48 770 428 433 377 170,不知道要多久才能找到一个。于是国王向公主求情,公主将答案相告:223 092 827 是它的一个真因子。国王很快就验证了这个数能除尽48 770 428 433 377 170。公主说:“我再给你一次机会,如果还求不出,将来你只好做我的证婚人了。”

方案二:分治法

国王立即回国,向时任宰相的大数学家求教,大数学家在仔细思考后认为这个数17位,则最小的一个真因子不会超过9位,于是他给国王除了一个主意:按自然数的顺序给全国的老百姓每人编一个人号发下去,让每个老百姓用自己的编号去除这个数,除尽了立即上报并赏金两万。最后,国王用这种方法求婚成功。

体现的计算思维

国王的婚姻这个问题有两种解决方案,一种是蛮力法,体现了计算思维的机械化特点;另一种是分治法,利用很多人同时处理这个问题,本质上是一个并行处理的概念,体现了计算思维的并行特点。