JEDNOROZMĚRNÉ POLE

JEDNOROZMĚRNÉ POLE

– strukturovaný typ, v kterém každý údaj pozůstává z množiny složek stejného typu

Budeme zpracovávat posloupnost celých čísel a₁, a₂, …, a_n uložených v proměnné a, která je datového typu jednorozměrné pole.

a

Nejprve ji musíme do pole a načíst. Informaci o délce pole (počtu členů zpracovávané posloupnosti) uložíme do proměnné n

začátek

čti(n);

i := 1;

dokud i £ n opakuj

začátek

čti(a[i]

i i + 1

konec;

konec.

stručně:

začátek

čti(n);

pro i od 1 do n opakuj

čti(a[i]

konec.

Proč pole?

Připomeňme jsi příklad z první přednášky:

Napište algoritmus, pomocí kterého postupně uložíte 3 hodnoty do proměnných a1, a2, a3 a určete počet proměnných, kterých hodnota je rovná nule. Počet vypište.

První algoritmus, který jsme vytvořili byl:

začátek

počet := 0;

čti (a1)

jestliže a1 = 0 pak počet := počet + 1;

čti (a2)

jestliže a2 = 0 pak počet := počet + 1;

čti (a3)

jestliže a3 = 0 pak počet := počet + 1;

napiš (“počet proměnných s hodnotou nula je “,počet);

konec.

Když jsme se naučili příkaz cyklu, tak jsme algoritmus přepracovali:

začátek

počet := 0

I := 1;

dokud I £ 3 opakuj začátek

čti (a)

jestliže a = 0 pak počet := počet +1;

I := I+1;

konec

napiš (“počet proměnných s hodnotou nula je “,počet);

konec.

Někdy potřebujeme uchovat údaje na delší čas nebo na vícenásobné zpracování. Tehdy postup, který jsme použili v druhém algoritme, s použitím cyklu, je nevýhodný. Načetli jsme totiž všechny hodnoty do jedné proměnné, takže hodnota jedné proměnné se promazala hodnotou další proměnné. Na druhé straně není praktické používat mnoho proměnných a muset si tak pamatovat mnoho měn jako v prvním algoritme (například, když by jsme mněli načíst 1000 hodnot). Proto se používá jeden společný název pro velkou skupinu údajů. Objekt takého typu nazýváme pole. Pole nám umožňuje vytvořit složitější údaj s určeným počtem hodnot (jednoho typu – celé čísla, reální čísla, char), přičemž jednotlivé hodnoty rozlišujeme v poli pomocí (celočíselných) indexů. Každému indexu zodpovídá jedna hodnota – prvek pole.

Zkusme teda přepsat algoritmus mocí pole. Pole nazveme a a bude mít 3 prvky: a ], a[2], a[3], v kterých budou uložené 3 hodnoty, které načteme:

začátek

pro i od 1 do 3 opakuj čti (a[i]

počet := 0;

pro i od 1 do 3 opakuj jestliže a[i] = 0 pak počet := počet + 1;

napiš (“počet proměnných s hodnotou nula je “,počet);

konec.

nebo načtení a podmínku pro nulu dáme do jednoho cyklu:

začátek

počet := 0;

pro i od 1 do 3 opakuj začátek

čti (a[i]

jestliže a[i] = 0 pak počet := počet + 1;

konec

napiš (“počet proměnných s hodnotou nula je “,počet);

konec.

Příklad 1

a

Vypište, kolik je nul v posloupnosti čísel a₁, a₂, …, a_n, která jsou již uložena v n položkách pole a

začátek

počet := 0;

i := 1;

dokud i £ n opakuj

začátek

jestliže a[i] = 0 pak

počet := počet + 1;

i := i + 1;

konec

napiš('počet nul = ', počet);

konec.

stručně:

začátek

počet := 0;

pro i od 1 do n opakuj

jestliže a[i] = 0 pak

počet := počet + 1;

napiš('počet nul = ', počet);

konec.

Příklad 2

Určete součet hodnot větších než 7, které se nacházejí v posloupnosti n čísel uložených v poli a v položkách a[1], …, a[n]. Pokud v posloupnosti není číslo větší než 7, podejte o tom informaci.

začátek

součet := 0;

i := 1;

dokud i £ n opakuj

začátek

jestliže a[i] > 7 pak

součet := součet + a[i];

i := i + 1

konec;

jestliže součet > 0 pak

napiš('součet čísel > 7 je ', součet)

jinak

napiš('V posloupnosti není číslo > 7.');

konec.

stručně:

začátek

součet := 0;

pro i od 1 do n opakuj

začátek

jestliže a[i] > 7 pak

součet := součet + a[i];

konec;

jestliže součet > 0 pak

napiš('součet čísel > 7 je ', součet)

jinak

napiš('V posloupnosti není číslo > 7.');

konec.

Příklad 3

Určete součet sudých hodnot, které se nacházejí v posloupnosti n čísel uložených v jednorozměrném poli a v položkách a[1], …, a[n]. Pokud v posloupnosti sudé číslo není, podá o tom informaci.

začátek

počet := 0;

součet := 0;

i := 1;

dokud i £ n opakuj

začátek

jestliže a[i] mod 2 = 0 pak

začátek

počet := počet + 1;

součet := součet + a[i];

konec

i := i + 1;

konec

jestliže počet > 0 pak

napiš('součet sudých čísel je ', součet)

jinak

napiš('V posloupnosti není sudé číslo.');

konec

stručně:

začátek

počet := 0;

součet := 0;

pro i od 1 do n opakuj

jestliže a[i] mod 2 = 0 pak

začátek

počet := počet + 1;

součet := součet + a[i];

konec;

jestliže počet > 0 pak

napiš('součet sudých čísel je ', součet)

jinak

napiš('V posloupnosti není sudé číslo.');

konec

Příklad 4

Sestavte algoritmus, který v posloupnosti n čísel a₁, a₂, …, a_n najde poslední sudé číslo a_k, a pak vypíše členy posloupnosti od následujícího (k+1). členu až do posledního členu posloupnosti. Pokud v posloupnosti sudé číslo není nebo se nachází až na konci posloupnosti (tj. je to člen a_n), podá o tom informaci.

začátek

index := 0

pro i od 1 do n opakuj

jestliže (a[i] mod 2) = 0 pak

index := i;

jestliže index = 0 pak

napiš('V posloupnosti není sudé číslo.')

jinak

jestliže index = n pak

napiš('Sudé číslo se nachází na posledním míste.')

jinak

pro i od index + 1 do n opakuj

napiš(a[i]) ;

konec

Příklad 5

Určete součet hodnot, které se nacházejí v posloupnosti n čísel uložených v jednorozměrném poli a v položkách a[1], …, a[n] na sudé pozici, tj. v položkách pole a se sudým indexem.

a

začátek

součet := 0;

i := 2;

dokud i £ n opakuj

začátek

součet := součet + a[i];

i := i + 2;

konec

napiš('součet členů se sudým indexem ', součet);

konec

Příklad 6

Do proměnné součin uložte součin hodnot, které se nacházejí v posloupnosti n čísel uložených v poli a, ale pouze v těch položkách, jejichž index je dělitelný 5.

začátek

součin := 1;

i := 5;

dokud i £ n opakuj

začátek

součin := součin a[i];

i := i + 5;

konec

konec

Příklad 7

Určete maximální člen a jeho pořadí (pořadí prvního ze všech maximálních členů) v posloupnosti a₁, a₂, …, a_n, kde n ³ 2. Výslednou maximální hodnotu uložte do proměnné max a pořadí do proměnné indexMax

začátek

max := a[1];

indexMax := 1;

i := 2;

dokud i £ n opakuj

začátek

jestliže a[i] > max pak

začátek

max := a[i];

indexMax := i;

konec;

i := i + 1;

konec;

konec

stručně:

začátek

max := a[1];

indexMax := 1;

pro i od 2 do n opakuj

jestliže a[i] > max pak

začátek

max := a[i];

indexMax := i;

konec;

konec

Příklad 8

a

Nalezněte a vypište maximální hodnotu vyskytující se v číselné posloupnosti a₁, a₂, …, a_n uložené v poli a a počet prvků posloupnosti, které tuto maximální hodnotu nabývají.

začátek

max := a[1];

pro i od 2 do n opakuj

jestliže a[i] > max pak  

max := a[i];

počet := 0;

pro i od 1 do n opakuj

jestliže a[i] = max pak

počet := počet + 1;

napiš(max);

napiš(počet);

konec

NEBO

začátek

max := a[1];

počet := 1;

pro i od 2 do n opakuj

jestliže a[i] ³ max pak

jestliže a[i] = max pak

počet := počet + 1

jinak

začátek

max := a[i];

počet := 1;

konec

napiš(max);

napiš(počet);

konec

Další zápisy druhého přístupu

začátek

max := a[1];

počet := 1;

pro i od 2 do n opakuj

začátek

jestliže a[i] = max pak

počet := počet + 1;

jestliže a[i] > max pak

začátek

max := a[i];

počet := 1;

konec;

konec

napiš(max);

napiš(počet);

konec

začátek

max := a[1];

počet := 1;

pro i od 2 do n opakuj

jestliže a[i] > max pak

začátek

max := a[i];

počet := 1;

konec

jinak

jestliže a[i]=max pak

počet := počet + 1;

napiš(max);

napiš(počet);

konec

určení prvního výskytu čísla, který má danou vlastnost

Úkolem je najít v posloupnosti a₁, a₂, …, a_n první člen (člen s nejmenším indexem), který má danou vlastnost, a v okamžiku jeho nalezení v dalším prohledávání posloupnosti nepokračovat. V případě, že se v posloupnosti žádné číslo s danou vlastností nenachází, podáme o tom informaci.

začátek

nalezen := 0;

i := 1;

dokud (i £ n) Ù (nalezen = 0) opakuj

začátek

jestliže a[i] má danou vlastnost pak

začátek

index := i;

nalezen := 1;

konec

i := i + 1;

konec

jestliže nalezen = 0 pak

napiš('Číslo s danou vlastností se v posloupnosti nevyskytuje.');

konec

Výše uvedenou úlohu můžeme ve většině případů řešit i pomocí následující konstrukce se „zarážkou“.

začátek

a[n + 1] := libovolné číslo s danou vlastností;

index := 1;

dokud a[index] nemá danou vlastnost opakuj

index := index + 1;

jestliže index > n pak

napiš('Číslo s danou vlastností se v posloupnosti nevyskytuje.');

konec

Příklad 9

Vypište první hodnotu větší než 7 z hodnot, které se nacházejí v posloupnosti n čísel uložených v jednorozměrném poli a v položkách a[1],…, a[n]. Pokud se v posloupnosti žádná hodnota větší než 7 nenachází, podejte o tom informaci.

začátek

nalezen := 0;

i := 1;

dokud (i £ n) Ù (nalezen = 0) opakuj

začátek

jestliže a[i] > 7 pak

začátek

napiš(a[i]);

nalezen := 1;

konec

i := i + 1;

konec

jestliže nalezen = 0 pak

napiš('v posloupnosti hodnota větší něž 7 neexistuje');

konec.

N E B O se zarážkou:

začátek

a[n + 1] := 8;

i := 1;

dokud a[i] £ 7 opakuj

i := i + 1;

jestliže i £ n pak

napiš(a[i])

jinak

napiš('v posloupnosti hodnota větší něž 7 neexistuje');

konec.

Příklad 10

Sestavte algoritmus, který mezi n členy posloupnosti, jejichž index je sudý, najde první číslo větší než 50 a uloží je do proměnné první. Pokud se v posloupnosti na sudých pozicích žádné číslo větší než 50 nevyskytuje, podá o tom informaci. (prvky posloupnosti jsou uloženy v n položkách pole a

začátek

nalezen := 0;

i := 2;

dokud (i £ n) Ù (nalezen = 0) opakuj

začátek

jestliže a[i] > 50 pak

začátek

index := i;

nalezen := 1;

konec

i := i + 2;

konec

jestliže nalezen = 0 pak

napiš('Číslo větší než 50 se na sudých pozicích posloupnosti nevyskytuje.')

jinak

první := a[index];

konec

N E B O se zarážkou – zkuste nejdřív sami

začátek

a[n + 1] := 51;

a[n + 2] := 51;

i := 2;

dokud a[i] £ 50 opakuj

i := i + 2;

jestliže i £ n pak

první := a[i];

jinak

napiš('Číslo větší než 50 se na sudých pozicích posloupnosti nevyskytuje.')

konec.

Příklad 11

Určete maximální hodnotu z čísel menších než 500, která se nacházejí v posloupnosti n čísel uložených v jednorozměrném poli a v položkách a[1],…, a[n]. Pokud se v posloupnosti žádná hodnota menší než 500 nenachází, podejte o tom informaci.

začátek

a[n + 1] := 499;

i := 1;

dokud a[i] ³ 500 opakuj

i := i + 1;

jestliže i £ n pak

začátek

max := a[i]

pro j od i + 1 do n opakuj

jestliže (a[j]< 500) Ù (a[j]> max) pak

max := a[j];

napiš(max)

konec

jinak

napiš('v posloupnosti hodnota menší něž 500 neexistuje');

konec.

a

b

uložení vybrané podposloupnosti do nové posloupnosti

Úkolem je najít všechny členy posloupnosti a₁, a₂, …, a_n, které mají danou vlastnost (označme jejich počet p, 0 £ p £ n) a tyto členy postupně uložit do posloupnosti b₁, b₂, …, b_p, tj. do jednotlivých p položek b[1] b[2] b[p] proměnné b typu jednorozměrné pole.

začátek

p := 0;

i := 1;

dokud i £ n opakuj

začátek

jestliže a[i] má danou vlastnost pak

začátek

p := p + 1;

b[p] := a[i];

konec

i := i + 1;

konec;

jestliže p = 0 pak

napiš('V posloupnosti neexistuje ani jedno číslo s danou vlastností.');

konec

Stručný zápis:

začátek

p := 0;

pro i od 1 do n opakuj

jestliže a[i] má danou vlastnost pak

začátek

p := p + 1;

b[p] := a[i];

konec

jestliže p = 0 pak

napiš('V posloupnosti neexistuje ani jedno číslo s danou vlastností.');

konec

Příklad 12

Uložte všechny hodnoty větší než 7, které se nacházejí v posloupnosti n čísel uložených v jednorozměrném poli a do jednorozměrného pole b. Pokud se v posloupnosti žádná hodnota větší než 7 nenachází, podejte o tom informaci.

začátek

p := 0;

i := 1;

dokud i £ n opakuj

začátek

jestliže a[i] > 7 pak

začátek

p := p + 1;

b[p] := a[i];

konec

i := i + 1;

konec;

jestliže p = 0 pak

napiš('v posloupnosti hodnota větší něž 7 neexistuje');

konec.

Stručně:

začátek

p := 0;

pro i od 1 do n opakuj

jestliže a[i] > 7 pak

začátek

p := p + 1;

b[p] := a[i];

konec

jestliže p = 0 pak

napiš('v posloupnosti hodnota větší něž 7 neexistuje');

konec.

nejdříve SAMI

Příklad 13

Určete aritmetický průměr ze sudých hodnot, které se nacházejí v posloupnosti n čísel uložených v jednorozměrném poli a, a všechny tyto sudé hodnoty uložte postupně do pole b. Pole b vypište, pokud jste tam nějakou hodnotu uložili. Pokud v posloupnosti sudé číslo není, podejte o tom informaci.

Řešení:

začátek

počet := 0;

součet := 0;

i := 1;

dokud i £ n opakuj

začátek

jestliže a[i] mod 2 = 0 pak

začátek

počet := počet + 1;

součet := součet + a[i];

b[počet] := a[i];

konec

i := i + 1;

konec

jestliže počet = 0 pak

napiš('V posloupnosti není sudé číslo.')

jinak

začátek

napiš(součet/počet);

pro i od 1 do počet opakuj

napiš(b[i]);

konec;

konec

Stručně

začátek

počet := 0

součet := 0;

pro i od 1 do n opakuj

jestliže a[i] mod 2 = 0 pak

začátek

počet := počet + 1;

součet := součet + a[i];

b[počet] := a[i];

konec;

jestliže počet = 0 pak

napiš('V posloupnosti není sudé číslo.')

jinak

pro i od 1 do počet opakuj

napiš(b[i]);

konec

Příklad 14

Uložte každý 10. člen posloupnosti n čísel uložených v jednorozměrném poli a prvním členem počínaje, do jednorozměrného pole b

začátek

p := 0;

i := 1;

dokud i £ n opakuj

začátek

p := p + 1;

b[p] := a[i];

i := i + 10;

konec;

konec.

Posuny hodnot v poli

Sestavte algoritmus, který z posloupnosti n čísel a₁, a₂, …, a_n odebere k. člen, 1 £ k £  n, přičemž k načte do proměnné k příkazem čti(k) a nově vzniklou posloupnost vypíše.

Např.: Odebrání položky a[6] z jednorozměrného pole a

začátek

čti(k);

pro i od k do n - 1 opakuj

a[i] := a[i + 1];

n := n - 1;

pro i od 1 do n opakuj

napiš(a[i]);

konec

Příklad 15

Sestavte algoritmus, který v posloupnosti n čísel a₁, a₂, …, a_n najde první hodnotu rovnající se nule a tuto hodnotu odebere. Pokud se v posloupnosti nula nevyskytuje, podá o tom informaci, v opačném případě nově vzniklou posloupnost vypíše.

začátek

nalezen := 0;

i := 1;

dokud (i £ n) Ù (nalezen = 0) opakuj

začátek

jestliže a[i] = 0 pak

začátek

index := i;

nalezen := 1;

konec

i := i + 1;

konec

jestliže nalezen = 0 pak

napiš('Nula v posloupnosti není.')

jinak

začátek

pro i od index do n - 1 opakuj

a[i] := a[i + 1];

n := n - 1;

pro i od 1 do n opakuj

napiš(a[i]);

konec;

konec

nebo se „zarážkou“.

začátek

a[n + 1] := 0;

index := 1;

dokud a[index] ¹ 0 opakuj

index := index + 1;

jestliže index > n pak

napiš('Nula v posloupnosti není.')

jinak

začátek

pro i od index do n - 1 opakuj

a[i] := a[i + 1];

n := n - 1;

pro i od 1 do n opakuj

napiš(a[i]);

konec;

konec

Příklad 16

Sestavte algoritmus, který do posloupnosti n čísel a₁, a₂, …, a_n přidá za k. člen (k načte do proměnné k £ k £  n, vámi zvolené číslo (které načte do proměnné x) a nově vzniklou posloupnost vypíše.

Např.: Přidání hodnoty x za položku a[6] do pole a

začátek

čti(x);

čti(k);

i := n;

dokud i ³ k + 1 opakuj

začátek

a[i + 1] := a[i];

i := i - 1;

konec;

a[k + 1] := x;

n := n + 1;

pro i od 1 do n opakuj

napiš(a[i]);

konec

Příklad 17

Sestavte algoritmus, který do posloupnosti n čísel a₁, a₂, …, a_n přidá před k. člen (k načte do proměnné k £ k £  n, vámi zvolené číslo (které načte do proměnné x) a nově vzniklou posloupnost vypíše.

Např.: Přidání hodnoty x před položku a[6] do pole a

a

začátek

čti(x);

čti(k);

i := n;

dokud i ³ k opakuj

začátek

a[i + 1] := a[i];

i := i - 1;

konec;

a[k] := x;

n := n + 1;

pro i od 1 do n opakuj

napiš(a[i]);

konec.

zkuste SAMI

Příklad 18

Sestavte algoritmus, který v posloupnosti n čísel a₁, a₂, …, a_n provede cyklický posun členů o jedno místo vpřed, přičemž člen, který byl prvním členem posloupnosti bude posledním členem nově vzniklé posloupnosti. Nově vzniklou posloupnost vypíše.

a

chceme

a

začátek

pomocná := a

pro i od 1 do n - 1 opakuj

a[i] := a[i + 1];

a[n] := pomocná;

pro i od 1 do n opakuj

napiš(a[i]);

konec

Příklad 19

Sestavte algoritmus, který v posloupnosti n čísel a₁, a₂, …, a_n najde první hodnotu větší než 100 a za tuto hodnotu přidá nulu. Pokud se v posloupnosti hodnota větší než 100 nevyskytuje, podá o tom informaci, v opačném případě nově vzniklou posloupnost vypíše.

začátek

nalezen := 0;

i := 1;

dokud (i £ n) Ù (nalezen = 0) opakuj

začátek

jestliže a[i] > 100 pak

začátek

index := i;

nalezen := 1;

konec

i := i + 1;

konec

jestliže nalezen = 0 pak

napiš('Hodnota větší než 100 v posloupnosti není.')

jinak

začátek

i := n;

dokud i ³ index + 1 opakuj

začátek

a[i + 1] := a[i];

i := i - 1;

konec;

a[index + 1] := 0;

n := n + 1;

pro i od 1 do n opakuj

napiš(a[i]);

konec;

konec

nebo se „zarážkou“.

začátek

a[n + 1] := 101;

index := 1;

dokud a[index] £ 100 opakuj

index := index + 1;

jestliže index > n pak

napiš('Hodnota větší než 100 v posloupnosti není.')

jinak

začátek

i := n;

dokud i ³ index + 1 opakuj 

začátek

a[i + 1] := a[i];

i := i - 1;

konec;

a[index + 1] := 0;

n := n + 1;

pro i od 1 do n opakuj

napiš(a[i]);

konec;

konec

roztřídění členů posloupnosti do dvou posloupností

Úkolem je rozdělit členy posloupnosti a₁, a₂, …, a_n do dvou posloupností: do posloupnosti b₁, b₂, …, b_m zařadit členy mající danou vlastnost a do posloupnosti c₁, c₂, …, c_p zařadit ty členy, které danou vlastnost nemají.

Zřejmě 0 £ m £ n, 0 £ p £ n, m + p = n.

začátek

m := 0;

p := 0;

i := 1;

dokud i £ n opakuj

začátek

jestliže a[i] má danou vlastnost pak

začátek

m := m + 1;

b[m] := a[i];

konec

jinak

začátek

p := p + 1;

c[p] := a[i];

konec

i := i + 1;

konec;

konec

Stručný zápis:

začátek

m := 0;

p := 0;

pro i od 1 do n opakuj

jestliže a[i] má danou vlastnost pak

začátek

m := m + 1;

b[m] := a[i];

konec

jinak

začátek

p := p + 1;

c[p] := a[i];

konec

konec

Příklad 20

Sestavte algoritmus, který n členů posloupnosti a₁, a₂, …, a_n uložených v poli a uloží do dvou polí, do pole sudé uloží všechny sudé členy a do pole liché uloží všechny liché členy posloupnosti.

začátek

m := 0;

p := 0;

pro i od 1 do n opakuj

jestliže (a[i] mod 2) = 0 pak

začátek

m := m + 1;

sudé[m] := a[i];

konec

jinak

začátek

p := p + 1;

liché[p] := a[i];

konec

konec

připojení jedné posloupnosti za druhou

Nechť jsou dány dvě posloupnosti a₁, a₂, …, a_n a b₁, b₂, …, b_m, n ³ 1, m ³ 1. Úkolem je vytvořit posloupnost c₁, c₂, …, c_p, p = n + m, která nejprve obsahuje všechny členy posloupnosti a₁, a₂, …, a_n  a pak všechny členy posloupnosti b₁, b₂, …, b_m v uvedeném pořadí.

začátek

i := 1;

dokud i £ n opakuj

začátek

c[i] := a[i];

i := i + 1;

konec;

i := 1;

dokud i £ m opakuj  

začátek

c[n + i] := b[i];

i := i + 1;

konec

konec

Stručný zápis:

začátek

pro i od 1 do n opakuj

c[i] := a[i];

pro i od 1 do m opakuj

c[n + i] := b[i];

konec