Programozási feladatok

[Kovács Dávid ( Davs )]

Hy!

A Pascal háromszögeset nem tudtam megoldani. Arra gondoltam, hogy együtt megoldhatnánk. Tehát nem áruljátok el a megfejtést, csak segítsetek, vezessetek rá. Ugyanez kellene a permutációs eremit-féle feladathoz is.

[atzs]

:!: Aki önállóan meg akarja csinálni a Pascal-háromszöget, az ezt ne olvassa el. :!:

 

Az egyik lehetõség:

Az n. sor nem más, mint az (n 0), (n 1), ... (n n) binomiális együtthatók. (Egymás alá kellene persze írni a számokat a zárójelben.)

 

(n k)=n!/(k!*(n-k)!) ahol n!=n*(n-1)*(n-2)*...

 

Az n! (olvasd: n faktoriális) kiszámítása egy sima for ciklus, n darab szorzással. Igaz, ami igaz, ez a leggazdaságtalanabb megoldás, mert ha kicsit gondolkodsz, akkor rájössz, hogy magát a binomiális együtthatót kevesebb mûvelettel is ki lehet számolni. Ötletképpen a helyesen kitöltött lehetséges lottószelvények száma (90 5)=(90*89*88*87*86)/(5*4*3*2*1)

 

Másik lehetõség:

0. sor 1

1. sor 1 1

2. sor 1 2 1

3. sor 1 3 3 1

4. sor 1 4 6 4 1

 

Ha a 0., 1. vagy 2. sort kérik: kiíratod, és kész, egyébként lefoglalsz két tömböt. Az elsõbe beírod a 2. sort, utána végig 0-kat.

A másodikba kiszámolod a következõ sort (ez már nem lesz nehéz). Ha ezt kerested, akkor kiírod. Ha nem, akkor átmásolod az elsõ tömbbe, és a másodikba a fenti módszerrel kiszámolod a következõ sort.

[csutomi]

Egy-két észrevétel a Pascal háromszöghöz:

Ha valaki nagyon profinak érzi már magát, akkor ne hozzon létre elõre tömböket, hanem az egyes sorok kiszámítása elõtt foglalja le dinamikusan a szükséges memóriát, ezzel kímélheti a gépe erõforrásait. Ha kész, akkor pedig szabadítsa fel az így lefoglalt területeket.

 

A másik, hogy észre vehetõ, hogy az elsõ tag mindig egy, a következõket pedig úgy kell kiszámolni, hogy a fölötte levõ + a fölötte levõ elõtti szám. A sor végén, ha nincs fölötte levõ szám, akkor az nulla, tehát például:

negyedik sor negyedik elem (4) = 3 + 1

harmadik sor utolsó elem (1) = 0 + 1

negyedik sor harmadik elem (6) = 3 + 3

Ez szerintem jóval gyorsabb, mint a binomiális.

[Gereby]

Dobok egy kis feladatot:

Van egy 10 tagú tömb, amit for ciklusok segítségével föltöltünk az elsõ 10db pozitív páros számmal (tehát 0,2,4...,18). Aztán kiíratjuk. Ez marha egyszerûnek tûnt máma proggyakon, igaz mikor a végén megmutatta a tanár a megoldást akkor tényleg egyszerû volt, nekem alig sikerült, aztmondta a tanár miután bemutattam neki, hogy neki így az életben eszébe nem jutott volna így megcsinálni... De jó lett, és egyedül az osztályban én tudtam megcsinálni, szóval mindenki egyest kapott rajtam kívül...

 

Van egy másik feladat is:

Van egy 2dimenziós 3*3-as tömb. Amit ciklusokkal föltöltünk a következõ képpen:

1 2 3

4 5 6

7 8 9

 

Aztán az 159-et vesszük tengelynek, és a melelttük lévõ számokat tükrözzük. Tehát ennek kell majd lennie:

1 4 7

2 5 8

3 6 9

[arpsoft]

Mondjuk C-ben:

void main(void)
{
 int iTomb[3][3];
 int x,y;
// akkor töltsük fel a tömböt
 for(x=0;x<3;x++)
   for(y=0;y<3;y++)
     iTomb[x][y]=x+3*y;
// feltöltve, akár ki is írhatjuk 
 for(y=0;y<3;y++)
   printf("%d %d %d\n",iTomb[0][y],iTomb[1][y],iTomb[2][y]);
// akkor cserélgessünk
 for (x=0;x<3;x++)
   for(y=0;y<x;y++)
   {
      int i; // egy segédváltozó
      i=iTomb[x][y];
      iTomb[x][y]=iTomb[y][x];
      iTomb[y][x]=i;
   }
// kész is van, most írjuk ki
 printf("\n"); // egy üres sor, csak az elválasztás kedvéért
 for(y=0;y<3;y++)
   printf("%d %d %d\n",iTomb[0][y],iTomb[1][y],iTomb[2][y]);
// meg is volnánk
}

Azt kell észrevenni, hogy a tükrözés nem más, mint az x és y indexek felcserélése.

[Calyd]

A feladat tulajdonképpen egy mátrix transzponálásaként fogható fel [meg a tömb is szerintem könnyen fogható fel, ha mátrixként gondolunk rá, akár egy akár kétdimenziós].

 

Sajnos C-hez még nem értek, és nem látom arpsoft megoldásában a következõt: a fõátlóbeli elemekhez hozzá sem kell nyúlni, Tehát csak akkor kell cserélni, ha a sor és az oszlopindex különbözõ [ha benne van, nem szóltam ]. Még egy apróság: észrevehetõ, hogy ha pl soronként haladunk, akkor elég a sorindex+1-tõl cserélni, mert az elõtte levõket már korábban kicseréltük [így, ha jól gondoltam végig, akkor az utolsó sorban nem is mozgunk majd ].

[arpsoft]

A gond az volt, hogy elég késõ volt már, ezért a cserélgetõs rutint elrontottam egy kicsit. A második for-ban az y csak x-ig megy, különben visszaáll az eredeti táblázatunk.

Így már egyébként a fõátlóhoz sem nyúl hozzá.

[Kovács Dávid ( Davs )]

atzs

Bocsi, de egy kukkot se értek abból, amit mondasz

Egyébként közben sikerült magam megoldanom:

CPP

EXE

 

Szóval ez megvan, most jöhet a permutáció. Inkább ezt magyarázzátok meg!

 

 

Gereby:

A tömbfeltöltõs ilyen?

#include <iostream>

void main()

{

int tomb[10] ;

for(int i=0; i<10; i++)

{

tomb=(i+1) + (i+1) ;

}

}

 

Vagy ha nullával kell kezdeni, akkor ez helyett:

tomb=(i+1) + (i+1) ;

 

ez kell:

tomb=i + i ;

[Gereby]

Talán egyszerûbb lenne így: i*2

Egyébként így van. (Mondjuk én másképp csináltam.)

Ha deklarálsz egy tömböt 10 elemûnek(vagy akárhánynak) , mindíg 0-val van jelölve az elsõ hely. Tehát: 0,1,2,...9

[Calyd]

Miért olyan jó, ha 0-tól indexelõdik egy tömb? C-ben úgy tudom így van, meg Delphiben is elég sok helyen [pl dinamikus tömb]. És biztos, hogy ennek van is értelme, de mi?

[eremit]

Azzal lehet kapcsolatban, hogy pl. 4 biten összesen 16 különbözõ szám adható meg. 0-tól 15-ig. 0000, 0001, 0010, 0011, . . . 1111

[csutomi]

Miért olyan jó, ha 0-tól indexelõdik egy tömb?

A tömb C-ben nem más, mint egy mutató. Ez azt jelenti, hogy ha te lefoglalsz valamennyi helyet egy tömbnek, akkor a tömböd (mutatóként) arra a helyre fog mutatni, ahol az elsõ elemed lesz. Viszont, ha a következõ elemet szeretnéd megkapni, akkor csak hozzá kell adnod a mutatódhoz egyet, hogy az a következõ címre mutasson. Ezzel a második elemet éred el, vagyis: második elem helye = tomb + 1. Ha az értékét is meg szeretnéd tudni, akkor *-ot kell elé rakni így: *(tomb+1), erre C-ben bevezettek egy egyszerû jelölést, ami nem más, mint: tomb[1]. Tehát az elsõ elemet (mármint az értéket) így kapod meg: tomb[0].

 

ui: A C nyelvnek egyébként szerintem nagyon jó logikája van, amit többek között ez is mutat .

[arpsoft]

Majdnem. A tömb a C-ben egy egybefüggõen lefoglalt memóriaterület, aminek mérete a tömb elemeinek száma szorozva a tömb elemeinek egyenkénti helyigényével, amit az elemek típusa határoz meg.

Ebbõl következik, hogy a C-ben egy tömb elemei csak ugyanabból a típusból származhatnak. Ez viszont nem jelenti azt, hogy az elemek által mindig ugyanannyi adatot lehet elérni, mivel az elemek lehetnek mutatók is, ezek pedig már akármekkora adatmennyiséget meg tudnak címezni.

 

A tömb neve maga egy mutató a tömb elsõ elemére.

De ezt nem célszerû eltologatni, mivel akkor nem biztos, hogy majd fel is tudjuk szabadítani a tömb által foglalt memóriát (ha elmentjük és visszaállítjuk az egy másik kérdés), ezért inkább indexeket használunk a tömb elemeinek elérésére.

 

Dettó ugyan ez vonatkozik a struktúrákra is, csak itt indexek halyett adattagok vannak. A struktúra is egy egybefüggõen lefoglalt memóriaterület, aminek tagjait egyenként elérhetjük. A struktúra neve magában használva pedig a struktúra által lefoglalt memóriaterület elsõ bájtjára mutató mutató.

[Machado]

1, Írjunk programot, ami a bemenetre adott szöveget úgy másolja át a kimenetre, hogy közben az egy vagy több szóközbõl álló karaktersorozatokat egyetlen szóközzel helyettesíti!

 

2, Írjunk programot, ami a bemenetére adott szöveg minden szavát új sorba írja ki!

 

Ha lehet, akkor C-ben oldjátok meg

[arpsoft]

void main(void)
{
 char c='a',cLast='a';
 do while(c=getch())!=EOF)
 {
    if(cLast!=' ' || (cLast==' ' && c!=' '))
    {
       putchar( c);
    }
    cLast=c;
 }
}

void main(void)
{
 char c='a';
 do while(c=getch())!=EOF)
 {
    if(c!=' ')
    {
       putchar( c);
    }
    else
    {
       putchar('\n');
    }
 }
}

[Calyd]

Ebbõl következik, hogy a C-ben egy tömb elemei csak ugyanabból a típusból származhatnak.

Van olyan nyelv, ahol nem?

[arpsoft]

Pl: Visual Foxpro

dimension a(3)
a(1)="alma"
a(2)=4
a(3)=date()

Gond nélkül...

[Calyd]

Ez érdekes, és mi az értelme? Bár biztos van Valami, de én most nem látom

[arpsoft]

A FoxPro-ban nincsenek struktúrák. Ezzel lehet pótoni ezt a hiányosságot.

[Kovács Dávid ( Davs )]

Valakinek valami ötlete permutációra?

[Calyd]

Mi kéne pontosan? Nem találtam meg a feladatot...

[marthazoli]

Valakinek valami ötlete permutációra?

No...

 

Ismétlés nélküli permutáció: {minden elem pontosan 1-szer szerepel}

 

n ismétlés nélküli permutációinak száma= n! {faktoriális}

Ez így néz ki Turbo Pascalban:

 

readln(szam);

segedvaltozo:=szam-1;

repeat

szam:=szam*segedvaltozo;

segedvaltozo:=segedvaltozo-1;

until segedvaltozo>=1;

Tehát: A program kéri a azoknak az elemeknek a számát, amelyeket sorba szeretnénk rendezni (kb. erre való a permutáció, pontosabban, hogy megtudjuk, hány féle módon lehet õket sorbarendezni ) majd kiszámolja a szám faktoriálisát.

 

Ismétléses permutáció: {n elemû sorozat, melyben egy elem többször is szerepelhet}

 

n elem ismétléses permutációinak száma= n^n (N az N-edik hatványon)

[eremit]

@marthazoli

 

Nem egészen stimmel, amit írtál.

 

n elem ismétléses permutációinak a számához tudni kell, hogy hányszoros ismétlõdések fordulnak elõ. Adott n elem, amik közül k1, k2, ..., ki db ugyanaz, ahol a k1+k2+ ... +ki összeg nagyobb 1-nél és nem nagyobb n-nél. i a legalább duplán szereplõ elemek száma. A permutációk számának kiszámítása: P=n!/(k1!*k2!* ... *ki!).

 

Pl. az xxxxyyvzzz betûsornál n=10, i=3, k1=4, k2=2, k3=3. P=10!/(4!*2!*3!)=12600

[ocsi]

És szerintem arra is nagyon vigyázni, kell hogy ne legyen túlcsordulás... mert egy ilyen permutáció, vagy hatványozós érték igen hamar átlépheti egy INT sõt akár egy LONG kereteit is...

[marthazoli]

@marthazoli

 

Nem egészen stimmel, amit írtál.

 

Tényleg! Ezt elfelejtettem, sorry. Elvesztettem az matekórai jegyzetemet.

 

A túlcsordulás tényleg probléma.

 

Akkor legyen a "szam" integer típusú mutató. Annak annyi helyet foglalhatunk le, amennyit akarunk.