คำอธิบายโดยละเอียดเกี่ยวกับวิธีใช้การเรียกซ้ำเพื่อค้นหาอาร์เรย์สองมิติที่เรียงลำดับ

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

สมมติว่าอาร์เรย์สองมิติสั่ง 4 × 4:

1 2 8 9

2 4 9 12

4 7 10 13

6 8 11 15

หมายเลขที่คุณกำลังมองหาคือ 6

แนวคิดหลักของอัลกอริทึมคือเอาเลข 9 ที่มุมซ้ายบนก่อน เนื่องจาก 9 มีขนาดใหญ่กว่า 6 คุณจึงสามารถแยกตัวเลขที่มากกว่า 9 ได้ นั่นคือคอลัมน์ที่สี่ แล้วจึงเอา 8 ในทำนองเดียวกัน แยกคอลัมน์ที่สามออกแล้วเอา 2 ถ้ามันน้อยกว่า 6 คุณสามารถยกเว้นตัวเลขที่เล็กกว่า 2 ได้นั่นคือแถวแรก ในทำนองเดียวกัน เอา 4 ไม่รวมแถวที่สอง เอา 7 ไม่รวม คอลัมน์ที่สอง เอา 4 เอาแถวที่สามออก เอา 6 เท่ากับ กลับค่าจริง

ที่นี่เราใช้การเรียกซ้ำเพื่อนำไปใช้ รหัสคือ:

คัดลอกรหัสรหัส ดังต่อไปนี้:

FindMatrixNumber คลาสสาธารณะ {

อินสแตนซ์ FindMatrixNumber แบบคงที่ส่วนตัว

พบบูลีนคงที่ส่วนตัว = false;

FindMatrixNumber สาธารณะคงที่ getInstance () {

ถ้า (อินสแตนซ์ == null) {

อินสแตนซ์ = FindMatrixNumber ใหม่ ();

-

ส่งคืนอินสแตนซ์;

-

ค้นหาบูลีนแบบคงที่สาธารณะ (int matrix []] จำนวน int) {

ถ้า (เมทริกซ์ == null || matrix.length == 0 || เมทริกซ์ [0].length == 0) {

กลับเท็จ;

} อื่น {

System.out.println("****เริ่มค้นหา****");

findMatrixNumber (เมทริกซ์, matrix.length, 0, เมทริกซ์ [0] .length,

ตัวเลข);

System.out.println("****สิ้นสุดการค้นหา*****");

-

พบผลตอบแทน;

-

โมฆะคงที่ส่วนตัว findMatrixNumber (int matrix [] ), แถว int, แถว int,

คอลัมน์ int, หมายเลข int) {

ถ้า (แถว > แถว - 1)

กลับ;

int cornerNumber = เมทริกซ์ [แถว] [คอลัมน์ - 1];

System.out.println (หมายเลขมุม);

ถ้า (cornerNumber == หมายเลข) {

พบ = จริง;

กลับ;

} อื่นถ้า (cornerNumber < หมายเลข) {

findMatrixNumber (เมทริกซ์, แถว, ++ แถว, คอลัมน์, หมายเลข);

} อื่นถ้า (cornerNumber > หมายเลข) {

findMatrixNumber (เมทริกซ์, แถว, แถว, --คอลัมน์, หมายเลข);

-

-

-

รหัสทดสอบคือ:

คัดลอกรหัสรหัส ดังต่อไปนี้:

TestFindMatrixNumber คลาสสาธารณะ {

โมฆะคงที่สาธารณะ main (String [] args) {

int เมทริกซ์[] = {{1,2,8,9},{2,4,9,12},{4,7,10,13},{6,8,11,15}};

System.out.println(FindMatrixNumber.find(เมทริกซ์, 6));

-

-

ผลลัพธ์ของการรันโค้ดทดสอบคือ:

คัดลอกรหัสรหัส ดังต่อไปนี้:

****เริ่มค้นหา****

9

8

2

4

7

4

6

*****สิ้นสุดการค้นหา*****

จริง