Nemes Tihamér OKSzTV 2002

Első forduló

I. kategória, 5-8. osztályosok

2001. november 13.

1. feladat: Válogatós (26 pont)


2. feladat: Kockapóker (30 pont)
3. feladat: Címletezés (29 pont)
Egy pénztárban hatféle bankjegyet (címletet) kezelnek.  Az alábbi címletező algoritmus, szándékunk szerint, meghatározza, hogy a P összeg hogyan fizethető ki a lehető legkevesebb bankjeggyel. Az eredményt a DB vektor tartalmazza. Minden címletből korlátlan mennyiség használható fel.
 
Címletezés(P,C,DB):
  K:=6; DB:=(0,0,0,0,0,0)
  Ciklus amíg P>0
    Ciklus amíg P>=C(K)
      DB(K):=DB(K)+1; P:=P-C(K)
    Ciklus vége
    K:=K-1
  Ciklus vége
Eljárás vége.

Ez az algoritmus például a C=(1,2,5,10,20,50) címletkészlet és 96 forint kifizetése esetén a DB=(1,0,1,0,2,1) vektort állítja elő.

Legyenek a címletkészletek a következők:

 i) C=(1,3,6,10,60,100)
ii) C=(1,4,6,10,40,60)
iii) C=(1,2,5,12,60,120)
iv) C=(1,5,7,21,35,49)

A. Mi lesz a DB vektor értéke 73 forint kifizetésekor a négy címletkészlet esetén?
B. A négy címletkészlet közül melyeknél címletez hibásan az algoritmus (azaz nem a lehető legkevesebb bankjegyet használja fel)?
C. Minden hibás eredményhez vezető címletkészletre add meg azt a legkisebb P összeget, amelynek a kifizetésére az algoritmus nem a lehető legkevesebb bankjegyet használja fel! Add meg az algoritmus által előállított hibás, valamint a helyes DB vektort is!


4. feladat: Piramis (15 pont)

Elérhető összpontszám: 100 pont