Hollosi Information eXchange /HIX/
HIX CODER 599
Copyright (C) HIX
1999-10-03
Új cikk beküldése (a cikk tartalma az író felelőssége)
Megrendelés Lemondás
1 Re: Rendezo algoritmus (#590) (mind)  75 sor     (cikkei)
2 PASCAL Windowsban (mind)  19 sor     (cikkei)
3 Sound Blaster - MIDI - Nekem IS =?UNKNOWN?Q?k=E9ne?= (mind)  19 sor     (cikkei)

+ - Re: Rendezo algoritmus (#590) (mind) VÁLASZ  Feladó: (cikkei)

On 30 Sep 99 at 12:33,  wrote:

> Olvastam par hozzaszolast, es nekem is eszembe jutott egy otlet, amit
> masok nem is javasoltak. Adva van egy lista, ami tartalmazza a szam nevet
> es idejet. Legyen ez n tagu. Ket eset van: egy szam felkerul a kazettara,
> vagy nem. Ez ugye 2^n lehetoseg. De ha egy olyan rekurziv algoritmust
> irunk, ami figyeli, hogy az eddig felvett szamok osszjatekideje tullepi-e
> a 30 percet, akkor egy "gyors", es pontos eredmenyt kapunk.

Ez egyebkent ugyanaz, mint amit en javasoltam masodjara :)
Kombinaciokat kell generalni, es a kombinacio hosszat az osszido
limitalja. Pontosabban elvileg kulonbozo a ket modszer, viszont a
limit kezelese miatt a program ugyanaz lesz.

Azt is irtam akkor, hogy kb. n!/((n/2)!^2) (vagyis n alatt_az n/2)
lepesre lesz szukseg. Ez a kombinaciokbol direktben kijon, de a Te
'binaris' algoritmusodra is igaz persze.

Viszont a ket otlet osszehasonlitasabol egy erdekes dolog kovetkezik,
ami a binomialis tetelbol persze gyorsan bizonyithato, de nem
emlekszem, hogy suliban tanultuk volna:

  Szumma(n alatt_a k) k=0..n eseten = 2^n

Nekem tetszik :))

> Pascalban: (a tsec tombot fel kell tolteni!)
 ....
 ....
>
> Lehet, hogy kihagytam valamit, de nem ellenoriztem a kodot. Lehet, hogy

Szerintem jo...

> lassu, nem tudom. De ha kicsinositod, akkor talan hasznalhato... Ha
> logikai hiba van, akkor javitsatok ki...

Logikai hiba nincs benne, de egy picit lehet javitani:
A ket rekurziv hivas kozul a masodik tail-rekurzio, helyette eleg
egy ciklus is.

Masik gyorsitasi otlet, hogy a 'tossz' fuggvenyt ketszer hivod, ha 
ujabb maximum jon ki; ezt konnyen meg lehet sporolni. Viszont kicsit 
mas szervezessel egyszer sincs ra szukseg, ha egy futo osszeget 
szamontartasz; sok osszeadast meg if-et lehet ugy megsporolni.

Ezzel a ket modositassal gyakorlatilag az en programom all elo :) Ez 
az enyem rekurziv magja: (C-ben)

// generalja a kombinaciokat, leall a kivant hossznal
void sorozat(int kezd, int eddigsec)
{
   for (int i=kezd; i<N; i++) {
      int ujhossz = eddigsec+cdsec[i];
      if (ujhossz <= 1800) {    // befer meg a kazettara
         aktsor[x++] = i;       // lerakjuk a sorozat uj tagjat
         if (ujhossz > max) {
            max = ujhossz;
            for (j=0; j<x; j++) // megjegyezzuk a sorozatot
               legjobb[j] = aktsor[j];
            legjobb_n = x;
         }
         sorozat(i+1, ujhossz); // generaljuk a folytatast
         x--;                   // felszedjuk a sorozat utolso tagjat
      }
   }
}

Nem irom ide a tobbi reszet a proginak, remelem, ertheto. Vegulis
csak a main() hianyzik, a szamok hosszinak beolvasasaval, meg az
eredmeny kiirasaval. A main-bol sorozat(0,0) hivodik. 

Istv?n
--  Istvan Marosi  --  http://www.sch.bme.hu/~marosi  --
--  Recosoft Ltd.  --  mailto:  --
+ - PASCAL Windowsban (mind) VÁLASZ  Feladó: (cikkei)

Sziasztok!

PASCAL programozasban szeretnem a segitsegeteket kerni...

Nemreg kezdtem tanulni Windowsos programokat irni PASCALban.
Eddig a peldaprogikbol, meg a HELPbol probaltam tanul(gat)ni,
de mostanaban egyre tobbszor elakadok. Probaltam a NETen
keresni valamilyen tutorialt, de nem talaltam olyat, ami
a windows-os programiras rejtelmeibe vezetne be. Tudtok
ajanlani valamilyen Budapesten kaphato tankonyvet, amelybol
tanulhatnek windows-os programirast PASCALban? (Nemcsak a
konyv szerzoje es cime, hanem a lelohelye is erdekel!)

Ezen kivul - ugyan ebben a temakorben - erdekelne tutorial
a NETrol is. (Nem baj, ha angol.) Ha tudtok ilyet, szoljatok.

Elore is koszi:
Zoli

+ - Sound Blaster - MIDI - Nekem IS =?UNKNOWN?Q?k=E9ne?= (mind) VÁLASZ  Feladó: (cikkei)

> irta :
> Sziasztok!
>
> Van egy konyvem, az Adlib, Sound Blaster, Gravis Ultrasound
> hangkartyak csaladjainak programozasarol...
> Egyetlen dolgot hianyolok, a Midi kepessegeket nem reszletezi...
> ...Ha valaki tud errol jo konyvet, vagy foleg magyar irast akar
> Interneten, vagy barmi ilyet a hangkartyak midi reszenek megszolaltatasat,
> elsosorban a Sound Blaster 16, Vibra tipusokrol, az kerem segitsen. Elore
> is koszonom.
>
> Sziasztok.
>

Ezek nekem is kellenek, aki tud ilyesmirol valamit, ide is kuldje el.

Elore is kosz.
Skolnik Zoltan


AGYKONTROLL ALLAT AUTO AZSIA BUDAPEST CODER DOSZ FELVIDEK FILM FILOZOFIA FORUM GURU HANG HIPHOP HIRDETES HIRMONDO HIXDVD HUDOM HUNGARY JATEK KEP KONYHA KONYV KORNYESZ KUKKER KULTURA LINUX MAGELLAN MAHAL MOBIL MOKA MOZAIK NARANCS NARANCS1 NY NYELV OTTHON OTTHONKA PARA RANDI REJTVENY SCM SPORT SZABAD SZALON TANC TIPP TUDOMANY UK UTAZAS UTLEVEL VITA WEBMESTER WINDOWS