教一個基本沒編過什么程序的朋友scheme

小說:棋牌游戲奔馳寶馬技巧作者:鄧平丁更新時間:2019-02-20字數:73275

教一個基本沒編過什么程序的朋友scheme


  版權申明:本文為博主窗戶(Colin Cai)原創,歡迎轉帖。如要轉貼,必須注明原文網址

  http://www.cnblogs.com/Colin-Cai/p/9123363.html 

  作者:窗戶

  QQ:6679072

  E-mail:6679072@qq.com

  教一個基本沒編過什么程序的朋友scheme,為什么教scheme呢?因為他想學,因為一直聽我鼓吹,而他覺得他自己多少有C語言一點基礎,而又因為我覺得函數式才像數學,而過程式是偏向物理現實的,感覺不夠抽象。當然,對于一個成年人來說,有著太多的生活、學習、工作經驗,這些很多因為是物理現實,很有過程式的意思,對于理解遞歸這種數學抽象總覺得是不容易的。我告訴他,這個和你曾經讀書時學的C語言有天壤之別。但無論如何,我決定試一試。

  理解了前綴表達,理解了基本的遞歸,想想還是從這里開始吧。

  我給出了三個函數:eq0,用來判斷是否為0;inc,用來得到一個自然數的后繼數;dec,用來得到一個自然數是哪個自然數的后繼(有個特例,0不是任何數的后繼,這里返回0)。然后讓他借助scheme的遞歸,其余的只利用這三個函數來構造加減乘除乃至余數、乘方、對數。

;使用這三個函數實現自然數內的加減乘除乘方對數(《遞歸論》里的運算,除法和對數都是向下取整,減法被減數小于減數得到0)
(define (eq0 x) (=  x 0))
(define (inc x) (+ x 1))
(define (dec x) (if (= x 0) 0 (- x 1)))

  遞歸論里都是自然數內部的函數,當然遞歸論其實本質上不過是用自然數(一個特殊的可列集)內的遞歸來模擬所有的運算,因為本質上我們一個確定的計算都是針對可列集。自然數里的計算搞定了,所有可計算問題都可以等價的轉為自然數內的計算。

  當然,上升到遞歸論層次,有些東西還是難懂的,比如一般遞歸算子和原始遞歸算子的理解。不過,如果只是學習函數式編程,而不是為了學習數學,一些東西可以庸俗化一點。

  很顯然,這個問題是難到他了,半天連加法似乎沒有出來。于是我決定啟發一下他。我們可以這樣去考慮遞歸:

  我們知道任何一個數加0都等于自身,那么假設計算4+3,可以這樣考慮遞歸的過程,

  4+3=5+2=6+1=7+0=7

  也就是x+y往(x+1)+(y-1)的方向去遞歸,直到第二個數字遞歸到0為止。

  很快這位仁兄寫出了以下代碼

(define (add x y) 
(if (= y 0) x
(add (inc x) (dec y))
)
)

  再接再厲,減法也是前后兩個數逐漸dec,直到兩個有一個變為0,嗯,也很快搞定(因為是自然數內的,這里的減法小的數減大的數結果為0,遞歸論里定義的減法就是這樣)

(define (sub x y) 
(if (= x 0) 0
(if (= y 0) x
(sub (dec x) (dec y))
)
)
)

  我然后說,這里其實可以縮減一下(0 dec還是0)

(define (sub x y) 
(if (= y 0) x
(sub (dec x) (dec y))
)
)

  做乘法的時候,遇到了困難,于是我就提醒了一下,其實x*y,y=0的時候為0,y不為0的時候,x*y=x*(y-1)+x,所以可以這樣寫

(define (mul x y)
 (if (eq0 y) 0
  (add x (mul x (dec y)))
 )
)

  他不可理解了,說add不是剛才定義過的嗎,為什么現在就可以用了?我頓時明白了他之所以為難的原因,于是解釋說,當然可以用,我們數學里面不是為了證明一個定理,很多時候先去證明一個引理嘛。他頓時理解了。

  然后我接著說,如果不直接用也是可以的,只是復雜一些。我用3*3來解釋這個問題,我需要記錄過程狀態:

  3 3 0 0

  3 2 3 0

  3 2 2 1

  3 2 1 2

  3 2 0 3

  3 1 3 3

  3 1 2 4

  3 1 1 5

  3 1 0 6

  3 0 3 6

  3 0 2 7

  3 0 1 8

  3 0 1 9

  左邊第一個是被乘數,第二個是乘數,第四個是累計的結果。

  計算過程規則如下:

  (1)最開始的時候,第三個數和第四個數都為0。

  (2)當第三個數為0的時候,第三個數減1,第四個數加1。
  (3)當第三個數為0的時候,如果乘數不為0,就借一個被乘數過來,然后乘數減1;如果乘數為0,那么第四個累計的結果就是乘積。

  作為函數式編程使用附加的值只能再加參數,于是有了這樣的計算方法:

(define (_mul x y x2 r)
 (if (eq0 x2)
  (if (eq0 y) r
   (_mul x (dec y) x r)
  )
  (_mul x y (dec x2) (inc r))
 )
)
(define (mul x y)
 (_mul x y 0 0)
)

  他很驚訝于原來還可以這么干,不過很快理解了我的做法,然后我又告訴他,因為這個_mul是為了解決mul臨時定義出來的函數,如同證明中的引理,可以寫到mul的定義里面,寫成

(define (mul x y)
 (define (_mul x y x2 r)
  (if (eq0 x2)
   (if (eq0 y) r
    (_mul x (dec y) x r)
   )
   (_mul x y (dec x2) (inc r))
  )
 )
 (_mul x y 0 0)
)

  接著,很快,他很快完成了乘方,

(define (pow x y)
 (if (eq0 y) 1
  (mul x (pow x (dec y)))
 )
)

  嗯,還算可以,至少會舉一反三,只是0的任意次冪為0,但0的0次冪嘛。。。算了,索性x不能等于0,算解決了。

  除法(自然數內的除法這里只考慮整數部分)也很快做完,

(define (div x y)
 (if (> y x) 0
  (inc (div (sub x y) y))
 )
)

  我“嗯?”了一下,然后說我這里只定義了一個謂詞eq0,并沒有定義>

  然后我提醒他需要定義>,他搞不定了。

  于是還是得我來寫,

(define (> x y)
  (if (eq0  x) #f
   (if (eq0 y)
        #t
        (> (dec x) (dec y))
   )
  )
)

  其實,也可以用之前的減法定義>

(define (> x y) (if (eq0 (- x y)) #f #t))
 

?

  接著,他完成了余數和對數

(define (rem x y)
 (if (> y x) x
  (rem (sub x y) y)
 )
)
;這里的對數,是實數下對數的整數部分
(define (log x y)
 (if (> y x) 0
  (inc (log (div x y) y))
 )
)

  然而對數的實現稍有問題(當然,不考慮x,y為0,y為1的情況),也不符合這個函數我想讓他寫成的樣子,不過我不得不說他寫對了,與其說是寫對了,倒不如說是蒙對了,因為這個的寫法是需要一個數學證明的(不要忘了,div返回的只是整數)。

  證明在這里我就不贅述了,我希望他完成的大致應該如下:

(define (log x y)
 (define (_log x y y^r r)
  (if (> y^r x) (dec r)
   (_log x y (mul y^r y) (inc r))
  )
 )
 (_log x y 1 0)
)

  不過整體來說,我還算滿意,畢竟只學了一點點時間,能在指導下搞定這么些,已經挺不錯。

當前文章:http://www.cheyijia.net/content/201902/19/content_16786.html

發布時間:2019-02-20 02:15:23

友玩廣西棋牌掛 1378游戲怎么可以作弊 免費棋牌游戲平臺 4056棋牌游戲官網 博雅自貢棋牌免費下載 波克棋牌安卓版立即下載 人民幣斗地主游戲平臺 與全民方塊類似 手機歡樂斗牛官網 現金翻牌機游戲

編輯:安文

我要說兩句: (0人參與)

發布
捕鱼达人之深海狩猎