Algorytmy i złożoność

[stean]

Witam prosiłbym o rozwiązanie 3 zadań. Z góry dziękuje

zad.1 Poniższy algorytm wyznacza q,r \(\displaystyle{ \in}\) N takie, że y=qz + r oraz r < z, gdzie y,z \(\displaystyle{ \in}\) N

Dziel(y,z)
1. r \(\displaystyle{ \leftarrow}\)y
2. q \(\displaystyle{ \leftarrow}\) 0
3. w\(\displaystyle{ \leftarrow}\) z
4. while w\(\displaystyle{ \le}\)y
5. __do w\(\displaystyle{ \leftarrow}\) 2w
6. while w > z
7. __do q \(\displaystyle{ \leftarrow}\) 2q
8. ____ w\(\displaystyle{ \leftarrow}\) [w/2]
9. ____ if w\(\displaystyle{ \le}\) r
10._______then r \(\displaystyle{ \leftarrow}\) r - w
11.___________q \(\displaystyle{ \leftarrow}\) q + 1
12. return (q,r)

ile razy zostanie odejmowanie ( w wierszu 10) w przypadku pesymistycznym ?

zad.2 Poniższy algorytm wyznacza \(\displaystyle{ y^{z}}\), gdzie y \(\displaystyle{ \in}\) R, z\(\displaystyle{ /in}\) N

Potega (y,z)
1. x\(\displaystyle{ \leftarrow}\) 1
2. while z > 0
3._____ do if odd(z)
4._________then x \(\displaystyle{ \leftarrow}\) x * y
5.________z \(\displaystyle{ \leftarrow}\) [z/2]
6.________y\(\displaystyle{ \leftarrow}\) \(\displaystyle{ y^{2}}\)
7. return x

Okresl ile razy zostanie wykonanie mnożenie( instrukcja w wierszu 4) w przypadku pesymistycznyym

zad.3 Poniższy algorytm wyznacza yz , gdzie y,z \(\displaystyle{ \in}\) N

Mnoz(y,z)
1. if z = 0
2.___then return 0
3.___else if odd(z)
4._______then return Mnoz(2*y,[z/2]) + y
5._______else return Mnoz(2*y,[z/2])

Jaka jest zlozonosc obliczeniowa?

[abc666]

Drobna uwaga. Następnym razem korzystaj ze znaczników

Kod: Zaznacz cały

.

[stean]

następnym razem użyje code ale chyba tam latex nie działa ?

btw czy naprawdę nikt nie pomoże z tymi zadankami ?