Ocislovani bitu – Pascal – Fórum – Programujte.com

zdravim,
Uvažujme takové posloupnosti N bitů (bit může být nula nebo jedna), které mají nanejvýš L jedniček. Všechny takové posloupnosti si můžeme setřídit podle slovníkového uspořádání. Vaším cílem je napsat program, který vrátí I-tou takovou posloupnost počítáno podle slovníkového uspořádání od nejmenší.

Popis vstupu: na první řádce standardního vstupu jsou tři mezerou oddělená čísla 1 mensi/rovno N mensi/rovno 31, 1 mensi/rovno L mensi/rovno N, 1 mensi/rovno I mensi/rovno počet N-bitových posloupností s nejvýš L jedničkami.

Popis výstupu: na standardní výstup vypište I-tou posloupnost N bitů, která má nejvýš L jedničkových bitů.

standardní vstup standardní výstup
5 3 19 10011

...pro tento priklad me nenapada zadny pekny efektivni a lehky reseni...kdyz to budu postupne zvysovat to cislo az do toho ktere chci (budu vynechavat ty co maj spatny pocet jednicek) tak proste pro cisla nad 1 000 000 je to docela hoooodne pomaly ---potrebuju to az do miliardy....

da se to delat i pres kombinatoriku, ale do toho bych se radsi nepoustel, pac ladit takovy reseni by mi zabralo mrte casu :-)))

nenapada nekoho peknej postup jak to delat???

Nikdo tu žádný fígl nenapsal, tak proč nevyužít tu kombinatoriku.
Jedeš zleva a Setuješ 1ku na Nbitu, zjistíš jestli počet kombinací
Suma N-1 pro X (od 0 do L-1) převyšuje I-tý prvek. Pokud ano bit N bude 0 a
nastavíš N-1 bit. Máš počet kombinací (tj. jen funkce házící výsledek) pro
N-2 pro X a dejme tomu podmínka zjistí, že už je menší (jako základ pro
danou skupinu vezmeš k následujícím počtům ale výsledek kombinace N-1 pro X (od 0 do L!!))
tak hurá tady jedeš dolů
dosazuješ zbylé 1ky na bitu N-3 až dolů a zjišťuješ počet kombinací pro takovou množinu
Y (od N-3 do X) nad X (zas od 0 do L-již nastavený počet) dokud nedojdeš součtem k I, a ne k vyššímu.
Pak to máš už myslim vyčíslený, používáš (snad) jen 1x cykl, žádný vnoření jen Sumy a Sety.

Ladění bezproblémový, otestovat můžeš otrockou inkrementální metodou pro malá N shodnost s tímto.
Ale ona ani otrocká inkrementace neni na dnešnim CPU pomalá.

Když už jsem nad tím včera přemýšlel napsal jsem teď i ten program.
Jeden cykl 5 řádek v něm v podmínce. Pro N nad 20 použít např. COMP místo longintu.
Ten můj předchozí popis je si řikám krapet nesrozumitelný.
Musel bych to ještě upravovat, nebere mi to N nad 21 ale je tam u takovýchto hodnot
patrná prodleva u testování nekombinatorickou metodou u DOSovýho pascalu.

Uživatelé nemáte chuť na malou soutěž? Nevim co bych nabídl za cenu.
Dám jednomu z prvních dvou Zdroják své hry v Pascalu co si vybere.
Alternativně symbolické kilčo bezhotovostním převodem :)
Ať zužitkuju svůj hotový program k ještě většímu mrhání...

Chci dva co sem hodí:
správné vyčíslení prvku pro toto zadání
N=37 L=14 I=5000000000 (5e9 !)

(podškrábněte se sem a pošlete mi mail se zaručeně správnou odpovědí)

Kritérium výběru z oněch 2? pokud budou samozřejmě, tak
rozhodne na nytimes.com délka 1. slova sudá-2 lichá-1
(u nadpisu 1.článku vlevo nahoře, v 18:00 14.11., má rafinovanost nezná mezí, takže musí být 2, a 1 z vás musí být registrovaný s počtem 10p. a více - kvůli neférovosti možného double:)
zadavatel si vyhrazuje právo jednat vždy fairplay, ale nic není právně vymahatelné :D

To o-lox : predpokladam ze to nebude neco jako:
1000000000001001000010010010010000

To KIIV : Jo musel by ses víc snažit, ale ona mnou nadefinovaná motivace není z těch nejsilnějších magnetů, co si budem povídat :D

To o-lox : no holt testnu brutal force :D ale to bude na dlouho

To KIIV : Účast vítána , moje mašina mi říkala cosi o 266 minutách, ale
to jsem neoptimalizoval, assembler v tomto případě výhodou :) o kombinatorice nemluvě :)

To o-lox : no zvladalo mi to tak milion cisel za sekundu... mozna trochu mene
nekdy rychleji nekdy pomaleji .. sneslo by to nekolik optimalizaci :D
skoncil sem nekde u cisla
0110000 10011 10001 00001 11011 10000 00101

ehm druhej algoritmus skoncil driv :)
00 11010 01011 11000 10110 00010 00000 00011

To KIIV : Jak skončil, to si se do toho obul s plným nasazením :D a všemi prostředky, všemi jádry :D a přesně v půlce (jak tak koukám 1 horní bit by to chtělo) šel na oběd a uklízečka zavadila o přepínač , já tomu nerozumí :D

To o-lox : no me to v noci zlikvidovala automaticka aktualizace... bych ty adminy uz podrezal.. hned sem je zase pekne zakazal :D

krom toho ze sem tu mel otevrenejch 10 terminalu 50stranek ... etc.
doufam ze sem nemel neco v textaku neulozene na odeslani :D

tak sem udelal mensi optimalizaci ... ted to zmakne cca 1miliardu moznosti za cca 6 - 7 minut

To KIIV : ..vejt A ho abych tě nevzal v 19:00 za slovo !!!

no jo jenze mi to vyslo zase jinak :D
00 11010 01011 11000 10110 00010 00000 00011

To já když je po 18:00 a šéf jde dom hupsnu za jeho cray a to je jízda ... :D

co to? :D

tak mam tady to puvodni reseni az to 2^31 - 1 (chtel sem to jen pro longint) ale podle naseho kompilatoru na skole to splnuje 70% spravnosti (3 testy dopadly Wrong Answer), takze kdyby to nekdo chtel testovat a najit odlisny (nepravny) cisla tak to uvitam :-D...problem je jak zjistit ze cislo je spravne, ten prvni postup, ktery projizdi kazde cislo, je celkem spolehlivy, ale tak max do 10^6 potom uz to tuhne :-)...

to KIIV: snažil jsem se sladit adekvátnost a relevanci ...

to drobas: nechápu tě, udělal jsi to Kombinatorikou ? Jak může být výsledek špatně, když jednou vyjde dobře tak matematika neni CIRKUS, přeci :)

pro ilustraci muj kod :D

#include <cstdlib>

#include <iostream>



using namespace std;



inline unsigned char cnt( unsigned char x ) {

  return  ((128&x)>0) +((64&x)>0) +((32&x)>0) +((16&x)>0) +((8&x)>0) +((4&x)>0) +((2&x)>0) +((1&x)>0);

}



int main(int argc, char *argv[]) {

   unsigned long long i = 0; // aktualni cislo

   unsigned long long p = 0; // predchozi cislo 

   unsigned long long s = 0; // pocty bitu

   

   unsigned long long counter = 0; 



   unsigned char *  bi = (unsigned char * ) &i;

   unsigned char *  bp = (unsigned char * ) &p;

   unsigned char *  bs = (unsigned char * ) &s; 



   int x = 0;

   

   for ( i=0; counter<5000000000LL; i++ ) {

     char z, suma=0;

 

     for ( z = 0 ; z < 8 ; z++ ) {

       if ( bi[z] != bp[z] ) {

         bp[z] = bi[z];    

         bs[z] = cnt(bi[z]);

       }

       suma += bs[z];  

       if ( suma > 14 ) break;                 

     }   

     if ( suma <= 14 ) {

       counter++;

     } 

      





      // zobrazeni prubezneho stavu 

      if ( (short int)(i) == 0 ) 

       if ( ((x++)%100)== 0 ) cout << counter << " " << i << endl;



     

   }

   cout << endl << counter << " " << i << endl;

   system("PAUSE");

   return EXIT_SUCCESS;

}

Já nemůžu :)
-1 jsme v jazyce PasQé?
-2 představ si že by Pause na konci nezafungovala..

Máš našlápnuto, nechce se mi to do detailu studovat a připravovat se
tak o majetek, ale myslim, že si nepřesně pochopil souvislost mezi
I-tým prvkem a binární soustavou jinak bys nekončil 5e9.
Jinak vych*a*á optimalizace jen co je pravda :D (jen tak by někoho nenapadla - bez ironie)

To o-lox : ha sem tam mel mensi upravu kdy sem zjistoval jestli to pocita spravne... jeste sem to zeditoval aby to bylo tak jak melo :D samo kontrolovat to jen do 5 miliard bych skoncil rychle a jeste nenasel to co hledam :)


system("pause") ; kdyby se nespustil - coz by hrozilo mozna na linuxu tak furt to tak jak tak spoustim z command line :D

To KIIV : zapal doutník a odpal výpočet, já balim kufry do Emirátů :D