Fa -kérdés

Algoritmusok

Sziasztok!

Az lenne a kérdésem h itt találhattok 1 pdf formátumú feladatot melyben nem bírok rájönni a fa felépítési algoritmusára! Probáltam több megoldást alkalmazni! de arra nem tudtam rájönni h mi alapján épül fel a fa! A lényeg az lenne h magamtól fel tudjam építeni a fát! Amit az Útmutatóban adtak azt értem az alapján a belső pontokat meg tudom határozni (pl. "jobb részfályának minimuma kerül a pontba" nem pontos az idézés sry ezért).

A feladatnak felező algoritmussal álltam neki! A gond csupán annyi volt h a párosaknál a számra amire Eva gondolt NEM-t dobott! Így arra gondoltam a számot "mod 2 " vel megdolgoztatom és ha 0 akkor a maradék két szám MAXIMUMát veszem! ellenkező esetben adja magát! ÁM pl az n=100 és a szám amire gondoltak 99 akkor az algoritmus nem fog jól működni! A felezéseknéál lefelé kerekítettem!

Ettől jobb algoritmus sajnos nem jutott eszembe! Minden ötletet szivesen fogadnék! :)

Előre is thx a válaszokért!
Zsolt

  • 1881 megtekintés

hali!

Thx a tippet végig olvasom! bár ahogyan csak így gyorsan végig futottam tettek bele csavart mrt nem azt kérdezik mint nekem de elolvasom! Bár inkább magam szeretnék írni rá progit nem pedig ctrl+c majd ctrl+v -s megoldást! Ezért szeretném megérteni h hogyan is működik illetve 1 kis rávezetést h talán mi lehetne a jo vagy a felezővel mit kellene csinálni h jobb legyen!

De mondom elolvasom a topicot! Thx!
Zsolt

-------------
2.6.17.8 Debian testing

( imp | 2006. 11. 02., cs – 22:28 )

n<=2^k, különben nem megoldható a feladat
tehát ha n<=2^k, akkor veszed a pascal-háromszög k-adik sorát (a 'csúcsa' a 0. sor, tehát
0: 1
1: 1 1
2: 1 2 1
3: 1 3 3 1
)
tehát ha k==3, akkor:
h=0 jobbralépéssel legfeljebb 1,
h=1 jobbralépéssel legfeljebb 1+3
h=2 jobbralépéssel legfeljebb 1+3+3,
h=3 jobbralépéssel legfeljebb 1+3+3+1
szám található ki.

(szerk.: bocs, hogy csak a megoldást írtam le, ha akarod, leírom, hogyan jutottam idáig:])

( gsimon | 2006. 11. 02., cs – 22:39 )

offtopic: "...részfályának..." -> részfájának! Ilyet sem láttam az általános iskola harmadik osztálya óta, már megbocsáss!

Elnézést kérek a durva helyesírási hibáért de tegnap este próbáltam ezt összedobni + meg kell csinálnom a munkámat szval picit lehet h túl vállaltam magam és ezen okból kifolyólag szét vagyok csúszva... :( sajnalom és sry!

Zsolt

-------------
2.6.17.8 Debian testing

( agosta | 2006. 11. 02., cs – 23:34 )

Ha azt keresed, hány levél fér egy n magas max. h jobbra élet tartalmazó fában, a problémát két részre tudod osztani: a fa egy n-1 magas, h-1 jobbra élet tartalmazó jobb részfából, és egy n-1 magas, h jobbraélet tartalmazó bal részfából áll. Azt tudjuk, hogy egy 1 magas fában (akármennyi h-val) max. 2 levél lehet. Azt is tudjuk, hogy 1 jobbraélet tartalmazó fában magasság+1 leveled lehet. Táblázatban:
10
9 2 4
8 2 4
7 2 4
6 2 4
5 2 4 8
4 2 4 8
3 2 4 8 15
2 2 4 7 11 16 22
1 2 3 4 5 6 7 8 9 10 11
/ 1 2 3 4 5 6 7 8 9 10 <- magasság
^
h
(Nyilván pont a főátlóban lesznek a 2 hatványok.)
bármelyik ([i][j]) belső pont [i-1][j-1]+[i-1][j] összegként megkapható. Így ha azt keresed, hogy mi az a legkisebb szám, ami nem kisebb n-nél adott h esetén, egyszerűen megkapod a magasságot.
u.i.: nekem is ez volt a köt.prog.-om.

Lehet hogy én értem félre a kérdezőt(csak átfutottam a belinkelt pdfet), de ott mintha a bináris fa magassága és a leveleinek száma lenne adott, és az a kérdés, hogy létezik-e ilyen fa(ugye n>2^k-ra, és n<=k-ra nem), és ha létezik, akkor minimalizáld a benne lévő jobbra élek számát.

( jcsaba | 2006. 11. 03., p – 08:00 )

A feladatot kicsit kicsavarva, konstans 1 nem válasszal számolhatsz. :-)
A kérdések: Ugye, igaz, hogy nem az 1-re gondoltál? :-)

Csaba

( saddam | 2006. 11. 05., v – 10:27 )

És a megoldás mely még csak sajnos 16ból 11-pontos (szval még csak beta :) ) de meg kiindulásnak jó ha vki hasonló problémával küzd! :)

#include

int main(){

int i,j,a[101][101],k,n,value,l,tomb[101],min;

FILE *fbe, *fki;

fbe=fopen("be.txt","rt");

fscanf(fbe,"%d %d",&n,&k);

fclose(fbe);

int hatvany(int a, int b)
{
if (b == 0)
{
return 1;
} else {
value = a;
for (i = 1; i < b; i++ )
{
value = value * a;
}

return value;
}
}

for (i=0;i<100;i++)
{

a[0][i]=1;

a[i][0]=1;

}

fki=fopen("ki.txt","wt");
l=0;
min=101;

if((n <= k) && (n > hatvany(2,k)))
{
min=-1;
}
else
{
for (i=1;i<=k;i++){

for (j=1;j<=k;j++){

a[i][j]=a[i-1][j]+a[i-1][j-1];
if(a[i][j] >= n)
{
tomb[l] = j;
l++;
}

}
}
}

for(i=0;i
{
if(tomb[i] < min) min = tomb[i];
}

fprintf(fki,"%d",min);

fclose(fki);

return 0;

}

Zsolt

-------------
2.6.17.8 Debian testing

Hello! Köszönöm jól! :) max 16ból 13 pont lett.
Próbáltam javítgatni és mivel max 10* lehet beküldeni a és 9ig próbálkoztam a javítással de nem ment :( pl 200000000 6 -nál rosszat számol ki :( ! Szval utsóra azért beküldtem a 13 pontosat! :)

Még1* köszönöm a segítségeteket!
Zsolt

-------------
2.6.17.8 Debian testing