Informatika2-2012/Gyakorlat12
A MathWikiből
A lap korábbi változatát látod, amilyen Wettl (vitalap | szerkesztései) 2012. május 11., 11:01-kor történt szerkesztése után volt.
12. gyakorlat
- Bemelegítő feladatok
- Írjuk ki a következő két Beatty-sorozat első 12 tagjának sorozatát: a jelöléssel , illetve .
- 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.
- 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ó . Számítsuk ki a lánctört első néhány szeletének értékét!
- 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!
- 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!
- SUDOKU
- Írjunk programot, mely minden SUDOKU-feladványt megold. A program inputja egy fájlban legyen megadva, ahol 9 sorban 9-hosszú karakterláncok szerepeljenek az alábbi minták szerint. Az output a megoldás legyen, vagyis 9 sorban 9-hosszú karakterláncok, melyekben csak az 1-től 9-ig terjedő számok szerepelhetnek.
- Í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 hiányzó 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..
Azoknak, akik nem tudják mi a SUDOKU: A játék alapja egy 9x9=81 mezőből álló négyzet, mely 9 db 3x3-as blokkra van osztva. Induláskor a feladványban a 81 mező némelyike ki van töltve a 1-től 9-ig terjedő számok valamelyikével. A feladat az, hogy töltsük ki a tábla minden mezőjét úgy, hogy minden sorban, minden oszlopban és minden blokkban az 1, 2, 3, 4, 5, 6, 7, 8, 9 számok mindegyike szerepeljen. Az előre megadott számok nem változtathatók meg. (Egy SUDOKU-feladvány akkor korrekt, ha annak pontosan egy megoldása létezik)
A fenti első feladat megoldása például:
542971836 936548271 718362594 825693417 674125983 391487652 257836149 169754328 483219765
Ugyanez a blokkokat is mutató áttekinthető kiírásban:
5 4 2 9 7 1 8 3 6 9 3 6 5 4 8 2 7 1 7 1 8 3 6 2 5 9 4 8 2 5 6 9 3 4 1 7 6 7 4 1 2 5 9 8 3 3 9 1 4 8 7 6 5 2 2 5 7 8 3 6 1 4 9 1 6 9 7 5 4 3 2 8 4 8 3 2 1 9 7 6 5