|
|
#1
14 กรกฎาคม 2005, 22:39
|
||||
|
||||
กำลัง งง
โจทย์มีอยู่ว่า
มีกระต่ายตัวผู้และตัวเมียคู่หนึ่ง เพิ่งเกิด โดนเจ้านายใจร้าย เอามาทิ้งบนเกาะร้าง โดยธรรมชาติของกระต่ายในที่นี้เมื่ออายุครบ 2 เดือนบริบูรณ์จะมีลูก 1 คู่ ซึ่งเป็น ตัวผู้กับตัวเมีย และจะเป็นสามีภรรยากันต่อไป สมมุติว่าไม่มีการตาย ของกระต่ายเกิดขึ้น เมื่อเวลาผ่านไป n เดือนจะมีจำนวนกระต่ายกี่คู่บนเกาะร้างนี้  โจทย์มีอย่างนี้แหละครับ ยังไงฝากช่วยคิดให้ทีนะครับ เหตุผลคือ ผมได้โจทย์มา แล้วอาจารย์ให้เขียนเป็นโปรแกรม คอมพิวเตอร์ แต่ ไม่เก่งคณิตศาสตร์ เลยอยากได้ที่มาที่ไปของสมการ ครับ  
|
|
#2
14 กรกฎาคม 2005, 23:37
|
|||
|
|||
|
อ้างอิง:
ถ้าให้ f(n) แทนจำนวนกระต่าย เมื่อสิ้นสุด เดือนที่ n จะเห็นว่า f(0)= 1 , f(1)=1 เพราะกระต่ายยังอายุไม่ครบ 2 เดือน แต่หลังจากนี้ จำนวนกระต่าย f(n) จะเท่ากับ จำนวนกระต่ายเดิมที่ยังอยู่ f(n-1) บวกกับ จำนวนกระต่ายคู่ใหม่ที่จะเกิด f(n-2) หรือเขียนเป็น recurrence relation ได้ว่า f(n) = f(n-1)+f(n-2) (nณ2) ถ้าไม่ เคลียร์ ดูได้จาก diagram ใน web นี้ครับ CLICK สรุปว่า recurrence relation สำหรับปัญหานี้ ก็คือ f(0)= 1 , f(1)=1 f(n) = f(n-1)+f(n-2) (nณ2) แล้วก็คงต้องเขียนโปรแกรม แบบ recursive แล้วล่ะครับ (อ้อ! ระวัง เรื่อง stack overflow ด้วยนะครับ)
__________________
เกษียณตัวเอง ปลายมิถุนายน 2557 แต่จะกลับมาเป็นครั้งคราว
|
|
#3
18 กรกฎาคม 2005, 19:22
|
|||
|
|||
|
ข้อนี้ไม่น่าใช้ recursive function นะครับ
มันเกิดกรณีที่คำตอบที่จะหาซ้อนกันค่อนข้างมาก ถ้าใช้ recursive function จะใช้เวลาประมาณ O (2n) เชียวนะครับ แต่ถ้าใช้ Dynamic programming จะใช้เวลาแค่ประมาณ O (n) เองครับ ถ้าเราใช้ความรู้เรื่อง ความสัมพันธ์เวียนบังเกิด (อยู่ใน ภิณทณะคณิตศาสตร์(Discrete Math)) หารูปผลเฉลยออกมาได้ แล้วแทนค่าเข้าไปใน program ก็จะดีมากเลยครับ ใช้เวลาเป็น O(c) 18 กรกฎาคม 2005 19:24 : ข้อความนี้ถูกแก้ไขแล้ว 1 ครั้ง, ครั้งล่าสุดโดยคุณ Pich
|
|
#4
19 กรกฎาคม 2005, 03:10
|
|||
|
|||
|
น้อง Pich นี่ ท่าทาง จะเชี่ยวชาญเรื่อง algorithm analysis มากๆ นะครับ สงสัยอนาคตจะได้ programmer ฝีมือดีซะแล้ว
ตอนนี้ ก็แล้วแต่คุณ mangcom แล้วกันครับ ว่า ชอบแบบไหน
__________________
เกษียณตัวเอง ปลายมิถุนายน 2557 แต่จะกลับมาเป็นครั้งคราว
|
  |
|
|
