===== Algoritmusok - bevető feladatok =====

==== 1995/9-10/1/1 ====

Egy vasúti rendező-pályaudvar egyetlen kitérőt tartalmaz, az ábrának megfelelően.

{{ :informatika:programozas:algoritmusok:nt-1995-9-1-1.png?direct&300|}}
Ha egy vonatszerelvény érkezik az 1,2,3...N sorszámú kocsikkal, akkor minden egyes lé­pésben három lehetőség közül választhatunk:

  * ÁT:	A szerelvény elején levő kocsit a kijárat felé továbbítjuk.
  * BE:	A szerelvény elején levő kocsit a kitérőbe visszük.
  * KI:	A kitérő végén álló utolsó kocsit a kijárat felé küldjük.

Állapítsd meg, hogy ha a beérkező szerelvény az 1,2,3,4 kocsikból áll, akkor lehet-e a kimenő szerelvény a következő sorrendű! Az előállíthatóknál add meg előállításuk lépéseinek sorrendjét, a többinél pedig magyarázd meg, hogy miért nem lehetséges az előállításuk!

  * A) 4,3,2,1
  * B) 4,1,2,3
  * C) 1,4,3,2
  * D) 1,4,2,3

==== 1995/9-10/1/3 ====

Egy útkereszteződésben autók áthaladására a KRESZ háromféle szabályt alkalmaz:

  - A főútvonalon haladónak mindig elsőbbsége van a mellékútvonalon haladóval szemben (két főútvonal sohasem találkozhat).
  - Egyenrangú utak esetén az azonos úton (szemben) közlekedők esetén az egyenesen haladónak elsőbbsége van a kanyarodókkal szemben.
  - Egyenrangú utak esetén a keresztező útvonalon haladók esetén annak van elsőbbsége, aki a másik jobbkeze felőli irányból érkezik.

Az autók mozgására három algoritmust írtunk. Add meg, hogy közülük melyik milyen esetben sérti meg a KRESZ előírásait, illetve van-e bennük felesleges vizsgálat!

<code>
   A. Autó1:
	Előre a kereszteződésig
	Várj amíg van autó jobbról
	Előre
   Eljárás vége.
</code>

<code>
   B. Autó2:
	Előre a kereszteződésig
	Várj amíg van autó szemből
	Balrafordulás
	Előre
   Eljárás vége.
</code>

<code>
   C. Autó3:
	Előre a kereszteződésig
	Ha a keresztező főút akkor Várj amíg van autó jobbról
	Jobbrafordulás
	Előre
   Eljárás vége.
</code>


==== 1995/9-10/1/4 ====

Egy grafikus nyelven a képernyővel a következő transzformációkat végezhetjük: 

  - Négyzet alakú rész forgatása 90 fokkal balra (''FORGAT( (x,y),(p,q) )'')
  - Téglalap alakú rész tükrözése a téglalap X-tengelyére (''XTÜKÖR( (x,y),(p,q) )'')
  - Téglalap alakú rész tükrözése a téglalap Y-tengelyére (''YTÜKÖR( (x,y),(p,q) )'')

Milyen transzformációkkal állítható elő a az alábbi négyzetből kiindulva a következő néhány állapot.
| A | B | C |
| D | E | F |
| G | H | I |

**Példa:** ''XTÜKÖR( (1,2),(2,3) )''

| A | E | F |
| D | B | C |
| G | H | I |

**A)**
| B | E | C |
| G | H | F |
| A | D | I |

**B)**
| B | A | C |
| E | F | I |
| H | D | G |

==== 2015/9-10/1/1 ====

Egy sormintában színek szerepelnek, melyeket a kezdőbetűikkel adunk meg: ''P'' – piros, ''Z'' – zöld, ''F'' – fehér, ''S'' – sárga.

A sormintát szabályok segítségével állítottuk elő, több lépésen keresztül. Ha van egy sormintát leíró karaktersorozatunk, akkor arra olyan következő sormintát előállító szabályokat alkalmazhatunk, amelyek megadják, hogy az eredeti sormintában szereplő karakterek helyére mit (vagy miket) kell írni.

Ismerjük a lépésenként előálló sorozatot, ki kell találni a hozzá tartozó szabályokat!

**Például** a kiinduló sorozat az ''PZP'', az első lépésben ebből a ''PZPZPZP'' sorozatot kapjuk, a második lépésben pedig a ''PZPZPZPZPZPZPZP''-t, akkor a két szabály: ''P'' -> ''PZP'', ''Z'' -> ''Z''.

**Magyarázat**: A kiinduló sorozat eleje és vége is ''P''. Emiatt az első lépésben keletkező sorozat elején és végén is ugyanannak kell lenni, azaz a szabály vagy a ''P'' -> ''P'', vagy a ''P'' -> ''PZP'' lehet. Az első esetben a ''Z'' -> ''ZPZPZ'' a másik szabály, a második esetben pedig a ''Z'' -> ''Z''. Ezek közül a második lépés eredménye alapján választhatunk. A második lépésben a 7 karakterből (4 ''P'' és 3 ''Z'') álló sorozatból 15 karakter lesz. Az első esetben 4+3*5=19 karakter hosszú eredményt kellene kapnunk, a másodikban pedig 4*3+3=15 hosszút, ami megfelel a második lépés végeredményének.

Add meg a szabályokat az alábbi sorozatokhoz:

  * A. ''PZP'' -> ''PZFPZF'' -> ''PZFZPZFZ''
  * B. ''PZP'' -> ''ZFSZZF'' -> ''SZPSPSZSZP''
  * C. ''PZP'' -> ''PZPSPZP'' -> ''PZPSPZPZZPZPSPZP''
  * D. ''PZ'' -> ''PPZF'' -> ''PPZPPZFZ''