Algoritma grocking utawa introduksi tanpa rasa sakit kanggo algoritma

Review saka buku "Grocking Algorithm". A pendapat pribadi sethitik, sawetara conto. Muga-muga review iki bakal mbantu sampeyan ngerti apa sampeyan pengin maca buku iki utawa ora bakal ana ing rak sampeyan. WARNING: Akeh teks)

"Algoritma Tuwuh" utawa Pambuka Algoritma Tanpa Rasa Sakit

Pambuka

Meh kabeh lowongan tingkat Junior duwe syarat kaya "kawruh babagan struktur data lan algoritma." Kanggo sing duwe pendhidhikan khusus, algoritma kalebu ing kursus umum lan ora ana masalah. Nanging apa yen pembangunan digawa saka steppes liyane? Sing isih ana yaiku sinau dhewe. Ana jawaban kanggo pitakonan "sapa sing kudu disalahake", nanging pitakonan "apa sing kudu ditindakake" jawaban kasebut kudu digoleki. Ayo katon ing buku. Lan aku arep pitutur marang kowe bab siji.

algoritma Grok

Ing antarane kabeh karya, aku nemokake buku kaya "Grocking Algorithm". Sampeyan bisa ngerteni luwih akeh ing kene: " Buku "Growing Algorithm. Pandhuan ilustrasi kanggo programer lan penasaran ." Aku weruh buku kasebut wis suwe, nanging ing ozon regane 680 rubel. Larang utawa murah - saben wong mutusake dhewe. Aku wis tuku buku kapindho ing Avito kanggo setengah rega. Dadi aku nemokake ing St. Petersburg, tuku, lan banjur grokking. Kang aku mutusaké kanggo nuduhake karo sampeyan. Ya, ora ana kode Jawa ing buku kasebut, nanging ana ... kode liyane, nanging luwih akeh babagan mengko.

Pengantar Algoritma (Seleksi Urut)

Dadi, ing wangun narasi sing gampang, kita tekan urutan pisanan ing kinerja kita. Iki Urut Pilihan. Intine yaiku kita ngliwati unsur saka kiwa menyang tengen (saka 0 unsur nganti pungkasan), lan golek sing paling gedhe ing antarane unsur sing isih ana. Yen kita nemokake, banjur kita ngganti unsur sing saiki lan unsur paling gedhe. Cara paling gampang kanggo mikir babagan array yaiku: [5, 3, 6, 2, 10]. Njupuk Piece saka kertas, pen (cara paling prasaja lan paling biaya-efektif) lan mbayangno carane kita duwe wates kiwa, indeks saiki (utawa wates tengen), lan indeks saka unsur minimal. Lan carane kita bisa karo. Tuladhane: Algoritma asring diterangake ing pseudocode, contone, ing Wikipedia. Kita ora persis pseudocode, nanging luwih akeh babagan mengko. Saiki ayo ndeleng:

def selectionSort(array):
    for left in range(0, len(array)):
        minIndex = left
        for right in range (left+1, len(array)):
            if array[right] < array[minIndex]:
                minIndex = right
        if minIndex != left:
            temp = array[left]
            array[left] = array[minIndex]
            array[minIndex] = temp
    return array

print(selectionSort([5, 3, 6, 2, 10]))

Saiki ayo diwenehi kode Jawa:

public static void selectionSort(int[] array) {
        for (int left = 0; left < array.length; left++) {
            int minIndex = left;
            for (int right = left+1; right < array.length; right++) {
                if (array[right] < array[minIndex]) {
                    minIndex = right;
                }
            }
            if (minIndex != left) {
                int temp = array[left];
                array[left] = array[minIndex];
                array[minIndex] = temp;
            }
        }
}

Nalika sampeyan bisa ndeleng, kode meh padha. Kode pisanan minangka conto saka buku. Kapindho yaiku eksekusi gratis ing kode Jawa.

Rekursi

Sabanjure kita dikandhani manawa ana rekursi. Kaping pisanan, ana masalah babagan petani sing duwe lapangan ukuran AxB. Sampeyan perlu kanggo dibagi lapangan iki dadi padha "kotak". Banjur sawise iki Algoritma Euclid kasebut. Sing ora dakkarepake yaiku dheweke ora nyoba nulis kode kasebut. Nanging algoritma Euclid prasaja lan efektif: Jujur, aku ora kejawab sawetara rincian ing buku kasebut, kaya ing video iki: " Informatika. Teori algoritma. Algoritma Euclid ." Contone, yen a kurang saka b, banjur sak roto pisanan b lan a bakal ngganti panggonan lan kaping pindho sing luwih gedhe bakal dibagi dening cilik. Mulane, urutan argumen ora penting. Kaya biasane, pisanan kita bisa "ngrasakake" algoritma ing selembar kertas: Saiki ayo goleki kode kasebut:

def euclidean(a, b):
    if a == 0 : return b
    if b == 0 : return a
    return euclidean (b, a % b)

Ayo nulis kode sing padha ing Jawa. Yen dikarepake, kita bisa nggunakake kompiler online :

public static int euclid(int a, int b) {
        if (a == 0) return b;
        if (b == 0) return a;
        return euclid(b, a%b);
}

Faktorial uga kasebut ing wiwitan buku. Faktorial saka nomer n (n!) yaiku produk saka nomer saka 1 nganti n. Kenapa nindakake iki? Ana siji aplikasi praktis ing kene. Yen kita duwe n obyek (contone, n kutha), banjur kita bisa nggawe n saka wong-wong mau! Kombinasi. Sampeyan bisa maca liyane babagan rekursi ing kene: " Rekursi. Tugas latihan ." Perbandingan pendekatan iteratif lan rekursif: " Rekursi ".

Urut cepet

Urut cepet minangka algoritma sing rada menarik. Buku kasebut ora nggatekake dheweke. Menapa malih, kode kasebut diwenehake mung kanggo kasus sing paling awon, nalika unsur pisanan dipilih. Nanging, mbok menawa kanggo kenalan pisanan conto iki bakal luwih gampang kanggo elinga. Lan luwih apik kanggo nulis quicksort sing ala tinimbang ora nulis kabeh. Punika conto saka buku:

def quicksort(array):
    if len(array) < 2:
        return array
    else:
        pivot = array[0]
        less = [i for i in array[1:] if i <= pivot]
        greater = [i for i in array[1:] if i > pivot]
    return quicksort(less) + [pivot] + quicksort(greater)

Kabeh ing kene super prasaja. Yen kita duwe array 0 utawa 1 unsur, ora perlu ngurutake. Yen luwih, kita njupuk unsur pisanan saka Uploaded lan nimbang iku "elemen poros". Kita nggawe 2 susunan anyar - siji ngemot unsur luwih gedhe tinimbang poros, lan liyane ngemot unsur cilik. Lan kita mbaleni rekursif. Ora pilihan sing paling apik, nanging maneh, luwih eling. Ayo dileksanakake algoritma iki ing Jawa, nanging luwih bener. Materi saka review " Ilmu Komputer ing JavaScript: Quicksort " bakal mbantu kita karo iki . Lan sadurunge nulis kode kasebut, ayo digambar maneh kanggo "ngrasakake" algoritma: Pisanan, ayo nggambar maneh ing selembar kertas kanggo ngerti algoritma kasebut: Iku misale jek kula sing salah siji saka wayahe paling mbebayani kanggo ngatasi masalah tanggung. Mulane, kita bakal nindakake implementasine ing sawetara langkah cilik:

• Kita kudu bisa ngganti unsur ing array:

  private static void swap(int[] array, int firstIndex, int secondIndex) {
          int temp = array[firstIndex];
          array[firstIndex] = array[secondIndex];
          array[secondIndex] = temp;
  }




• Kita butuh metode sing mbagi array ing interval sing ditemtokake dadi 3 bagean

  
  

  private static int partition(int[] array, int left, int right) {
          int pivot = array[(right + left) / 2];
          while (left <= right) {
              while (array[left] < pivot) {
                  left++;
              }
              while (array[right] > pivot) {
                  right--;
              }
              if (left <= right) {
                  swap(array, left, right);
                  left++;
                  right--;
              }
          }
          return left;
  }

  Rincian ing link ndhuwur. Ing cendhak, kita mindhah kursor ngiwa nganti unsur kurang saka poros. Kajaba iku, pindhah kursor tengen saka mburi liyane. Lan kita nindakake swap yen kursor ora cocog. We terus nganti kursor converge. Kita ngasilake indeks sing mbagi proses luwih lanjut dadi 2 bagean.

• Ana pamisahan, kita kudu ngurutake dhewe:

  public static void quickSort(int[] array, int left, int right) {
          int index = 0;
          if (array.length > 1) {
              index = partition(array, left, right);
              if (left < index - 1) {
                  quickSort(array, left, index - 1);
              }
              if (index < right) {
                  quickSort(array, index, right);
              }
          }
  }

  Tegese, yen array kasusun saka paling ora rong unsur, mula bisa diurutake. Pisanan, kita dibagi kabeh array dadi rong bagean, unsur sing luwih cilik tinimbang poros lan unsur sing luwih gedhe. Banjur kita nindakake tumindak sing padha kanggo saben bagean sing diasilake.

  Lan kanggo tes:

  public static void main(String []args){
          int[] array = {8,9,3,7,6,7,1};
          quickSort(array, 0, array.length-1);
          System.out.println(Arrays.toString(array));
  }

Buku kasebut nyatakake yen algoritma iki kalebu algoritma sing disebut "Divide and Conquer", nalika set data sing diproses dibagi setengah saben wektu. Kompleksitas algoritma: O(nLogn) Apa ala (yaiku, apa aku ora seneng) iku buku nyebataken nggabung Urut ing pass, nanging ora nyedhiyani conto utawa kode. Rincian liyane bisa ditemokake ing kene: " Informatika. Telusuri lan ngurutake algoritma: Gabung urut ". Mula, kanggo konsistensi, ayo padha nindakake dhewe. Algoritma dhewe, mesthi, pancen prasaja lan langsung:

public static void mergeSort(int[] source, int left, int right) {
    if ((right - left) > 1) {
        int middle = (right + left) / 2;
        mergeSort(source, left, middle);
        mergeSort(source, middle + 1, right);
    }
    merge(source, left, right);
}

Kita nemtokake tengah lan dibagi dadi setengah. Kanggo saben setengah kita nindakake padha lan sateruse. Kondisi mandeg utawa kasus dasar - kita kudu duwe luwih saka siji unsur, amarga kita ora bisa dibagi siji unsur dadi loro. Saiki kita kudu ngetrapake penggabungan, yaiku, gabung:

public static void merge(int[] array, int from, int to) {
    int middle = ((from + to) / 2) + 1;
    int left = from;
    int right = middle;
    int cursor = 0;

    int[] tmp = new int[to - from + 1];
    while (left < middle || right <= to) {
        if (left >= middle) {
            tmp[cursor] = array[right];
            System.out.println("Остаток справа: " + array[right]);
            right++;
        } else if (right > to) {
            tmp[cursor] = array[left];
            System.out.println("Остаток слева: " + array[left]);
            left++;
        } else if (array[left] <= array[right]) {
            tmp[cursor] = array[left];
            System.out.println("Слева меньше: " + array[left]);
            left++;
        } else if (array[right] < array[left]) {
            tmp[cursor] = array[right];
            System.out.println("Справа меньше: " + array[right]);
            right++;
        }
        cursor++;
    }
    System.arraycopy(tmp, 0, array, from, tmp.length);
}

Ora akeh sing kudu dikomentari ing kene. Saka jeneng variabel printlnkabeh jelas. Inggih, kanggo mriksa:

int array[] = {1, 7, 3, 6, 7, 9, 8, 4};
mergeSort(array, 0, array.length - 1);
System.out.println(Arrays.toString(array));

Tabel hash

Buku kasebut uga ndemek tabel hash. Sampeyan ora kudu ngleksanakake dhewe, lan inti saka tabel hash cukup prasaja. Sawise kabeh, Jawa uga duwe implementasi tabel hash, java.util.HashTable. Yen kita katon ing piranti HashTable, kita bakal weruh sing Uploaded Entri manggon nang. Entri minangka rekaman sing minangka kombinasi saka Kunci - Nilai. HashTable nduweni initialCapacity - yaiku ukuran awal. Lan loadFactor - faktor beban. Default yaiku 0.75. Nomer iki ngandhani apa beban array (jumlah unsur / jumlah total) ukuran sing kudu ditambah. Ing Jawa mundhak 2 kali. Buku kasebut nerangake yen tabel Hash diarani tabel hash amarga adhedhasar fungsi hash, sel array (basket) ing ngendi file Entry. Sampeyan uga bisa maca liyane kene: Struktur data ing gambar. HashMap lan LinkedHashMap . Sampeyan uga bisa maca ing buku. Contone ing kene: " Dasar HashTable "

Graphs, Breadth First Search (search path paling cendhak)

Mbokmenawa salah sawijining topik sing paling menarik yaiku grafik. Lan ing kene, supaya adil, buku kasebut menehi perhatian banget marang dheweke. Mungkin kuwi sebabe maca buku iki. Senajan, mbok menawa, iku bisa wis nyatakake sethitik liyane cetha)) Nanging, kita duwe Internet lan saliyane buku, sampeyan bisa ndeleng dhaptar lagu iki ing teori kanggo "wong sing krungu bab grafik kanggo pisanan . ” Mesthi wae, ing wiwitan buku kasebut, algoritma telusuran sing paling jembar, breadth-first-searchuga dikenal minangka BFS, diwenehake. Buku kasebut ngemot grafik ing ngisor iki: Buku kasebut nyatakake yen antrian bakal mbantu kita. Kajaba iku, supaya kita bisa nambah unsur ing pungkasan lan proses antrian saka wiwitan. Antrian kuwi diarani antrian loro utawa Deque ing basa Inggris. Buku kasebut nyaranake nggunakake struktur data - tabel hash. Kanggo nggandhengake jeneng lan tanggane. Kanthi simpul nomer, sampeyan mung bisa nggunakake array. Panyimpenan simpul iki diarani "Dhaptar simpul jejer," sing ora kasebut ing buku kasebut. Iki minangka minus kanggo wong-wong mau. Ayo dileksanakake ing Jawa:

private Map<String, String[]> getGraph() {
    Map<String, String[]> map = new HashMap<>();
    map.put("you", new String[]{"alice", "bob", "claire"});
    map.put("bob", new String[]{"anuj", "peggy"});
    map.put("alice", new String[]{"peggy"});
    map.put("claire", new String[]{"thom", "jonny"});
    map.put("annuj", null);
    map.put("peggy", null);
    map.put("thom", null);
    map.put("johny", null);
    return map;
}

Saiki telusuran dhewe, dibangun ing data iki:

private String search() {
    Map<String, String[]> graph = getGraph();
    Set<String> searched = new HashSet<>();
    Deque<String> searchQue = new ArrayDeque<>();
    searchQue.add("you");
    while (!searchQue.isEmpty()) {
        String person = searchQue.pollFirst();
        System.out.println(person);
        if (personIsSeller(person)) {
            return person;
        } else {
            String[] friends = graph.get(person);
            if (friends == null) continue;
            for (String friend : friends) {
                if (friend != null && !searched.contains(friend)) {
                    searchQue.addLast(friend);
                }
            }
        }
    }
    return null;
}

Nalika sampeyan bisa ndeleng, ora ana sing rumit. Yen sampeyan mbandhingake karo kode saka buku, iku meh padha.

Grafik, Algoritma Dijkstra

Duwe luwih utawa kurang ngerti BFS, penulis buku ngajak kita ngerti algoritma Daysktra lan grafik bobot. Grafik ing ngisor iki diusulake kanggo solusi: Kaping pisanan, kita kudu ngerti carane makili grafik kita. Kita bisa makili minangka matriks. Artikel babagan Habré bakal mbantu kita ing kene: Algoritma Dijkstra. Nemokake rute optimal ing grafik . Ayo nggunakake matriks adjacency:

public Integer[][] getGraphMatrix(int size) {
    Integer[][] matrix = new Integer[size][size];
    matrix[0][1] = 6;
    matrix[0][2] = 2;
    matrix[2][1] = 3;
    matrix[1][3] = 1;
    matrix[2][3] = 5;
    return matrix;
}

Lan saiki logika dhewe:

@Test
public void dijkstra() {
    Integer[][] graph = getGraphMatrix();           // Данные графа
    Integer[] costs = new Integer[graph.length];    // Стоимость перехода
    Integer[] parents = new Integer[graph.length];  // Родительский узел
    BitSet visited = new BitSet(graph.length);      // "Ферма" маркеров посещённости

    Integer w = 0;
    do {
        System.out.println("-> Рассматриваем вершину: " + w);
        Integer min = null;
        for (int i = 0; i < graph.length; i++) {    // Обрабатываем каждую дугу
            if (graph[w][i] == null) continue;      // Дуги нет - идём дальше
            if (min == null || (!visited.get(i) && graph[w][min] > graph[w][i])) {
                min = i;
            }
            if (costs[i] == null || costs[i] > costs[w] + graph[w][i]) {
                System.out.print("Меням вес с " + costs[i]);
                costs[i] = (costs[w] != null ? costs[w] : 0) + graph[w][i];
                System.out.println(" на " + costs[i] + " для вершины " + i);
                parents[i] = w;
            }
        }
        System.out.println("Вершина с минимальным весом: " + min);
        visited.set(w);
        w = min;
    } while (w != null);

    System.out.println(Arrays.toString(costs));
    printPath(parents, 3);
}

public void printPath(Integer[] parents, int target) {
    Integer parent = target;
    do {
        System.out.print(parent + " <- ");
        parent = parents[parent];
    } while (parent != null);
}

Buku kasebut ngilangi cukup langkah demi langkah. Yen sampeyan nambahake artikel babagan Habré ing Internet + deleng kode kasebut, sampeyan bisa ngelingi. Aku nemokake analisis langkah-langkah sing rada cluttered. Nanging kanggo alam step-by-step dhewe iku plus. Sakabèhé, ok, sanajan bisa luwih apik)

Algoritma rakus

Bagean sabanjure dikhususake kanggo "algoritma rakus". Bagian iki menarik amarga nggunakake set (java.util.Set). Pungkasan, kita bisa ndeleng kenapa bisa uga dibutuhake. Kita nggunakake dhaptar negara minangka input:

Set<String> statesNeeded = new HashSet();
statesNeeded.addAll(Arrays.asList("mt", "wa", "or", "id", "nv", "ut", "ca", "az" ));

Lan uga dhaptar stasiun radio sing nyakup sawetara negara kasebut:

Map<String, Set<String>> stations = new HashMap<>();
stations.put("kone", new HashSet(Arrays.asList("id", "nv", "ut")));
stations.put("ktwo", new HashSet(Arrays.asList("wa", "id", "mt")));
stations.put("kthree", new HashSet(Arrays.asList("or", "nv", "ca")));
stations.put("kfour", new HashSet(Arrays.asList("nv", "ut")));
stations.put("kfive", new HashSet(Arrays.asList("ca", "az")));

Buku kasebut terus nuduhake lan nerangake algoritma kasebut dhewe:

Set<String> finalStations = new HashSet();
while (!statesNeeded.isEmpty()) {
    String bestStation = null;
    Set<String> statesCovered = new HashSet();
    for (String station: stations.keySet()) {
        Set covered = new HashSet(statesNeeded);
        covered.retainAll(stations.get(station));
        if (covered.size() > statesCovered.size()) {
           bestStation = station;
           statesCovered = covered;
        }
    }
    statesNeeded.removeAll(statesCovered);
    finalStations.add(bestStation);
}
System.out.println(finalStations);

Pemrograman dinamis

Buku kasebut uga nggambarake masalah sing ditrapake pendekatan sing diarani "pemrograman dinamis". Tugas kasebut diwenehi: Kita duwe tas 4 lb. Sampeyan kudu nemokake item sing paling nguntungake kanggo bobot tartamtu. Pisanan, ayo nggawe dhaptar item:

List<Thing> things = new ArrayList<>();
things.add(new Thing("guitar", 1, 1500));
things.add(new Thing("tape recorder", 4, 3000));
things.add(new Thing("notebook", 3, 2000));

Saiki algoritma dhewe:

int bagSize = 4;
int cell[][] = new int[things.size()][bagSize];
// Заполняем первую строку без условий
for (int i = 0; i < bagSize; i++) {
    cell[0][i] = things.get(0).cost;
}
// Заполняем оставшиеся
for (int i = 1; i < cell.length; i++) {
    for (int j = 0; j < cell[i].length; j++) {
        // Если вещь не влезает - берём прошлый максимум
        if (things.get(i).weight > j+1) {
            cell[i][j] = cell[i - 1][j];
        } else {
            // Иначе текущая стоимость + предыдущий максимум оставшегося размера
            cell[i][j] = things.get(i).cost;
            if (j + 1 - things.get(i).weight > 0) {
                cell[i][j] += cell[i-1][j + 1 - things.get(i).weight];
            }
        }
    }
}
System.out.println(Arrays.deepToString(cell));

Ana uga tugas sing menarik kanggo nemokake tembung sing paling padha. Menarik, ta? Rincian liyane ing kene: LongestCommonSubsequence.java

Telusuri tetanggan sing paling cedhak

Buku kasebut uga ngomong kanthi jelas babagan algoritma tetanggan sing paling cedhak: Lan rumus kanggo pitungan diwenehi:

Garis ing ngisor

Buku kasebut diakhiri karo bagean "Apa Sabanjure?", sing menehi ringkesan cepet babagan algoritma sing menarik. Mangkene katrangan ringkes babagan makna wit lan algoritma liyane. Sakabèhé, aku seneng buku kasebut. Sampeyan ngirim ora dianggep serius minangka sawetara jinis informasi lengkap. Sampeyan kudu nggoleki lan ngerti dhewe. Nanging minangka informasi pambuko kanggo kapentingan lan menehi idea dhisikan, iku cukup apik. Ya, kode ing buku kasebut ditulis nganggo Python. Dadi kabeh conto ing ndhuwur bisa dikompilasi) Muga-muga review iki bisa mbantu sampeyan ngerteni apa isi buku kasebut lan apa sing kudu dituku.

Kajaba iku

Sampeyan uga bisa mriksa sumber ing ngisor iki babagan topik iki:

1. EdX - Pambuka Pemrograman Java: Struktur Data Fundamental lan Algoritma
2. LinkedIn - Pambuka Struktur Data & Algoritma ing Jawa (mbayar)
3. 27 situs kanthi teka-teki kanggo ngasah katrampilan program sampeyan
4. Java CodingBat
5. Tugas kanggo programer, jawaban kanggo tugas saka macem-macem kerumitan

#Viacheslav