บทความนี้อธิบายอัลกอริทึมของ Java สำหรับการแก้ปัญหาตัวหารร่วมที่ยิ่งใหญ่ที่สุดของจำนวนเต็มที่ไม่เป็นลบสองตัว แบ่งปันสำหรับการอ้างอิงของคุณดังนี้:
ฟังก์ชั่นรหัส:
1. การใช้งาน Java (ซอร์สโค้ดเต็มพร้อมกรณีทดสอบ);
2. แก้ปัญหาตัวหารสามัญที่ยิ่งใหญ่ที่สุดของจำนวนเต็มที่ไม่เป็นลบสอง p และ q (p> = q);
3. สองวิธีแก้ปัญหา: วิธีการวนซ้ำและวิธีการเรียกซ้ำ;
ซอร์สโค้ดที่สมบูรณ์:
/ * GCD: Greateast Common Divisor */คลาสสาธารณะ GCD {โมฆะคงที่สาธารณะหลัก (สตริง args []) {/ * กรณีทดสอบ */int p = 32; int Q = 24; System.out.println ("ตัวแบ่งที่ยิ่งใหญ่ที่สุดของ"+p+"และ"+q+"คือ /n"+"[GCD1]:"+GCD1 (p, q)+" /n"+"[GCD2]:"+GCD2 (P, Q)); } // (q % gcd == 0 และ p % gcd == 0 [gcd จาก q ถึง 1]) สาธารณะคงที่ int gcd1 (int p, int q) {int gcd = 1; int d = q; ในขณะที่ (d> 0) {d--; if (q%d == 0 && p%d == 0) {gcd = d; หยุดพัก; }} ส่งคืน GCD; } // gcd (p, q) = gcd (q, p%q) [ถ้า q = 0, gcd = p] สาธารณะคงที่ int gcd2 (int p, int q) {ถ้า (q == 0) ส่งคืน p; int r = p%q; //system.out.println("("+Q+","+R+ ")"); ส่งคืน GCD2 (Q, R); -กำลังใช้งานภาพหน้าจอ:
รหัสคำอธิบาย:
วิธีวงกลม GCD1 (P, Q)
คำอธิบายภาษาธรรมชาติ: วิธีการวนรอบแก้ตัวหารร่วมที่ยิ่งใหญ่ที่สุดของจำนวนเต็มที่ไม่เป็นลบสอง p, q (p> = q) นั่นคือแก้ไขค่าสูงสุดของตัวหารทั่วไปของ Q นั่นคือ p ให้ D (แบ่ง) ลดลงจาก p (ขั้นตอนการลดลง = 1) d คือ "ค่าสูงสุดของเงื่อนไขที่กำลังจะพอใจ" เมื่อ D เป็นไปตามเงื่อนไข (สามารถแบ่งด้วย P และหารด้วย P) D เป็นตัวหารทั่วไปของ P และ Q และ D เป็นตัวหารร่วมที่ยิ่งใหญ่ที่สุดของ P และ Q;
วิธีการเรียกซ้ำ GCD2 (P, Q)
คำอธิบายภาษาธรรมชาติ: วิธีการเรียกซ้ำแก้ตัวหารร่วมที่ยิ่งใหญ่ที่สุดของจำนวนเต็มที่ไม่เป็นลบสอง p, q (p> = q) เมื่อ Q เท่ากับ 0 ตัวหารร่วมที่ยิ่งใหญ่ที่สุดคือ P; มิฉะนั้นให้ใช้ส่วนที่เหลือของ P และ Q เพื่อรับ R = P%Q และตัวหารร่วมที่ยิ่งใหญ่ที่สุดของ P และ Q เป็นตัวหารร่วมที่ยิ่งใหญ่ที่สุดของ Q และ R;
ประสบการณ์รหัส:
เกี่ยวกับวิธีการวนรอบในตอนแรกสิ่งที่ฉันคิดคือการเขียนวิธีการแก้ปัญหาตัวหารทั่วไปใช้อาร์เรย์จำนวนเต็มเพื่อเก็บตัวหารทั่วไปทั้งหมดของจำนวนเต็มที่ไม่เป็นลบจากนั้นเปรียบเทียบและค้นหาตัวหารทั่วไปที่ใหญ่ที่สุดใน P และ Q ต่อมาฉันคิดว่าเพราะมันคือการหาค่าสูงสุดจะไม่ง่ายกว่าที่จะลดลงโดยตรงจากด้านหลังไปด้านหน้า? การลดลงจากด้านหลังไปด้านหน้าสามารถมั่นใจได้ว่าจำนวนนี้ใหญ่ที่สุดในปัจจุบันเพราะคนที่ใหญ่กว่าไม่ตรงตามเงื่อนไข (สามารถแบ่งด้วย P และ Q ในเวลาเดียวกัน) จะถูกกำจัดซึ่งหลีกเลี่ยงปัญหาในการค้นหาค่าสูงสุดในขั้นต้น แม้ว่าจะมีหลายวิธีในการค้นหาสูงสุดหากคุณมีหรือไม่จำเป็นต้องพิสูจน์และค้นหาฮ่าฮ่าทำไมคุณถึงรู้สึกเกี่ยวกับปรัชญาเล็กน้อย?
เกี่ยวกับการเรียกซ้ำสิ่งที่ฉันสามารถเข้าใจได้อย่างเต็มที่จากสัญชาตญาณของฉันคือประโยคเดียวที่ตัวหารร่วมที่ยิ่งใหญ่ที่สุดของ P และ Q เป็นตัวหารที่ยิ่งใหญ่ที่สุดของ Q และ R (R = P%Q) ซึ่งเป็นจุดเริ่มต้นของวงแหวน แต่ฉันก็ยังไม่เข้าใจ
แม้ว่ามันจะเป็นทางออกที่ง่ายมากสำหรับอัลกอริทึมตัวหารร่วมที่ยิ่งใหญ่ที่สุด แต่ฉันต้องเขียนมันด้วยสองวิธีส่วนใหญ่จะรู้สึกถึงวิธีการเรียกซ้ำที่ฉันไม่คุ้นเคย ในอดีตฉันเห็นสูตรที่ชัดเจนของอัลกอริทึมการเรียกซ้ำสำหรับการแก้ปัญหา Hannover Tower และ Fibonacci ที่ส่องสว่างอยู่ที่นั่นและฉันถอนหายใจว่านี่เป็นคณิตศาสตร์ที่สมบูรณ์! ความรู้สึกที่ฉันเรียนรู้ในวันนี้น่าตกใจยิ่งกว่าเวลานั้น ฉันสงสัยว่าเกิดอะไรขึ้นและแก้ไขได้อย่างแปลกประหลาด ในเวลานั้นฉันไม่สนใจความทรงจำประสิทธิภาพและตัวบ่งชี้อื่น ๆ มากนัก ฉันแค่คิดว่าคนที่คิดว่าสิ่งนี้ฉลาดจริงๆ สำหรับพวกเขาไม่ว่าจะเป็นคอมพิวเตอร์หรือภาษาการเขียนโปรแกรมมันเป็นเพียงเครื่องมือในการแก้ปัญหา บางคนบอกว่าการเรียกซ้ำเป็นอัลกอริทึมที่ช่วยให้สมองคิดเกี่ยวกับคอมพิวเตอร์ในการคำนวณและรู้สึกเหมาะสมจริงๆ
การอ้างอิง
ชุดการเขียนโปรแกรมทัวริง: อัลกอริทึม (รุ่นที่ 4) Robert Sedgewick (ผู้แต่ง), Kevin Wayne (ผู้แต่ง), Xie Luyun (นักแปล)
สำหรับข้อมูลเพิ่มเติมเกี่ยวกับอัลกอริทึม Java ผู้อ่านที่มีความสนใจในเว็บไซต์นี้สามารถดูหัวข้อ: "โครงสร้างข้อมูล Java และการสอนอัลกอริทึม", "บทสรุปของเคล็ดลับการดำเนินงาน Java Dom", "บทสรุปของไฟล์ Java และเคล็ดลับการดำเนินการไดเรกทอรี" และ "สรุป
ฉันหวังว่าบทความนี้จะเป็นประโยชน์กับการเขียนโปรแกรม Java ของทุกคน