PDF《科别：数学科》

科别:数学科 组别:高中组 作品名称:如何最快? 关键词:最佳化、排列组合、逻辑推理 编号:040410 学校名称: 国立花莲高级中学 作者姓名: 陈渊琮、黄承伟、李孟璁、刘恒敬 指导老师: 彭成钿、江俊宏 摘要 从一开始过桥最短时间的单一讨论,进而分析其它日常生活事例的本身限制,寻求其最 佳化的结果.

举凡:滑草(坡度)、健行(秒数渐增),甚至有些个别想法的有趣实验(趟数),都 设法去归纳出一定的规则. 壹、研究动机 学校的资讯课出了个「过桥」的程式挑战,最难的部分在於一开始的数学归纳和逻辑推 理.由於条件的限制,加上可能性多样,逻辑性的缜密是解题的基础.再者,需要寻求各个 关系式的规律性,达到最佳化的效果.仔细分析题干的要求,内容包含了排列组合等相关数 学技巧,在没有标准答案的情况下,基於好奇心的驱使,和想要解决难题的j望,开始著手 实验研究. 贰、研究目的 整个研究一方面不只是为了满足解决难题的乐趣,另一方面也积极寻求在日常生活中常 见问题的答案.寻求事件的最佳化,将助於事情的处理效率,也意涵将数学结合生活的妙趣. 参、研究设备与器材 笔、纸、电脑、人脑 肆、研究与讨论 1. 过桥 题目:晚上时,有n人要过一座桥,每次最多限载

2 人,且每人过桥速度不一,快 的人要等慢的人.过桥时,每组人员均需要油灯辅助,而现在油灯只有一盏, 每一组过去后皆需要请该岸的某个人提灯返回.现为了避免油灯在中途熄 灭,因此需要做个过桥顺序的排列,才能使大家用最短的时间过完这座桥. 想法:设法缩短「回程时间」 ,用最快者带灯回来为优先考虑. 「由最快脚程带灯回来」是指速度最快者充当每趟的灯持有者(最快脚程者带灯回来). 走法: 「最快脚程带灯来回」(包括带人过桥和带灯回来). 为了印证此想法,便尝试以最快脚程带灯来回和非最快脚程带灯来回来作为对照. 测试数:(

1、

2、

4、

7、8) 由最快脚程带灯来回 不一定最快脚程带灯来回(乱凑) 左右时间 左右时间 2,4,7 → 1,8

8 4,7,8 → 1,2

2 1,2,4,7 ←

8 1 2,4,7,8 ←

1 2 2,4, → 1,7,8

7 2,8 → 1,4,7

7 1,2,4 ← 7,8

1 2,4,8 ← 1,7

4 2 → 1,4,7,8

4 2 → 1,4,7,8

8 1 1,2 ← 4,7,8

1 1,2 ← 4,7,8

1 → 1,2,4,7,8

2 → 1,2,4,7,8

2 24

26 由这组数夏阎苯涌闯鍪

2 秒的差异点,於是将数宰稣,便不难做出判断.(如下表) 最快脚程带灯来回

8 1

7 1

4 1

2 不一定最快脚程带灯来回 C)

2 2

7 4

8 1

2 -2 (快2秒) 第一个想法是比较直观的看法,但是否还有其他更快的走法呢?於是便推出了另一种想 法. 想法:(1)最慢两人合并过桥,即可不计其中一人的时间. (2)回程时间不宜太长. 走法:利用速度最快的两人搭配以运送最慢两人过桥,而不需最慢两者将灯送回. 此走法称为「新法」 测试数:(

1、

2、

4、

7、8) 新法 最快脚程带灯来回 左右时间 左右时间 4,7,8 → 1,2

2 2,4,7 → 1,8

8 1,4,7,8 ←

2 1 1,2,4,7 ←

8 1 1,4 → 2,7,8

8 2,4, → 1,7,8

7 1,2,4 ← 7,8

2 1,2,4 ← 7,8

1 4 → 1,2,7,8

2 2 → 1,4,7,8

4 1,4 ← 2,7,8

1 1,2 ← 4,7,8

1 → 1,2,4,7,8

4 → 1,2,4,7,8

2 20

24 所使用的新方法,竟比原来的快多了

4 单位时间.为了推究时间省下的原因,将数字整理对 照. 新法