อัลกอริทึม Knuth-Morris-Pratt ใน Scheme
นี่คือรหัสสำหรับคำนวณฟังก์ชันความล้มเหลว (จำนวนขั้นตอนที่เราต้องย้อนกลับ) ใน Scheme เมื่อเราใช้อัลกอริทึม Knuth-Morris-Pratt:
(define (compute-failure-function p)
(define n-p (string-length p))
(define sigma-table (make-vector n-p 0))
(let loop
((i-p 2)
(k 0))
(cond
((>= i-p n-p)
(vector-set! sigma-table (- n-p 1) k))
((eq? (string-ref p k)
(string-ref p (- i-p 1)))
(vector-set! sigma-table i-p (+ k 1))
(loop (+ i-p 1) (+ k 1)))
((> k 0)
(loop i-p (vector-ref sigma-table k)))
(else ; k=0
(vector-set! sigma-table i-p 0)
(loop (+ i-p 1) k))))
(vector-set! sigma-table 0 -1)
(lambda (q)
(vector-ref sigma-table q)))
k > 0
แต่ผมไม่เข้าใจว่าส่วนหนึ่งเมื่อ ใครช่วยอธิบายหน่อยได้ไหม
คำตอบ
ผมเห็นคุณกำลังสับสนกับไวยากรณ์ของการตั้งชื่อ letนี้โพสต์ไม่ได้งานที่ดีอธิบายวิธีการทำงาน แต่บางทีอาจจะยกตัวอย่างเช่นมีไวยากรณ์ที่คุ้นเคยมากขึ้นจะทำในสิ่งที่ชัดเจน ใช้รหัสนี้ใน Python ซึ่งจะเพิ่มจำนวนเต็มทั้งหมดตั้งแต่ 1 ถึง 10:
sum = 0
n = 1
while n <= 10:
sum += n
n += 1
print(sum)
=> 55
ตอนนี้ขอพยายามที่จะเขียนมันในแฟชั่น recursive loop
ฉันจะเรียกใช้ฟังก์ชันของฉัน สิ่งนี้เทียบเท่าอย่างสมบูรณ์:
def loop(n, sum):
if n > 10:
return sum
else:
return loop(n + 1, n + sum)
loop(1, 0)
=> 55
ในตัวอย่างข้างต้นloop
ฟังก์ชันจะใช้การวนซ้ำพารามิเตอร์n
จะใช้เพื่อติดตามตำแหน่งปัจจุบันและพารามิเตอร์จะsum
สะสมคำตอบ ทีนี้มาเขียนโค้ดเดียวกัน แต่ใน Scheme:
(let loop ((n 1) (sum 0))
(cond ((> n 10) sum)
(else (loop (+ n 1) (+ n sum)))))
=> 55
ตอนนี้เราได้กำหนดโพรซีเดอร์เฉพาะที่เรียกว่าloop
ซึ่งจะถูกเรียกโดยอัตโนมัติด้วยค่าเริ่มต้น1
และ0
สำหรับพารามิเตอร์n
และsum
. เมื่อถึงกรณีฐานของการเรียกซ้ำเราจะส่งคืนsum
มิฉะนั้นเราจะเรียกโพรซีเดอร์นี้ต่อไปโดยส่งผ่านค่าที่อัปเดตสำหรับพารามิเตอร์ มันเหมือนกับรหัส Python ทุกประการ! อย่าสับสนกับไวยากรณ์
ในอัลกอริทึมของคุณi-p
และk
เป็นตัวแปรการวนซ้ำซึ่งเริ่มต้นเป็น2
และ0
ตามลำดับ ทั้งนี้ขึ้นอยู่กับสภาพเป็นจริงการทำซ้ำอย่างต่อเนื่องเมื่อเราเรียกloop
อีกครั้งกับการปรับปรุงค่าสำหรับi-p
และk
หรือมันจะสิ้นสุดลงเมื่อคดีถึงที่จุดนี้ออกจากวงและราคาคำนวณอยู่ในตัวแปร(>= i-p n-p)
sigma-table
ขั้นตอนจะสิ้นสุดลงโดยส่งคืนฟังก์ชันใหม่เรียกว่า "ฟังก์ชันความล้มเหลว"