====== Cvičení 4: 1D pole ====== ==== 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. ==== 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) */ ==== 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é)! ==== 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é)! ===== Témata k procvičení ===== ==== 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$ ==== 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'' ==== 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. ==== Výpočet maximální (minimální) hodnoty polynomu ==== * 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 **two_same.py**, který načte dvě řádky pole celých čísel ze standardního vstupu a v nich najde nejdelší podposloupnost, která se vyskytuje v první řádce i v druhé řádce * **Vstup:** * Dvě řádky standardního vstupu, každá obsahující posloupnost celých čísel oddělených mezerou * Pole na vstupu obsahuje vždy alespoň jedno číslo, jednotlivé řádky mohou obsahovat každá jiný počet čísel * ** Úkol ** * Program najde v zadaných polích dvě nejdelší souvislé podposloupnosti čísel, které jsou shodné v první posloupnosti i v druhé posloupnosti * Podposloupnosti jsou shodné, když x-tý prvek první podposloupnosti se rovná x-tému prvku druhé podposloupnosti pro všechna x od prvního prvku až do posledního prvku podposloupností * Můžete předpokládat, že v polích je jenom jedna dvojice nejdelších shodných posloupností * Podposloupnost i posloupnost může mít i jen jeden prvek * Vždy existuje alespoň dvojice dvou shodných čísel z první a druhé posloupnosti, tedy dvě podposloupnosti o jednom čísle * ** Výstup ** * program vytiskne tři čísla: **délku** nalezených podposloupností, **index** prvního prvku v první posloupnosti a **index** prvního prvku v druhé posloupnosti * Indexy prvních prvků počítáme jako indexy v zadaných polích od 0 * Délka je počet prvků posloupnosti * Tedy posloupnosti ''3 1 2 4 5'' a ''3 4 1 2 4 4 5'' obsahují oběstejnou podposloupnost ''1 2 4'' délky 3 od pozice 1 (první posloupnost) a od pozice 2 (druhá posloupnost). * Program v souboru **two_same.py** odevzdejte pomocí odevzdávacího systému (úloha HW04). * **Příklady**: Vstup programu je: 1 2 3 3 3 3 3 3 3 3 5 6 3 3 3 1 3 3 3 3 3 3 3 3 Výstup programu bude: 8 2 4 protože program obsahuje dvě nepřekrývající se posloupnosti délky 8 ''3 3 3 3 3 3 3 3'' od indexu 2 v první řádce a od indexu 4 v druhé řádce Vstup programu je: 10 1 2 3 10 3 2 1 Výstup programu bude: 1 0 3 První posloupnost obsahuje jen jedno číslo, které je na pozici 3 v druhé posloupnosti. Vstup programu je: 1 2 3 4 1 2 3 4 Výstup programu bude: 4 0 0 Obě zadané posloupnosti o délce 4 jsou shodné, tedy nalezené podposloupnosti obsahují celou posloupnost ''1 2 3 4'' ==== Těžká varianta ==== * Napište program **max_sum.py**, který v posloupnosti čísel najde souvislé podposloupnosti, které se v posloupnosti vyskytují dvakrát. Pokud je takových dvojic podposloupností více, program nalezne tu s největším součtem. Pokud existuje vícero dvojic se shodným součtem, program vybere tu s nejdelší délkou. * **Vstup:** * jedna řádka ze standarního vstupu * řádka obsahuje posloupnost celých čísel $x_1, ... ,x_n$ oddělených mezerou * pro načtení a převedení vstupu na pole celých čísel můžete použít příkaz x = list(map(int, input().split())) * **Úkol:** * Program nalezne dvě souvislé podposloupnosti $x_{i+0}, x_{i+1}, ... ,x_{i+j}$ a $x_{k+0}, x_{k+1}, ... ,x_{k+j}$, které: * jsou shodné jak číselně tako svou délkou (tedy platí $x_{i+0} = x_{k+0}, x_{i+1} = x_{k+1}, ... , x_{i+j} = x_{k+j}$), * nepřekrývají se a * mají největší součet $x_i + x_{i+1} + ... + x_{i+j}$ ze všech podposloupností s uvedenou vlastností. * **Výstup:** * **2** čísla oddělená mezerou: **počet čísel** (délku) a **součet čísel** ve zdvojené podposloupnosti. * **Poznámky:** * Pole na vstupu obsahuje vždy alespoň dvě čísla a alespoň jednu opakující se sekvenci (minimálně tedy dvě stejná čísla). * Délka jednočíselné podposloupnosti je 1. * **Příklady:** * 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 budou čísla ''3'' (délka podposloupnosti) ''7'' (součet podposloupnosti). * Posloupnost ''3 1 2 4 1 2 4 1 5'' má stejné řešení jako předchozí posloupnost, protože podposloupnosti ''1 2 4 1'' se překrývají a nesplňují tak zadání. * **Odevzdání:** * Program v souboru **max_sum.py** odevzdejte pomocí odevzdávacího systému **BRUTE, úloha HW04**. **Více příkladů:** Vstup programu je: 3 3 3 3 3 3 3 3 3 Výstup programu bude: 4 12 protože program obsahuje dvě nepřekrývající se podposloupnosti délky 4 ''3 3 3 3'', jejíž součet je 12. Vstup programu je: 1 1 1 6 2 2 2 6 1 1 1 Výstup programu bude: 1 6 protože opakující se podposloupnost s největším součtem je posloupnost s jedním prvkem ''6''. Vstup programu je: 1 2 5 -6 8 -3 2 1 1 2 2 5 -6 8 -3 2 3 Výstup programu bude: 4 9 Přestože nejdelší stejné podposloupnosti jsou ''2 5 -6 8 -3 2'', větší součet má její část ''2 5 -6 8'' o délce 4.