Alkogor algoritmleri ýa-da algoritmlere agyrsyz giriş

"Grocking algoritmleri" kitabyna syn. Biraz şahsy pikir, birnäçe mysal. Bu syn, bu kitaby okamak isleýändigiňize ýa-da tekjäňizde ýer almajakdygyna düşünmäge kömek eder diýip umyt edýärin. DUNDURYŞ: Köp tekst)

“Grocking algoritmleri” ýa-da algoritmlere agyrsyz giriş

Giriş

Junior derejesindäki boş iş ýerleriniň hemmesinde diýen ýaly “maglumat gurluşlaryny we algoritmleri bilmek” ýaly talaplar bar. Specializedöriteleşdirilen bilimi bolanlar üçin algoritmler umumy dersiň içine girýär we hiç hili problema bolmaly däldir. Emma ösüş beýleki sähralardan getirilen bolsa näme etmeli? Galan zat, özbaşdak öwrenmek. “Kim günäkär” diýen soraga jogap bar, ýöne “näme etmeli” diýen soraga jogap gözlemeli. Geliň, kitaplara seredeliň. Men size biri hakda aýdasym gelýär.

Grok algoritmleri

Thehli eserleriň arasynda “Grocking algoritmleri” ýaly kitaba duş geldim. Bu ýerde has giňişleýin maglumat alyp bilersiňiz: " Ösýän algoritmler kitaby. Programmistler we bilesigelijiler üçin suratly gollanma ." Kitaby köp wagt öň görüpdim, ýöne ozonyň bahasy 680 rubl. Gymmat ýa-da arzan - her kim özi karar berýär. Men eýýäm Avito-da ikinji kitaby ýarym bahadan satyn alýaryn. Şeýdip, Sankt-Peterburgda tapdym, satyn aldym we gözümi açdym. Haýsy siziň bilen paýlaşmak kararyna geldim. Hawa, kitapda Java kody ýok, ýöne ... başga kod bar, ýöne soňrak has köp.

Algoritmlere giriş (Saýlama tertibi)

Şeýlelik bilen, aňsat kyssa görnüşinde, çykyşymyzda birinji tertibe ýetýäris. Bu saýlama tertibi. Onuň düýp manysy, elementleri çepden saga (0 elementden iň soňuna çenli) geçip, galan elementleriň arasynda iň ulusyny gözlemekdir. Eger tapsak, häzirki elementimizi we iň uly elementi çalşarys. Ilki bilen bir massiw hakda pikirlenmegiň iň ýönekeý usuly: [5, 3, 6, 2, 10]. Kagyz kagyzy, ruçka (iň ýönekeý we iň arzan ýol) alyň we çep araçägimiziň (çepde), häzirki indeksiň (ýa-da sag serhediň) bardygyny göz öňüne getiriň, iň az elementiň görkezijisi bar. Munuň bilen nähili işleýäris. Mysal üçin: Algoritmler köplenç psevd kodunda, mysal üçin Wikipediýada beýan edilýär. Biziňkiler takyk pseudokod däl, has soňrak. Häzirlikçe göreliň:

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]))

Indi ony Java kody görnüşinde hödürläliň:

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;
            }
        }
}

Görşüňiz ýaly, kod birmeňzeş diýen ýaly. Birinji kod kitapdan mysal. Ikinjisi, Java koddaky mugt ýerine ýetirişim.

Gaýtalanma

Ondan soň gaýtalanma ýaly bir zadyň bardygyny aýdýarlar. Ilki bilen, AxB ululygy bolan daýhan hakda bir mesele bar. Bu meýdany deň “kwadratlara” bölmek zerur. Ondan soň ucewklid algoritmi agzalýar. Halamaýan zadym, koduny ýazmaga synanyşmadylar. Emma ucewklid algoritmi ýönekeý we täsirli: Dogrymy aýtsam, şu wideodaky ýaly kitapdaky käbir maglumatlary sypdyrdym: “ Informatika. Algoritmleriň nazaryýeti. Ewklidiň algoritmi . " Mysal üçin, a b-den az bolsa, birinji ylgaw wagtynda b we a üýtgeýär ýerleri üýtgeder we ikinji gezek ulusy kiçisi bilen bölüner. Şonuň üçin argumentleriň tertibi möhüm däl. Hemişe bolşy ýaly, ilki bilen kagyz ýüzündäki algoritmi “duýup bileris”: Indi koda seredeliň:

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

Şol bir kody Java-da ýazalyň. Isleseňiz, onlaýn düzüjini ulanyp bileris :

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

Kitabyň başynda zawod hem agzaldy. N (n!) Sanyň faktory 1-den n-a çenli sanlaryň önümidir. Näme üçin beýle edýär? Bu ýerde bir amaly programma bar. N obýektlerimiz bar bolsa (mysal üçin, n şäherler), onda olardan n ýasap bileris! Kombinasiýa. Gaýtalanma barada has giňişleýin maglumaty şu ýerden okap bilersiňiz: " Gaýtalanma. Okuw meseleleri ." Gaýtalama we gaýtalanýan çemeleşmeleri deňeşdirmek: " Gaýtalanma ".

Çalt görnüş

Çalt sortlamak gaty gyzykly algoritmdir. Kitap oňa kän bir ähmiýet bermeýär. Mundan başga-da, kod diňe birinji element saýlananda iň erbet ýagdaý üçin berilýär. Şeýle-de bolsa, ilkinji tanyşlygy üçin bu mysaly ýatda saklamak has aňsat bolar. Hemmesini ýazmazlykdan erbet çalt ýazmak has gowudyr. Ine, kitapdan bir mysal:

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)

Bu ýerdäki hemme zat gaty ýönekeý. 0 ýa-da 1 elementden ybarat massiwimiz bar bolsa, ony tertiplemegiň zerurlygy ýok. Has ulurak bolsa, massiwiň birinji elementini alarys we ony “esasy element” hasaplaýarys. 2 sany täze massiw döredýäris - biri merkezden has uly elementleri, ikinjisinde kiçi elementleri öz içine alýar. We gaýtalaýarys. Iň oňat warianty däl, ýöne ýene-de has gowy ýatda saklanýar. Geliň, bu algoritmi Java-da durmuşa geçireliň, ýöne has dogrysy. “ JavaScript-de kompýuter ylymlary: Quicksort ” synyndan alnan material bize bu meselede kömek eder . Kod ýazmazdan ozal, algoritmi “duýmak” üçin ýene bir gezek çekeliň: Ilki bilen, algoritme düşünmek üçin ýene bir kagyz ýüzüne çekeliň: Iň howply pursatlaryň biri problemalary doly çözmek ýaly bolup görünýär. Şonuň üçin durmuşa geçirmegi birnäçe ownuk ädimde ýerine ýetireris:

• Elementleri bir massiwde çalşyp bilmeli:

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




• Bize görkezilen aralykda massiwi 3 bölege bölýän usul gerek

  
  

  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;
  }

  Jikme-jiklikler ýokardaky baglanyşykda. Gysgaça aýdanymyzda, element kursdan az bolýança çep kursory süýşürýäris. Edil şonuň ýaly, sag kursory beýleki ujundan süýşüriň. Kursorlar gabat gelmese çalşarys. Kursorlar birleşýänçä dowam edýäris. Geljekde gaýtadan işlemegi 2 bölege bölýän indeks gaýtarýarys.

• Aýralyk bar, sortlamagyň özi gerek:

  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);
              }
          }
  }

  .Agny, massiw azyndan iki elementden ybarat bolsa, onda eýýäm tertiplenip bilner. Ilki bilen, ähli massiwi iki bölege bölýäris, pivotdan kiçi elementler we has uly elementler. Soňra emele gelen bölekleriň her biri üçin şuňa meňzeş hereketleri edýäris.

  Synag üçin:

  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));
  }

Kitapda, bu algoritmiň gaýtadan işlenen maglumatlar toplumy her gezek iki bölege bölünende, “Bölün we ýeň” diýilýän algoritmlere degişlidigi aýdylýar. Algoritm çylşyrymlylygy: O (nLogn) Erbet tarapy (ýagny, halamadyk zadym) kitapda geçişiň birleşmegi hakda aýdylýar, ýöne hiç hili mysal ýa-da kod berilmeýär. Has giňişleýin maglumaty şu ýerden tapyp bilersiňiz: " Informatika. Algoritmleri gözläň we tertipläň: sortlaşdyryň ". Şonuň üçin yzygiderlilik üçin geliň, muny özümiz edeliň. Elbetde, algoritmiň özi ýönekeý we gönümel:

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);
}

Biz ortasyny kesgitleýäris we massiwi iki bölege bölýäris. Her ýarym üçin edil şonuň ýaly edýäris we ş.m. Stopagdaýy ýa-da esasy ýagdaýy duruzmak - birden köp element bolmaly, sebäbi bir elementi ikä bölüp bilmeris. Indi birleşmegi amala aşyrmaly, ýagny birleşdirmeli:

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);
}

Bu ýerde teswir ýazjak kän däl. Üýtgeýjileriň atlaryndan printlnhemme zat düşnüklidir. Barlamak üçin:

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

Haş tablisalary

Kitap hash tablisalaryna-da degýär. Muny özüňiz amala aşyrmak hökman däl we hash tablisalarynyň manysy gaty ýönekeý. Galyberse-de, Java-da java.util.HashTable hash tablisalary bar. “HashTable” enjamyna seretsek, Giriş massiwiniň içerde ýaşaýandygyny göreris. Giriş, açar - bahanyň utgaşmasy bolan ýazgydyr. HashTable başlangyçCapacity - ýagny başlangyç ululygy bar. LoadFactor - ýük faktory. Bellenen 0.75. Bu san massiwiň haýsy ýükünde (elementleriň sany / jemi mukdar) ululygyny köpeltmelidigini aýdýar. Java-da 2 esse ýokarlanýar. Kitap, Haş tablisalaryna hash tablisalary diýilýändigini düşündirýär, sebäbi hash funksiýasyna esaslanyp, massiw öýjügi (sebedi) Entry. Şeýle hem bu ýerde has köp okap bilersiňiz: Suratlardaky maglumatlar gurluşlary. HashMap we LinkedHashMap . Kitaplarda hem okap bilersiňiz. Mysal üçin şu ýerde: " HashTable esaslary "

Grafalar, giňlik ilkinji gözleg (iň gysga ýol gözlegi)

Iň gyzykly mowzuklaryň biri grafiklerdir. Ine, dogrymy aýtsam, kitap olara köp üns berýär. Belki, şonuň üçinem bu kitaby okamaga mynasypdyr. Belki-de, birneme has aýdyň beýan edilip bilnerdi)) Emma, ​​biziň internetimiz bar we kitapdan başga-da, “ ilkinji gezek grafikalary eşidýänler üçin” teoriýa boýunça bu pleýliste seredip bilersiňiz . " Elbetde, kitabyň başynda breadth-first-searchBFS diýlip hem atlandyrylýan giňlikdäki gözleg algoritmi berilýär. Kitapda aşakdaky grafik bar: Kitapda nobatyň bize kömek etjekdigi aýdylýar. Mundan başga-da, ahyryna elementler goşup, nobaty başdan başlap bileris. Şeýle nobatlara iňlis dilinde iki taraplaýyn nobat ýa-da Deque diýilýär. Kitap maglumat gurluşyny - hash tablisasyny ulanmagy teklip edýär. Adyny we goňşularyny baglanyşdyrmak. Sanly diklikler bilen diňe bir massiw ulanyp bilersiňiz. Bu dikligine ammarda “goňşy depeleriň sanawy” diýilýär, bu kitapda agzalmaýar. Bu olar üçin minus. Muny Java-da durmuşa geçireliň:

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;
}

Indi gözlegiň özi, şu maglumatlara esaslanýar:

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;
}

Görşüňiz ýaly çylşyrymly zat ýok. Kitabyň kody bilen deňeşdirseň, birmeňzeş.

Grafalar, Dijkstranyň algoritmi

BFS-ä has az düşünen kitabyň awtory, “Daysktra” algoritmine we agyr grafiklere düşünmäge çagyrýar. Çözüw üçin aşakdaky grafik teklip edilýär: Ilki bilen grafiklerimizi nädip görkezmelidigine düşünmeli. Matrisa hökmünde görkezip bilerdik. Habré hakda bir makala bize şu ýerde kömek eder: Dijkstranyň algoritmi. Grafada iň amatly ugurlary tapmak . Goňşy matrisany ulanalyň:

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;
}

Indi logikanyň özi:

@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);
}

Kitap ony ädim-ädim bölekleýär. Internetde Habré hakda makala goşsaňyz, koda serediň, ýadyňyza düşüp biler. Stepdimme-ädim derňewi birneme bulaşyk gördüm. Natureöne ädimme-ädim tebigatyň özi goşmaça. Umuman, bolýar, has gowy bolup bilerdi)

Açgöz algoritmler

Indiki bölüm “açgöz algoritmlere” bagyşlanýar. Bu bölüm gyzykly (sebäbi java.util.Set). Ahyrynda näme üçin zerur bolup biljekdigini görüp bileris. Döwletleriň sanawyny giriş hökmünde ulanýarys:

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

Şeýle hem bu ştatlaryň käbirini öz içine alýan radiostansiýalaryň sanawy:

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")));

Kitap algoritmiň özüni görkezýär we düşündirýär:

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);

Dinamiki programmirleme

Şeýle hem kitapda “dinamiki programmirleme” diýilýän çemeleşmäniň ulanylýan meseleleri beýan edilýär. Wezipe berilýär: Bizde 4 funt sumka bar. Berlen agram üçin iň girdejili zatlary tapmaly. Ilki bilen zatlaryň sanawyny düzeliň:

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));

Indi algoritmiň özi:

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));

Iň meňzeş sözleri tapmak üçin gyzykly mesele hem bar. Gyzykly, şeýlemi? Has giňişleýin maglumat şu ýerde: LongestCommonSubsequence.java

Iň ýakyn goňşulary gözläň

Kitapda iň ýakyn goňşularyň algoritmi barada-da aýdyň aýdylýar: Hasaplamagyň formulasy berilýär:

Aşakdaky setir

Kitap gyzykly algoritmlere gysgaça syn berýän gyzykly "Indiki näme?" Bölümi bilen tamamlanýar. Ine, agaçlaryň we beýleki algoritmleriň manysynyň gysgaça beýany. Umuman, kitaby haladym. Bir hili giňişleýin maglumat hökmünde çynlakaý garamaly däldir. Özüňiz gözlemeli we düşünmeli bolarsyňyz. Interestöne gyzyklanma we başlangyç pikir bermek üçin giriş maglumatlary hökmünde gaty gowy. Hawa, kitapdaky kod Python-da ýazyldy. Şonuň üçin ýokardaky mysallaryň hemmesi düzülip bilner) Bu syn, kitabyň içinde nämeleriň bardygyny we satyn almaga mynasypdygy barada düşünje almaga kömek eder diýip umyt edýärin.

Mundan başga-da

Şeýle hem bu mowzukdaky aşakdaky çeşmeleri gözden geçirip bilersiňiz:

1. EdX - Java programmirleme bilen tanyşlyk: Esasy maglumatlar gurluşlary we algoritmler
2. LinkedIn - Java-da maglumat gurluşlary we algoritmler bilen tanyşlyk (tölegli)
3. Programmirleme ukyplaryňyzy ýitileşdirmek üçin 27 sany saýt
4. Java kodlaşdyrma
5. Programmistler üçin meseleler, dürli çylşyrymly meseleleriň jogaplary

# Wiaçeslaw