Informatika2-2012/Gyakorlat12

A MathWikiből
(Változatok közti eltérés)
(Új oldal, tartalma: „=== 12. gyakorlat === # '''Bemelegítő feladatok''' #* Írjuk ki a következő két ''Beatty-sorozat'' első 12 tagjának sorozatát: a <math>\phi=\frac{\sqrt5+1}{2…”)
 
 
20. sor: 20. sor:
 
#* 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!
 
#* 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'''
 
# '''SUDOKU'''
−
#* Írjunk programot, mely minden SUDOKU-feladványt megold.
+
#* Í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 számot oda beírja, és ezt addig folytatja, míg van ilyen mező a táblán.
+
#* Í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:
 
Néhány feladvány:
66. sor: 66. sor:
 
  .......13
 
  .......13
 
  ..531.4..
 
  ..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

A lap jelenlegi, 2012. május 11., 11:01-kori változata

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. 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
A lap eredeti címe: „http://wiki.math.bme.hu/index.php?title=Informatika2-2012/Gyakorlat12&oldid=7481”
Személyes eszközök