Informatika2-2012/Gyakorlat12

12. gyakorlat

1. Bemelegítő feladatok
   • Írjuk ki a következő két Beatty-sorozat első 12 tagjának sorozatát: a $\phi=\frac{\sqrt5+1}{2}$ jelöléssel $a_n=\lfloor n\phi\rfloor$, illetve $a_n=\lfloor n\phi^2\rfloor$.
   • Keressük meg az összes olyan Pitagorászi számhármast, ahol a három szám összege 1000.
   • Írjuk ki a barátságos számpárok listáját 10000-ig.
2. Nest
   • Írjunk egy Nest nevű függvényt, mely a Nest(f, x, n) hívásra visszaadja az f(f(f(...f(x)...))) értéket, ahol f n-szer szerepel.
   • Keressünk numerikus megoldást a cos(x)=x egyenletre!
   • Írjunk egy NestList nevű függvényt, mely a NestList(f, x, n) hívásra visszaadja az [x, f(x), f(f(x)), ..., f(f(f(...f(x)...)))] listát.
   • Tudjuk, hogy az [1,1,1,....] végtelen lánctört értéke az aranymetszés arányát adó $\phi=\frac{\sqrt5+1}{2}$. Számítsuk ki a lánctört első néhány szeletének értékét!
3. Fold
   • Írjunk Fold nevű programot, mely a Fold(f, x, [a, b, c, d]) hívásra az f(f(f(f(x,a),b),c),d) értéket adja vissza.
   • Számoljuk ki a Horner-módszerrel az x^3+2x^2+3x+4 polinom értékét a -2 helyen!
4. Generátorfüggvény, bejáró
   • Írjunk programot a Collatz-problémára (más néven 3x+1), és írjuk meg annak generátorfüggvényes változatát (ami a next hívására a következő számot adja)!
   • Programozzuk be azt az újraírási rendszert, mely a 0 -> 01, 1 -> 0 helyettesítéseket végzi a 0-ból indulva. Vegyük észre, hogy a 0-k és 1-ek sorszámai a Beatty-sorozat elemei.
   • Olyan karakterláncot keresünk, amely egy n-elemű ábécéből készült, maximális hosszú, és nincs benne két egymást követő azonos részlánc. Be van bizonyítva, hogy 2-elemű ábécé esetén e maximum 3, 3-elemű ábécé esetén viszont van ilyen végtelen hosszú sorozat is, melyet a A -> ABC, B -> AC, C -> B helyettesítésekkel megkaphatunk az 'A' karakterláncból indulva. Írjunk e karakterláncot adó generátort!
5. SUDOKU
   • Írjunk programot, mely minden SUDOKU-feladványt megold.
   • Írjunk olyan SUDOKU-feladványt megoldó programot, mely csak azt az egyetlen technikát alkalmazza, hogy ha egy mező oszlopában, sorában és blokkjában egyet kivéve minden szám előfordul, akkor azt a számot oda beírja, és ezt addig folytatja, míg van ilyen mező a táblán.

Néhány feladvány:

5.2...8.6
...548...
7..3.2..4
.25.9.41.
.7.1.5.8.
.91.8.65.
2..8.6..9
...754...
4.3...7.5

.56...81.
2.1...6.5
43..5..97
...543...
..38.61..
...219...
31..6..79
5.9...4.8
.64...32.

És néhány, ami csak a második technikával nem oldható meg:

51.3.4.72
2..5.9..1
....2....
64.....89
..2...1..
39.....65
....4....
9..2.6..7
45.8.7.23

..2.3...8
.....8...
.31.2....
.6..5.27.
.1.....5.
2.4.6..31
....8.6.5
.......13
..531.4..