การวิเคราะห์รหัสของปัญหาการแก้ปัญหากระต่ายภาษาชวา

1. คิด

ปัญหากระต่ายเป็นคำแถลงที่เป็นรูปเป็นร่างของซีรี่ส์ Fischer ซึ่งเป็นคำถามที่เกิดขึ้นในผลงานของนักคณิตศาสตร์ชื่อ Fibonacci

2. คำอธิบาย

ปัญหาเกี่ยวกับเทคนิคทางกายภาพของมันคือ: หากทารกให้กำเนิดทารกทุกเดือนทารกจะเริ่มให้กำเนิดทารกในอีกหนึ่งเดือนต่อมา ในตอนแรกมีทารกเพียงคนเดียวและมีเด็กชายสองคนในหนึ่งเดือนเด็กชายสามคนในสองเดือนและเด็กชายทารกห้าคนในสามเดือน (เด็กชายตัวเล็ก ๆ ถูกนำไปผลิต) ...

เราแสดงในลักษณะทางคณิตศาสตร์ซึ่งเป็นชุดลำดับต่อไปนี้:

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89 ......

หมายเหตุ: ทารกแรกเกิดจะใช้เวลาหนึ่งเดือนในการเริ่มผลิต! และกระต่ายเหล่านี้เป็นอมตะ! - -

3. กฎ

เมื่อเราพบปัญหานี้อย่างลึกลับมันเป็นเรื่องยากที่จะหากฎ แต่คิดเกี่ยวกับปัญหานี้ตามกฎหมายของลำดับในวิชาคณิตศาสตร์และรอการเปรียบเทียบหรือไม่? ความแตกต่างของอวตาร? หรืออย่างอื่น? เนื่องจากนี่เป็นคำถามที่เกิดขึ้นจากนักคณิตศาสตร์จึงควรมีกฎทางคณิตศาสตร์บางอย่างอยู่ใช่ไหม? กฎคืออะไร? หากคุณวิเคราะห์ชุดลำดับข้างต้นอย่างระมัดระวังคุณมีคำตอบอยู่แล้ว ถูกต้องมันแสดงในหนึ่งประโยค เริ่มต้นจากเทอมที่สามผลรวมของสองคำแรกเทอมเทอมที่สาม

สมมติว่าค่าของเทอมที่ n คือ FN ความสม่ำเสมอของลำดับจะแสดงดังนี้โดยใช้สูตรทางคณิตศาสตร์:

4. Pseudocode

รหัสหลอกที่เรียกว่าไม่ใช่รหัสจริง ไม่สามารถดำเนินการบนเครื่องได้ มันเป็นเพียงสัญลักษณ์ที่มีความหมายระหว่างภาษาธรรมชาติและภาษาการเขียนโปรแกรมที่แสดงถึงตรรกะของโปรแกรม สำหรับ pseudocode ของปัญหากระต่ายเราใช้วิธีการเรียกซ้ำของสูตรข้างต้นที่นี่และเราสามารถมี pseudocode ต่อไปนี้:

 ขั้นตอน fib (n) [ถ้า (n <0) พิมพ์ ("ข้อผิดพลาดอินพุต"); ถ้า (n = 0 หรือ n = 1) return (n); ผลตอบแทนอื่น (FIB (N-1) + FIB (N-2)); -

ตามแนวคิดการเรียกซ้ำที่อธิบายไว้ในบทความก่อนหน้านี้คุณสามารถอ้างถึง "ปัญหาฮันโน" ก่อนหน้านี้สำหรับรายละเอียด เมื่อเทียบกับทุกคนคุณจะไม่คุ้นเคยกับการเรียกซ้ำอีกต่อไป จากนั้นขึ้นอยู่กับสูตรทางคณิตศาสตร์ที่เราได้รับข้างต้นการลดการเรียกซ้ำ pseudocode ดังกล่าวจะกระชับและชัดเจนมาก แต่อืมคุณอาจเดาได้ว่าฉันอยากจะพูด คุณพบปัญหาที่เมื่อค่า N ของเรามีขนาดใหญ่เกินไปโปรแกรมจะช้าลงหรือไม่?

หากคุณรู้ว่าคุณคิดเกี่ยวกับปัญหานี้อย่างจริงจังและคุณควรแก้ข้อสงสัยในใจ หากยังไม่ต้องสงสัยเลยว่าได้รับการแก้ไขให้ฉันแก้ข้อสงสัยของทุกคน ทำไมมันช้ากว่า? เหตุผลก็คือเมื่อเราคำนวณเทอมที่ N เราจำเป็นต้องคำนวณคำศัพท์ N-1 และ N-2 อีกครั้งและมีการคำนวณคำศัพท์ทั้งสองมาก่อน เมื่อเราพบหมายเลขถัดไปเรายังต้องคำนวณด้านข้าง อย่างล้นหลามเราได้ทำงานที่ไร้ประโยชน์มากมาย

ดังนั้นเรามีวิธีที่ดีในการแก้ปัญหานี้หรือไม่? มีคำตอบ จากการวิเคราะห์ข้างต้นเมื่อเราแก้คำที่ NTH คำศัพท์ N-1 และ N-2 ก่อนหน้านี้ได้รับการแก้ไขแล้ว ดังนั้นทำไมเราไม่บันทึกมัน - - -

ฮ่าฮ่าทันใดนั้นคุณก็รู้หรือไม่? ใช่! เราใช้พื้นที่เพื่อแลกเปลี่ยนเวลาที่นี่ซึ่งสามารถปรับปรุงประสิทธิภาพได้อย่างมาก! ฉันจะไม่เขียนรหัสหลอกที่นี่

5. รหัส

โอเคฉันขายได้ทั้งหมดเพียงอัปโหลดรหัส:

 ระดับสาธารณะ Fibonacci {โมฆะคงที่สาธารณะหลัก (สตริง [] args) {int [] fib = int ใหม่ [20]; FIB [0] = 0; FIB [1] = 1; สำหรับ (int i = 2; i <fib.length; i ++) {fib [i] = fib [i-1]+fib [i-2]; } สำหรับ (int i = 0; i <fib.length; i ++) {system.out.print (fib [i]+""); } system.out.println (); -

6. คิด

ที่นี่เราเสนอคำถามคิด หากกระต่ายไม่ได้ให้กำเนิดกระต่ายหนึ่งตัวและกระต่ายหลายตัวเราจะแก้ปัญหาได้อย่างไร? แน่นอนสิ่งที่เราหมายถึงโดยการให้กำเนิดหลายครั้งคือจำนวนคงที่ กระต่ายตัวหนึ่งจะไม่ให้กำเนิดกระต่ายมากขึ้นและหนึ่งกระต่ายจะไม่ให้กำเนิดน้อยลงมิฉะนั้นมันจะเป็นไปไม่ได้ที่จะแก้ปัญหา

ไม่มีรหัสที่นี่ คุณสามารถค้นหาทรัพยากรที่เหมาะสมทางออนไลน์และดูวิธีการแก้ปัญหาได้

สรุป

ข้างต้นเป็นเนื้อหาทั้งหมดของบทความนี้เกี่ยวกับการวิเคราะห์รหัสของภาษา Java เพื่อแก้ปัญหากระต่าย ฉันหวังว่ามันจะเป็นประโยชน์กับทุกคน เพื่อนที่สนใจสามารถอ้างถึงหัวข้ออื่น ๆ ที่เกี่ยวข้องในเว็บไซต์นี้ต่อไป หากมีข้อบกพร่องใด ๆ โปรดฝากข้อความไว้เพื่อชี้ให้เห็น!