***8.35（最大塊）給定一個元素為0或者1的方陣，編寫程序，找到一個元素都為1的最大的子方陣。程序提示用戶輸入矩陣的行數。然后顯示最大的子方陣的第一個元素、行數

• 題目
• • 題目描述與運行示例
  • 破題
• 代碼（非正式）
• 正式代碼與博主錯誤

題目

題目描述與運行示例

***8.35（最大塊）給定一個元素為0或者1的方陣，編寫程序，找到一個元素都為1的最大的子方陣。程序提示用戶輸入矩陣的行數。然后顯示最大的子方陣的第一個元素、最大子方陣的行數

Enter the number of rows in the matrix: 5 Enter the matrix row by row: 1 0 1 0 1 1 1 1 0 1 1 0 1 1 1 1 0 1 1 1 1 0 1 1 1 The maximum square submatrix is at (2, 2) with size 3

破題

輸出提示語句，從控制臺獲取方陣大小

聲明一個二維數組，長度為剛剛獲取的大小

使用循環獲取用戶賦值

使用多層循環遍歷數組，找到最大的子方陣

輸出子方陣第一個元素位置和行數

代碼（非正式）

import java.util.Scanner;public class Test8_35 {public static void main(String[] args) {//1. 輸出提示語句，從控制臺獲取方陣大小Scanner input = new Scanner(System.in);System.out.print("Enter the number of rows in the matrix: ");int length = input.nextInt();//2. 聲明一個二維數組，長度為剛剛獲取的大小int[][] arr = new int[length][length];//3. 使用循環獲取用戶賦值System.out.println("Enter the matrix row by row: ");for (int i = 0 ; i < length ; i++){for (int j = 0 ; j < length ; j++){arr[i][j] = input.nextInt();}}//4. 使用多層循環遍歷數組，找到最大的子方陣// 子方陣長度從arr.length開始到1結束，全為1的則輸出結果for (int substring_length = length ; substring_length > 0 ; substring_length--){for (int i = 0 ; i <= length - substring_length ; i++){for (int j = 0 ; j <= length - substring_length ; j++){if (is_substring(arr, i, j, substring_length)){System.out.println("The maximum square submatrix is at (" + i +", " + j + ") with size " + substring_length);return;}}}}}/** 判斷下標從[i][j]開始的substring_length圍成的矩陣中是否全部為1 */public static boolean is_substring(int[][] arr, int i, int j, int length){for (int x = i ; x < i + length ; x++){for (int y = j ; y < j + length ; y++){if (arr[x][y] != 1){return false;}}}return true;} }

正式代碼與博主錯誤

做題的時候沒看到最后還有一行要求
程序需要實現和使用下面的方法來找到最大的子方陣
public static int[] findLargestBlock(int[][] m)
返回值是一個包含三個值的數組
前面兩個值是子方陣的行和列的下標，第三個值是子方陣中的行數

對程序修改如下：

import java.util.Scanner;public class Test8_35 {public static void main(String[] args) {//1. 輸出提示語句，從控制臺獲取方陣大小Scanner input = new Scanner(System.in);System.out.print("Enter the number of rows in the matrix: ");int length = input.nextInt();//2. 聲明一個二維數組，長度為剛剛獲取的大小int[][] arr = new int[length][length];//3. 使用循環獲取用戶賦值System.out.println("Enter the matrix row by row: ");for (int i = 0; i < length; i++) {for (int j = 0; j < length; j++) {arr[i][j] = input.nextInt();}}//4. 傳入方法int[] feedback = findLargestBlock(arr);// 輸出System.out.println("The maximum square submatrix is at (" + feedback[0] +", " + feedback[1] + ") with size " + feedback[2]);}public static int[] findLargestBlock(int[][] m){int[] feedback = new int[3];for (int substring_length = m.length ; substring_length > 0 ; substring_length--){for (int i = 0 ; i <= m.length - substring_length ; i++){for (int j = 0 ; j <= m.length - substring_length ; j++){if (is_substring(m, i, j, substring_length)){feedback[0] = i;feedback[1] = j;feedback[2] = substring_length;return feedback;}}}}return feedback;}/** 判斷下標從[i][j]開始的substring_length圍成的矩陣中是否全部為1 */public static boolean is_substring(int[][] arr, int i, int j, int length){for (int x = i ; x < i + length ; x++){for (int y = j ; y < j + length ; y++){if (arr[x][y] != 1){return false;}}}return true;} }

總結

以上是生活随笔為你收集整理的Java黑皮书课后题第8章：***8.35（最大块）给定一个元素为0或者1的方阵，编写程序，找到一个元素都为1的最大的子方阵。程序提示用户输入矩阵的行数。然后显示最大的子方阵的第一个元素、行数的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。