Cvičení 4: 1D pole

• 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.

• 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.

• 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é)!

• 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é)!

• 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$

• 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

• 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.

• Napište funkci, která pro zadaný polynom najde maximum/minimum v zadaném intervalu $<a,b>$. Ř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$

• 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

• 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.