Paglutas ng mga problemang kinasasangkutan ng one-dimensional at two-dimensional array

Isasaalang-alang ng artikulong ito (at, sa mas malaking lawak, magbibigay ng independiyenteng pagsusuri) mga problemang kinasasangkutan ng mga array. Pagbutihin namin ang aming mga kasanayan sa mga sumusunod na lugar:

1. Mga one-dimensional na array

   1. Mga problema "Ipagpatuloy ang pagkakasunud-sunod" ;
   2. Mga gawain sa paghahanap ng elemento;
   3. Mga problemang kinasasangkutan ng pag-uuri ng mga elemento ng array.

2. Dalawang-dimensional na array

   1. Mga Gawain "Bumuo ng isang matrix ng form" ;
   2. Mga Gawain "Maghanap ng mga elemento sa mga hindi inaasahang lugar (mga row, column, diagonal)" ;
   3. Mga Gawain "Ayusin ang mga barko para sa isang labanan sa tubig . "

Para sa lahat ng mga problema, gagamitin namin ang mga array ng integer.

Mga problemang kinasasangkutan ng mga one-dimensional na array

Ipagpatuloy ang pagkakasunod-sunod

Sa seryeng ito ng mga gawain kakailanganin mong:

1. Tukuyin ang pattern ayon sa kung saan ito o ang numerical sequence ay nabuo.
2. Sumulat ng isang function na bumubuo sa unang N elemento ng isang ibinigay na sequence bilang isang integer array at ipinapakita ang mga elemento ng array sa screen.

Ipagpalagay na nahaharap tayo sa gawain ng pagpapatuloy ng sumusunod na serye ng numero:

1, 2, 3, 4, 5…

Hakbang 1: Tukuyin ang pattern. Ang lahat dito ay elementarya - ito ay isang serye ng mga natural na numero. Hakbang 2: magsulat ng isang function na bubuo sa unang N elemento ng isang row bilang array:

public class Main {

    public static void main(String[] args) {
        System.out.println(Arrays.toString(createArrayOfIntegers(10)));

        // Output: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
    }

    public static int[] createArrayOfIntegers(int n) {
        int[] array = new int[n];
        for (int i = 1; i <= n; i++) {
            array[i-1] = i;
        }

        return array;
    }
}

Katulad nito, kinakailangan na magsulat ng mga function na magpapatuloy sa mga sumusunod na pagkakasunud-sunod:

A. 2,  4,  6,   8,  10...
B. 1,  3,  5,   7,   9...
C. 1,  4,  9,  16,  25...
D. 1,  8, 27,  64, 125...
E. 1, -1,  1,  -1,   1,  -1...
F. 1, -2,  3,  -4,   5,  -6...
G. 1, -4,  9, -16,  25....
H. 1,  0,  2,   0,   3,   0,  4....
I. 1,  2,  6,  24, 120, 720...
J. 1,  1,  2,   3,   5,   8, 13, 21…

Maghanap ng mga elemento

Sa seryeng ito ng mga gawain, kinakailangan upang makahanap ng isang elemento sa natapos na hanay na may ilang mga katangian. Halimbawa, ang elementong may pinakamataas na halaga. Upang ipakita, magsulat tayo ng code para sa isang function na kumukuha ng array at tinutukoy ang index ng maximum na elemento sa array, at pagkatapos ay i-output ang elementong ito kasama ang index nito sa console. Ipapakita ko rin kung paano, gamit ang klase, java.util.concurrent.ThreadLocalRandommabilis kang makakabuo ng isang integer array ng isang naibigay na haba, na binubuo ng mga random na elemento:

public class Main {

    public static void main(String[] args) {
        int[] array = generateRandomIntArray(10);
        findMax(array);

        /*
        Output:
        Generated random array: [50551934, -551646189, 410352642, 1822778873, -1744293692, -1140287711, 878876868, -2116893120, -797503442, -703924530]
        Max element is [1822778873] with index [3]
        */

    }


    public static int[] generateRandomIntArray(int n) {
        int[] array = ThreadLocalRandom.current().ints().limit(n).toArray();
        System.out.println("Generated random array: " + Arrays.toString(array));
        return array;
    }

    public static void findMax(int[] array) {
        int maxIndex = 0;
        int max = array[maxIndex];
        for (int i = 1; i < array.length; i++) {
            if (array[i] > max) {
                max = array[i];
                maxIndex = i;
            }
        }

        System.out.println(String.format("Max element is [%d] with index [%d]", max, maxIndex));
    }
}

Ngayon ang mga gawain mismo. Mula sa isang hanay ng mga random na integer na elemento kailangan nating hanapin:

1. Pinakamataas.
2. pinakamababa.
3. Katamtaman.
4. Ang bilang ng mga elemento sa pagitan ng maximum at minimum na mga elemento.
5. Ang unang prime number.
6. Ang huling prime number.
7. Ang bilang ng mga prime number sa array.

Maaari mong ipakita ang parehong halaga at ang mga indeks. Kung walang elementong hinahanap mo, ipakita ito sa screen sa iyong kaginhawahan. Para sa huling gawain, kailangan mong maghanda ng hanay ng mga elemento ng integer na pinagsunod-sunod sa pataas na pagkakasunud-sunod. Sa array na ito, kailangan mong maghanap ng elemento ayon sa halaga sa pinakamababang bilang ng mga operasyon ( Hint ).

Pag-uuri

Sa seryeng ito ng mga problema, kailangan mong pag-uri-uriin ang isang hanay ng mga elemento ng integer gamit ang iba't ibang mga algorithm sa pag-uuri. Mayroong maraming mga materyales sa Internet sa iba't ibang mga algorithm. Subukang maunawaan muna ang kakanyahan ng algorithm, at pagkatapos ay subukang ipatupad ito sa iyong sarili. Una sa papel (block diagram, pseudocode, anuman ang nababagay sa iyo), at pagkatapos ay sa IDEA. Algorithm para sa pagpapatupad:

• pag-uuri ng bula;
• uri ng pagpili;
• insertion sort;
• sumanib-uuri.

Mga problemang kinasasangkutan ng dalawang-dimensional na array

Gumuhit ng matrix

Sa susunod na serye ng mga gawain, kinakailangan upang gumuhit (output sa console) dalawang-dimensional na mga arrays (matrices) na binubuo sa isang tiyak na paraan: dapat silang tumutugma sa pattern na tinukoy ng gawain. Bigyan kita ng isang halimbawa. Kailangan nating bumuo at magpakita ng matrix m*n(kung saan mang bilang ng mga row, at nang bilang ng mga elemento sa row) ng form:

1, 2, 3, 4
5, 6, 7, 8
9,10,11,12

Sumulat tayo ng isang function na gagawin ang lahat para sa amin, at magbigay din ng isang function na maganda ang output ng matrix sa console (maaaring makita mong kapaki-pakinabang ito):

public class Main {

    public static void main(String[] args) {
        createAndDrawMatrix(3, 4);

    }

    public static void createAndDrawMatrix(int m, int n) {
        int[][] matrix = new int[m][n];

        int value = 1;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                matrix[i][j] = value;
                value ++;
            }
        }

        printMatrix(matrix);
    }

    public static void printMatrix(int[][] matrix) {
        for (int[] array : matrix) {
            for (int anInt : array) {
                System.out.print(String.format("%3d", anInt));
            }
            System.out.println();
        }
    }
}

Mga gawain ngayon: Magpakita ng matrix m*nng form: 4, 3, 2, 1 8, 7, 6, 5, 12,11,10, 9 ----------- 1, 4, 7 2, 5, 8 3, 6, 9 ----------- 9, 8, 7 6, 5, 4 3, 2, 1 ----------- 12,11,10, 9 8, 7, 6, 5, 4, 3, 2, 1

Maghanap ng mga elemento

Sa seksyong ito, kinakailangang magpatupad ng paghahanap para sa iba't ibang elemento sa iba't ibang bahagi ng matrix: sa isang partikular na column o sa isang partikular na row. Ipagpalagay natin na mayroon tayong matrix ng form: -1 2 -3 4 -5 6 -7 8 -9 10 -11 12 -13 14 -15 16 -17 18 -19 20 -21 22 -23 24 -25 26 -27 28 -29 30 -31 32 -33 34 -35 Bilang halimbawa, hanapin natin ang bilang ng mga negatibong elemento sa ikatlong hilera:

public class Main {

    public static void main(String[] args) {
        int [][] matrix = {
                { -1,   2,   -3,    4,   -5,    6,   -7},
                {  8,  -9,   10,  -11,   12,  -13,   14},
                {-15,  16,  -17,   18,  -19,   20,  -21},
                { 22, -23,   24,  -25,   26,  -27,   28},
                {-29,  30,  -31,   32,  -33,   34,  -35}
        };

        findNegativeCountInRow(matrix, 3);
    }

    private static void findNegativeCountInRow(int[][] matrix, int rowNumber) {
        int negativeCount = 0;
        for (int element : matrix[rowNumber]){
            if (element < 0) {
                negativeCount ++;
            }
        }

        System.out.println("Matrix: ");
        printMatrix(matrix);
        System.out.println(String.format("Has %d negative elements in #%d row ", negativeCount, rowNumber));

    }

    public static void printMatrix(int[][] matrix) {
        for (int[] array : matrix) {
            for (int anInt : array) {
                System.out.print(String.format("%5d", anInt));
            }
            System.out.println();
        }
    }
}

Bilang resulta ng pagpapatupad ng pangunahing pamamaraan, ang mga sumusunod ay magiging output sa console:

Matrix: 
   -1    2   -3    4   -5    6   -7
    8   -9   10  -11   12  -13   14
  -15   16  -17   18  -19   20  -21
   22  -23   24  -25   26  -27   28
  -29   30  -31   32  -33   34  -35
Has 3 negative elements in #3 row 

Ngayon ang mga gawain. Para sa anumang kakaiba, nmag-print ng matrix n*nng form:

1,  -2,  3,  
-4,  5, -6,
7,  -8,  9

Mula sa matrix na ito, kunin ang:

• lahat ng negatibong elemento;
• lahat ng negatibong elemento sa string i;
• lahat ng negatibong elemento sa column j;
• lahat ng mga elemento ng dayagonal (simula sa kaliwang sulok sa itaas);
• lahat ng diagonal na elemento (simula sa ibabang kaliwang sulok).

Labanan sa dagat

Huling seksyon na may asterisk: walang mga tip o halimbawa. Ang mga matrice ay mainam para sa pagprograma ng laro ng labanan sa dagat. Isa sa mga yugto ng pagprograma ng larong ito ay ang paglalagay ng mga barko sa playing field. Kung malulutas mo ang isang bilang ng mga problemang ito, makatitiyak na magagawa mong makayanan ang labanan sa hukbong-dagat. Kaya, binigyan ng 10x10 matrix na binubuo ng mga zero. Ipagpalagay natin na ito ay isang larangan para sa paglalaro ng naval battle. Sa field na ito, ang 0 ay isang walang laman na cell, ang 1 ay isang barko o bahagi ng isang barko. Sumulat ng mga pag-andar, na ang bawat isa, ayon sa mga patakaran ng laro ng labanan sa dagat, ay inilalagay ang mga ito nang random:

• 10 single-deck na barko;
• 10 double-deck corbals;
• 5 tatlong-decker na barko;
• inaayos ang lahat ng mga barko para sa laro ng labanan sa dagat (4 single-deck, 3 double-deck, 2 three-deck, 1 four-deck).

Iyon lang! Tulad ng anumang paksa sa programming, ang mga array ay pinakamahusay na natutunan sa pamamagitan ng pagsasanay. Maligayang warm-up!