====== Cvičení 4: 1D pole ====== ==== Úkol 1 Opakování funkce a for cykly ==== * Napište program, který porovná dvě funkce ''a(x,y,z)'' a ''b(x,y,z)'' se třemi logickými proměnnými a zjistí, zda výrazy jsou ekvivalentní, případně vypíše pro jaké kombinace vstupů se výstupy liší. * Porovnejte následující funkce: def a(x,y,z): return (x and y) or (not y and z) def b(x,y,z): return x or z ==== Úkol 2 Najdi a změň ==== * Napište funkci ''my_find(a,b)'', která v řetezci ''a'' hledá řetězec ''b'' (nepoužívejte vestavěnou funkci find). * Pokud řetězec najde, vrátí index jeho prvního výskytu zleva. * Pokud řetězec nenajde, vrátí -1. * Napište funkci ''my_replace(a,b,c)'', která v řetězci ''a'' nahradí všechny výskyty řetězce ''b'' řetězcem ''c''. * Ve funkcích používejte pouze funkce * ''len(s)'' - délka řetězce, * ''s[i]'' - znak na pozici ''i'', * ''s[i:j]'' - podřetezec od ''i'' do ''j'' * ''s[:j]'', ''s[i:]'' - podřetězec od počátku do ''j'', resp. od ''i'' do konce. ==== Úkol 3 Záměna slova ==== * Napište program, který čte standardní vstup a v načteném řetězci zamění slovo ''Ahoj'' za slovo ''Cau''. * Můžete využít vestavěné funkce find, replace, nebo Vaše funkce z předchozí úlohy. * Pokud se ve vstupním řetězci objeví slovo ''Konec'', program skončí. V tomto řádku ale nejdříve zamění Ahoj za Cau. ==== Načítání ze souboru ==== * Načtení 1D pole ze souboru * Pole může být v souboru uloženo dvěma způsoby: * všechna čísla na jednom řádku oddělená mezerami, nebo jiným znakem * pro načtení nejdřív rozdělte řádek na řetězce podle dělicího znaku - funkce ''split()'' * pak převeďte řetězce na čísla a uložte do pole f=open('line.txt','r') line = f.readline() pole = list(map(int, line.split())) f.close() * na řádku pouze jedno číslo, počet řádek udává délku pole * otevřete soubor pro čtení - ''open''(název_souboru, "r" - read čtení) * přečtěte celý soubor po řádcích - ''readline'', nebo cyklus ''for'' * každý řádek převeďte na číslo a připojte na konec pole - funkce ''append'' * po dokončení čtení je správné soubor uzavřít - funkce ''close'' proměnné soubor pole=[] f=open('pole.txt','r') for line in f: pole.append(int(line)) f.close() * Tisk a formátování výstupu * nejjednodušší výpis jednorozměrného pole je přímo využít vestavěnou funkci print - ''print(pole)'' * pokud chcete vypsat pole na každý řádek jednu hodnotu, pak využijte cyklus ''for'' for x in pole: print(x) ==== Úkol 4 funkce nalezení maxima ==== * Napište funkci, která vrací největší hodnotu v poli a zároveň vrací index tohoto prvku * Pro pole nulové délky vrací index -1. * Pozor: je třeba předpokládat, že v poli mohou být jakékoliv hodnoty (kladné, nuly, záporné)! ==== Úkol 5 funkce nalezení druhého největšího prvku v poli ==== * Napište funkci, která vrací druhou největší hodnotu v poli a zároveň vrací index tohoto prvku * Pro pole délky méně než 2 vrací index -1. * Pozor: je třeba předpokládat, že v poli mohou být opět jakékoliv hodnoty (kladné, nuly, záporné)! ==== Polynomy ==== * Polynom $a_0 + a_1 x + a_2 x^2 + \ldots + a_n x^n$ můžeme reprezentovat polem koeficientů ''[ a_0, a_1, a_2, ... , a_n ]'' * Příklad: * polynomu $1 + x - 2x^2$ odpovídá pole ''[1, 1, -2 ]'' * polynomu $x - x^3$ odpovídá pole ''[0, 1, 0,-1 ]'' * Nulové koeficienty lze vynechat u nejvyšších mocnin, ale ne u nejnižších. * Příklad: * ''[0,1,2]'' vyjadřuje polynom $x + 2x^2$ * ''[0,1,2,0]'' vyjadřuje taktéž polynom $x + 2x^2$ * ale ''[1,2,0]'' vyjadřuje polynom $1 + 2x$ ==== Úkol 6 hezký výpis polynomu ==== * Napište funkci ''printPoly'',která vypíše polynom, přičemž mocniny bude tisknout znakem '^'. * Pokud je nějaký koeficient nulový, příslušný člen se nevypíše. * Příklad: * ''printPoly( [ 1, 1, 0, -2] )'' vytiskne ''1 + x - 2x^3'' * ''printPoly( [ -2, 0, 0, -2, 0, 0, 0] )'' vytiskne ''-2 - 2x^3'' ==== Úkol 7 výpočet hodnoty polynomu ==== * Napište funkci ''polyValue'' , která pro zadaný polynom a hodnotu x vypočte jeho hodnotu v zadaném bodě $x$ * Tedy ''polyValue([1,0,2], 4)'' má hodnotu ''33'', protože $1 + 2x^2$ pro $x=4$ je 33. ===== Témata k procvičení ===== * Napište funkci, která pro zadaný polynom najde maximum/minimum v zadaném intervalu $$. Řešte numericky, např. s krokem $\delta=0.1$. Nápověda: použijte funkci pro výpočet hodnoty polynomu. * Napište funkci pro výpočet první derivace polynomu: * Příklad: derivace ''[0,2,-3]'' je ''[2,-6]'' neboť derivace $2x - 3x^2$ je $2 - 6x$ ===== Domácí úkol ===== ==== Lehká varianta ==== * Napište program **same.py**, který načte jednu řádku pole celých čísel ze standardního vstupu. * Pole na vstupu obsahuje vždy alespoň jedno číslo * Program najde v zadaném poli dvě nejdelší souvislé posloupnosti čísel, které jsou shodné, a vytiskne: **jejich délku, index prvního prvku první posloupnosti a index prvního prvku druhé posloupnosti** * Nalezené dvě shodné posloupnosti se nesmí překrývat a musí mít stejnou délku * Indexy prvních prvků počítáme jako indexy v zadaném poli od 0 * Posloupnosti jsou shodné, když x-tý prvek první posloupnosti se rovná x-tému prvku druhé posloupnosti pro všechna x od prvního prvku až do posledního prvku posloupností * Tedy posloupnost ''3 1 2 4 1 2 4 5'' obsahuje dvakrát posloupnost ''1 2 4'' od pozice 1 a od pozice 4. * Výstupem programu je délka nalezené shodné posloupnosti, index prvního prvku první posloupnosti a index prvního prvku druhé posloupnosti * index prvního prvku první posloupnosti musí být menší než index prvního prvku druhé posloupnosti * délka je počet prvků posloupnosti * můžete předpokládat, že v poli je jenom jedna dvojice nejdelších shodných posloupností * posloupnost může mít i jen jeden prvek * vždy existuje alespoň dvojice dvou shodných čísel, tedy dvě posloupnosti o jednom čísle * Program v souboru **same.py** odevzdejte pomocí odevzdávacího systému (úloha HW04). * Příklad: Vstup programu je: 1 2 3 3 3 3 3 3 3 3 5 6 Výstup programu bude: 4 2 6 protože program obsahuje dvě nepřekrývající se posloupnosti délky 4 ''3 3 3 3'' od indexu 2 a od indexu 6 Vstup programu je: 1 2 3 4 1 2 3 4 Výstup programu bude: 4 0 4 Vstup programu je: 1 2 3 4 5 6 5 7 8 9 Výstup programu bude: 1 4 6 ==== Těžká varianta ==== * Napište program **compose.py**, který načte řetězec cifer na první řádce a celé číslo N na řádce druhé. Program vloží znaky +, * mezi zadané cifry tak, aby hodnota vytvořeného výrazu byla N * Vstup: * první řádka řetězec cifer 0-9 * druhá řádka celé kladné číslo * Testované úlohy mohou mít více řešení, v tom případě vytiskněte jedno libovolné řešení, nebo úloha nemá žádné řešení a pak vytiskněte: NO_SOLUTION * **POZOR:** Program může být výpočetně náročnější, otestujte si nejdříve Váš program na počítači a pouze důkladně otestovaný program nahrávejte do odevzdávacího systému * Nezapomeňte, že násobení má větší prioritu než sčítání * Celé dva body získají jen programy, které pracují chytřeji než zkoušení všech možností * Jedna možnost zrychlit program je, pokud při vyhodnocování překročí hodnota sčítanců cílovou hodnotu, tak již není potřeba testovat zbytek výrazu a umisťovat tam znaménka výpočtu. **Hodnocení** (2b) Program umí řešit malé problémy s maximálně 9 ciframi **[1.2b]** Vstup: 876504 21 Výstup: 8+7+6+5*0*4 Vstup: 98706543 34 Výstup: 9+8+7*0*6+5+4*3 Vstup: 98706543 103 Výstup (jedna z následujících řádek): 9+87+0*65+4+3 9+87+0*6*5+4+3 Program **navíc** umí rychle řešit i dlouhé vstupy s až 16 ciframi v čase do 1s **[0.8b]** Vstup: 223344556677889 96 Výstup: 2+2*3+3*4+4*5+5+6+6+7+7+8+8+9 Vstup: 1122334455667788 78 Výstup (jedna z následujících řádek): 1+1+2+2*3+3*4+4+5+5+6+6+7+7+8+8 1*1*2+2+3+3+4*4+5+5+6+6+7+7+8+8 1*1*2*2+3+3+4*4+5+5+6+6+7+7+8+8 Vstup: 1122334455667788 60 Výstup: NO_SOLUTION Všechny nuly na vstupu ponechte i na výstupu: Vstup: 1042 43 Výstup (jedna z vícero možností): 1+042