Segítségre lenne szükségem: az alábbi programok közül kellene BÁRMELYIKET megírni C programnyelven. Aki tud kérem segítsen, nagyon fontos lenne. Elõre köszönöm!
Összegzések, rendezések
1. Az input egy olyan fájl, melynek minden sorában egy-egy név, és maximum
öt szám áll. A pista 5 7 4 2 8 sor jelentése a következõ: pista
programja 8 hét, 2 nap, 4 óra, 7 perc és 5 másodpercet futott. Összegezze
személyek szerint a programhasználatot!
2. Adott egy fájl a vegyesbolt hiteleivel, amelyben soronként két bejegyzés
jelzi az igénylõt, és a hitel összegét (ami törlesztés esetén negatív). Csökkenõ
érték szerint listázza ki a hitelek összegét személy szerinti lebontásban.
3. Adott egy fájl, melynek minden sorában egy-egy tört szerepel, n/m form
ában (0 _ n,m _ 1000). Adja össze sorra ezeket a számokat és a
részösszegeket meg a végeredményt is a lehetõ legegyszerûbb alakban írja
ki!
4. A k inputra írja ki a n
m számokat n/m formában, növekvõ sorrendben, ahol
0 _ n,m _ k és n < m. Ha több szám egyenlõ, akkor közülük a legkisebb
nevezõjét írja ki! A programban csak egész számokat használjon!
5. Adott igen nagy számok listája (soronként egy-egy szám, és egy szám
kisebb, mint 1050). Adja meg a számok összegét!
6. Számítsa ki pontosan az 1·2·... ·n szorzatot, ahol n paraméter és ötvennél
nagyobb.
7. Az euklidészi algoritmust használva adja meg két nagyon nagy szám legnagyob
közös osztóját! (m, n > 1050. Javaslat: addig helyettesítsük a
nagyobb vagy egyenlõ számot a különbségükkel, míg nullát nem kapunk
eredményül! Ekkor a másik szám lesz a keresett.)
8. Egy szövegfájlból olvassa be a számokat, amelyeket egy kétirányú láncolt
listában helyezzen el. Balról a monoton növekvõ, jobbról a monoton
csökkenõ sorozatokat fésülje össze egy ugyanekkora méretû hasonló
listába, ahol balra monoton növekvõ, jobbra monoton csökkenõ sorozatokat
írjon! Ismételje ezt az eljárást mindaddig, amig rendezi az egész
listát!
- _ - _ . . .
. . . - _
9. Az input fájl egy normál szövegfájl, csak szavakat tartalmaz Készítsen
egy fát, melynek csúcsaiban betûk szerepelnek és amelyben az input minden
szavának a fa egy ága vagy ágrészlete felel meg. Minden betû mellett
tárolja a szó elõfordulásanak a számát is! A fa tárolására használjon
bináris fát, ahol az egyik él a _legidõsebb gyerek_, a másik él a _sorban
következõ testvér_ felé mutat. A fa elkészítése után írja ki a szavakat
gyakoriságukkal együtt.
1
10. A szövegfájl sorait rendezze úgy, hogy elõre a legkevesebb szót tartalmazó
sorok kerüljenek! Az azonos szószámú sorok között az lexikogra_kus sorrend
a döntõ.
11. Adottak dátumokat tartalmazó sorok, például 1999. januar 12. Rendezze
értelemszerûen a dátumokat!
12. Adottak két dátumot (mindkettõ hó és nap) tartalmazó sorok. Rendezze
a sorokat az két dátum közti idõtartam alapján csökkenõ sorrendben.
Permutációk
Az 1, 2, ..., n elemek permutációjának hívjuk az i1, i2, ..., in sorozatot, ha
{1, 2, ..., n} = {i1, i2, ..., in}. A 346251 sorozatot így is felfoghatjuk, hogy az 1
helyébe 3-t, a 2 helyébe 4-t, ..., a 6 helyébe 1-t kell írni. Az elõbbieket más
sorrendben felírva úgy is mondhatjuk, hogy az egy helyébe hármat, a három
helyébe hatot, a hat helyébe egyet kell írni (egy ciklus); a kettõ helyébe négyet,
a négy helyébe kettõt kell írni (másik ciklus), az ötös pedig helyben marad.
Két permutáció egymás utáni végrehajtása (a két permutáció szorzata) újra
permutációt ad. Ha az elõbbi 346251 permutációt megszorozzuk a 243165 permut
ációval, akkor például a kettõ helyébe elõször négyet, majd a másik permut
áció miatt a négy helyébe egyet kell írni. Az összes értéken végigjátszva
ezt a 315462 permutációhoz jutunk. Egy permutációban futamnak nevezzük az
egymást követõ számok monoton növekvõ sorozatát. Az alábbi feladatokban az
input fájl soronként ugyanazon elemek egy-egy permutációját tartalmazza.
1. Adja meg az egymást követõ sorokban levõ permutációk szorzatát!
2. Bontsa fel a permutációt ciklusok szorzatára.
3. Az egymást követõ sorokban levõ permutációkat bontsa ciklusokra, majd
számítsa ki a ciklusok szorzatát.
4. Határozza meg a permutáció inverzét, azaz azt a permutációt, amellyel
megszorozva a kérdéses permutációt, a számok növekvõ sorozatát kapjuk!
5. Bontsa a permutációt futamokra!
6. Határozza meg a leghosszabb futamot!
7. A permutáció jelölje egy lexikon köteteinek az elhelyezkedését a könyvespolcon.
Legkevesebb lépésben (egy könyv elvétele a könyvespolcról, majd
visszahelyezése valahova) állítsa vissza a hagyományos elrendezést!
8. A permutáció konténerek elhelyezkedését jelenti. Legkevesebb lépésben
(két konténer kicserélése) állítsa növekvõ sorrendbe a konténereket!
2
Táblázatok
1. Az input fájl minden sora azonos darab számot tartalmaz. Tartalmaz-e ez
a táblázat nyeregelemet, azaz olyant, amely a saját sorában a legnagyobb,
viszont oszlopában a legkisebb? Ha igen, akkor a táblázatnak csak ezt a
sorát és oszlopát írassa ki!
2. Töltsön fel egy 2n+1×2n+1 tömböt! (Induljon meg az elsõ sor középsõ
mezõjébõl, és haladjon folyamatosan balra fel! Ha kilépne az egyik oldalon,
jöjjön vissza a szemköztin! (n paraméter
3. Töltsön fel egy m× n-es tömböt cikkcakkban. Azaz az egyik soron balra,
a következõn jobbra haladjon. (Vagy az egyik oszlopban fel, a másikban
le.)
4. Töltsön fel egy m × n-es tömböt csigavonalban. (m és n paraméter.)
5. Az input sakktáblapozíciók sorozatát tartalmazza (e2 g1 h3. . . ). Döntse
el, hogy lépkedhet-e egy huszár ilyen sorrendben a táblán!
6. Az input sakktáblapozíciók sorozatát tartalmazza. Döntse el, minden
megadott pozíción egy huszár áll, hányan vannak ütésben!
7. Az input sakktáblapozíciók sorozatát tartalmazza.
8. Az input fájl n2 db 0 vagy 1 számjegyet tartalmaz. Ezekkel töltsön fel
egy n × n-es mátrixot, majd a sorok, illetve oszlopok cseréjével alakítsá
át a mátrixot úgy, hogy téglalapokra felbontva a mátrixot az 1-eket is
tartalmazó téglapok mérete minimális legyen!
Pontpárok, topológia, gráfok
Az itt következõ feladatok mindegyike egy olyan fájlból veszi az adatait, amelynek
minden sora két számot tartalmaz.
1. Legyenek ezek a számok egy konvex sokszög csúcsainak a koordinátái.
Irassa ki az átlókat csúcspontjaik koordinátáival.
2. A számpárok n darab síkbeli pont koordinátái. A pontok távolságát
értelmezzük a hagyományos módon: di,j = p(xi − xj)2 + (yi − yj)2, azaz
a koordináták különbségének négyzetösszegébõl vont négyzetgyökkel. Irassa
ki a pontok minimális hosszúságú kifeszítõ fáját!
3. A számpárokban szereplõ számokat írja fel úgy, hogy a számpárok elsõ
elemei sorrendben a megfelelõ hátsó elemek elõtt szerepeljenek a sorban.
Azaz írjon fel a megadott parciális rendezésnek megfelelõ teljes rendezést!
4. A számpár a gráf egy élét alkotó csúcspár azonosítója. Irassa ki a gráf
komponenseit.
3
5. A számok egy nem irányított, összefüggõ gráf csúcsait jelentik, így a számp
árok ennek a gráfnak az éleit. Adjon meg a fában egy szabad fát, azaz
összefüggõ, körmentes részgráfot.
6. A számok egy irányított gráf éleit jelentik. Minden egyes él súlya 1. Milyen
messze vannak a gráf csúcsai az 1-el jelölt csúcstól, és milyen messze van
az 1-el jelölt csúcs a gráf csúcsaitól?
7. Az elõbbi pontpárok egy szabad fa (irányítatlan, összefüggõ és körmentes
gráf) éleit jelölik. Határozza meg a gráf közepét (amely a legkisebb súlyú
csúcsa)! Egy csúcs súlya megegyezik a gráfból ennek a csúcsnak elhagyásá-
val kapott részgráfok fokszámának maximumával. (Ez a súlyfogalom nem
esik egybe az elõzõ feladat súlyfogalmával!)
Aritmetikai kifejezések
Az alábbi feladatok inputja egy olyan szövegfájl, amelynek minden sora egy-egy
pre_x formában felírt aritmetikai kifejezést tartalmaz. (Mveletek az +, * és
a -.) Az inputban bármely két szomszédos szám legalább egy szóközzel van
elválasztva, és csak egész számok szerepelnek benne.
1. Az inputot írja át in_x alakba, kirakva minden zárójelet!
2. In_x alakba átalakítás során csak a mindenképpen szükséges zárójeleket
tegye ki!
3. Számítsa ki a kifejezés értékét!
4. Egy kifejezés bonyolultságán a neki megfelelõ kiszámítási fa magasságát,
azaz a leghosszabb ágát értjük. Ekvivalens átalakításokkal _x + y =