افترض أنه تم تقديم مصفوفة ثنائية الأبعاد مرتبة، ويزداد كل صف من اليسار إلى اليمين، ويزداد كل عمود من الأعلى إلى الأسفل. كيفية إكمال دالة، وإدخال مثل هذه المصفوفة ثنائية الأبعاد وعدد صحيح، وتحديد ما إذا كان هذا العدد صحيحًا موجود في هذه المجموعة ثنائية الأبعاد.
افترض مصفوفة مرتبة 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 ثابت خاص؛
تم العثور على قيمة منطقية ثابتة خاصة = خطأ؛
FindMatrixNumber العام الثابت getInstance() {
إذا (مثيل == فارغ) {
مثيل = جديد FindMatrixNumber();
}
مثيل الإرجاع؛
}
البحث المنطقي الثابت العام (int مصفوفة []]، رقم int) {
إذا (مصفوفة == فارغة || مصفوفة.طول == 0 || مصفوفة[0].طول == 0) {
عودة كاذبة.
} آخر {
System.out.println("****ابدأ في البحث عن****");
findMatrixNumber(matrix, array.length, 0, مصفوفة[0].length,
رقم)؛
System.out.println("****انتهى البحث*****");
}
تم العثور على العودة؛
}
FindMatrixNumber باطل ثابت خاص (int مصفوفة []]، صفوف int، صف int،
أعمدة كثافة العمليات، عدد كثافة العمليات) {
إذا (صف > صفوف - 1)
يعود؛
int CornerNumber = مصفوفة [صف] [أعمدة - 1]؛
System.out.println(cornerNumber);
إذا (رقم الزاوية == الرقم) {
وجدت = صحيح؛
يعود؛
} وإلا إذا (رقم الزاوية < الرقم) {
findMatrixNumber(matrix,rows, ++row, columns, number);
} وإلا إذا (رقم الزاوية > الرقم) {
findMatrixNumber(matrix,rows,row, --columns, number);
}
}
}
رمز الاختبار هو:
انسخ رمز الكود كما يلي:
الطبقة العامة TestFindMatrixNumber {
public static void main(String[] args) {
مصفوفة كثافة العمليات[][] = {{1,2,8,9},{2,4,9,12},{4,7,10,13},{6,8,11,15}};
System.out.println(FindMatrixNumber.find(matrix, 6));
}
}
نتيجة تشغيل كود الاختبار هي:
انسخ رمز الكود كما يلي:
**** البدء في البحث ****
9
8
2
4
7
4
6
*****انتهى الاكتشاف*****
حقيقي