USE rozhodnutí Informatika
1. Úkol. Kolik jedniček je v binárním zápisu pro hexadecimální číslo 12F0 16 ?
Vysvětlení.
Přeložme si číslo 12F0 16 do dvojkové číselné soustavy: 12F0 16 = 1001011110000 2 .
Spočítejme počet jednotek: je jich 6.
Odpověď: 6.
2. Úkol Booleovská funkce F je dáno výrazem (¬ z ) ∧ x ∨ x ∧ y . Určete, který sloupec pravdivostní tabulky funkce F odpovídá každé z proměnných x, y, z.
Variabilní 1 | Variabilní 2 | Variabilní 3 | Funkce |
Napište písmena ve své odpovědi. x, y, z v pořadí, v jakém se objevují jejich odpovídající sloupce (nejprve - písmeno odpovídající 1. sloupci; poté - písmeno odpovídající 2. sloupci; poté - písmeno odpovídající 3. sloupci). Písmena v odpovědi pište za sebou, mezi písmena nemusíte dávat žádné oddělovače. Příklad. Nechte výraz x → y v závislosti na dvou proměnných x a y a pravdivostní tabulka:
Variabilní 1 | Variabilní 2 | Funkce |
Pak 1. sloupec odpovídá proměnné y , a 2. sloupec odpovídá proměnné X . Ve své odpovědi napište: yx.
Vysvětlení.
Tento výraz je disjunkcí dvou spojek. Můžeme si všimnout, že v obou termínech existuje faktor X . Tedy pro x = 0 bude součet roven 0. Tedy pro proměnnou X hodí se pouze třetí sloupec.
V osmém řádku tabulky X = 1 a hodnota funkce je 0. To je možné pouze tehdy, když z = 1, y = 0, tj. proměnná1 − z , a proměnná2 − y
Odpověď: zyx
3. Úkol Na obrázku vpravo je grafická mapa okresu N-sky, tabulka obsahuje informace o délkách těchto silnic (v kilometrech).
Vzhledem k tomu, že tabulka a diagram byly nakresleny nezávisle na sobě, není číslování sídel v tabulce nijak spojeno s písmenným označením v grafu. Určete délku cesty z bodu B do bodu E. Ve své odpovědi zapište celé číslo - jak je uvedeno v tabulce.
Vysvětlení.
Bod B je jediný bod s pěti silnicemi, takže odpovídá P6, a bod E je jediný bod se čtyřmi silnicemi, takže odpovídá P4.
Délka silnice z P6 do P4 je 20.
Odpověď: 20.
4. Úkol Fragment databáze poskytuje informace o vztazích. Na základě uvedených údajů určete, kolik přímých potomků (tj. dětí a vnuků) Pavlenka A.K. jsou uvedeny v tabulce 1.
|
|
NEBO
Pro dávkové operace se soubory se používají masky názvů souborů. Maska je posloupnost písmen, čísel a dalších znaků povolených v názvech souborů, která může obsahovat také následující znaky:
Symbol "?" (otazník) znamená právě jeden libovolný znak.
Symbol "*" (hvězdička) znamená libovolnou sekvenci znaků libovolné délky, včetně "*" může také specifikovat prázdnou sekvenci.
Adresář obsahuje 6 souborů:
maverick.mapa
maverick.mp3
taverna.mp4
revolver.mp4
vera.mp3
zveri.mp3
Níže je osm masek. Kolik z nich odpovídá přesně čtyřem souborům z daného adresáře?
*ver*.mp* | *?ver?*.mp? | ?*ver*.mp?* | *v*r*?.m?p* |
???*???.mp* | ???*???.m* | *a*.*a* | *a*.*p* |
Vysvětlení.
Z tabulky 2 vidíme, že Pavlenko A.K. (ID 2155) má dvě děti, jejich ID jsou 2302 a 3002.
Pavlenko E. A. (ID 2302) má tři děti a Pavlenko I. A. (ID 3002) dvě.
Pavlenko AK má tedy sedm přímých potomků: dvě děti a pět vnoučat.
Odpověď: 7.
NEBO
Zvažte každou masku:
1. Podle masky *ver*.mp* bude vybráno pět souborů:
maverick.mp3
taverna.mp4
revolver.mp4
vera.mp3
zveri.mp3
2. Podle masky *?ver?*.mp? budou vybrány tři soubory:
maverick.mp3
taverna.mp4
zveri.mp3
3. Podle masky?*ver*.mp?* budou vybrány čtyři soubory:
maverick.mp3
taverna.mp4
revolver.mp4
zveri.mp3
4. Podle masky *v*r*?.m?p* bude vybrán jeden soubor:
maverick.mapa
5. Podle masky???*???.mp* budou vybrány tři soubory:
maverick.mp3
taverna.mp4
revolver.mp4
6. Maska ???*???.m* vybere čtyři soubory:
maverick.mapa
maverick.mp3
taverna.mp4
revolver.mp4
7. Pomocí masky *a*.*a* bude vybrán jeden soubor:
maverick.mapa
8. Podle masky *a*.*p* budou vybrány čtyři soubory:
maverick.mapa
maverick.mp3
taverna.mp4
vera.mp3
Tedy tři masky, které odpovídají právě čtyřem souborům z daného adresáře.
Odpověď: 3.
Odpověď: 7|3
5. Úkol Komunikačním kanálem jsou přenášeny zprávy obsahující pouze čtyři písmena: P, O, S, T; pro přenos se používá binární kód, který umožňuje jednoznačné dekódování. Pro písmena T, O, P se používají tato kódová slova: T: 111, O: 0, P: 100.
Zadejte nejkratší kódové slovo pro písmeno C, u kterého kód umožní jednoznačné dekódování. Pokud existuje několik takových kódů, uveďte kód s nejmenší číselnou hodnotou.
Vysvětlení.
Písmeno C nelze zakódovat jako 0, protože 0 je již obsazeno.
Písmeno C nelze zakódovat jako 1, protože kódování písmene T začíná 1.
Písmeno C nelze zakódovat jako 10, protože kódování písmene P začíná 10.
Písmeno C nelze zakódovat jako 11, protože kódování písmene T začíná na 11.
Písmeno C lze zakódovat jako 101, což je nejmenší možná hodnota.
Odpověď: 101.
6. Hledání Vstupem algoritmu je přirozené číslo N. Algoritmus z něj sestaví nové číslo R následovně.
1. Je sestrojena binární reprezentace čísla N.
2. K tomuto záznamu vpravo se přidávají další dvě číslice podle následujícího pravidla:
A) sečtou se všechny číslice binárního zápisu a na konec čísla (vpravo) se přičte zbytek po dělení součtu 2. Například záznam 11100 je převeden na záznam 111001;
B) na tomto záznamu se provádějí stejné úkony - vpravo se přidá zbytek dělení součtu číslic 2.
Takto získaný záznam (obsahuje o dvě číslice více než v záznamu původního čísla N) je binárním záznamem požadovaného čísla R.
Uveďte nejmenší číslo N, pro které je výsledek algoritmu větší než 125. Ve své odpovědi zapište toto číslo v desítkové soustavě.
NEBO
Výkonná kalkulačka má dva týmy, které mají přidělená čísla:
1. přidat 2,
2. vynásobte 5.
Při provádění prvního z nich Kalkulačka přičte k číslu na obrazovce 2 a při provádění druhého jej vynásobí 5.
Například program 2121 je program
vynásobte 5
přidat 2,
vynásobte 5
přidat 2,
který převádí číslo 1 na číslo 37.
Napište pořadí příkazů v programu, který převede číslo 2 na číslo 24 a neobsahuje více než čtyři příkazy. Zadejte pouze čísla příkazů.
Vysvětlení.
Tento algoritmus přiřadí na konec čísla buď 10, pokud mělo původně v binárním zápisu lichý počet jedniček, nebo 00, pokud bylo sudé.
126 10 = 1111110 2 lze získat jako výsledek algoritmu z čísla 11111 2 .
11111 2 = 31 10 .
Odpověď: 31.
NEBO
Vyřešme problém z opačné strany a přijaté příkazy si pak zapišme zprava doleva.
Pokud číslo není dělitelné 5, pak přijato příkazem 1, pokud je dělitelné, pak příkazem 2.
22 + 2 = 24 (tým 1)
20 + 2 = 22 (tým 1)
4 * 5 = 20 (tým 2)
2 + 2 = 4 (tým 1)
Odpověď: 1211.
Odpověď: 31|1211
7. Úkol. Je uveden fragment tabulky. Vzorec byl zkopírován z buňky E4 do buňky D3. Při kopírování adres buněk ve vzorci se automaticky změnily. Jaká je číselná hodnota vzorce v buňce D3?
= $ B2 * C $ 3 |
Poznámka: Znak $ označuje absolutní adresování.
NEBO
Je uveden fragment tabulky.
=(A1-3)/(B1-1) | =(A1-3)/(C1-5) | C1/(A1 – 3) |
Jaké celé číslo by mělo být zapsáno do buňky A1, aby graf postavený na hodnotách buněk v rozsahu A2:C2 odpovídal obrázku? Je známo, že všechny hodnoty buněk z uvažovaného rozsahu jsou nezáporné.
Vysvětlení.
Vzorec se po zkopírování do buňky D3 změnil na =$B1 * B$3.
B1 * B3 = 4 * 2 = 8.
Odpověď: 8.
NEBO
Dosaďte hodnoty B1 a C1 do vzorců A2:C2:
A2 = (A1-3)/5
B2 = (A1-3)/5
C2 = 10/(A1-3)
Protože A2 = B2, pak С2 = 2 * A2 = 2 * B2
Nahradit:
10/(A1-3) = 2*(A1-3)/5
A1 - 3 = 5
A1 = 8.
Odpověď: 8.
8. Úkol Zapište si číslo, které bude vytištěno jako výsledek následujícího programu. Pro vaše pohodlí je program prezentován v pěti programovacích jazycích.
ZÁKLADNÍ | Krajta |
DIM S, N JAKO CELÉ ČÍSLO S=0 N=0 KDYŽ S S=S+8 N=N+2 ZAMÍŘIT TISKNOUT N | s = 0 n=0 zatímco s s = s + 8 n = n + 2 tisknout(n) |
Algoritmický jazyk | Pascal |
alg brzy celé číslo n, s n:=0 s:= 0 nc ahoj s s:= s + 8 n:= n + 2 kts výstup n ošidit | var s, n: celé číslo; začít s:= 0; n:=0; zatímco s začít s:= s + 8; n:= n + 2 konec; writeln(n) konec. |
Xi |
|
#zahrnout int main() (int s = 0, n = 0; zatímco (s printf("%d\n", n); návrat 0; |
|
Vysvětlení.
Cyklus while se provádí tak dlouho, dokud platí podmínka s
Odpověď: 28.
9. Úkol. Jaká je minimální velikost paměti (v kB), která musí být vyhrazena, aby bylo možné uložit jakoukoli bitmapu 64 × 64 pixelů, za předpokladu, že v obrázku lze použít 256 různých barev? Do odpovědi zapište pouze celé číslo, měrnou jednotku psát nemusíte.
NEBO
Hudební fragment byl nahrán v mono formátu, digitalizován a uložen jako soubor bez použití komprese dat. Velikost výsledného souboru je 24 MB. Poté byla stejná hudební skladba znovu nahrána ve stereu (dvoukanálový záznam) a digitalizována s rozlišením 4krát vyšším a vzorkovací frekvencí 1,5krát nižší než poprvé. Komprese dat nebyla provedena. Zadejte velikost souboru v MB vyplývající z přepisu. Do odpovědi zapište pouze celé číslo, měrnou jednotku psát nemusíte.
Vysvětlení.
Jeden pixel je kódován 8 bity paměti.
Celkem 64 * 64 = 2 12 pixelů.
Množství paměti obsazené obrázkem 2 12 * 8 = 2 15 bitů = 2 12 bajtů = 4 KB.
Odpověď: 4.
NEBO
Při nahrávání stejného souboru ve stereo formátu se jeho hlasitost zvýší dvakrát. 24 * 2 = 48
Když se jeho rozlišení zvýší čtyřnásobně, zvětší se také čtyřnásobně jeho objem. 48 * 4 = 192
Když se vzorkovací frekvence sníží 1,5krát, jeho objem se zmenší 1,5krát. 192 / 1,5 = 128.
Odpověď: 128.
Odpověď: 4|128
10. Úkol Igor vytvoří tabulku kódových slov pro přenos zpráv, každá zpráva má své kódové slovo. Igor používá jako kódová slova 5písmenná slova, ve kterých jsou pouze písmena P, I, R a písmeno P se objevuje přesně 1x. Každé z ostatních platných písmen se může v kódovém slově vyskytovat kolikrát, nebo se nevyskytuje vůbec. Kolik různých kódových slov může Igor použít?
Vysvětlení.
Igor umí 2 4 slova tak, že na první místo umístíte písmeno P. Podobně to můžete umístit na druhé, třetí, čtvrté a páté místo. Dostáváme 5*2 4 = 80 slov.
Odpověď: 80.
11. Úkol Níže jsou dvě rekurzivní funkce (procedury) napsané v pěti programovacích jazycích: F a G.
ZÁKLADNÍ | Krajta |
DECLARE SUB F(n) DECLARE SUB G(n) SUB F(n) POKUD n > 0 POTOM G(n - 1) KONEC SUB SUB G(n) TISK "*" POKUD n > 1 POTOM F(n - 3) KONEC SUB | def F(n): Pokud n > 0: G(n - 1) def G(n): Tisk("*") Pokud n > 1: F(n - 3) |
Algoritmický jazyk | Pascal |
alg F(celé číslo n) brzy Pokud n > 0, pak G(n - 1) Všechno ošidit alg G(celé číslo n) brzy Závěr "*" Pokud n > 1, pak F(n - 3) Všechno ošidit | procedura F(n: celé číslo); vpřed; procedura G(n: celé číslo); vpřed; procedura F(n: celé číslo); začít Pokud n > 0, pak G(n-1); konec; procedura G(n: celé číslo); začít writeln("*"); Pokud n > 1, pak F(n-3); konec; |
Xi |
|
void F(int n); void G(int n); void F(int n)( Pokud (n > 0) G(n-1); void G(int n)( printf("*"); Pokud (n > 1) F(n-3); |
|
Kolik hvězdiček se vytiskne na obrazovku při volání F(11)?
Vysvětlení.
Pojďme simulovat práci programu:
F(11)
G(10): *
F(7)
G(6): *
F(3)
G(2): *
F(-1)
Odpověď: 3.
12. Hledání V síťové terminologii TCP/IP je maska sítě binární číslo, které určuje, která část adresy IP hostitele odkazuje na síťovou adresu a která část odkazuje na adresu samotného hostitele v této síti. Obvykle se maska zapisuje podle stejných pravidel jako IP adresa – ve tvaru čtyř bajtů, přičemž každý bajt je zapsán jako desetinné číslo. Současně jsou v masce nejprve (v nejvyšších číslicích) jedničky a poté od určité číslice - nuly. Síťová adresa se získá aplikací bitové konjunkce na danou hostitelskou IP adresu a masku.
Pokud je například IP adresa hostitele 231.32.255.131 a maska je 255.255.240.0, je síťová adresa 231.32.240.0.
Pro hostitele s IP adresou 111.81.208.27 je síťová adresa 111.81.192.0. Jaká je nejmenší možná hodnota třetího bajtu zleva masky? Svou odpověď napište jako desetinné číslo.
Vysvětlení.
Zapišme třetí bajt IP adresy a síťové adresy v binárním zápisu:
208 10 = 11010000 2
192 10 = 11000000 2
Vidíme, že první dva bity masky vlevo jsou jedničky, což znamená, že aby byla hodnota nejmenší, musí být zbývající bity nula. Dostaneme, že třetí bajt masky zleva je 11000000 2 = 192 10
Odpověď: 192.
13. Úkol Při registraci na počítačový systém každému uživateli je přiděleno heslo skládající se z 15 znaků a obsahující pouze znaky ze sady 12 znaků: A, B, C, D, E, F, G, H, K, L, M, N. Databáze pro ukládání informací o každém uživateli má stejný a minimální možný celočíselný počet bajtů. V tomto případě se používá znak po znaku kódování hesel, všechny znaky jsou kódovány stejným a minimálním možným počtem bitů. Kromě samotného hesla jsou v systému pro každého uživatele uloženy další informace, pro které je přidělen celý počet bajtů; toto číslo je stejné pro všechny uživatele. Uložení informací o 20 uživatelích trvalo 400 bajtů. Kolik bajtů je přiděleno pro uložení dalších informací o jednom uživateli? Do odpovědi zapište pouze celé číslo – počet bajtů.
Vysvětlení.
Podle podmínky lze v čísle použít 12 písmen. Je známo, že pomocí N bitů je možné zakódovat 2N různých variant. Od 2 3 4 , pak jsou k zápisu každého z 12 znaků zapotřebí 4 bity.
Pro uložení všech 15 znaků hesla potřebujete 4 15 = 60 bitů a protože se pro záznam používá celý počet bajtů, vezmeme nejbližší nemenší hodnotu, násobek osmi, toto číslo je 64 = 8 8 bitů (8 bajtů).
Nechte množství paměti přidělené pro další relace být x, pak:
20 * (8+x) = 400
x=12
Odpověď: 12.
14. Hledání Executor Editor přijímá řetězec čísel jako vstup a převádí jej. Editor může provádět dva příkazy, v obou příkazech v a w znamenají řetězce čísel.
A) nahradit (v, w).
Tento příkaz nahradí první výskyt v vlevo v řetězci za w. Například provedení příkazu
nahradit (111, 27)
převede řetězec 05111150 na řetězec 0527150. Pokud řetězec neobsahuje žádné výskyty řetězce v, pak provedení příkazu nahradit (v, w) řetězec nezmění.
B) zjištěno (v).
Tento příkaz zkontroluje, zda se v řádku editoru spouštěče vyskytuje řetězec v. Pokud k němu dojde, pak příkaz vrátí logickou hodnotu "true", jinak vrátí hodnotu "false". Čára
interpret se nezmění.
Cyklus
BYE stav
Posloupnost příkazů
KONEC BYE
Spustí se, dokud podmínka platí.
V designu
IF podmínka
DO týmu 1
JINÝ tým 2
KONEC POKUD
Příkaz1 (pokud je podmínka pravdivá) nebo příkaz2 (pokud je podmínka nepravdivá) se provede.
Jaký řetězec bude výsledkem použití následujícího
program na řetězec sestávající z 68 po sobě jdoucích číslic 8? V odpověď
zapište výsledný řetězec.
START
JEŠTĚ nalezeno (222) NEBO nalezeno (888)
POKUD nalezeno (222)
TO nahradit (222, 8)
ELSE nahradit (888, 2)
KONEC POKUD
KONEC BYE
KONEC
Vysvětlení.
V 68 po sobě jdoucích číslech 8 je 22 skupin po třech osmičkách, které budou nahrazeny 22 dvojkami a dvě osmičky zůstanou.
68(8) = 22(2) + 2(8)
22(2) + 2(8) = 1(2) + 9(8)
1(2) + 9(8) = 4(2)
4(2) = 1(2) + 1(8) = 28
Odpověď: 28.
15. Hledání Na obrázku je schéma silnic spojujících města A, B, C, D, D, E, G, H, I, K, L, M.
Na každé silnici se můžete pohybovat pouze jedním směrem, označeným šipkou.
Kolik různých cest existuje z města A do města M?
Vysvětlení.
Začněme počítat počet cest od konce trasy - od města M. Let N X - počet různých cest z města A do města X, N - celkový počet způsoby. Do města M se lze dostat z L nebo K, takže N = N M \u003d N L + N K. (*)
Podobně:
N K \u003d N And;
N L \u003d N And;
N I \u003d N E + N F + N Z
N K \u003d N E \u003d 1.
Přidejme další vrcholy:
N B \u003d N A \u003d 1;
N B \u003d N B + NA + N G \u003d 1 + 1 + 1 \u003d 3;
N E \u003d N G \u003d 1;
N G \u003d N A \u003d 1.
Dosaďte ve vzorci (*): N = N M = 4 + 4 + 4 + 1 = 13.
Odpověď: 13.
Odpověď: 56
16. Hledání Hodnota aritmetického výrazu: 9 8 + 3 5 - 9 - zaznamenané v číselných soustavách se základem 3. Kolik číslic "2" obsahuje tento záznam?
Vysvětlení.
Převedeme výraz:
(3 2 ) 8 + 3 5 - 3 2
3 16 + 3 5 - 3 2
3 16 + 3 5 = 100...00100000
100...00100000 - 3 2 = 100...00022200
Ve výsledném čísle jsou tři 2.
Odpověď: 3
17. Úkol V dotazovacím jazyce vyhledávače se symbol "|" používá k označení logické operace "OR" a symbol "&" se používá k označení logické operace "AND". Tabulka zobrazuje dotazy a počet jimi nalezených stránek pro určitý segment internetu.
Kolik stránek (v tisících) bude nalezeno pro dotazHomer & Odyssey & Ilias?Předpokládá se, že všechny požadavky byly provedeny téměř současně, takže množina stránek obsahujících všechna hledaná slova se v průběhu času neměnila.
vyřizování žádostí.
Vysvětlení.
Počet požadavků v této oblasti bude označen Ni. Naším cílem je N5.
Pak z tabulky zjistíme, že:
N5 + N6 = 355,
N4 + N5 = 200,
N4 + N5 + N6 = 470.
Z první a druhé rovnice: N4 + 2N5 + N6 = 555.
Z poslední rovnice: N5 = 85.
Odpověď: 85
18. Úkol Označte m&n bitová konjunkce nezáporných celých čísel m a n . Takže například 14&5 = 1110 2 &0101 2 = 0100 2 = 4.
Jaké je nejmenší nezáporné celé číslo A vzorec
x&25 ≠ 0 → (x&17 = 0 → x&A ≠ 0)
je identicky pravdivá (tj. má hodnotu 1 pro jakoukoli nezápornou celočíselnou hodnotu proměnné X )?
Vysvětlení.
Představme si notaci:
(x ∈ A) ≡ A; (x ∈ P) ≡ P; (x ∈ Q) ≡ Q.
Transformací získáme:
¬P ∨ ¬(Q ∧ ¬A) ∨ ¬P = ¬P ∨ ¬Q ∨ A.
Logický OR je pravdivý, pokud je pravdivý alespoň jeden z výroků. Stav ¬P∨ ¬Q = 1 uspokojí paprsky (−∞, 40) a (60, ∞). Protože výraz ¬P∨ ¬Q ∨ A musí být shodně pravdivé, výraz A musí platit na intervalu . Jeho délka je 20.
Odpověď: 20.
Odpověď: 8
19. Hledání Program používá jednorozměrné celočíselné pole A s indexy od 0 do 9. Hodnoty prvků jsou 4, 7, 3, 8, 5, 0, 1, 2, 9, 6, tzn. A=4, A=7 atd.
Určete hodnotu proměnné C po spuštění následujícího fragmentu tohoto programu(napsáno níže v pěti programovacích jazycích).
ZÁKLADNÍ | Krajta |
C=0 PRO i = 1 AŽ 9 IF A(i) C=c+1 T = A(i) A(i) = A(0) A(0) = t ENDIF Příště já | C=0 Pro i v rozsahu (1,10): Pokud A[i] C=c+1 t = A[i] A[i] = A A=t |
Algoritmický jazyk | Pascal |
c:= 0 nc pro i od 1 do 9 pokud A[i] c:= c + 1 t:= A[i] A[i] := A A := t Všechno kts | c:=0; pro i:= 1 až 9 do pokud A[i] začít c:= c + 1; t:= A[i]; A[i] := A; A := t; konec; |
Xi |
|
c = 0; pro (i = 1; i pokud (A[i] { c++; t = A[i]; A[i] = A; A=t; } |
|
Vysvětlení.
Pokud je A[i] prvkem pole menší než A, pak je program prohodí a zvýší hodnotu proměnnéCo 1. Program bude proveden dvakrát, poprvé se prohodí A a A, od 3 Sse rovná 2.
Odpověď: 2.
20. HledáníAlgoritmus je napsán v pěti níže uvedených programovacích jazycích. Po obdržení číslaX, tento algoritmus vypíše čísloM. Je známo žeX> 100. Uveďte nejmenší takové (tj. větší než 100) čísloX, po zadání kterého algoritmus vytiskne 26.
ZÁKLADNÍ | Krajta |
DIM X, L, M JAKO CELÉ ČÍSLO VSTUP X L=X M = 65 POKUD L MOD 2 = 0 POTOM M = 52 ENDIF KDYŽ L M POKUD L > M PAK L=L-M JINÝ M=M-L ENDIF ZAMÍŘIT TISKNOUT M | x = int(vstup()) L=x M = 65 pokud L % 2 == 0: M = 52 zatímco L != M: pokud L > M: L=L-M jiný: M=M-L tisk (M) |
Algoritmický jazyk | Pascal |
alg brzy celé číslo x, L, M vstup x L:= x M:= 65 pokud mod(L,2)=0 Že M:= 52 Všechno nc zatímco L M pokud L > M Že L:= L - M v opačném případě M:= M - L Všechno kts terminál M ošidit | var x, L, M: celé číslo; začít readln(x); L:=x; M:= 65; pokud L mod 2 = 0, pak M:= 52; zatímco L M dělat pokud L > M pak L:= L - M jiný M:= M - L; writeln(M); konec. |
Xi |
|
#zahrnout void main() { intx, L, M; scanf("%d", &x); L=x; M = 65; if (L % 2 == 0) M = 52; zatímco (L != M)( pokud (L > M) L = L - M; jiný M = M - L; } printf("%d", M); } |
|
Vysvětlení.
V těle smyčky se čísla M a L zmenšují, dokud se nestanou stejnými. Aby bylo možné nakonec vytisknout 26, musí být v určitém okamžiku obě čísla rovna 26. Pojďme od konce k začátku: v předchozím kroku bylo jedno číslo 26 a druhé 26 + 26 = 52. O krok dříve 52 + 26 = 78 a 52. Předtím je 78 + 52 a 5 nalezené číslo 2 nejmenší, tedy 3 je nejmenší možné číslo 10. , pak M bude přiřazena hodnota 52, což povede k požadovanému výsledku.
Odpověď: 130.
21. HledáníNapište do odpovědi nejmenší hodnotu vstupní proměnnák, při kterém program vygeneruje stejnou odpověď jako se vstupní hodnotouk= 10. Pro vaše pohodlí je program prezentován v pěti programovacích jazycích.
ZÁKLADNÍ | Krajta |
DIM K, JÁ JSEM DLOUHÝ VSTUP K já = 1 KDYŽ F(I) I = I + 1 ZAMÍŘIT TISK I FUNKCE F(N) F=N*N*N FUNKCE UKONČENÍ FUNKCE G(N) G = 2*N + 3 FUNKCE UKONČENÍ | def f(n): vrátit n*n*n def g(n): návrat 2*n+3 k = int(vstup()) i = 1 zatímco f(i) i+=1 tisknout (i) |
Algoritmický jazyk | Pascal |
alg brzy celé číslo i, k vstup k i:= 1 nc zatímco f(i) i:= i + 1 kts výstup i ošidit alg celé číslo f(int n) brzy val:= n * n * n ošidit alg celé číslo g(int n) brzy hodnota:= 2*n + 3 ošidit | var k, i: longint; funkce f(n: longint): longint; začít f:= n * n * n; konec; funkce g(n: longint): longint; začít g:= 2*n + 3; konec; začít readln(k); i:= 1; zatímco f(i) i:=i+1; writeln(i) konec. |
Xi |
|
#zahrnout dlouhé f (dlouhé n) ( návrat n*n*n; } dlouhé g (dlouhé n) ( návrat 2*n + 3; } int main() { dlouhé k, i; scanf("%ld", &k); i = 1; zatímco(f(i) i++; printf("%ld", i); návrat 0; } |
|
Vysvětlení.
Tento program porovnáváAa přidává kijednotka až do. A vypíše první hodnotu proměnnéipod kterými
Při k = 10 program vytiskne číslo 3.
Zapišme si nerovnost:tedy dostaneme tu nejmenší hodnotuk = 3.
Odpověď: 3.
22. HledáníUmělec 15. května převede číslo na obrazovce. Účinkující má dva týmy, které mají přidělená čísla:
1. Přidejte 1
2. Vynásobte 2
První příkaz zvýší číslo na obrazovce o 1, druhý ho vynásobí 2. Program pro performera 15. května je posloupnost příkazů. Kolik existuje programů, pro které je s počátečním číslem 2 výsledkem číslo 29 a trajektorie výpočtů obsahuje číslo 14 a neobsahuje číslo 25?
Trajektorie programu je posloupnost výsledků
provádění všech příkazů programu. Například pro program 121 s počátečním číslem 7 bude trajektorie sestávat z čísel 8, 16, 17.
Vysvětlení.
Navíc platí komutativní (komutativní) zákon, což znamená, že pro výsledek nezáleží na pořadí instrukcí v programu.
Všechny příkazy zvyšují počáteční počet, takže počet příkazů nemůže překročit (30 − 21) = 9. V tomto případě je minimální počet příkazů 3.
Příkazů tedy může být 3, 4, 5, 6, 7, 8 nebo 9. Na pořadí příkazů tedy nezáleží, každý počet příkazů odpovídá jedné sadě příkazů, které mohou být uspořádány v libovolném pořadí.
Zvažme všechny možné množiny a spočítejme počet možností umístění příkazů do nich. Sada 133 má 3 možná umístění. Sada 1223 - 12 možných uspořádání: toto je počet permutací s opakováním (1+2+1)!/(1! · 2! · 1!). Nastavte 12222 - 5 možností. Nastavte 111222 - 20 možných možností. Nastavte 11123 - 20 možností. Sada 111113 - 6 možností, sada 1111122 - 21 možností, sada 11111112 - 8 možností, sada 111111111 - jedna možnost.
Celkem máme 3 + 12 + 5 + 20 + 20 + 6 + 21 + 8 + 1 = 96 programů.
Odpověď: 96.
Odpověď: 96.
Odpověď: 13
23. HledáníKolik různých sad booleovských hodnot existujeX1 , X2 , ... X9 ,y1 ,y2 , ... y9 které splňují všechny následující podmínky?
(¬ (X1 ≡ y1 )) ≡ (X2 ≡ y2 )
(¬ (X2 ≡ y2 )) ≡ (X3 ≡ y3 )
…
(¬ (X8 ≡ y8 )) ≡ (X9 ≡ y9 )
Odpověď nemusí uvádět všechny různé sady hodnot proměnnýchX1 , X2 , ... X9 ,y1 ,y2 , ... y9 , podle kterého tento systém rovnosti platí. Jako odpověď musíte uvést počet takových sad.
Vysvětlení.
Z poslední rovnice zjistíme, že existují tři možné hodnoty x8 a y8: 01, 00, 11. Vytvořme strom možností pro první a druhý pár hodnot.
Máme tedy 16 sad proměnných.
Strom možností pro pár hodnot 11:
Máme 45 možností. Systém tedy bude mít 45 + 16 = 61 různých sad řešení.
Odpověď: 61.
Odpověď: 1024
24. HledáníZpracovává se kladné celé číslo nepřesahující 10.9 . Potřebujete napsat program, který zobrazí součet číslic tohoto čísla menší než 7. Pokud v čísle nejsou žádné číslice menší než 7, musíte na obrazovce zobrazit 0. Programátor napsal program špatně. Níže je tento program pro vaše pohodlí uveden v pěti programovacích jazycích.
ZÁKLADNÍ | Krajta |
DIM N, ČÍSLICE, SOUČET JAKO DLOUHÝ VSTUP N SOUČET = 0 KDYŽ N > 0 DIGIT=NMOD 10 POKUD DIGIT SOUČET = SOUČET + 1 KONEC POKUD N=N\10 ZAMÍŘIT TISKNOUT ČÍSLICE | N = int(vstup()) součet = 0 zatímco N > 0: číslice = N% 10 pokud číslice součet = součet + 1 N = N // 10 tisknout (číslice) |
Algoritmický jazyk | Pascal |
alg brzy celé číslo N, číslice, součet vstup N součet:= 0 nc, zatímco N > 0 digit:= mod(N,10) pokud číslice součet:= součet + 1 Všechno N:=div(N;10) kts číslicový výstup ošidit | var N, číslice, součet: longint; začít readln(N); součet:= 0; zatímco N > 0 ano začít číslice:= N mod 10; pokud číslice součet:= součet + 1; N:= N div 10; konec; writeln (číslice) konec. |
Xi |
|
#zahrnout int main() { int N, číslice, součet; scanf("%d", &N); součet = 0; zatímco (N > 0) { číslice = N% 10; pokud (číslice součet = součet + 1; N = N/10; } printf("%d",číslice); návrat0; } |
|
Postupujte následovně.
1. Napište, co tento program zobrazí, když zadáte číslo 456.
2. Uveďte příklad takového třímístné číslo, po zadání kterého program dá správnou odpověď.
3. Najděte všechny chyby v tomto programu (může být jedna nebo více). Je známo, že každá chyba ovlivňuje pouze jeden řádek a lze jej opravit, aniž by bylo nutné měnit další řádky. Pro každou chybu:
1) zapište řádek, kde došlo k chybě;
2) uveďte, jak chybu opravit, tzn. uveďte správnou verzi řetězce.
Pro jeden programovací jazyk stačí uvést chyby a způsob jejich opravy. Vezměte prosím na vědomí, že musíte najít chyby ve stávajícím programu a ne psát své vlastní, případně pomocí jiného algoritmu řešení. Oprava chyby by měla ovlivnit pouze řádek, který chybu obsahuje.
Vysvětlení.
Řešení používá položku programu Pascal. Program můžete používat v kterémkoli ze čtyř dalších jazyků.
1. Program vytiskne číslo 4.
2. Příklad čísla, po zadání program dá správnou odpověď: 835.
Poznámka pro recenzenta. Program nepracuje správně kvůli špatně zobrazené proměnné a špatnému navýšení částky. V souladu s tím bude program fungovat správně, pokud se nejvyšší číslice (zcela vlevo) v čísle rovná součtu číslic menším než 7.
3. V programu jsou dvě chyby.
První chyba. Špatné zvýšení částky.
Chybový řádek:
součet:= součet + 1;
Správná oprava:
součet:= součet + číslice;
Druhá chyba. Nesprávné zobrazení odezvy na obrazovce.
Chybový řádek:
writeln (číslice)
Správná oprava:
writeln (součet)
25. HledáníJe dáno celočíselné pole 20 prvků. Prvky pole mohou nabývat celočíselné hodnoty od -10000 do 10000 včetně. Popište v přirozeném jazyce nebo v jednom z programovacích jazyků algoritmus, který vám umožní najít a zobrazit počet párů prvků pole, ve kterých je alespoň jedno číslo dělitelné 3. V tomto problému pár znamená dva po sobě jdoucí prvky pole. Například pro pole pěti prvků: 6; 2; 9; -3; 6 - odpověď: 4.
Počáteční data jsou deklarována tak, jak je uvedeno níže v příkladech pro některé programovací jazyky a přirozený jazyk. Je zakázáno používat proměnné, které nejsou popsány níže, ale je povoleno nepoužívat některé z popsaných proměnných.
ZÁKLADNÍ | Krajta |
KONST N JAKO CELÉ ČÍSLO = 20 DIM A (1 AŽ N) JAKO CELÉ ČÍSLO DIM I JAKO CELÉ ČÍSLO, J JAKO CELÉ ČÍSLO, K JAKO CELÉ ČÍSLO PRO I = 1 až N VSTUP A(I) PŘÍŠTĚ JÁ ... KONEC | # také povoleno # použijte dva # celočíselné proměnné ja k a = n=20 pro i v rozsahu (0, n): a.append(int(input())) ... |
Algoritmický jazyk | Pascal |
alg brzy celé číslo N = 20 celtab a celá čísla i, j, k nc pro i od 1 do N zadejte a[i] kts ... ošidit | konst N = 20; var a: pole celých čísel; i, j, k: celé číslo; začít pro i:= 1 až N do readln(a[i]); ... konec. |
Xi | přirozený jazyk |
#zahrnout #definujte N 20 int main() ( int a[N]; int i, j, k; pro (i = 0; i scanf("%d", &a[i]); ... návrat 0; } | Deklarujeme pole A o 20 prvcích. Deklarujeme celočíselné proměnné I, J, K. Ve smyčce od 1 do 20 zadáváme prvky pole A od 1. do 20. … |
Jako odpověď musíte poskytnout fragment programu (nebo popis algoritmu v přirozeném jazyce), který by měl být na místě elipsy. Řešení můžete napsat i v jiném programovacím jazyce (uveďte název a verzi použitého programovacího jazyka, například Free Pascal 2.6) nebo jako vývojový diagram. V tomto případě musíte použít stejná počáteční data a proměnné, které byly navrženy v podmínce (například v ukázce napsané v přirozeném jazyce).
k:=k+1
Všechno
kts
výstup k
Pascal
k:= 0;
pro i:= 1 až N-1 do
if (a[i] mod 3=0) nebo (a mod 3=0) pak
inc(k);
writeln(k);
Xi
k = 0;
pro (i = 0; i
if (a[i]%3 == 0 || a%3 == 0)
k++;
printf("%d", k);
přirozený jazyk
Počáteční hodnotu rovnou 0 zapíšeme do proměnné K. Ve smyčce od prvního prvku k předposlednímu najdeme zbytek z dělení aktuálního a dalšího prvku pole 3. Pokud je první nebo druhý z výsledných zbytků 0, zvětšíme proměnnou K o jedna. Po dokončení smyčky zobrazíme hodnotu proměnné K
26. HledáníDva hráči, Péťa a Váňa, hrají následující hru. Před hráči jsou dvě hromady kamenů. Hráči se pohybují postupně, Péťa dělá první tah. V jednom tahu může hráč přidat jeden kámen na jednu z hromádek (dle vlastního výběru) nebo zdvojnásobit počet kamenů v hromádce. Například ať je v jedné hromadě 10 kamenů a v druhé 7 kamenů; taková pozice ve hře bude označena (10, 7). Pak můžete jedním tahem získat kteroukoli ze čtyř pozic: (11, 7), (20, 7), (10, 8), (10, 14). Aby mohl provádět tahy, má každý hráč neomezený počet kamenů.
Hra končí v okamžiku, kdy celkový počet kamenů v hromádkách dosáhne alespoň 73. Vítězem se stává hráč, který provedl poslední tah, tzn. první, kdo získá takovou pozici, že v hromadách bude celkem 73 kamenů nebo více.
Řekneme, že hráč má vítěznou strategii, pokud může vyhrát za jakékoli tahy soupeře. Popsat hráčovu strategii znamená popsat, jaký tah by měl udělat v jakékoli situaci, se kterou se může setkat s různými soupeřovými hrami. Například s počátečními pozicemi (6, 34), (7, 33), (9, 32) má Péťa vítěznou strategii. K vítězství mu stačí zdvojnásobit počet kamenů na druhé hromádce.
Cvičení 1.Pro každou z počátečních pozic (6, 33), (8, 32) označte, který z hráčů má vítěznou strategii. V každém případě popište vítěznou strategii; vysvětlete, proč tato strategie vede k vítězství, a uveďte maximální počet tahů, které může vítěz provést, aby vyhrál s touto strategií.
Úkol 2.Pro každou z počátečních pozic (6, 32), (7, 32), (8, 31) označte, který z hráčů má vítěznou strategii. V každém případě popište vítěznou strategii; vysvětlete, proč tato strategie vede k vítězství, a uveďte maximální počet tahů, které může vítěz provést, aby vyhrál s touto strategií.
Úkol 3.Pro počáteční pozici (7, 31) označte, který z hráčů má vítěznou strategii. Popište vítěznou strategii; vysvětlete, proč tato strategie vede k vítězství, a uveďte maximální počet tahů, které může vítěz provést, aby vyhrál s touto strategií. Sestavte si strom všech možných her s vítěznou strategií, kterou jste určili. Prezentujte strom ve formě obrázku nebo tabulky.
(7,31)
Celkem 38
(7,31+1)=(7,32)
Celkem 39
(7+1,32)=(8,32)
Celkem 40
(8+1,32)=(9,32)
Celkem 41
(9,32*2)=(9,64)
Celkem 73
(8,32+1)=(8,33)
Celkem 41
(8,33*2)=(8,66)
Celkem 74
(8*2,32)=(16,32)
Celkem 48
(16,32*2)=(16,64)
Celkem80
(8,32*2)=(8,64)
Celkem 72
(8,64*2)=(8,128)
Celkem 136
(7+1,31)=(8,31)
Celkem 39
(8,31+1)=(8,32)
Celkem 40
(8+1,32)=(9,32)
Celkem 41
(9,32*2)=(9,64)
Celkem 73
(8,32+1)=(8,33)
Celkem41
(8,33*2)=(8,66)
Celkem 74
(8*2,32)=(16,32)
Celkem 48
(16,32*2)=(16,64)
Celkem 80
(8,32*2)=(8,64)
Celkem 72
(8,64*2)=(8,128)
Celkem 136
(7*2,31)=(14,31)
Celkem 45
(14,31*2)=(14,62)
Celkem 76
(7,31*2)=(7,62)
Celkem 69
(7,62*2)=(7,124)
Celkem 131
Cvičení 1.Na úvodních pozicích (6, 33), (8, 32) má Váňa vítěznou strategii. S počáteční pozicí (6, 33) lze po Péťově prvním tahu získat jednu z následujících čtyř pozic: (7, 33), (12, 33), (6, 34), (6, 66). Každá z těchto pozic obsahuje méně než 73 kamenů. Navíc z kterékoli z těchto pozic může Váňa získat pozici obsahující alespoň 73 kamenů zdvojnásobením počtu kamenů na druhé hromádce. Pro pozici (8, 32) lze po Péťově prvním tahu získat jednu z následujících čtyř pozic: (9, 32), (16, 32), (8, 33), (8, 64). Každá z těchto pozic obsahuje méně než 73 kamenů. Navíc z kterékoli z těchto pozic může Váňa získat pozici obsahující alespoň 73 kamenů zdvojnásobením počtu kamenů na druhé hromádce. Tedy, Váňo, za jakýkoli Péťův pohyb
vyhraje na svůj první tah.
Úkol 2.Na úvodních pozicích (6, 32), (7, 32) a (8, 31) má Péťa vítěznou strategii. S výchozí pozicí (6, 32) musí nejprve pohnout, aby získal pozici (6, 33), z výchozích pozic (7, 32) a (8, 31). Péťa by po prvním tahu měl dostat pozici (8, 32). Pozice (6, 33) a (8, 32) byly brány v úvahu při analýze úkolu 1. V těchto pozicích má hráč, který se posune jako druhý (nyní je to Péťa), vítěznou strategii. Tato strategie byla popsána v analýze úkolu 1. V jakékoli hře, kterou Vanya hraje, tedy Péťa vyhrává svým druhým tahem.
Úkol 3.Na úvodní pozici (7, 31) má Váňa vítěznou strategii. Po Péťově prvním tahu se může objevit jedna ze čtyř pozic: (8, 31), (7, 32), (14, 31) a (7, 62). Na pozicích (14, 31) a (7, 62) může Vanya vyhrát v jednom tahu zdvojnásobením počtu kamenů na druhé hromádce. Pozice (8, 31) a (7, 32) byly zohledněny v analýze úlohy 2. V těchto pozicích má hráč, který musí provést tah (nyní je to Vanya), vítěznou strategii. Tato strategie byla popsána v analýze úkolu 2. V závislosti na Peťově hře tedy Váňa vyhrává v prvním nebo druhém tahu.
27. HledáníVe fyzikální laboratoři probíhá dlouhodobý experiment na studium gravitačního pole Země. Každou minutu je do laboratoře přenášeno přes komunikační kanál kladné celé číslo - aktuální odečet přístroje Sigma 2015. Počet přenášených čísel v řadě je znám a nepřesahuje 10 000. Všechna čísla nepřesahují 1000. Dobu, po kterou přenos probíhá, lze zanedbat.
Je nutné vypočítat "beta hodnotu" série odečtů přístrojů - minimální sudý součin dvou odečtů, mezi jejichž okamžiky přenosu uplynulo alespoň 6 minut. Pokud takový produkt nelze získat, považuje se odpověď za rovna -1.
Jsou vám nabídnuty dva úkoly související s tímto úkolem: úkol A a úkol B. Můžete vyřešit oba úkoly nebo jeden z nich podle vašeho výběru. Výsledná známka je stanovena jako maximum známek za úlohy A a B. Není-li řešení některé z úloh předloženo, má se za to, že známka za tuto úlohu je 0 bodů. Úloha B je komplikovaná verze úlohy A, obsahuje další požadavky na program.
A. Napište program pro řešení problému v libovolném programovacím jazyce, ve kterém budou vstupní data uložena v poli, po kterém budou zkontrolovány všechny možné dvojice prvků. Před programem zadejte verzi programovacího jazyka.
UVEĎTE, že program je řešením ÚLOHY A.
Maximální skóre za splnění úkolu A jsou 2 body.
B. Napište program pro řešení problému, který je efektivní jak z hlediska času, tak paměti (nebo alespoň jedné z těchto charakteristik).
Program je považován za efektivní z hlediska času, pokud je doba běhu
program je úměrný počtu přijatých odečtů přístroje N, tzn. když se N zvýší o kkrát, doba běhu programu by se neměla zvýšit o více než kkrát.
Program je považován za paměťově efektivní, pokud velikost paměti použité v programu pro ukládání dat nezávisí na čísle N a nepřesahuje 1 kilobajt.
Před programem uveďte verzi programovacího jazyka a stručně popište použitý algoritmus.
UVEĎTE, že program je řešením ÚLOHY B.
Maximální skóre za správný program, který je efektivní z hlediska času a paměti, jsou 4 body.
Maximální skóre za správný program, který je časově efektivní, ale paměťově neefektivní, jsou 3 body. PŘIPOMÍNKA! Nezapomeňte uvést, ke kterému úkolu každý z vámi odevzdaných programů patří.
Vstupní data jsou prezentována následovně. První řádek obsahuje číslo N - celkový počet odečtů přístroje. Je zaručeno, že N > 6. Každý z dalších N řádků obsahuje jedno kladné celé číslo - další čtení přístroje.
Příklad vstupu:
11
12
45
5
3
17
23
21
20
19
18
17
Program by měl zobrazit jedno číslo - produkt popsaný ve stavu, nebo -1, pokud takový produkt nelze získat.
Příklad výstupu pro výše uvedený příklad vstupu:
54
Vysvětlení.
Úloha B (řešení úlohy A je uvedeno níže, viz program 4). Aby byl součin sudý, musí být alespoň jeden faktor sudý, proto lze při hledání vhodných produktů posuzovat sudé údaje přístroje v tandemu s jakýmikoli jinými a liché pouze se sudými.
Pro každou indikaci s číslem k, počínaje k = 7, považujeme všechny dvojice za přípustné za podmínek úlohy, ve které je tato indikace získána jako druhá. Minimální součin všech těchto dvojic se získá, pokud se nejprve ve dvojici ze všech přijatých odečte minimální vhodný odečet od začátku příjmu a až po odečet s číslem k - 6. Je-li další odečet sudý, může být minimum mezi předchozími libovolné, je-li liché - pouze sudé.
Chcete-li získat časově efektivní řešení, pamatujte si při zadávání dat absolutní minimum a minimum sudých hodnot pro každý časový bod, vynásobte každou nově získanou hodnotu odpovídajícím minimem, které bylo k dispozici o 6 prvků dříve, a vyberte minimum všech takových produktů.
Vzhledem k tomu, že každý aktuální nízký údaj se použije po zadání 6 dalších položek a poté se stane nepotřebným, stačí uložit pouze posledních 6 nejnižších hodnot. K tomu můžete použít pole 6 prvků a procházet je při zadávání dat. Velikost tohoto pole není závislá na celkovém počtu zadaných odečtů, takže toto řešení bude efektivní nejen z hlediska času, ale i paměti. Chcete-li uložit absolutní a sudá minima, musíte použít dvě taková pole. Níže je uveden příklad takového programu napsaného v algoritmickém jazyce.
Příklad 1. Příklad správného programu v algoritmickém jazyce. Program je efektivní jak z hlediska času, tak paměti.
alg
brzy
celé číslo s = 6 | požadovaná vzdálenost mezi čteními
celé číslo amax = 1001 | více než maximální možné čtení
celé číslo N
vstup N
celé číslo a | další čtení přístroje
celtab mini | aktuální minima posledních s prvků
celtab minichet | sudá minima posledních s prvků
cíl i
| zadejte první hodnoty s, opravte minima
celá ma; ma:= amax | minimální čtení
celý spěch; spěchá:= amax | minimální rovnoměrné čtení
nc pro i od 1 do s
vstup a
ma:= imin(ma, a)
mini := máma
minichet := spěchat
kts
celé číslo mp = amax*amax | minimální hodnotu produktu
celý p
nc pro i od s+1 do N
vstup a
pokud mod(a,2)=0
pak n:= a * mini
jinak pokud spěchá
pak n:= a * minieven
jinak n:= amax*amax;
Všechno
Všechno
mp:= imin(mp, n)
ma:= imin(ma, a)
pokud mod(a,2) = 0, pak bliká:= imin(flash,a) vše
mini := máma
minichet := spěchat
kts
pokud mp = amax*amax, pak mp:=-1 vše
výkon mp
ošidit
Jiné implementace jsou také možné. Například místo cyklického vyplňování pole můžete pokaždé posouvat jeho prvky. V níže uvedeném příkladu nejsou uložena a posunuta minima, ale původní hodnoty. To vyžaduje o něco méně paměti (stačí jedno pole místo dvou), ale řešení s posuny je časově méně efektivní než s cyklickým plněním. Doba běhu však zůstává úměrná N, takže maximální skóre za toto řešení je také 4 body.
Program 2. Příklad správného programu v Pascalu.
Program používá směny, ale je časově a paměťově efektivní
var
N: celé číslo
a: pole celých čísel; (ukládání odečtů přístroje)
a_: celé číslo; (zadání další indikace)
p: celé číslo;
i, j: celé číslo;
začít
readln(N);
(Zadání prvních čísel s)
for i:=1 to s do readln(a[i]);
(Zadání dalších hodnot, nalezení minimálního produktu)
ma:= amax; já:= amax;
mp:=amax*amax;
for i:= s + 1 až N do begin
readln(a_);
Pokud
jestliže (a mod 2 = 0) a (a
pokud a_ mod 2 = 0, pak p:= a_ * ma
jinak když já
jinak p:= amax* amax;
pokud (str
(posunout prvky pomocného pole doleva)
pro j:= 1 až s - 1 do
a[j] := a;
a[s] := a_
konec;
jestliže mp = amax*amax, pak mp:=-1;
writeln(mp)
konec.
Pokud jsou místo malého pole pevné velikosti (cyklické nebo posunuté) uložena všechna původní data (nebo všechna aktuální minima), program zůstává časově efektivní, ale stává se paměťově neefektivní, protože požadovaná paměť roste úměrně k N. Níže je příklad takového programu v Pascalu. Podobné (a v podstatě podobné) programy jsou hodnoceny nejvýše 3 body.
Program 3. Příklad správného programu Pascal. Program je časově nenáročný, ale paměťově neefektivní
const s = 6; (požadovaná vzdálenost mezi čteními)
amax = 1001; (větší než maximální možné čtení)
var
N, p, i: celé číslo;
ma: celé číslo; (minimální počet bez posledních s)
já: celé číslo; (minimální sudé číslo bez posledních s)
mp: celé číslo; (minimální hodnota produktu)
začít
readln(N);
(Zadání všech hodnot přístroje)
pro i:=1 až N do readln(a[i]);
ma:= amax;
já:= amax;
mp:= amax*amax;
pro i:= s + 1 až N do
začít
Pokud
jestliže (a mod 2 = 0) a (a
já:= a;
pokud a[i] mod 2 = 0, pak p:= a[i] * ma
jinak když já
jinak p:= amax * amax;
pokud (str
konec;
jestliže mp = amax*amax, pak mp:= -1;
writeln(mp)
konec.
Možné je i výčtové řešení, ve kterém se najdou součiny všech možných dvojic a vybere se z nich minimum. Níže (viz program 4) je příklad takového řešení. Toto (a podobné) řešení není časově ani paměťově efektivní. Jedná se o řešení úlohy A, nikoli však řešení úlohy B. Bodové hodnocení za takové řešení je 2 body.
Program 4. Příklad správného programu Pascal. Program není časově ani paměťově nenáročný
const s = 6; (požadovaná vzdálenost mezi čteními)
var
N: celé číslo
a: pole celých čísel; (všechny údaje přístroje)
mp: celé číslo; (minimální hodnota produktu)
i, j: celé číslo;
začít
readln(N);
(Zadejte hodnoty nástroje)
pro i:=1 až N do
readln(a[i]);
teplota tání:= 1000 x 1000 + 1;
pro i:= 1 až N-s začínají
pro j:= i+s až N do begin
if (a[i]*a[j] mod 2 = 0) a (a[i]*a[j]
pak mp:= a[i]*a[j]
konec;
konec;
pokud mp = 1000 * 1000 + 1, pak mp:= -1;
writeln(mp)
Test USE v informatice není povinným testem pro všechny absolventy škol, ale je vyžadován pro přijetí na řadu technických univerzit. Tato zkouška se skládá jen zřídka, protože vyšší vzdělávací instituce tam, kde je to požadováno, trochu. Častým případem při vstupu do řady specializací na polytechnických univerzitách je možnost volby mezi fyzikou a informatikou. V takové situaci mnozí volí to druhé, protože fyzika je právem považována za složitější disciplínu. Znalosti informatiky budou užitečné nejen pro přijetí, ale také v procesu zvládnutí specializace na vysoké škole.
Hlavním rysem školního předmětu "Informatika" je malý objem, proto je pro kvalitní přípravu potřeba méně času než u jiných předmětů. Je možné připravit "od nuly"! Jako kompenzaci malého množství materiálu nabízejí autoři otázek a úkolů předměty náročné úkolyúkoly, které vyvolávají chyby, vyžadují kvalitní znalost informací a jejich kompetentní využití. Obsah zkoušky obsahuje značné množství úloh, které se blíží znalostem matematiky a logiky. Významnou součástí je blok úloh pro algoritmizaci, úlohy, programování. Překontrolovat
Všechny úlohy lze rozdělit do 2 bloků - testování (úkoly na znalost teorie, nutná krátká odpověď), podrobné úlohy. První části se doporučuje věnovat asi hodinu a půl, druhé více než dvě. Udělejte si čas na kontrolu chyb a vyplňte odpovědi do formuláře.
Naučit se snadno překonávat překážky v podobě obtížné úkoly, použijte zdroj "zkoušku vyřeším". Je to skvělá příležitost otestovat se, upevnit znalosti, analyzovat své vlastní chyby. Pravidelné online testování zbaví úzkosti a obav z nedostatku času. Úkoly jsou zde většinou těžší než u zkoušky.
- Doporučuje se, abyste si pozorně přečetli přípravný program USE – díky tomu bude proces opakování systematický a strukturovaný, abyste se naučili teorii.
- Dodnes bylo vyvinuto mnoho cvičebních pomůcek – využijte je k procvičování a studiu látky.
- Naučte se řešit problémy různého typu – s pomocí lektora je to jednodušší. V přítomnosti vysoká úroveň znalosti, můžete to udělat sami.
- Rozhodněte se pro dobu, kdy jste si osvojili potřebná data a naučili se řešit problémy. S tím pomůže online testování.
- Důležité je nevynechat příležitosti k přípravě: kurzy, školení, dálkové kurzy, doučování, sebevzdělávání. Popište problémy, které způsobují největší počet otázky a potíže.
- Praxe v řešení problémů – čím více, tím lépe.
- Věnujte práci s úkoly správný čas různé úrovně potíže.
- Najděte si profesionálního lektora, který vám pomůže vyplnit mezery ve znalostech.
Možnost č. 3490088
Při plnění úkolů s krátkou odpovědí zadávejte do pole odpovědi číslo, které odpovídá číslu správné odpovědi, nebo číslo, slovo, posloupnost písmen (slov) nebo číslic. Odpověď by měla být psána bez mezer nebo jakýchkoli dalších znaků. Oddělte zlomkovou část od celé desetinné čárky. Jednotky měření nejsou povinné.
Pokud je možnost nastavena učitelem, můžete do systému zadávat nebo nahrávat odpovědi na úkoly s podrobnou odpovědí. Učitel uvidí výsledky úkolů s krátkými odpověďmi a bude moci ohodnotit nahrané odpovědi k úkolům s dlouhými odpověďmi. Body udělené učitelem se zobrazí ve vašich statistikách.
Verze pro tisk a kopírování v MS Word
Zadejte nejmenší čtyřmístné hexadecimální číslo, jehož binární zápis obsahuje přesně 5 nul. Ve své odpovědi zapište pouze samotné hexadecimální číslo, základ číselné soustavy uvádět nemusíte.
Odpovědět:
Fragment pravdivostní tabulky výrazu F je dán:
| x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | F |
|---|---|---|---|---|---|---|---|---|
| 1 | 0 | 1 | 0 | 1 | 1 | 1 | 0 | 0 |
| 0 | 1 | 0 | 1 | 1 | 0 | 0 | 1 | 0 |
| 1 | 0 | 0 | 1 | 0 | 1 | 0 | 1 | 1 |
Který z následujících výrazů může být F?
1) (x2→x1) ∧ ¬x3 ∧ x4 ∧ ¬x5 ∧ x6 ∧ ¬x7 ∧ x8
2) (x2→x1) ∨ ¬x3 ∨ x4 ∨ ¬x5 ∨ x6 ∨ ¬x7 ∨ x8
3) ¬(x2→x1) ∨ x3 ∨ ¬x4 ∨ x5 ∨ ¬x6 ∨ x7 ∨ ¬x8
4) (x2→x1) ∧ x3 ∧ ¬x4 ∧ x5 ∧ ¬x6 ∧ x7 ∧ ¬x8
Odpovědět:
Mezi osad Staví se silnice A, B, C, D, E, F, jejichž délka je uvedena v tabulce. Absence čísla v tabulce znamená, že mezi body nevede žádná přímá cesta.
| A | B | C | D | E | F | |
| A | 2 | 4 | 8 | 16 | ||
| B | 2 | 3 | ||||
| C | 4 | 3 | ||||
| D | 8 | 3 | 3 | 5 | 3 | |
| E | 5 | 5 | ||||
| F | 16 | 3 | 5 |
Určete délku nejkratší cesty mezi body A a F, která prochází bodem E a neprochází bodem B. Pohybovat se můžete pouze po vyznačených cestách.
Odpovědět:
Pro dávkové operace se soubory se používají masky názvů souborů. Maska je posloupnost písmen, čísel a dalších znaků povolených v názvech souborů, která může obsahovat také následující znaky:
symbol "?" () otazník znamená právě jeden libovolný znak.
symbol "*" (hvězdička) znamená libovolnou sekvenci znaků libovolné délky, včetně "*" může také specifikovat prázdnou sekvenci.
Adresář obsahuje 6 souborů:
Určete, která maska bude použita k výběru zadané skupiny souborů z adresáře:
Odpovědět:
K přenosu dat komunikačním kanálem se používá 5bitový kód. Zpráva obsahuje pouze písmena A, B a C, která jsou kódována následujícími kódovými slovy:
A - 11111, B - 00011, C - 00100.
Přenos může být přerušen. Některé chyby však lze opravit. Libovolná dvě z těchto tří kódových slov se od sebe liší alespoň ve třech pozicích. Pokud tedy přenos slova nemá chybu na více než jedné pozici, lze kvalifikovaně odhadnout, které písmeno bylo přeneseno. (Říkají, že „kód opravuje jednu chybu.“) Pokud je například přijato kódové slovo 10111, má se za to, že bylo přeneseno písmeno A. (Rozdíl od kódového slova pro A je pouze v jedné poloze, u zbývajících kódových slov je rozdílů více.) Pokud se přijaté kódové slovo liší od kódových slov pro písmena A, B, C na více než jedné pozici, pak se má za to, že došlo k chybě (x).
Odpovědět:
Automat obdrží jako vstup čtyřmístné číslo (číslo nemůže začínat od nuly). Na základě tohoto čísla se sestaví nové číslo podle následujících pravidel.
1. První a druhá, druhá a třetí, třetí a čtvrtá číslice daného čísla se přidávají samostatně.
2. Nejmenší z přijatých tří částek je odstraněna.
3. Zbývající dvě částky se zapisují jedna po druhé v neklesajícím pořadí bez oddělovačů.
Příklad. Původní číslo: 1984. Součty: 1 + 9 = 10, 9 + 8 = 17, 8 + 4 = 12.
10 je odstraněno. Výsledek: 1217.
Upřesněte nejméněčíslo, při jehož zpracování stroj vygeneruje výsledek 613.
Odpovědět:
Je uveden fragment tabulky.
| A | B | C | D | E | F | |
|---|---|---|---|---|---|---|
| 1 | ||||||
| 2 | 1 | 10 | 100 | 1000 | ||
| 3 | 2 | 20 | 200 | 2000 | ||
| 4 | 3 | 30 | 300 | 3000 | ||
| 5 | 4 | 40 | 400 | 4000 | ||
| 6 | 5 | 50 | 500 | 5000 |
Do buňky B2 jsme napsali vzorec =D$4 + $F3. Poté byla buňka B2 zkopírována do buňky A3. Jaké číslo se zobrazí v buňce A3?
Poznámka: Znak $ se používá k označení absolutního adresování.
Odpovědět:
Zapište si číslo, které bude vytištěno jako výsledek následujícího programu. Pro vaše pohodlí je program prezentován v pěti programovacích jazycích.
Odpovědět:
Produkoval čtyřkanálový (quad) zvukový záznam se vzorkovací frekvencí 32 kHz a 32bitovým rozlišením. Záznam trvá 3 minuty, jeho výsledky se zapisují do souboru, komprese dat se neprovádí. Určete přibližnou velikost výsledného souboru (v MB). Uveďte svou odpověď jako nejbližší celočíselný násobek pěti k velikosti souboru.
Odpovědět:
Šifra kódového zámku je posloupnost pěti znaků, z nichž každý je číslice od 1 do 5. Kolik různých možností šifry lze zadat, je-li známo, že číslice 1 se vyskytuje právě třikrát a každá z ostatních platných číslic se může v šifře vyskytovat libovolněkrát nebo se nevyskytuje vůbec?
Odpovědět:
Níže je rekurzivní algoritmus napsán v pěti programovacích jazycích F.
Jako odpověď uveďte sekvenci číslic, která se vytiskne na obrazovku v důsledku volání F(5).
Odpovědět:
V terminologii sítí TCP / IP je maska podsítě 32bitové binární číslo, které určuje, které bity IP adresy počítače jsou společné pro celou podsíť – tyto bity masky obsahují 1. Masky se obvykle zapisují jako čtyři desetinná čísla– podle stejných pravidel jako IP adresy. Pro některé podsítě je maska 255.255.248.0. Kolik různých adres počítačů tato maska umožňuje?
Poznámka. V praxi se k adresování počítačů nepoužívají dvě adresy: síťová adresa a broadcast adresa.
Odpovědět:
Číslo vozu se skládá z několika písmen (počet písmen je ve všech číslech stejný), za nimiž následují 4 číslice. To používá 10 čísel a pouze 5 písmen: P, O, M, A, N. Musíte mít alespoň 1 000 000 různých čísel. Jaký minimální počet písmen by měl být v čísle auta?
Odpovědět:
Interpret CAR „žije“ v omezeném pravoúhlém labyrintu na kostkované rovině, jak je znázorněno na obrázku. Šedé buňky - vztyčené stěny, buňky bez světla, po kterých se CAR může volně pohybovat. Podél okraje pole labyrintu je také vztyčená zeď s čísly a písmeny použitými k identifikaci buněk v bludišti.
Příkazový systém vykonavatele MACHINKA:
Po provedení některého z těchto příkazů se CAR posune o jednu buňku (vzhledem k pozorovateli): nahoru, dolů ↓, doleva ←, doprava →.
Čtyři příkazy ověřují pravdivost podmínky nepřítomnosti stěny na každé straně buňky, kde se nachází CAR (také ve vztahu k pozorovateli):
SBOHEM<условие>tým
se provede, když je podmínka pravdivá, jinak se přesune na další řádek.
Když se pokusíte přesunout do jakékoli šedé buňky, CAR narazí na zeď.
Kolik buněk daného labyrintu splňuje požadavek, aby se STROJ po spuštění v něm a provedení níže navrženého programu nezhroutil?
SBOHEM<снизу свободно>dolů
SBOHEM<слева свободно>doleva
Odpovědět:
Na obrázku je schéma silnic spojujících města A, B, C, D, D, E, K, L, M, N, P, R, T. Po každé silnici se můžete pohybovat pouze jedním směrem, označeným šipkou.
Kolik různých cest existuje z města A do města T?
Odpovědět:
V základním číselném systému N záznam čísla 87 10 končí 2 a obsahuje nejvýše dvě číslice. Uveďte všechny použitelné hodnoty oddělené čárkami ve vzestupném pořadí N.
Odpovědět:
V dotazovacím jazyce vyhledávače se symbol "|" používá k označení logické operace "OR" a symbol "&" se používá pro logickou operaci "AND".
Tabulka zobrazuje dotazy a počet jimi nalezených stránek pro určitý segment internetu.
| Žádost | Nalezené stránky (v tisících) |
|---|---|
| Francie a Německo | 274 |
| Německo a (Francie | Rakousko) | 467 |
| Francie & Německo & Rakousko | 104 |
Kolik stránek (v tisících) bude nalezeno pro dotaz Německo a Rakousko?
Předpokládá se, že všechny požadavky byly provedeny téměř současně, takže množina stránek obsahující všechna hledaná slova se během provádění požadavků nezměnila.
Odpovědět:
Označte m&n bitovou konjunkci nezáporných celých čísel m A n.
Takže například 14&5 = 1110 2 &0101 2 = 0100 2 = 4.
Pro jaké je nejmenší nezáporné celé číslo A vzorec
X&51 = 0 ∨ (X&41 = 0 → X&A = 0)
je identicky pravdivá (tj. má hodnotu 1 pro jakoukoli nezápornou celočíselnou hodnotu proměnné X)?
Odpovědět:
Níže je záznam různé jazyky programovací fragment stejného programu. Program popisuje jednorozměrné celočíselné pole A; v prezentovaném fragmentu jsou zpracovány prvky pole s indexy od 1 do 10.
Před spuštěním programu měly tyto prvky pole hodnoty 0, 1, 2, 3, 4, 5, 4, 3, 2, 1 (tj. A = 0; A = 1; ...; A = 1).
Který z těchto prvků pole bude mít po provedení fragmentu programu největší hodnotu? Ve své odpovědi uveďte index prvku - číslo od 1 do 10.
Odpovědět:
Algoritmus je napsán v pěti níže uvedených jazycích. Po přijetí čísla x jako vstupu tento algoritmus vypíše dvě čísla: a a b. Zadejte nejmenší z těchto čísel x, když je zadáno, algoritmus vytiskne nejprve 3 a poté 12.
Odpovědět:
Napište do odpovědi nejvyšší hodnotu vstupní proměnná k, při kterém program vygeneruje stejnou odpověď jako se vstupní hodnotou k= 20. Pro vaše pohodlí je program prezentován v pěti programovacích jazycích.
Odpovědět:
Exekutor kalkulačky má dva příkazy:
1. přidat 4,
2. odečíst 2.
První z nich zvyšuje číslo na obrazovce o 4, druhé - snižuje jej o 2. Pokud se během výpočtů objeví záporné číslo, zhroutí se a vymaže to, co je napsáno na obrazovce. Program kalkulačky je posloupnost příkazů. Kolik různých čísel lze získat z čísla 8 pomocí programu, který obsahuje přesně 16 instrukcí?
Odpovědět:
Kolik různých sad hodnot booleovských proměnných x1, x2, x3, x4, x5, x6, x7, x8, x9, x10 existuje, které splňují všechny následující podmínky:
((x1 → x2) → (x3 → x4)) ∧ ((x3 → x4) → (x5 → x6)) = 1;
((x5 → x6) → (x7 → x8)) ∧ ((x7 → x8) → (x9 → x10)) = 1;
x1∧x3∧x5∧x7∧x9 = 1.
V odpovědi není třeba vypisovat všechny různé sady hodnot proměnných x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, pod kterými je daný systém rovnosti splněn. Jako odpověď musíte uvést počet takových sad.
Odpovědět:
Bylo nutné napsat program, který zadá z klávesnice souřadnice bodu v rovině ( x, y jsou reálná čísla) a určuje, zda bod patří do stínované oblasti. Programátor spěchal a program napsal špatně.
Postupně proveďte následující:
1. Překreslete a vyplňte tabulku, která ukazuje, jak program pracuje s argumenty patřícími do různé oblasti(A, B, C, D, E, F, G a H).
Body ležící na hranicích regionů se samostatně neuvažují. Ve sloupcích podmínky zadejte „ano“, pokud je podmínka splněna, „ne“, pokud podmínka splněna není, „-“ (pomlčka), pokud podmínka nebude kontrolována, „neznámo“, pokud se program chová odlišně pro různé hodnoty patřící do této oblasti. Ve sloupci "Program bude výstup" určete, co program zobrazí na obrazovce. Pokud program nic nezobrazuje, napište "-" (pomlčka). Pokud se pro různé hodnoty patřící do oblasti zobrazují různé texty, napište „neznámé“. Do posledního sloupce zadejte „ano“ nebo „ne“.
2. Uveďte, jak je třeba program vylepšit, aby nedocházelo k případům jeho nesprávného fungování. (To lze provést několika způsoby, stačí zadat jakýkoli způsob, jak upřesnit původní program.)
| Kraj | Podmínka 1 (y >= −x*x) | Podmínka 2 (y >= −x−2) | Podmínka 3 | Program vypíše |
S moderní svět technologie a reality programování, voj POUŽITÍ v informatice má málo společného. Existuje několik základních bodů, ale i když úkolům trochu rozumíte, neznamená to, že se nakonec stanete dobrým vývojářem. Ale je spousta oblastí, kde jsou IT specialisté potřeba. Vůbec neztratíte, pokud chcete mít stabilní nadprůměrný příjem. V IT to dostanete. Samozřejmě za předpokladu, že máte odpovídající dovednosti. A můžete se zde rozvíjet a růst, jak chcete, protože trh je tak obrovský, že si to ani nedokážete představit! A neomezuje se pouze na náš stát. Pracujte pro jakoukoli společnost odkudkoli na světě! To vše je velmi inspirativní, nechť je tedy příprava na zkoušku z informatiky prvním malým krůčkem, po kterém budou následovat roky seberozvoje a zdokonalování se v této oblasti.
Struktura
Část 1 obsahuje 23 úloh s krátkou odpovědí. Tato část obsahuje úlohy s krátkou odpovědí, které implikují nezávislou formulaci posloupnosti znaků. Úkoly prověřují látku všech tematických bloků. 12 úkolů souvisí základní úroveň, 10 úkolů na zvýšenou úroveň složitosti, 1 úkol na vysokou úroveň složitosti.
2. část obsahuje 4 úkoly, z nichž první pokročilá úroveň obtížnosti, zbývající 3 úkoly vysoké úrovně složitosti. Úkoly této části zahrnují napsání podrobné odpovědi v libovolné formě.
K provedení zkušební práce Jsou přiděleny 3 hodiny 55 minut (235 minut). Na splnění úkolů z 1. části se doporučuje zabrat 1,5 hodiny (90 minut). Zbytek času se doporučuje věnovat úkolům z části 2.
Vysvětlivky k hodnocení úkolů
Splnění každého úkolu z 1. části se odhaduje na 1 bod. Úkol z části 1 se považuje za splněný, pokud zkoušející uvedl odpověď odpovídající kódu správné odpovědi. Splnění úkolů 2. části se odhaduje na 0 až 4 body. Odpovědi na úkoly 2. části kontrolují a vyhodnocují odborníci. Maximální počet bodů, které lze získat za splnění úkolů z části 2, je 12.
