上篇文章裡,說到,小程序找出了一個排列。對程序來說,找出所有沒有陷阱的排列代碼反而更簡單,因為邏輯判斷少了。
蚱蜢組長
蚱蜢副組長
為蚱蜢跳躍選排列
比如下面這6個互不相同的正整數,所有排列總數是6!=720,小樣,你5個元素的集合M,最多不就5個陷阱嘛,怕什麼!蚱蜢們都一起找吧。
互不相同的6個正整數:9, 4, 6, 2, 45, 12
包含5個元素的集合M:12,57,70,13,19
結果,312個紛紛掉進陷阱,408個跳到了終點!大家此刻想到了什麼?終點加個陷阱!
程序遍曆找排列
找到408種排列
有坑的路線很多,沒坑的也很多。所以證明會很難很難… 從網上找了三種證明方法,列在這兒。
1、第一個是反證法,是歸納總結裡帶着反證,看了,好像明白了。
反證法
2、第二個證明方法,證明的中心思想是“如果蚱蜢要嘗試的機會嚴格大于前方的陷阱個數的話,就一定會有一個機會,讓蚱蜢不落入陷阱”。看了,好像明白了。
高斯學堂證明法
3、第三個證明方法,标準答案,就是韋神的答案。圖片有點模糊,有些下标看不太清楚,不看了,等圖片清楚了再看。
韋神證明法
诓了這麼多蚱蜢。請請請~
烤螞蚱
油炸螞蚱
幹杯
和蚱蜢在一起的其他五道題。
一個都不會
,更多精彩资讯请关注tft每日頭條,我们将持续为您更新最新资讯!