Úlohy na procvičení

Úlohy na procvičení algoritmů teorie čísel (2. a 3. přednáška).

Úlohy se seznamem čísel

Je dán seznam čísel.

  1. Zjistěte, jestli jsou všechna čísla navzájem různá.

  2. Vypište všechna opakující se čísla (ale každé jen jednou).

  3. Najděte dvojici s co nejmenším rozdílem.

Jaká je časová složitost vašich řešení (vzhledem k počtu čísel \(N\))?

Umíte předchozí úkoly vyřešit efektivněji, pokud víte, ze všechna zadaná čísla leží v předem daném rozsahu \(0\) až \(R\) (např. \(0\) až \(100\))? Jaká pak bude časová složitost vašeho řešení vzhledem k \(N\) a \(R\)?

Číselné soustavy

Zobecněte funkce bin_int a int_bin z přednášky (můžete využít moji implementaci, kde se jmenují from_base2 a to_base2) tak, aby prováděly konverzi z a do libovolné číselné soustavy o základu \(b\), kde \(2 \le b \le 16\). Pro \(b > 10\) chybějící cifry reprezentujte písmeny A, B, …, F.

Až to budete mít, můžete váš kód využít pro řešení úlohy Soustavy.

Rychlejší Eratosthenovo síto

Vylepšete implementaci algoritmu Eratosthenova síta tak, aby seznam is_prime neevidoval sudá čísla.

Funkčnost řešení si můžete ověřit na úloze Eratosthenovo síto. Kdyby vás zajímalo časové srovnání, moje původní řešení běželo na testu 3 v ReCodExu 45 % časového limitu (134 ms), vylepšené pak 35 % časového limitu (105 ms).