Határidő: 2022-03-29 24:00

• Az euklideszi algoritmus segítségével két szám legnagyobb közös osztója hatékonyan meghatározható. Tudjuk, hogy ha \(a, b \in \mathbb{Z}^+\) a bemeten kettes számrendszerben van megadva, akkor a bemenet hossza \(O(\log a + \log b)\), az euklideszi algoritmus pedig \(\mathop{\mathrm{lnko}}(a, b)\) értékét legfeljebb \(O(\log a + \log b)\) lépésben meg tudja határozni.
• Az euklideszi.py fájlban megadtunk egy olyan kódrészletet, ami a matplotlib.pyplot Python csomag segítségével kirajzolja a \(\log a + \log b\) függvény hőtérképét (heat map) az \((a, b)\) koordinátasíkon, úgy, hogy \(a\) és \(b\) értéke \(1\) és \(100\) közötti egész legyen. A hőtérkép a szivárvány színeivel jelzi a számok nagyságát (az ibolyától a sárgáig).
• Módosítsuk a programot úgy, hogy bemutassa az euklideszi algoritmus futását! Jelenítsünk meg három hőtérképet, egymás mellett egy ablakban, az alábbihoz hasonlóan:

  

  A hőtérképeken az alábbi függvények legyenek láthatóak:

  1. Az első hőtérkép mutassa a \(\log_2 a + \log_2 b\) függvényt, ezt generálja a kiadott programkód.
  2. A második hőtérképen ábrázoljuk az euklideszi algoritmus lépésszámát az egyes \((a, b)\) párokon. Számoljuk meg, hány lépést tesz meg az euklideszi algoritmusban szereplő rekurzió, azaz hányszor végzünk maradékos osztást az \((a_i, b_i)\) párral, vagy döntünk a leállás mellet.
  3. Végül a harmadik hőtérkép mutassa \(\mathop{\mathrm{lnko}}(a, b)\) értékét.
• Több ábra megjelenítéséhez használható a matplotlib.pyplot csomag subplot függvénye. Ennek argumentuma egy \(nmk\) alakú háromjegyű szám, ami az ábra pozícióját határozza meg. Ennek jelentése: a rajzvásznat \(n \times m\) részre osztjuk, és a továbbiakban ezek közül a \(k\)-adik részre rajzolunk, ahol a \(k=1\) a bal felső részábra indexe. Így például a

  plt.subplot(132)
      

  hívás vízszintesen három részre osztja a vásznat, és a középső részre rajzolja a további plt hívások eredményeit.