每日彙整: 2015-07-12

樹莓派、樹莓派之學習、樹莓派之教育

勇闖新世界︰ 《 pyDatalog 》 導引《七》…

在我們進一步探討『台北捷運網』之前，先回顧一下『遞迴』這個重要『概念』，《 λ 運算︰計物數《遞迴補遺》》一文中談到︰

為什麼數學上常常要用『遞迴定義』的呢？假使你出於『好玩』，想『定義』一個『數列』，那麼有什麼『簡單』的辦法的呢？

有人說︰這很簡單啊！就給一個 F_n 『公式』Formula 就好了，就好比講這個數列是

F_n =_{df} \Box \Box, n=0 \cdots \infty。

有人問︰萬一你不知道『那個公式』呢？還是說如果『公式不存在』這樣子就根本『沒辦法』去定義『數列』的呢？

有人答︰『可以』的啊！比方說假使你『知道』

一、F_0 的『值』

二、曉得如何從 F_k 『計算』出 F_{k+1} 的『值』，這樣就算是不知道 F_n 是能不能夠表達，一樣可以『定義』這個『數列』的啊！

據說義大利的數學家李奧納多‧費波那契 Leonardo Fibonacci 描述各代『兔子生育』總數目時得到這個數列︰

F_0 = 0
F_1 = 1
F_n = F_{n-1} + F_{n-2}

因此 F_2 = F_1 + F_0 = 1 + 0 = 1, F_3 = F_2 + F_1 = 1 + 1 = 2. \cdots，所以可以逐步的得到『費波那契數列』。當然可以求解那一個『差分方程式』得到

F_{n}=\frac{\sqrt{5}}{5} \cdot \left[\left(\frac{1 + \sqrt{5}}{2}\right)^{n} - \left(\frac{1 - \sqrt{5}}{2}\right)^{n}\right]。

然而並非所有可以『遞迴定義』的數列，都能有『公式解』，或者說還沒將它『算出來』。所以能這樣從幾個『初始資料』和一個『遞迴關係』來定義東西的方式，自然有它的好處的了。

一般人們用程式計算『數列』a_n 的『級數和』

S_n = a_0 + a_1+\cdots +a_n

，很自然的會用『疊代』的想法，可以表達為

R := a_0
R := R+ a_n, n=1 \cdots N

，此處『:=』表示變數『賦值』，逐項累加到所需要的 N 次。這或許是大部分的程式語言都有『FOR LOOP』的原因。但是遇到了像『河內塔』這一類問題，由於那個 a_n 本身就先需要計算出來，況且還和 a_k, k=1 \cdots n-1 有關，這時想寫個『疊代法』程式就很困難的了。所以『方法選擇』應當針對『問題狀況』，難有『萬能之法』的啊！……

這個『費波那契數』我們可以用著『pyDatalog 範例』中所講的『縮寫』辦法，寫作如下︰

>>> pyDatalog.create_terms('費波那契數')
>>> 費波那契數[N] = 費波那契數[N - 1] + 費波那契數[N - 2]
>>> 費波那契數[0] = 0
>>> 費波那契數[1] = 1
>>> print(費波那契數[5] == N)
N
-
5
>>>

由於這樣的作法『駕輕就熟』，以至於有時會『忘記』，或許根本不知道這個『縮寫』是指，下面的程式，

>>> pyDatalog.create_terms('factorial, N')
>>> factorial[N] = N*factorial[N-1]
>>> factorial[1] = 1
>>> print(factorial[25]==N)
N                         
--------------------------
15511210043330985984000000
>>>

『語法』上『完整』的寫法是︰

>>> pyDatalog.create_terms('階乘,T數')
>>> (階乘[N] == T數) <= (T數 == N * 階乘[N - 1]) 
階乘[1]==(*,N,T數) <= 階乘[1]==(*,(N-'1'),_pyD_X28)&==(
>>> (階乘[1] == T數) <= (T數 == 1) 
階乘[1]==(*,'1',T數) <= ==(T數,'1')
>>> print(階乘[3] == T數)
T數
--
6 
>>>

或許反而容易誤解下面的『條件取值』的意義，以及事實上陳述的『內容』與『條件安排』相關的事實了。

# the tax rate for salaries above 0 is 33%, and above 100 is 50 %
(tax_rate_for_salary_above[X] == 0.33) <= (0 <= X)
(tax_rate_for_salary_above[X] == 0.50) <= (100 <= X)
print(tax_rate_for_salary_above[70]==Y)
print
print(tax_rate_for_salary_above[150]==Y)

為什們人們覺得『遞迴思維』很困難呢？或許是因為還不『習慣』這麼一種思考方式。也由於它要求『邏輯之嚴密』性，否則很可能會自陷泥沼，自相矛盾的吧！舉個例子︰讀者可以想一想要如何用『遞迴』表達簡單的自然數之『加法』和『乘法』呢？嘗試寫一個 pyDatalog 程式，在這個過程裡，你將對 pyDatalog 語言，以及遞迴『終止條件』都能有更深入的了解！【※參考程式】

>>> pyDatalog.create_terms('加,乘, X數, Y數')
>>> 加[X數, Y數] = 1 + 加[X數, Y數 - 1]
>>> 加[X數, 0] = 1 + 加[X數 - 1, 0]
>>> 加[0, 0] = 0
>>> pyDatalog.create_terms('Z數')
>>> print(加[3, 2] == Z數)
Z數
--
5 
>>> print(加[7, 8] == Z數)
Z數
--
15
>>> 乘[X數, Y數] = 加[X數, 0] + 乘[X數, Y數 - 1]
>>> 乘[X數, 1] = 加[X數, 0]
>>> print(乘[3, 2] == Z數)
Z數
--
6 
>>> print(乘[7, 8] == Z數)
Z數
--
56
>>>

如果說人們常常卡在『字面意義』上，是指『語法』上不如電腦的一板一眼，『語意』上不像計算機般斤斤計較，也許此時讀一讀

《 λ 運算︰計物數》《上》‧《中》‧《下》三篇文章，多一些『思考機會』，累積些『實務經驗』，也許可以是個『起始點』的吧。

如是我們是否已能『解讀』下面文本之『片段』的呢？！

 

【例子捷運網】

台北捷運

 

【所有路徑述詞定義】

‧ 所有路徑(X站名, Y站名, P路徑甲) <=

所有路徑(X站名, Z站名, P路徑乙) & 【※前段】

連接(Z站名, Y站名) & 【※後段】

(X站名 != Y站名) & 【※避免迴路】

(X站名._not_in(P路徑乙)) & 【※避免迴路】

(Y站名._not_in(P路徑乙)) & 【※避免迴路】

(P路徑甲 == P路徑乙 + [Z站名]) 【※ 經過路徑累計】

 

‧ 所有路徑(X站名, Y站名, P路徑甲) <=

連接(X站名, Y站名) & 【※基本連接事實】

(P路徑甲 == []) 【※基本直通，無經由路徑。】

 

【範例程式】

# 探尋一般情況
>>> 所有路徑(X站名, Y站名, P路徑甲) <= 所有路徑(X站名, Z站名, P路徑乙) & 連接(Z站名, Y站名) & (X站名 != Y站名) & (X站名._not_in(P路徑乙)) & (Y站名._not_in(P路徑乙)) & (P路徑甲 == P路徑乙 + [Z站名])
所有路徑(X站名,Y站名,P路徑甲) <= 所有路徑(X站名,Z站名,P路徑乙)&連接(Z站名,Y站
>>> 所有路徑(X站名, Y站名, P路徑甲) <= 連接(X站名, Y站名) & (P路徑甲 == []) 
所有路徑(X站名,Y站名,P路徑甲) <= 連接(X站名,Y站名)&==(P路徑甲,'[]')
>>> print(所有路徑('台北車站', '世貿台北101', P路徑甲))

P路徑甲
                                                                                                         
-------------------------------------------------------------------------------------------------------------
('西門', '小南門', '中正紀念堂', '東門', '大安森林公園', '大安', '信義安和')                                                         
('善導寺', '忠孝新生', '松江南京', '中山', '北門', '西門', '小南門', '中正紀念堂', '東門', '大安森林公園', '大安', '信義安和')                      
('台大醫院', '中正紀念堂', '東門', '忠孝新生', '松江南京', '南京復興', '忠孝復興', '大安', '信義安和')                                        
('西門', '小南門', '中正紀念堂', '東門', '忠孝新生', '忠孝復興', '大安', '信義安和')                                                   
('西門', '小南門', '中正紀念堂', '古亭', '東門', '忠孝新生', '忠孝復興', '大安', '信義安和')                                             
('善導寺', '忠孝新生', '東門', '大安森林公園', '大安', '信義安和')                                                                
('善導寺', '忠孝新生', '忠孝復興', '南京復興', '松江南京', '中山', '北門', '西門', '小南門', '中正紀念堂', '東門', '大安森林公園', '大安', '信義安和')      
('西門', '北門', '中山', '松江南京', '南京復興', '忠孝復興', '大安', '信義安和')                                                     
('台大醫院', '中正紀念堂', '小南門', '西門', '北門', '中山', '松江南京', '忠孝新生', '忠孝復興', '大安', '信義安和')                             
('台大醫院', '中正紀念堂', '東門', '忠孝新生', '忠孝復興', '大安', '信義安和')                                                        
('中山', '北門', '西門', '小南門', '中正紀念堂', '東門', '忠孝新生', '忠孝復興', '大安', '信義安和')                                       
('中山', '北門', '西門', '小南門', '中正紀念堂', '東門', '大安森林公園', '大安', '信義安和')                                             
('善導寺', '忠孝新生', '忠孝復興', '南京復興', '松江南京', '中山', '北門', '西門', '小南門', '中正紀念堂', '古亭', '東門', '大安森林公園', '大安', '信義安和')
('善導寺', '忠孝新生', '東門', '古亭', '中正紀念堂', '小南門', '西門', '北門', '中山', '松江南京', '南京復興', '忠孝復興', '大安', '信義安和')          
('台大醫院', '中正紀念堂', '小南門', '西門', '北門', '中山', '松江南京', '南京復興', '忠孝復興', '大安', '信義安和')                             
('中山', '北門', '西門', '小南門', '中正紀念堂', '古亭', '東門', '大安森林公園', '大安', '信義安和')                                       
('西門', '小南門', '中正紀念堂', '古亭', '東門', '大安森林公園', '大安', '信義安和')                                                   
('中山', '松江南京', '忠孝新生', '東門', '大安森林公園', '大安', '信義安和')                                                         
('中山', '北門', '西門', '小南門', '中正紀念堂', '東門', '忠孝新生', '松江南京', '南京復興', '忠孝復興', '大安', '信義安和')                       
('善導寺', '忠孝新生', '忠孝復興', '大安', '信義安和')                                                                        
('西門', '北門', '中山', '松江南京', '南京復興', '忠孝復興', '忠孝新生', '東門', '大安森林公園', '大安', '信義安和')                             
('西門', '北門', '中山', '松江南京', '忠孝新生', '東門', '大安森林公園', '大安', '信義安和')                                             
('台大醫院', '中正紀念堂', '小南門', '西門', '北門', '中山', '松江南京', '忠孝新生', '東門', '大安森林公園', '大安', '信義安和')                     
('台大醫院', '中正紀念堂', '東門', '大安森林公園', '大安', '信義安和')                                                              
('西門', '小南門', '中正紀念堂', '東門', '忠孝新生', '松江南京', '南京復興', '忠孝復興', '大安', '信義安和')                                   
('台大醫院', '中正紀念堂', '古亭', '東門', '大安森林公園', '大安', '信義安和')                                                        
('中山', '松江南京', '南京復興', '忠孝復興', '忠孝新生', '東門', '大安森林公園', '大安', '信義安和')                                         
('西門', '小南門', '中正紀念堂', '古亭', '東門', '忠孝新生', '松江南京', '南京復興', '忠孝復興', '大安', '信義安和')                             
('善導寺', '忠孝新生', '松江南京', '南京復興', '忠孝復興', '大安', '信義安和')                                                        
('中山', '松江南京', '南京復興', '忠孝復興', '大安', '信義安和')                                                                 
('中山', '北門', '西門', '小南門', '中正紀念堂', '古亭', '東門', '忠孝新生', '忠孝復興', '大安', '信義安和')                                 
('台大醫院', '中正紀念堂', '古亭', '東門', '忠孝新生', '松江南京', '南京復興', '忠孝復興', '大安', '信義安和')                                  
('善導寺', '忠孝新生', '松江南京', '中山', '北門', '西門', '小南門', '中正紀念堂', '古亭', '東門', '大安森林公園', '大安', '信義安和')                
('善導寺', '忠孝新生', '東門', '中正紀念堂', '小南門', '西門', '北門', '中山', '松江南京', '南京復興', '忠孝復興', '大安', '信義安和')                
('台大醫院', '中正紀念堂', '小南門', '西門', '北門', '中山', '松江南京', '南京復興', '忠孝復興', '忠孝新生', '東門', '大安森林公園', '大安', '信義安和')     
('中山', '松江南京', '忠孝新生', '忠孝復興', '大安', '信義安和')                                                                 
('中山', '北門', '西門', '小南門', '中正紀念堂', '古亭', '東門', '忠孝新生', '松江南京', '南京復興', '忠孝復興', '大安', '信義安和')                 
('台大醫院', '中正紀念堂', '古亭', '東門', '忠孝新生', '忠孝復興', '大安', '信義安和')                                                  
('西門', '北門', '中山', '松江南京', '忠孝新生', '忠孝復興', '大安', '信義安和')                                                     
>>> 
>>> Ans = P路徑甲.data
# 尋找第一個最短路徑
>>> [len(i) for i in Ans].index(min(map(len, Ans)))
21
>>> Ans[21]
('善導寺', '忠孝新生', '忠孝復興', '大安', '信義安和')

# 尋找第一個最長路徑
>>> [len(i) for i in Ans].index(max(map(len, Ans))) 
22 
>>> Ans[22] 
('善導寺', '忠孝新生', '忠孝復興', '南京復興', '松江南京', '中山', '北門', '西門', '小南門', '中正紀念堂', '古亭', '東門', '大安森林公園', '大安', '信義安和') 
>>> 

# 探尋連接站情況
>>> print(所有路徑('忠孝新生', '忠孝復興', P路徑甲))
P路徑甲 
-------------------------------------------------------------------------------
('松江南京', '中山', '台北車站', '台大醫院', '中正紀念堂', '東門', '大安森林公園', '大安') 
('松江南京', '中山', '北門', '西門', '小南門', '中正紀念堂', '古亭', '東門', '大安森林公園', '大安') 
('東門', '古亭', '中正紀念堂', '小南門', '西門', '台北車站', '中山', '松江南京', '南京復興') 
('東門', '中正紀念堂', '小南門', '西門', '台北車站', '中山', '松江南京', '南京復興') 
('善導寺', '台北車站', '西門', '小南門', '中正紀念堂', '古亭', '東門', '大安森林公園', '大安') 
('善導寺', '台北車站', '西門', '小南門', '中正紀念堂', '東門', '大安森林公園', '大安') 
() 
('松江南京', '中山', '台北車站', '西門', '小南門', '中正紀念堂', '東門', '大安森林公園', '大安') 
('松江南京', '中山', '北門', '西門', '小南門', '中正紀念堂', '東門', '大安森林公園', '大安') 
('善導寺', '台北車站', '中山', '北門', '西門', '小南門', '中正紀念堂', '東門', '大安森林公園', '大安') 
('善導寺', '台北車站', '台大醫院', '中正紀念堂', '小南門', '西門', '北門', '中山', '松江南京', '南京復興') 
('東門', '古亭', '中正紀念堂', '台大醫院', '台北車站', '中山', '松江南京', '南京復興') 
('松江南京', '中山', '台北車站', '台大醫院', '中正紀念堂', '古亭', '東門', '大安森林公園', '大安') 
('東門', '中正紀念堂', '小南門', '西門', '北門', '中山', '松江南京', '南京復興') 
('東門', '中正紀念堂', '台大醫院', '台北車站', '西門', '北門', '中山', '松江南京', '南京復興') 
('松江南京', '中山', '北門', '西門', '台北車站', '台大醫院', '中正紀念堂', '古亭', '東門', '大安森林公園', '大安')
('善導寺', '台北車站', '中山', '北門', '西門', '小南門', '中正紀念堂', '古亭', '東門', '大安森林公園', '大安') 
('松江南京', '中山', '台北車站', '西門', '小南門', '中正紀念堂', '古亭', '東門', '大安森林公園', '大安') 
('東門', '中正紀念堂', '台大醫院', '台北車站', '中山', '松江南京', '南京復興') 
('善導寺', '台北車站', '台大醫院', '中正紀念堂', '東門', '大安森林公園', '大安') 
('善導寺', '台北車站', '中山', '松江南京', '南京復興') 
('松江南京', '中山', '北門', '西門', '台北車站', '台大醫院', '中正紀念堂', '東門', '大安森林公園', '大安') 
('東門', '古亭', '中正紀念堂', '台大醫院', '台北車站', '西門', '北門', '中山', '松江南京', '南京復興') 
('善導寺', '台北車站', '西門', '北門', '中山', '松江南京', '南京復興') 
('善導寺', '台北車站', '台大醫院', '中正紀念堂', '古亭', '東門', '大安森林公園', '大安') 
('東門', '古亭', '中正紀念堂', '小南門', '西門', '北門', '中山', '松江南京', '南京復興') 
('松江南京', '南京復興') 
('東門', '大安森林公園', '大安') 
>>> Ans = P路徑甲.data

# 尋找第一個最短路徑
>>> [len(i) for i in Ans].index(min(map(len, Ans)))
6
# [()] 一致性
>>> Ans[6]
()

# 尋找第一個最長路徑
>>> [len(i) for i in Ans].index(max(map(len, Ans)))
15
>>> Ans[15]
('松江南京', '中山', '北門', '西門', '台北車站', '台大醫院', '中正紀念堂', '古亭', '東門', '大安森林公園', '大安')
>>>