Zaimplementuj funkcje:

1) diofantyczne_ma_rozwiązanie(a, b, c), sprawdzającą czy równanie diofantyczne liniowe postaci $$ ax + by = c$$ ma rozwiązanie. Przykładowe wywołanie.

diofantyczne_ma_rozwiązanie(18, 16, 500) is True

Możesz skorzystać z funkcji xgcd z materiałów po wykładzie.

2) diofantyczne_rozwiązanie(a, b, c), znajdującą dowolne rozwiązanie równania diofantycznego liniowego postaci $$ ax + by = c.$$

Jeśli rozwiązania istnieje funkcja powinna zwrócić parę liczb (x, y). Jeśli rozwiązania nie istnieje, funkcja powinna zwrócić None. Przykładowe wywołanie.

(x, y) = diofantyczne_rozwiązanie(18, 16, 500)
18*x + 16*y == 500

3) diofantyczne_nieujemne(a, b, c), znajdującą zbiór rozwiązań równania diofantycznego liniowego postaci $$ ax + by = c,$$ spełniających jednocześnie $x \geq 0$ oraz $y \geq 0$. Funkcja powinna zwracać zbiór par (x, y) spełniających podane warunki, w szczególności, jeśli nie ma rozwiązań nieujemnych lub wcale nie ma rozwiązania równania, funkcja powinna zwrócić zbiór pusty. Przykładowe wywołanie.

diofantyczne_nieujemne(18, 16, 500) == {(26, 2), (18, 11), (10, 20), (2, 29)}

Wykorzystaj funkcje z poprzednich punktów do rozwiązania następującego zadania:

Skoczek pustynny Alfred zakończył imprezę i wyszedł z baru. W tym stanie potrafi wykonywać krótkie skoki długości 84 centymetry lub długie długości 2.28 metra. Porusza się dokładnie w linii prostej, kierując się prosto do celu lub z powrotem prosto do baru (widać nie może się zdecydować).

Nasz skoczek pustynny do domu ma 430 centymetrów. Alfred ma też inną opcję - może nocować u kumpla, tłustogona afrykańskiego imieniem Horacy. Horacy mieszka 432 centymetry od baru. Czy w tym stanie Alfred może trafić do domu lub do kolegi, czy będzie musiał spać pod gołym niebem? Jeśli nocuje pod dachem, to gdzie i w ilu co najmniej skokach tam trafi?

Napisz funkcje:

1) Newton_rekurencja(n, k) wyznaczającą rekurencyjnie $\binom{n}{k}$ za pomocą tożsamości:

$$ \binom{n}{0} = \binom{n}{n} = 1,$$ $$ \binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}.$$

2) Newton_iteracja(n, k) wyznaczającą iteracyjnie $\binom{n}{k}$ za pomocą tożsamości:

$$ \binom{n}{0} = \binom{n}{n} = 1,$$ $$ \binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}.$$

Jeśli nie masz pomysłu jak się zabrać za implementację wersji iteracyjnej, pomyśl o trójkącie Pascala i jak stopniowo się go wypełnia. Jako trójkąt możesz wykorzystać listę list lub tablicę dwuwymiarową.

3) Newton_silnia(n, k) wyznaczającą $\binom{n}{k}$ za pomocą tożsamości:

$$\binom{n}{k} = \frac{n!}{(n-k)! k!}.$$

Możesz wykorzystać funkcję factorial z biblioteki math. Zadbaj o to, aby wynik był liczbą całkowitą, a nie liczbą zmiennoprzecinkową.

Wykonaj pomiar czasu działania trzech implementacji z powyższych podpunktów dla kilku różnych wartości parametrów. Które implementacje są najszybsze?

Władca pewnego królestwa miał $k > 0$ dzieci. Postanowił podzielić swoją ziemię pomiędzy nich tak, aby nie było kłótni i aby cała ziemia została rozdzielona. Ustalił, że ewentualny spadek koniecznie musi przyjąć najstarszy syn, natomiast każde kolejne dziecko może przyjąć lub odmówić udziału w podziale majątku. Po ustaleniu kto uczestniczy w podziale, każdy z partycypujących potomków ma otrzymać tyle samo ziemi.

Na ile części (co najmniej) król musi podzielić swoją ziemię, aby w żadnej sytuacji nie było problemów z podziałem? Wiemy, że żadne z dzieci nie może otrzymać kawałka wydzielonej części, ponieważ wypowie wojnę bratu lub siostrze, z którą miałoby go dzielić. Napisz funkcję przyjmującą $k$ jako argument i zwracającą liczbę działek.