Snímek 1 - MENDELU

Snímek 1 - MENDELU

Vnitn azen v poli (in sito) Je dn vektor N sel (celch, desetinnch, znak, etzc znak). Vytvote proceduru pro jejich vzestupn seazen. een: Za pedpokladu, e jsou definovny typy type INDEX = 0..MAXPOCET; SLOZKA = integer; {me bt real, string[20] atp.} A = array[INDEX] of SLOZKA; kde MAXPOCET je definovan konstanta nap. const MAXPOCET=20; omezujc pouitelnost dle uvedench procedur na zpracovn N-lennch vektor (N je maximln MAXPOCET). 1 K seazen poloek pouijeme metodu pmho vbru (straight selection). Princip: Ze vech poloek vektoru vyber nejmen hodnotu. Vym vzjemn nalezenou hodnotu s hodnotou v prv poloce vektoru. Pot vyber nejmen prvek ze zbylch N-1 prvk (z 2. a N-t poloky) a vym ho s druhou polokou atd. a zstane posledn Nt (maximln) prvek. 2 procedure STRSEL(var POLE:A; N:INDEX);

var I,J,K: INDEX; POM: SLOZKA; begin for I:=1 to N-1 do begin K:=I; POM:=POLE[I]; for J:= I+1 to N do if POLE[J]

POM :SLOZKA; begin for I:=2 to N do begin POM:=POLE[I]; POLE[0]:=POM; J:=I-1; while POM

6 procedure BUBBLE(var POLE:A; N:INDEX); var I,J :INDEX; POM :SLOZKA; begin for I:=2 to N do for J:=N downto 2 do {s vhodou downto I} if POLE[J-1]>POLE[J] then begin POM:=POLE[J-1]; POLE[J-1]:=POLE[J]; POLE[J]:=POM end end end; 7 b) u bublinovho azen s vhodou (tzv. Ripple sort) je vzata v vahu skutenost, e vektor me bt setdn dve ne po N-1 krocch. Princip: Postupujeme zkoumnm J-t dvojice, pro J=1..N-I, v rmci I-tho kroku Testujeme, zda v I-tm kroku dolo k vmn alespo u jedn dvojice. Pokud ne, je ji vektor setdn. 8

procedure RIPPLE(var POLE:A; N:INDEX); var J,I : INDEX; POM : SLOZKA; SETRIDENO : Boolean; begin I:=1; repeat SETRIDENO := true; {setdno} for J:=1 to POC do if POLE[J+1]

jdeme tot opakovat do dalho kroku. Seazen vektoru nastv v okamiku, kdy ani pi prchodu zdola nahoru, ani pi prchodu shora dol neprovdme vmnu. 10 procedure SHAKER(var POLE:A; N:INDEX); var I,J,H,D : INDEX; POM : SLOZKA; begin H := 2; D := N; I := N; repeat for J := D downto H do if POLE[J-1] > POLE[J] then begin POM := POLE[J-1]; POLE[J-1] := POLE[J]; POLE[J] := POM; I := J end; H := I + 1; for J:= H to D do if POLE[J-1] > POLE[J] then begin POM := POLE[J-1]; POLE[J-1] := POLE[J]; POLE[J] := POM; I := J end; D := I-1;

until H > D; end; 11 Pedchoz 3 metody (Bubble, Ripple a Shaker sort) vychzely z principu, e v kadm kroku se prohldly vechny dvojice sousednch poloek vektoru. Posledn z ukzanch jednoduchch metod azen, je metoda Shuttle sort. Princip: Metoda vychz opt z prohlen sousednch poloek tdnho vektoru, avak jakmile je zjitna nutnost proveden vmny, je provedena a vektor je opt prohlen od prvch dvou poloek. 12 procedure SHUTT(var POLE:A; N:INDEX); var I :INDEX; POM :INTEGER; begin I:=2; while I<=N do if POLE[I]

else I :=I+1 end; 13 K seazen vtho mnostv dat se pouvaj duchaplnj metody, z nich jmenujme alespo Quick sort, Shell sort a Heap sort. Metoda Quick sort vychz z nsledujcho principu: Z vektoru se vyhled vhodn hodnota POM1 (nap. hodnota umstn uprosted). Pak se prochz vektor azench hodnot zleva, a se najde slo vt ne POM1, nae se prohl vektor zprava, a se najde hodnota men ne POM1. Tato nalezen sla se vzjemn vymn. Uveden postup aplikujeme tak dlouho, dokud se vmna ned provst a vektor je rozdlen na dv sti (nap. poloviny); v lev polovin jsou sla men ne njak hodnota POM1, v prav polovin pak jsou sla vt ne njak hodnota POM1. Cel proces opakujeme s kadou polovinou hodnot samostatn (dle tvrtinou atd.), a nakonec seadme sousedn dvojice a tm je loha vyeena. 14 procedure QUICK(var POLE:A; N: INDEX); const M = 12; type STRUKTURA = array[1..M] of record H, D : INDEX end; var I, J, H, D : INDEX; S : 0..M;

POM1, POM2 : SLOZKA; Z : STRUKTURA; begin S := 1; Z[1].H := 1; Z[1].D := N; repeat H := Z[S].H; D := Z[S].D; S := S-1; repeat I := H; J := D; POM1:=POLE[(H+D) div 2]; repeat while POLE[I] < POM1 do I := I+1; while POM1 < POLE[J] do J := J-1; if I <= J then begin POM2 := POLE[I]; POLE[I] := POLE[J]; POLE[J] := POM2; I := I+1; J := J-1 end until I > J; if I < D then begin S := S+1; Z[S].H:=I; Z[S].D:=D; end; D := J until H >= D until S = 0 end; { konec procedury QUICK } 15 Rekurzivn obdoba pedchozho algoritmu: procedure QUICKR(var POLE:A; N: INDEX); procedure SORT(H,D : INDEX);

var I, J : INDEX; POM1, POM2 : SLOZKA; begin I := H; J := D; POM1 := POLE[(H+D) div 2]; repeat while POLE[I] < POM1 do I := I+1; while POM1 < POLE[J] do J := J-1; if I <= J then begin POM2 := POLE[I]; POLE[I] := POLE[J]; POLE[J] := POM2; I := I+1; J := J-1 end until I > J; if H < J then SORT(H,J); if I < D then SORT(I,D); end; {konec procedury SORT} begin SORT(1,N) end; {konec procedury QUICKR} 16 Verz je mono vytvoit mnoho. Pstup 5 11 3

4 9 7 QUICK1 PRESKUP J 1 DM 1 DM 1 D 1 HM 8

HM 8 H 8 3 3 . . . QUICK1 3 11 5 4 3 3

3 4 2 J 2 9 H 7 J 4 5 9 POM 5 7

6 5 7 6 11 6 5 7 3 3 X D D 8

9 4 6 4 6 11 4 QUICK1 DM 1 DM 5 HM 3

HM 8 17 postihuje algoritmus s procedurami PRESKUP a QUICK1 Procedure PRESKUP(DM,HM:byte; var J:byte); var D, H :byte; POM,X : COSI; begin POM:=A[DM]; J:=DM; H:=HM; D:=DM; repeat while (H>D) and (A[H]>=POM) do H:=H-1; J:=H; if H<>D then begin X:=A[D]; A[D] := A[H]; A[H]:=X; while (DD then begin X:=A[H]; A[H]:=A[D]; A[D]:=X end end until D=H; A[J]:=POM end; Procedure QUICK1(DM,HM:byte); var J:byte; begin if DM

QUICK1(DM,J-1); QUICK1(J+1,HM) end; end; 18 Algoritmus zaloen na metod QUICKsort pin tak nsledujc een: Program QUICKSORT000; uses CRT; type COSI=integer; var A : array[1..20] of COSI; N,I : byte; Procedure QUICKRRR(DM,HM:byte); var D, H :byte; POM,X : COSI; Procedure ROZDEL; begin POM:=A[(DM+HM) div 2]; H:=HM; D:=DM; repeat while A[H]>POM do H:=H-1; while A[D]H; end;

begin ROZDEL; if DMD then QUICKRRR(D,HM); end; begin ClrScr; Write('Zadej pocet vstupnich hodnot: '); Readln(N); for I:=1 to N do begin Write('Zadej ',I,'. hodnotu: '); Readln(A[I]) end; QUICKRRR(1,N); for I:=1 to N do write(A[I]:3) end. 19 Pouit kad z ve uvedench adcch procedur vyaduje stejn definice a deklarace. Meme tedy vytvoit program nap. ve tvaru: program SETRIDENI; {* Definice typ, kter byly pedpokldny na zatku *} var POCET, K: INDEX; HODNOTY : A; {* Na tomto mst zapeme kteroukoliv z ve uvedench *} {* deklarac procedur na azen (nap. proceduru SHUTT) *} begin write('Zadej pocet nacitanych hodnot k razeni: '); readln(POCET); for K:=1 to POCET do begin write('Zadej ',K,'. hodnotu: '); readln(HODNOTY[K]) end; {* Na tomto mst zavolme deklarovanou proceduru, *} {* nap. SHUTT(HODNOTY,POCET); *}

writeln('Tisk serazenych hodnot:'); for K:=1 to POCET do writeln(K,'. hodnota je ',HODNOTY[K]:4); end. 20 Metoda Shell sort, neboli Shellova metoda azen (azen se sniujcm se prstkem) . Princip: Rozdlen azench hodnot na 4 skupiny tak, e prvky kad skupiny jsou od sebe vzdleny o 4 sloky (1. skupinu tvo 1., 5., 9. ... sloka azenho vektoru, 2. skupinu 2., 6., 10. ... atd). Kadou skupinu seadme zvl njakou znmou metodou azen. V dal etap rozdlme pole azench hodnot na 2 skupiny tak, e prvky kad skupiny jsou od sebe vzdleny o 2 sloky (tj. sloky 1., 3., 5. ... resp. 2., 4., 6. ...). V posledn fzi seadme celou posloupnost ppadnou vmnou sousednch dvojic. 21 Nsledujc program m stejnou logiku jako posledn ve uveden program. Za povimnut stoj pouze jin definice typu A nutn pro pouit procedury SHELL: Program SETRIDENI; const MAXPOCET= 30; PS = 4;

type SLOZKA = integer; INDEX = 0..MAXPOCET; A = array[-9..MAXPOCET] of SLOZKA; var POCET, K: INDEX; HODNOTY : A; 22 procedure SHELL(var POLE:A; N: INDEX); type STRUKTURA = array[1..PS] of INDEX; var I, J, R, S : integer; POM : SLOZKA; M : 0..PS; PO : STRUKTURA; begin PO[1]:=9; PO[2]:=5; PO[3]:=3; PO[4]:=1; for M:=1 to PS do begin R:=PO[M]; S:=-R; for I:=R+1 to N do begin POM:=POLE[I]; J:=I-R; if S=0 then S:=-R; S:=S+1; POLE[S]:=POM;

while POM

setdn nhodn poet prvk 256 512 Pm vbr 489 1907 509 1956 695 2675 12 23

366 1444 704 2836 Bubble sort 540 2165 1026 4054 1442 5931 Ripple sort 5 8 1104

4270 1645 6542 Shaker sort 5 9 961 3642 1619 6520 Shell sort 58 116 127

349 157 492 Quick sort 31 69 60 146 37 79 Pm vkldn 256 opan set. 512 256

512 25 Zvrem tohoto pkladu jet jednou poznamenejme, e tvar vech ve uvedench algoritm zstv zcela zachovn i pro azen selnch relnch hodnot, ppadn etzc znak, i jen znak. V sti definic programu je teba pouze zmnit definici typu SLOZKA na nap. SLOZKA = real nebo SLOZKA = string[20] nebo SLOZKA = char atp. 26

Recently Viewed Presentations

  • Biological Rhythms: Sleep and Dreaming

    Biological Rhythms: Sleep and Dreaming

    Miles et al (1977) reported the case study of a blind man who had a daily rhythm of 24.9 hours. Other zeitgebers such as clocks, radio etc. failed to reset the endogenous clock and the man relied on stimulants and...
  • Psychology 5310: Learning - City University of New York

    Psychology 5310: Learning - City University of New York

    Associative Learning. Pavlovian Conditioning (Pavlov) Instrumental (Operant) Conditioning (e.g.,Thorndike, Skinner)
  • www.peerteaching.co.uk

    www.peerteaching.co.uk

    TACS: MCA +ACA. Contralateral hemiplegia + homonymous hemianopia. Higher cortical function dysfunction . PACS: MCA or ACA. Deficits from same hemisphere. Any 2 of Sx of TAC, but not all 3 together. POCS: Cerebellum, occipital lobes. homonymous hemianopia. DANISH cerebellar...
  • Male Reproductive System - Radioloksabha

    Male Reproductive System - Radioloksabha

    Liver is always involved- cysts, bile duct ectasia, periportal fibrosis. 4 categories-perinatal, neonatal, infantile and juvenile. As the age increases hepatic involvement increases and renal involvement decreases. These infants at risk for pulmonary hypoplasia.
  • The Story of The Rich Man and Lazarus

    The Story of The Rich Man and Lazarus

    * This page shows us that Jesus Christ went down into Hades after His Resurrection and took the believers souls from the Paradise compartment of hades and brought them all to heaven. The unbelievers were left in Hades in the...
  • Operate a Private Automatic Branch Exchange (Pabx) Switchboard

    Operate a Private Automatic Branch Exchange (Pabx) Switchboard

    Meter the calls based on time and pulses. Additional costs . Cost counters . Local currency . Slide . Call metering is the process for determining call charges for a telephone call made through your telephone system for local, national...
  • inst.eecs.berkeley.edu

    inst.eecs.berkeley.edu

    It isn't just the stack... Control flow attacks require that the attacker overwrite a piece of memory that contains a pointer for future code execution. The return address on the stack is just the easiest target. ... An attempt at...
  • Pigment Chromatography

    Pigment Chromatography

    Plant leaves contain different color pigments that give the leaf color. Plant pigments come in many different colors but we are the most familiar with chlorophyll because of its important job in photosynthesis. Chlorophyll is the green pigment that absorbs...