Matematické Fórum

3.14.TR · 19. 10. 2012 20:30

zdravim,
mám takový problém:

Code:

a + b = m
a xor b = n

a,b jsou přirozené neznámé, m,n jsou přirozené parametry, xor je binární operace exlusive or
jdou tyto rovnice vůbec jednoznačně vyřešit?

zkusil jsem:

Code:

(m - b) xor b = n

ale zdá se, že xor neni zrovna distributivní přes sčítání/odčítání

tudy cesta asi nevede, ale možná by to šlo jinak...?
Díky za pomoc

Brano · 19. 10. 2012 20:55 — Editoval Brano (19. 10. 2012 20:58)

ako funguje to xor? je to myslene binarne? aky typ maju premenne ... char? maju povolene pretecenie?

teda aby som specifikoval otazku s xor. Ak a, b su ulozene v jednom bajte tak to robis po bitoch?
a ta otazka na typ je hlavne o tom v kolkych bajtoch su ulozene premenne.

3.14.TR · 19. 10. 2012 21:03

Brano napsal(a):
ako funguje to xor? je to myslene binarne? aky typ maju premenne ... char? maju povolene pretecenie?

teda aby som specifikoval otazku s xor. Ak a, b su ulozene v jednom bajte tak to robis po bitoch?
a ta otazka na typ je hlavne o tom v kolkych bajtoch su ulozene premenne.

xor myslím zhruba takto http://cs.wikipedia.org/wiki/Hradlo_XOR
proměnné musí být celočíselné, jinak velikost je libovolná, můžeš použít libovolně velkou, a to s povolením přetečení nebo bez

Brano · 19. 10. 2012 21:37

↑ 3.14.TR:

To nie je to co som myslel. $a\ xor\ b$ je standardne definovane ak $a,b\in\{0,1\}$ . Ty ocividne predpokladas aj vacsie a,b. Ak napr a je ulozene v 1 bajte, tak sa jedna o vektor osmich nul alebo jednotiek a xor urobis po zlozkach takze to som chcel vediet, ci sa to robi po zlozkach. Niekedy sa totiz xor na prirodzenych cislach mysli tak, ze pri vstupe 0 povazuje za 0 a vsetko ostatne za 1.

Dalsia otazka bola ze v akej grupe to vlastne ideme riesit, bud je to $Z$ vsetky cele cisla, alebo $Z_{2^k}$ zvyskove triedy. Ty si mi v podstate odpovedal, ze si mozem vybrat, ale to asi nie je to co si myslel.

A k poznamke ze to nie je distributivne - no iste, napr. v $Z_2$ (kde nieje pochybnost s interpretaciou) je xor a + to iste, tak sa lahko vidi, ze to nie je.

3.14.TR · 19. 10. 2012 21:43

↑ Brano:
myslím tím programátorské xor, tzn každé číslo je zapsáno jako vektor nul a jedniček, jeho velikost je libovolná, ale předpokládejme klidně 4B int - xor se vyhodnocuje po složkách, tedy po bitech

číslo je přirozené

mně jde hlavně o to, jestli to jde nějak udělat jinak, protože ta distributivita nefunguje :-/
díky za pomoc

Brano · 19. 10. 2012 22:16 — Editoval Brano (19. 10. 2012 22:18)

Ok tak, uz sme si ujasnili zadanie. Smola, ze nejaky rozumny vztah medzi xor a + co by sa dal vyuzit ma nenapada :-( Tak aspon par postrehov

1. riesenie vo vseobecnost nemusi existovat, lebo ak $a\ xor\ b=0$ tak $a=b$ a potom $a+b$ nemoze byt neparne.
2. ak ta nezaujima nejake elegantne riesenie na papieri, tak ho mozes hladat jednoduchym cyklom od 0 po m/2.
3. este sa ten cyklus da vylepsit, ale aby to malo cenu, tak by n muselo byt dostatocne male oproti m - neviem ci ta to zaujma, tak zatial vynecham detaily.
4. ak je ten priklad v ramci nejakeho konkretneho predmetu - nehovorili ste o nejakom vztahu medzi + a xor? aj zdanlivo nevinna vec by mohla pomoct :-)
5. mozno niekto iny bude mat lepsi vhlad - asi som sa do toho nemal hned vkladat, len ma to zaujalo :-)

3.14.TR · 19. 10. 2012 22:21

↑ Brano:
díky moc, postřehy jsou super... jedná se o jednu úlohu, kterou jsem zjednodušil na toto, a chtěl jsem vědět jestli to vůbec má smysl, vidím že nemá... cyklem bych si zhoršil časovou složitost.

díky moc ;)

Brano · 19. 10. 2012 22:53

Skus pripadne napisat tu povodnu ulohu. Ten cyklus by sa myslim dal vyspekulovat aby bol zavisly na n - len neviem ci to pomoze.

3.14.TR · 19. 10. 2012 23:01

↑ Brano:
jde o to v lineárnim čase najít 2 chybějící čísla v nesetříděné posloupnosti N čísel (víme že všechna jsou 1..N+2)
je tu ale omezení na paměť - konstatní počet proměnných a do proměnné se vejde velikost max 2N, tzn držet si součin nebo součet kvadr členů neprojde

chtěl bych si na to přijít sám, proto jsem se původně ptal jenom na výsledné zjednodušení
každopádně díky moc za předchozí rady :))

Brano · 20. 10. 2012 01:14 — Editoval Brano (20. 10. 2012 01:31)

googlil som ako divy a uz asi viem ako si to chcel robit ... preco si myslis, ze to pokazi linearny cas, ved $m<2N+4$ a robis to iba raz, nie?

tak toto si pozri az ked to vyriesis!! (dufam, ze nevytvaram prave syndrom zakazaneho ovocia :-)

Autor skryl část textu. Zobrazit/skrýt!

Matematické Fórum

#1 19. 10. 2012 20:30

distributivita xor přes sčítání

Code:

Code:

#2 19. 10. 2012 20:55 — Editoval Brano (19. 10. 2012 20:58)

Re: distributivita xor přes sčítání

#3 19. 10. 2012 21:03

Re: distributivita xor přes sčítání

Brano napsal(a):

#4 19. 10. 2012 21:37

Re: distributivita xor přes sčítání

#5 19. 10. 2012 21:43

Re: distributivita xor přes sčítání

#6 19. 10. 2012 22:16 — Editoval Brano (19. 10. 2012 22:18)

Re: distributivita xor přes sčítání

#7 19. 10. 2012 22:21

Re: distributivita xor přes sčítání

#8 19. 10. 2012 22:53

Re: distributivita xor přes sčítání

#9 19. 10. 2012 23:01

Re: distributivita xor přes sčítání

#10 20. 10. 2012 01:14 — Editoval Brano (20. 10. 2012 01:31)

Re: distributivita xor přes sčítání

Zápatí