Matematické Fórum
Nevíte-li si rady s jakýmkoliv matematickým problémem, toto místo je pro vás jako dělané.
Nástěnka
❗22. 8. 2021 (L) Přecházíme zpět na doménu forum.matweb.cz!
❗04.11.2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
❗23.10.2013 (Jel.) Zkuste před zadáním dotazu použít některý z online-nástrojů, konzultovat použití můžete v sekci CAS.
Nejste přihlášen(a). Přihlásit
#1 06. 07. 2017 08:46
Výber podmnožiny z množiny čísel
Majme 8 čísel zapísaných v binárnej forme:
1) 0000 0001 => 1 dekadicky
2) 0000 0010 => 2 dekadicky
3) 0000 0100 => 4
4) 0000 1000 => 8
5) 0001 0000 => 16
6) 0010 0000 => 32
7) 0100 0000 => 64
8) 1000 0000 => 128
Binárnym zápisom 1001 1100 => 156 dekadicky, vyberieme čísla 3,4,5,8 zo zoznamu. Teda jednoducho pozrieme ktoré bity sú nastavené a podľa toho vieme ktoré čísla zo zoznamu tam spadajú. Avšak na vygenerovanie 8 čísel sme spotrebovali 8 bitov, teda 1 bajt.
Moja otázka znie, či by sa tento problém výberu podmnožiny z množiny čísel nedal riešiť ešte inak, ideálne s menšou dĺžkou prvkov samotnej množiny.
Ďakujem.
Offline
#2 08. 07. 2017 08:09
Re: Výber podmnožiny z množiny čísel
Mozna te chapu spatne, ale nedava mi tvoje otazka smysl. 1bit je minimalni velikost do ktere muzes cokoliv ulozit. Navic na kazde cislo ze seznamu si spotreboval 8bitu a na vsechny dohromady 8bytu.
Teoreticky nemusis zadne cislo (do mnoziny) ukladat - muzes si napr :
1) testovane cislo mas ulozene jako x
2) udelat smycku pro i od 8 do 1
3) v kazdem cyklu otestujes jestli x > 2^(i-1)
3a) pokud ne, tak nic
3b) pokud ano, tak i-ty prvek mnoziny (kterou si sice ani nevytvarel, ale vis, ze 2^(i-1) by bylo i-ty prvek mnoziny) je jedno z tebou hledanych cisel; zaroven udelas x=x-2^(i-1)
4) na konci smycky by melo byt x=0 a mel bys mit vytisteno z ceho se sklada
Offline