Ocislovani bitu – Pascal – Fórum – Programujte.com
 x   TIP: Přetáhni ikonu na hlavní panel pro připnutí webu
Reklama
Reklama

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

 

Hledá se programátor! Plat 1 800 € + bonusy (firma Boxmol.com)
drobas0
Newbie
9. 11. 2008   #1
-
0
-

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???

Nahlásit jako SPAM
IP: 62.77.118.–
Reklama
Reklama
o-lox0
Super člen
10. 11. 2008   #2
-
0
-

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á.

Nahlásit jako SPAM
IP: 85.71.152.–
o-lox0
Super člen
11. 11. 2008   #3
-
0
-

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.

Nahlásit jako SPAM
IP: 85.71.152.–
o-lox0
Super člen
12. 11. 2008   #4
-
0
-

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

Nahlásit jako SPAM
IP: 85.71.152.–
KIIV+42
God of flame
13. 11. 2008   #5
-
0
-

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

Nahlásit jako SPAM
IP: 80.250.27.–
Program vždy dělá to co naprogramujete, ne to co chcete...
o-lox0
Super člen
13. 11. 2008   #6
-
0
-

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

Nahlásit jako SPAM
IP: 85.71.152.–
KIIV+42
God of flame
13. 11. 2008   #7
-
0
-

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

Nahlásit jako SPAM
IP: 80.188.94.–
Program vždy dělá to co naprogramujete, ne to co chcete...
o-lox0
Super člen
13. 11. 2008   #8
-
0
-

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ě :)

Nahlásit jako SPAM
IP: 85.71.152.–
KIIV+42
God of flame
13. 11. 2008   #9
-
0
-

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

Nahlásit jako SPAM
IP: 80.188.94.–
Program vždy dělá to co naprogramujete, ne to co chcete...
o-lox0
Super člen
13. 11. 2008   #10
-
0
-

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

Nahlásit jako SPAM
IP: 85.71.152.–
KIIV+42
God of flame
13. 11. 2008   #11
-
0
-

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

Nahlásit jako SPAM
IP: 80.188.94.–
Program vždy dělá to co naprogramujete, ne to co chcete...
KIIV+42
God of flame
13. 11. 2008   #12
-
0
-

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

Nahlásit jako SPAM
IP: 80.250.27.–
Program vždy dělá to co naprogramujete, ne to co chcete...
o-lox0
Super člen
13. 11. 2008   #13
-
0
-

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

Nahlásit jako SPAM
IP: 85.71.152.–
KIIV+42
God of flame
13. 11. 2008   #14
-
0
-

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

Nahlásit jako SPAM
IP: 80.250.27.–
Program vždy dělá to co naprogramujete, ne to co chcete...
o-lox0
Super člen
13. 11. 2008   #15
-
0
-

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

Nahlásit jako SPAM
IP: 85.71.152.–
KIIV+42
God of flame
13. 11. 2008   #16
-
0
-

co to? :D

Nahlásit jako SPAM
IP: 80.250.27.–
Program vždy dělá to co naprogramujete, ne to co chcete...
drobas0
Newbie
14. 11. 2008   #17
-
0
-

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 :-)...

Nahlásit jako SPAM
IP: 195.113.69.–
o-lox0
Super člen
14. 11. 2008   #18
-
0
-

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 :)

Nahlásit jako SPAM
IP: 85.71.152.–
KIIV+42
God of flame
14. 11. 2008   #19
-
0
-

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;
}


ted uz je to snad spravne :D

Nahlásit jako SPAM
IP: 80.188.94.–
Program vždy dělá to co naprogramujete, ne to co chcete...
o-lox0
Super člen
14. 11. 2008   #20
-
0
-

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)

Nahlásit jako SPAM
IP: 85.71.152.–
KIIV+42
God of flame
14. 11. 2008   #21
-
0
-

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

Nahlásit jako SPAM
IP: 80.188.94.–
Program vždy dělá to co naprogramujete, ne to co chcete...
o-lox0
Super člen
14. 11. 2008   #22
-
0
-

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

Nahlásit jako SPAM
IP: 85.71.152.–
Zjistit počet nových příspěvků

Přidej příspěvek

Toto téma je starší jak čtvrt roku – přidej svůj příspěvek jen tehdy, máš-li k tématu opravdu co říct!

Ano, opravdu chci reagovat → zobrazí formulář pro přidání příspěvku

×Vložení zdrojáku

×Vložení obrázku

Vložit URL obrázku Vybrat obrázek na disku
Vlož URL adresu obrázku:
Klikni a vyber obrázek z počítače:

×Vložení videa

Aktuálně jsou podporována videa ze serverů YouTube, Vimeo a Dailymotion.
×
 
Podporujeme Gravatara.
Zadej URL adresu Avatara (40 x 40 px) nebo emailovou adresu pro použití Gravatara.
Email nikam neukládáme, po získání Gravatara je zahozen.
-
Pravidla pro psaní příspěvků, používej diakritiku. ENTER pro nový odstavec, SHIFT + ENTER pro nový řádek.
Sledovat nové příspěvky (pouze pro přihlášené)
Sleduj vlákno a v případě přidání nového příspěvku o tom budeš vědět mezi prvními.
Reaguješ na příspěvek:

Uživatelé prohlížející si toto vlákno

Uživatelé on-line: 0 registrovaných, 20 hostů

Podobná vlákna

Testování bitu. — založil zbynek

Změna bitu — založil Huge

NASM - výměna bitů — založil Thomasso

Datový typ - 256 bitů — založil Hlavinka

Moderátoři diskuze

 

Hostujeme u Českého hostingu       ISSN 1801-1586       ⇡ Nahoru Webtea.cz logo © 20032016 Programujte.com
Zasadilo a pěstuje Webtea.cz, šéfredaktor Lukáš Churý