ผลต่างระหว่างรุ่นของ "Ioi/recursion"
Jittat (คุย | มีส่วนร่วม) |
Jittat (คุย | มีส่วนร่วม) |
||
| (ไม่แสดง 7 รุ่นระหว่างกลางโดยผู้ใช้คนเดียวกัน) | |||
| แถว 1: | แถว 1: | ||
หน้านี้รวมแบบฝึกหัดการเขียน recursion ด้วย Racket | หน้านี้รวมแบบฝึกหัดการเขียน recursion ด้วย Racket | ||
| + | |||
| + | * [http://theory.cpe.ku.ac.th/wiki/images/01204435-lect02-scheme.pdf เอกสาร lisp/scheme/racket] | ||
| + | |||
| + | == เริ่มต้น == | ||
| + | 1. myprod (หาผลคูณ, คืน 1 ถ้าเป็นรายการว่าง) | ||
| + | |||
| + | > (myprod '()) | ||
| + | 1 | ||
| + | > (myprod '(1 2 3 4 5)) | ||
| + | 120 | ||
| + | |||
| + | 2. unitlist | ||
| + | |||
| + | เขียนฟังก์ชัน unitlist รับรายการ lst ทีคืนค่า #t ถ้า lst เป็นรายการความยาว 1 (ไม่ต้องสนใจกรณีที่เป็นรายการว่าง) | ||
| + | |||
| + | > (unitlist '(1)) | ||
| + | #t | ||
| + | > (unitlist '(1 2 3)) | ||
| + | #f | ||
| + | |||
| + | 3. mymin | ||
| + | |||
| + | > (mymin '(1 2 3 -1 100)) | ||
| + | -1 | ||
== ฝึกฝน == | == ฝึกฝน == | ||
| แถว 10: | แถว 34: | ||
'(1 2 3 4 10) | '(1 2 3 4 10) | ||
| − | 2. | + | ฟังก์ชันที่เขียนทำงานในเวลาเท่าใด ถ้าลิสต์ที่ได้รับมีความยาว n |
| + | |||
| + | 2. mylast | ||
| + | |||
| + | เขียนฟังก์ชัน mylast รับ list และคืนข้อมูลสุดท้ายใน list ไม่ต้องพิจารณากรณีที่ได้รับ list ว่าง | ||
| + | |||
| + | > (mylast '(10 20 30)) | ||
| + | 30 | ||
| + | |||
| + | 3. myappend | ||
| + | |||
| + | เขียนฟังก์ชันรับ list สอง list และคืน list ที่เกิดจากการต่อกันของทั้งสอง list | ||
| + | |||
| + | > (myappend '(1 2 3) '(20 30 40)) | ||
| + | '(1 2 3 20 30 40) | ||
| + | |||
| + | == ท้าทาย == | ||
| + | 1. myrev | ||
| + | |||
| + | เขียนฟังก์ชัน myrev ที่รับรายการแล้วคืนรายการที่กลับหน้าหลัง | ||
| + | |||
| + | > (myrev '(1 3 4 5 6 7 8)) | ||
| + | '(8 7 6 5 4 3 1) | ||
| + | |||
| + | สามารถเขียนฟังก์ชันอื่นประกอบได้ เวลาในการทำงานของฟังก์ชันที่เขียนเป็นเท่าใด ถ้ารายการมีความยาว n | ||
| + | |||
| + | 2. myflat | ||
| + | |||
| + | เขียนฟังก์ชัน myflat ที่รับรายการ จากนั้นแปลงรายการเป็นแบบรายการชั้นเดียว สามารถใช้ฟังก์ชัน list? เพื่อตรวจสอบว่าข้อมูลเป็นรายการหรือไม่ได้ | ||
| + | |||
| + | > (myflat '(1 2 (1 2 3 (4 5) 6) (((7) 8) 9) 10 (11))) | ||
| + | '(1 2 1 2 3 4 5 6 7 8 9 10 11) | ||
| + | |||
| + | == merge sort == | ||
| + | |||
| + | === merge-list === | ||
| + | เขียนฟังก์ชัน merge-list รับลิสต์สองลิสต์ที่เรียงจากน้อยไปหามาก แล้วคืนค่าลิสต์ที่เป็นลิสต์รวมของลิสต์ทั้งสองที่เรียงลำดับจากน้อยไปหามากแล้ว | ||
| + | |||
| + | > (merge-list '(1 2 3 5 7 11 13) '(2 4 6 8 10 12)) | ||
| + | '(1 2 2 3 4 5 6 7 8 10 11 12 13) | ||
| + | |||
| + | === split-list === | ||
| + | ให้เขียนฟังก์ชัน split-list ที่รับลิสต์ของจำนวนเต็ม แล้วคืนค่าเป็นลิสต์ที่มีสมาชิกสองตัว ตัวแรกเป็นลิสต์ที่ประกอบด้วยสมาชิกในลิสต์ที่มีตำแหน่งเป็นเลขคี่ ตัวที่สองลิสต์ของสมาชิกที่มีตำแหน่งเป็นเลขคู่ | ||
| + | |||
| + | ตัวอย่างการทำงาน | ||
| + | |||
| + | > (split-list '(1 3 2 4 5 7 4 3 6 9 10)) | ||
| + | '((1 2 5 4 6 10) (3 4 7 3 9)) | ||
| + | > (split-list '(1)) | ||
| + | '((1) ()) | ||
| + | > (split-list '()) | ||
| + | '(() ()) | ||
| + | |||
| + | hint: อาจจะใช้ฟังก์ชัน cond ในการแยกกรณี, สามารถใช้ฟังก์ชัน first และ second เพื่ออ่านข้อมูลตัวแรก และตัวที่สองของลิสต์ได้, ให้ทดลองใช้ฟังก์ชัน let | ||
| + | |||
| + | === merge-sort === | ||
| + | |||
| + | เขียนฟังก์ชัน merge-sort ที่เรียงลำดับข้อมูลในลิสต์ ให้ใช้ฟังก์ชัน merge-list และ split-list | ||
| + | |||
| + | ตัวอย่างการทำงาน | ||
| + | |||
| + | > (merge-sort '(1 9 8 2 3 7 4 6 10 39 28 17 50 60 70)) | ||
| + | '(1 2 3 4 6 7 8 9 10 17 28 39 50 60 70) | ||
| + | |||
| + | hint: อย่าลืม base cases (กรณีที่เป็นลิสต์ว่าง และกรณีที่ลิสต์มีสมาชิก 1 ตัว) | ||
| + | |||
| + | == ต้นไม้ == | ||
รุ่นแก้ไขปัจจุบันเมื่อ 04:22, 26 ตุลาคม 2558
หน้านี้รวมแบบฝึกหัดการเขียน recursion ด้วย Racket
เนื้อหา
เริ่มต้น
1. myprod (หาผลคูณ, คืน 1 ถ้าเป็นรายการว่าง)
> (myprod '()) 1 > (myprod '(1 2 3 4 5)) 120
2. unitlist
เขียนฟังก์ชัน unitlist รับรายการ lst ทีคืนค่า #t ถ้า lst เป็นรายการความยาว 1 (ไม่ต้องสนใจกรณีที่เป็นรายการว่าง)
> (unitlist '(1)) #t > (unitlist '(1 2 3)) #f
3. mymin
> (mymin '(1 2 3 -1 100)) -1
ฝึกฝน
1. mypushback
เขียนฟังก์ชัน mypushback รับ list และ element แล้ว return list ที่มี element ต่อท้าย
> (mypushback '(1 2 3 4) 10) '(1 2 3 4 10)
ฟังก์ชันที่เขียนทำงานในเวลาเท่าใด ถ้าลิสต์ที่ได้รับมีความยาว n
2. mylast
เขียนฟังก์ชัน mylast รับ list และคืนข้อมูลสุดท้ายใน list ไม่ต้องพิจารณากรณีที่ได้รับ list ว่าง
> (mylast '(10 20 30)) 30
3. myappend
เขียนฟังก์ชันรับ list สอง list และคืน list ที่เกิดจากการต่อกันของทั้งสอง list
> (myappend '(1 2 3) '(20 30 40)) '(1 2 3 20 30 40)
ท้าทาย
1. myrev
เขียนฟังก์ชัน myrev ที่รับรายการแล้วคืนรายการที่กลับหน้าหลัง
> (myrev '(1 3 4 5 6 7 8)) '(8 7 6 5 4 3 1)
สามารถเขียนฟังก์ชันอื่นประกอบได้ เวลาในการทำงานของฟังก์ชันที่เขียนเป็นเท่าใด ถ้ารายการมีความยาว n
2. myflat
เขียนฟังก์ชัน myflat ที่รับรายการ จากนั้นแปลงรายการเป็นแบบรายการชั้นเดียว สามารถใช้ฟังก์ชัน list? เพื่อตรวจสอบว่าข้อมูลเป็นรายการหรือไม่ได้
> (myflat '(1 2 (1 2 3 (4 5) 6) (((7) 8) 9) 10 (11))) '(1 2 1 2 3 4 5 6 7 8 9 10 11)
merge sort
merge-list
เขียนฟังก์ชัน merge-list รับลิสต์สองลิสต์ที่เรียงจากน้อยไปหามาก แล้วคืนค่าลิสต์ที่เป็นลิสต์รวมของลิสต์ทั้งสองที่เรียงลำดับจากน้อยไปหามากแล้ว
> (merge-list '(1 2 3 5 7 11 13) '(2 4 6 8 10 12)) '(1 2 2 3 4 5 6 7 8 10 11 12 13)
split-list
ให้เขียนฟังก์ชัน split-list ที่รับลิสต์ของจำนวนเต็ม แล้วคืนค่าเป็นลิสต์ที่มีสมาชิกสองตัว ตัวแรกเป็นลิสต์ที่ประกอบด้วยสมาชิกในลิสต์ที่มีตำแหน่งเป็นเลขคี่ ตัวที่สองลิสต์ของสมาชิกที่มีตำแหน่งเป็นเลขคู่
ตัวอย่างการทำงาน
> (split-list '(1 3 2 4 5 7 4 3 6 9 10)) '((1 2 5 4 6 10) (3 4 7 3 9)) > (split-list '(1)) '((1) ()) > (split-list '()) '(() ())
hint: อาจจะใช้ฟังก์ชัน cond ในการแยกกรณี, สามารถใช้ฟังก์ชัน first และ second เพื่ออ่านข้อมูลตัวแรก และตัวที่สองของลิสต์ได้, ให้ทดลองใช้ฟังก์ชัน let
merge-sort
เขียนฟังก์ชัน merge-sort ที่เรียงลำดับข้อมูลในลิสต์ ให้ใช้ฟังก์ชัน merge-list และ split-list
ตัวอย่างการทำงาน
> (merge-sort '(1 9 8 2 3 7 4 6 10 39 28 17 50 60 70)) '(1 2 3 4 6 7 8 9 10 17 28 39 50 60 70)
hint: อย่าลืม base cases (กรณีที่เป็นลิสต์ว่าง และกรณีที่ลิสต์มีสมาชิก 1 ตัว)
