編程解決算法問題，窮舉思想輕松學

我們在數(shù)橙科學中Python的極客戰(zhàn)記很多關(guān)卡在向孩子教學代碼的同時，也是在潛移默化地訓練孩子的編程思維。

在學習「While-True」循環(huán)語句的同時，訓練使用「循環(huán)思維」解決重復問題的能力：

1.發(fā)現(xiàn)并拆解重復部分

2.解決重復問題

3.循環(huán)運行問題的解決方法

這樣，就能只用一段代碼，高效地解決重復問題了。可見，在編程中，學習代碼的編寫只是基本，更重要的還是掌握運用代碼的編程思維。

一、農(nóng)民過河問題

在編程的數(shù)道經(jīng)典算法問題中，有一個「農(nóng)夫過河」問題：一個農(nóng)夫帶著一只狼、一只羊和一些菜過河。河邊只有一條船，由于船太小，只能裝下農(nóng)夫和他的一樣東西，在無人看管的情況下，狼要吃羊，羊要吃菜，請問農(nóng)夫如何才能使三樣東西平安過河。

為了用代碼解決這個問題，程序員需要利用「窮舉搜索思想」，嘗試所有的過河方案，直到找出正確的過河方案。

二、士兵、食人魔和農(nóng)民

關(guān)卡地址：https：//codecombat.163.com/play/level/soldier-ogre-

and-peasant？

關(guān)卡介紹：

你需要使用獅鷲，把士兵、食人魔、農(nóng)民，帶去河的對岸，獅鷲每次只能帶一個人離開，而食人魔會傷害農(nóng)民，士兵會攻擊食人魔，因此不要讓士兵和食人魔單獨留在一起，也不要讓食人魔和農(nóng)民單獨留在一起。

在本關(guān)，我們可以學習一下如何使用「窮舉思想」解決編程問題。

三、窮舉是什么？

窮舉是什么呢？它有著一個高大上的名字，但它的本質(zhì)卻十分的簡單樸實。

窮舉法的基本思想：根據(jù)題目的部分條件確定答案的大致范圍，并在此范圍內(nèi)對所有可能的情況逐一驗證，直到全部情況驗證完畢。

簡單來說就是：把所有的答案都試一遍，找出正確的答案。

非常的簡單粗暴。因此，它也是編程中效率較低的一種算法。使用窮舉法，通常需要三步：解析題目——優(yōu)化運算過程——開始窮舉。我們來試試利用窮舉法解決關(guān)卡「士兵、食人魔和農(nóng)民」吧！

四、解析題目

窮舉法的第一步就是分析題目，把原本的文字題目，轉(zhuǎn)化成更易于分析，簡潔有邏輯的題目類型。

（一）題目的對象

題目看似只是三個人的過河問題，但實際上在題目里有四個人物：獅鷲、士兵、食人魔、農(nóng)民。獅鷲負責幫助大家過河。

（二）題目的條件

（1）士兵和食人魔不能單獨留在一起；

（2）食人魔和農(nóng)民也不能單獨留在一起。

也就是說，當獅鷲、士兵、食人魔待在一起的時候，也不會發(fā)生問題，因為士兵和食人魔馬上就要被獅鷲運走，來不及打架。

（三） 題目的狀態(tài)

我們需要使用獅鷲來幫助他們從右邊飛到左邊，因此題目具有以下幾種可能發(fā)生的情況：

1.左邊有士兵、食人魔、農(nóng)民、獅鷲，右邊什么都沒有。

2.左邊有食人魔、農(nóng)民、獅鷲，右邊有士兵。

3.左邊有農(nóng)民、獅鷲，右邊有士兵、食人魔。

……等等多種情況

（四） 優(yōu)雅地表示題目

可以看到，用文字表示題目可能發(fā)生的情況，十分復雜。因此，在編程中，我們常常會用一些特定的符號來簡潔地表達題目可能發(fā)生的情況。

看看題目，人物只會有兩種狀態(tài)，在右邊（還沒過河），在左邊（過河了），因此我們可以直接用0、1來表示人物的位置。

0表示還沒過河；1表示已經(jīng)過河。

那么就可以這樣表示：（獅鷲、士兵、食人魔、農(nóng)民）

1. （1，1，1，1）表示所有人物都已過河，到了左邊。

2. （1，0，1，1）表示食人魔和農(nóng)民過了河，士兵還沒有。

3.……等等

用這種簡潔的方式，把題目的所有情況表示出來就是：共16種狀態(tài)（如圖）。

根據(jù)題目的條件，我們可知，有以下幾種情況是不可取的：農(nóng)民和食人魔單獨在一起：（0，0，1，1）、（1，1，0，0）；士兵和食人魔單獨在一起：（0，1，1，0）、（1，0，0，1）；還有兩種隱含的不可取條件：

只有獅鷲自己在一邊：（1，0，0，0），這表示，所有人都沒過河，只有獅鷲過河了，而獅鷲本來就是幫助大家過河的，不可能自己單獨待在河的一邊。所以這種情況是不會發(fā)生的。

那么同理還有：（0，1，1，1）這種情況，所有人都過了河，獅鷲沒有過河，這也不會發(fā)生。

那么本題的問題就變成了：如何在符合條件的情況下，把（0，0，0，0）轉(zhuǎn)化成（1，1，1，1）。