|
|
|
ช่วยอธิบายการเขียนโปรแกรมโดยใช้อัลกอริทึม backtracking มาแก้ปัญหาการแลกเหรียญหน่อยครับ |
|
|
|
|
|
|
|
ลองคิดแบบบ้านๆดูนะครับ
จงหารูปแบบทั้งหมดในการคิดเงินดังต่อไปนี้
1 บาท
2 บาท
3 บาท
5 บาท
13 บาท
100 บาท
111 บาท
ถ้าคิดรูปแบบทั้งหมดได้ก็ออกแบบ อัลกอริทึม แบบบ้านๆได้ครับ
|
|
|
|
|
Date :
2015-10-17 08:24:31 |
By :
lamaka.tor |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
เอาวิธีการต่างๆมาแยกออกตามความเป็นจริง เช่น ทอน 16 cent
ตามโจทย์ (จาก link ) แต่จ่ายหรือทอนเป็นเหรียญ 50 20 cent ไม่ได้
ซึ่งเขาใช้วิธีลบออก (จะใช้วิธีเทียบค่าก็ได้ครับ ถ้ามากกว่าก็ข้ามไป)
จากนั้นก็แจงตามเงื่อนไขออกไปเรื่อย ๆ แบบเวียนเกิด
ซึ่งเขียนอธิบายด้วยโครงสร้างข้อมูลแบบ tree
ท้ายสุดมันตอบได้หลายแบบ
มันก็คือการแจงการแก้ปัญหาและวิธีการของ ทฤษฎีกราฟ นั่นแหละครับ
พอเขียนออกมาจะสังเกตุเห็นรูปแบบที่ซ้ำๆ และการเวียนเกิด
จะได้เขียน code ออกมาง่ายๆ กระชับๆ และมีประสิทธิภาพครับ
ปล. เหมือนจะโจทย์/การบ้านพื้นฐานของปัญหาแบบ Heuristic หรือเปล่า
เห็นเอกสารอ้างถึง TSP, knapsack, job-scheduling
<< เอกสารจะบอกว่าเป็น optimized problem
แต่ยุคผมจะเรียกว่าเป็น Heuristic algorithm ในวิชา AI
ปัญหาลักษณะนี้จะตอบได้หลายแบบ และการถอดออกมาเป็น code
ก็จะทำได้หลายแบบเช่นกัน ปัญหาต่อมาคือต้องมาต้องสรุปอีกว่า
ไอ้ที่เขียนที่ทำมาน่ะใช้แบบไหนดีที่สุด เพราะอะไร
ซึ่งมันขึ้นกับตัวลักษณะของตัวปัญหา หรือ business rule น่ะครับ
|
|
|
|
|
Date :
2015-10-30 10:29:23 |
By :
DOG{B} |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Load balance : Server 00
|