Cvičení 4: 1D pole

• 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

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

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

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

4 2 6 

Vstup programu je:

1 2 3 4 1 2 3 4

4 0 4

Vstup programu je:

1 2 3 4 5 6 5 7 8 9

1 4 6

• 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