2007. Structuri de date, algoritmi, obiecte

Recomandați documente

Structuri de date, algoritmi, obiecte

BMF-NIK-AAO Structuri de date, algoritmi, obiecte (AAO) Colecție de extrase din materialul 2005/2006 pe baza prelegerilor lui László Csink și Árpád Miklós.

Conţinut. 1. Descrierea algoritmului, definiție. . 4 Rezolvarea unei ecuații pătratice. 5 Scădere aproximativă a rădăcinii (metoda Newton). 7 2. Elemente de programare simple. 8 Calcul serial. 8 Decizie. 9 Selecție. 10 Numărare. 11 Căutarea. 12 Căutare maximă. 12 3. Conversii de date, cicluri, funcții, tablouri. 13 Conversii de date. 13 Funcții. 16 4. Sortare, sortare, căutare binară. 19 Selecție. 19 Sortare (în două blocuri). 20 Sortare (într-o singură matrice). 20 Căutare binară. 21 5. Operații de setare. 22 Secțiunea. 22 Uniunea. 23 Potrivire. 23 6. Aranjamente. 24 Sortare cu bule. 24 Linie de cocktail. 25 Aranjament gnom de grădină. 26 Dispunerea pieptenei (rândul coapsei). 27 Sortare maximă a selecției. 28 Inserați sortarea. 28 Amenajarea porumbelului. 29

BMF-NIK-AAO 7. Sortarea rapidă (rapid). 30 Recursiv. 30 Nu recursiv. 31 8. Algoritmi de jocuri. 35 9. Găsirea unei căi labirint. 39 10. Cuvântul problemă. 42 11. Algoritmi cu matrice. 45 Matrici rare. 45 Înmulțirea în lanț a matricelor. 47 Înmulțirea matricei Strassen. 47 12. Pătratul magic. 49 Conceptul pătratului magic. 49 pătrate magice echivalente. 50 Obținerea sumei magice. 50 Metoda Coxeter. 51 Metoda piramidei. 52 13. Alți algoritmi. 53 Algoritmul euclidian. 53 Seria Fibonacci. 53 Schema Horner. 54 Sita Eratostenea. 54 14. Partea OOP (prelegeri de Árpád Miklós). 55 Modele de calcul și paradigme de programare. 55 Paradigma de programare orientată pe obiecte. 60 Fundamentele paradigmei orientate obiect. 66 Deblocarea, ascunderea datelor. 74 Moștenire. 79 Diversitate. 83 Reutilizarea codului (contur prescurtat). 89

2. Elemente de programare simple: Calcul serial, am anulat factura la gaz în fiecare lună a anului trecut. Vreau să calculez câți bani costă consumul anual de gaze. ” Etape ale soluției: 1. Resetați o variabilă de agregare. 2. Repet următorii doi pași de 12 ori: mă uit la următoarea factură, o adaug la suma anterioară. 3. În sfârșit obțin rezultatul. Pseudocod: VARIABILE i, suma ÎNTREG, factură [i] REAL (sau ÎNTREG) i ← 0; suma ← 0; REPETĂ DACĂ (i mai puțin de 12) < sum←sum+szamla[i]; >ANUNȚ (sumă)

(numerotarea lunilor începe de la 0 conform marcajului)

Decizie BMF-NIK-AAO Aș dori să decid pe baza notelor unui elev dacă este excelentă sau nu. Sunt posibile două tipuri de idei: 1.

Dacă există vreunul dintre biletele dvs. care nu sunt cinci, acestea nu sunt excelente

Să ne uităm la bilete, mai întâi primul, apoi restul la rând și să ne asigurăm că sunt cinci. Dacă găsim ceva care nu este ridicat la cinci, atunci nu este nevoie să ne uităm la bilete suplimentare, deoarece există o notă care nu este de cinci, adică nu excelentă. Pseudocod: VARIABILE număr_subiect, i, bilete [i] ÎNTREGI, van_nemotos LOGIC i ← 1 REPETĂ DACĂ (i numărul_subiect) PREZENT (toate_otos)

Selecția BMF-NIK-AAO Din hârtiile închise ale unui cerc rezervor, selectați una dintre hârtiile suficiente. Soluție: să ne uităm la disertații, mai întâi la primele, apoi la celelalte unul câte unul până găsim suficiente disertații. Când vom găsi suficient, el va fi ales. Pseudocod: VARIABILE i, număr, număr de lucrări, lucrări [i] ÎNTREGI i ← 1 REPETĂ DACĂ ((numărul de zile) Console.WriteLine („Fără soluție”); altfel Console.Write (i + „ziua!”);

Numărare BMF-NIK-AAO Problema anterioară este ușor modificată. Numărați câte zile (dacă există) venitul companiei a depășit 20.000 HUF? Cod de numărare: int piece = 0; pentru (i = 1; i 20) piese ++; Console.WriteLine (piesa + „venitul zilei a fost de peste 20 de mii de forinți”);

Selecție maximă M-am uitat aseară la hartă. Mi-am scris altitudinea a 10 munți înalți deasupra nivelului mării. Intră pe cel mai înalt vârf! Soluție: observ înălțimea primului munte. Consider că acesta este cel mai înalt. Mă uit printre ceilalți munți unul câte unul: dacă unul este mai înalt decât cel mai înalt de până acum, îl uit pe cel mai înalt de până acum și îl notez pe cel nou. La final, se va nota cel mai înalt munte. Cod: numar int munte = 10; int [] high = new int [număr munte + 1]; // pentru că indexăm de la 1 int i; Random RandomClass = new Random (); pentru (i = 1; i max) < max=magas[i]; eddigi=i; >Console.WriteLine ("cel mai mare număr de serie din (unul):" + precedent + "înălțime:" + max);

Dacă, să zicem, Muntele 2 și Muntele 7 au aceeași înălțime și restul sunt toate mai mici, va rezulta 2 sau șapte? Vor fi 2. Cu toate acestea, dacă se introduce> = în loc de>, atunci 7.

3. Conversii de date, bucle, funcții, tablouri Conversii de date Conversia în C # poate fi implicită sau explicită. Dacă conversia este automată, vorbim despre o conversie implicită, caz în care nu există pierderi de date. Conversia explicită este forțată, caz în care poate apărea pierderea datelor. Conversia are loc cel mai adesea în timpul unui transfer de parametri de apel funcțional sau pentru calcule numerice cu date mixte. Săgețile arată opțiunile implicite de conversie:

Conversie numerică implicită: lung x1; int y1 = 25; x1 = y1; Console.WriteLine (x1); int x1; lung y1 = 25; x1 = y1;

// conversie numerică implicită int → lung

// lung → săgeată int lipsă: mesaj de eroare ...; // dar ok pentru că este posibilă pierderea de date!

Soluție BMF-NIK-AAO cu turnare (explicită): int x1, x2; lung y1 = 2147483647, y2 = 21474836470; // y1 „se potrivește” în int, y2 nu se potrivește x1 = (int) y1; x2 = (int) y2; // (int) cast Console.WriteLine (x1 + ”” + x2); // x1 = 2147483647, x2 = -10 // x2 a pierdut date

Întreaga divizare sau diviziune reală? int i = 13, j = 7; int k = i/j; Console.WriteLine (k); float k1 = i/j; Console.WriteLine (k1); float k2 = (float) i/j; Console.WriteLine (k2); Console.WriteLine (55/7); Console.WriteLine (55.0/7); plutitor i = 13; int j = 7; Console.WriteLine (i/j); Console.WriteLine ((int) i/j); dublu i1 = 13,15; int j = 7; Console.WriteLine (i1/j); Console.WriteLine ((int) i1/j); plutitor i2 = 13,15; int j = 7; Console.WriteLine ((int) i2/j);

// ambele argumente sunt inițial întregi // PRINT: 1 // PRINT: 1 //1.857143 // (float) i/(float) j sau i/(float) j este de asemenea bun! // 7 //7.8571 . // i real dar cu valoare întreagă //1.85 . // 1 // i1 valoare dublă, fără număr întreg //1.87 . // 1 // i2 real non-întreg valoare // EROARE: float nu poate fi convertit

Convertiți o variabilă cu punct dublu într-un număr întreg cu pierderi de date: dublu i2 = 13,83; Console.WriteLine ((int) i2);

Exemplu de expresie logică: int a = 7; jurnal bool; log = a% 2 == 0; // log = (a% 2 == 0); if (log) Console.WriteLine ("asociat"); else Console.WriteLine ("ciudat");

BMF-NIK-AAO Șir → șir de valoare numeric (întreg) sz = ”123”; int sz1 = Int32.Parse (sz); int sz2 = Convert.ToInt32 (sz);

Șir → șir de valori numerice (reale) myDoubleStr = ”- 12.2”; double x = Double.Parse (myDoubleStr) +5,3; y dublu = Convert.ToDouble (myDoubleStr) +1,1; Console.WriteLine (x); // - 6.9 Console.WriteLine (y); // - 11.1 // merită să fim atenți la utilizarea punctelor zecimale sau a virgulelor

Divizați textul în cuvinte șir s = "Odată # unde # nu exista" char [] seps = new char [] foreach (șir ss sin s.Split (seps)) Console.WriteLine (ss);

// Acest lucru trebuie dezasamblat // caracterele separatoare // ss rezultatul

Rezultat: A fost odată nu

Funcții BMF-NIK-AAO Folosirea funcțiilor fără schimbarea valorii statice publice a valorii returnate < b=5; >gol static Main ()

Returnează o valoare în numele metodei static static int change (int b) < b=5; return b; >gol static Main ()

// va fi egal cu 5

Transferul parametrilor după adresă (ieșire) modificare statică publică nulă (ieșire int b) < b=5; >gol static Main ()

// nu trebuie să obțineți valoarea

BMF-NIK-AAO Listă de argumente variabile Utilizarea unui set de parametri vă permite să utilizați un număr variabil de parametri de același tip. Cuvântul cheie params trebuie inclus în definiție, dar nu atunci când este apelat. Lista parametrilor este urmată de o matrice unidimensională în definiție, orice număr de parametri (până la zero) poate fi inclus la apel, cu condiția ca tipul să fie compatibil. Exemplu de utilizare a parametrilor: static ShowNumbers nul (parametrii int [] numere) < foreach (int x in numbers)< Console.Write(x+” ”); >Console.WriteLine (); > static gol Main ()< int[] x=; ShowNumbers(x); ShowNumbers(4, 5); Console.ReadKey(); >

Rezultate: 123 45

BMF-NIK-AAO One-dimensional array int [] itomb; itomb = new int [3]; pentru (int i = 0; i 0) < p[pdb]=t[i]; pdb++; >altceva < np[npdb]=t[i]; npdb++; >i ++; >

// index de la 0 la n-1

Separare (într-o singură matrice) În ceea ce privește alocarea memoriei, algoritmul anterior care utilizează două matrice este ineficient: ambele matrice p și np trebuie declarate ca n elemente, dar există doar n elemente în cele două matrice în total. De asemenea, puteți utiliza o matrice, apoi puneți numerele pozitive în prima jumătate a acesteia și puneți restul în a doua jumătate (începând din spate). Acest algoritm plasează elementele pozitive ale unui tablou t (indici de la 0 la n-1) la începutul unui tablou p, elementele negative la sfârșitul unui tablou p. Cod C #: i = 0; pdb = 0; veg = n-1; în timp ce (i 0) p [pdb ++] = t [i]; else p [veg -] = t [i]; i ++; >

BMF-NIK-AAO Căutare binară Puteți căuta cu el numai într-o secvență ordonată. k = necesită pași log2n. (n număr de articole) Cum funcționează: înjumătățește întotdeauna lista de date și analizează ce parte a datelor pe care o căutați. Atunci uită-te mai departe în el. C # cod int de asemenea, sus, centru, spațiu, n; // n = numărul de elemente elementtype data = new elementtype (); // tipul de element de date de căutat [] a = tip de element nou []; // lista pe care o căutăm; de asemenea = 1; felso = n; mijloc = (și + sus)/2; while ((și = n) c [k ++] = a [j]; // dacă a existat unul, puneți c>> k; // setați sfârșitul lui c pentru (i = 0; ia [i + 1 ]) < //ha rossz a sorrend cserélünk int cs; cs=a[i]; a[i]=a[i+1]; a[i+1]=cs; csere_volt=1; //még nem biztos hogy jó a sorrend >>

Când bucla while rulează o dată, cel mai mare element va fi ultimul. Dacă secvența este (accidental) sortată în avans, suntem pregătiți, dacă a avut loc cel puțin o înlocuire, timpul va rula din nou, iar următorul element ca mărime va fi penultimul. Un element este înlocuit în fiecare pas, deci în timp ce nu poate rula mai mult de n ori. Cel mai rău caz: Sortarea cu bule necesită cel mai rău caz O (n * n). Fiecare articol se poate deplasa la o poziție cu prețul unei comparații (sunt comparate articolele adiacente). Un element poate fi la o distanță de cel mult n-1 de locația sa corespunzătoare secvențial, deci poate fi restaurat cu cel mult n-1 = O (n) operațiuni, astfel încât la (n-1) * (n-1 ) = O (n * n) operații nu pot exista mai mult decât pentru sortare completă.

Experimentele pe o matrice de 10.000 de elemente au arătat că pieptănarea a fost puțin mai proastă decât cea rapidă (10%); schimbarea nu este mare în comparație cu balonul. Cu toate acestea, nu este nevoie să vă faceți griji cu privire la o carcasă pre-aranjată, care încetinește foarte mult rapiditatea. Stabilind decalajul, mai întâi sortăm elementele absente. Apoi, decalajul se micșorează până când devine în cele din urmă unul. În acest caz, programul este același cu balonul; în consecință corectă. Lacey și Richard Box au arătat că decalajul este divizibil cu 1,3 în fiecare mișcare. Mai mult, s-a descoperit că 9 și 10 nu sunt potrivite pentru goluri și trebuie înlocuite cu 11.

BMF-NIK-AAO Selectare maximă Sortare Sortare matrice folosind cel mai mare element. Selectați cel mai mare și înlocuiți-l cu ultimul. (n este lungimea tabloului) C # cod int max, cs; pentru (int i = n; i> 1; i--)< max=i; for(int j=i-1; j>0; j--) if (a [j]> a [max]) max = j; cs = a [i]; a [i] = a [max]; a [max] = cs; >

Inserare sortare Luați următorul articol și găsiți-l în partea deja sortată din stânga. În paralel cu căutarea, elementele mai mari sunt mutate unul spre dreapta, respectiv. C # cod element tip x = nou tip element (); tip de element [] a = tip de element nou []; int i, j; pentru (i = 2; i = 1) && (x
28

// aruncați piramida

// produce pătratul magic

// dacă este verde // dacă este violet // dacă este roșu // dacă este albastru

13. Alte algoritmi Algoritmul euclidian gcd = cel mai mare divizor comun = cel mai mare divizor comun Vrem să determinăm cel mai mare divizor comun al numerelor A și B. Să presupunem că T este restul obținut prin împărțirea lui A la B. Deci: A = qB + T, unde q este coeficientul diviziunii. Orice divizor comun al lui A și B împarte T (din moment ce T = A-qB). În mod similar, orice divizor comun al lui B și T îl împarte pe A. Cel mai mare divizor comun al lui A și B este egal cu cel mai mare divizor comun al lui B și T. Deci, este suficient dacă continuăm procedura cu B și T. De când | T | b) a = a-b; altfel b = b-a; retur a; >

// scade întotdeauna cel mai mic din cel mai mare

Seria Fibonacci este o serie de numere Fibonacci: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, ... Un membru al seriei este obținut prin adăugarea celor doi anteriori. (cu toate acestea, dacă n = 0, atunci valoarea elementului este 0, dacă n = 1, atunci valoarea elementului este 1). C # cod // această funcție returnează al X-lea număr Fibonacci. nesemnat int f (int x)< return x