Největší společný dělitel

9.3.2005 20:57 | Linux | poslední úprava: 11.3.2005 08:41

Tak jsem se mrknul co dovede dc. Fakt užitečná hračička. Tak třeba jak udělat program pro nalezení největšího společného dělitele. Brnkačka:

dc -e '[r]sb[szpq]sc[sadlarla>b~d0=cldx]sd??ldx'

No já vím, že jsem cvok, ale tahle věcička se mi fakt líbí. tac v sedu

sed 'x;1!H;$!d;x'

už není tak c00l, už vím co chci mít v podpisu teď.

Updated: Takže to mám blbě a až budu mít čas tak to zkusím přepsat.

Updated2: Po obědě se makat nechce, tak konečně fungující verze.

dc -e '[rSadLar%d0<a]sa??laxsap'

A to s použitím jediného registru. Pro ty co vyžadují GUI tu mám vylepšenou verzi

dc -e '[rSadLar%d0<a]sa[a=]P?[b=]P?laxsa[result:]Pp'

Updated3: Zkrácení o jeden znak a ochrana před poškozením od uživatele.

dc -e '??[rSadLar%d0<a]dsaxsap'
dc -e '[a=]P?[b=]P?[rSadLar%d0<a]dsaxsa[result:]Pp'

Updated4: Nějak nemám den nebo co. Ještě kratší verze.

dc -e '??[dSarLa%d0<a]dsaxsap'
dc -e '[a=]P?[b=]P?[dSarLa%d0<a]dsaxsa[result:]Pp'

Updated5: A ještě jeden znak.

dc -e '??[dSarLa%d0<a]dsax+p'
dc -e '[a=]P?[b=]P?[dSarLa%d0<a]dsax+[result:]Pp'

       

Komentáře

[Michal Marek (twofish)]

The Brainfuck Programming Language

Jedna implementace pro x86 vypadá takhle:

0000000: 7f45 4c46 83c6 eead a5a4 a48d 710e 933d  .ELF........q..=
0000010: 0200 0300 89fd eb3c 95b0 e945 2c00 0000  .......<...E,...
0000020: a591 5929 cf97 ab92 eb1a 2000 0100 0000  ..Y)...... .....
0000030: 0000 0000 00b0 e945 55ab ebce ab00 0000  .......EU.......
0000040: 3095 0000 b301 b004 cd80 6140 cd80 4149  0.........a@..AI
0000050: fe01 fe09 b003 31db cd80 09c0 7ec2 ad8b  ......1.....~...
0000060: 013c 3e74 a546 3c3c 74a0 462c 2b74 9a48  .<>t.F<<t.F,+t.H
0000070: 7495 4646 4874 9248 748a 3c2d 74b7 3c2f  t.FFHt.Ht.<-t.</
0000080: 7589 b83a 310f 85ab 8d77 f858 29c6 8930  u..:1....w.X)..0
0000090: 29f8 abeb eb31 c031 dbb9 00d0 e945 9942  )....1.1.....E.B
00000a0: 60b5 b051 b13c 8d79 65eb d5              `..Q.<.ye..

[Marek Bernát]

co takto:
echo 1
a ten vas skript mi ako vystup dava:
floor(max(a,b)/min(a,b))

btw, na rozdiel od vas som prilis lenivy na precitanie manu dc, tak sa nehnevajte, ze nerozumiem vasmu skriptu

[Michal Marek (twofish)]

Nj, já jsem to taky nějak nepochopil. Ale tohle mi funguje:

dc -e '[lxly%lylbx]sa [sxsylxly*0<a]sb [a = ]P? [b = ]P? lbx lxly+[result: ]f'

Nechal jsem tam i mezery abych usnadnil reverse-engineering

[Michal Marek (twofish)]

Vylepšná verze (bere prázdný vstup jako nulu)

dc -e '[lxly%lylbx]sa [sxsylxly*0<a]sb 0 0 [a = ]P? [b = ]P? lbx lxly+[result: ]Pp'

[Zdeněk Burda]

Panové, evidentně se nudíte. Co kdybysme vám našli nějakou práci?

[Michal Marek (twofish)]

Nj, ale jak má dneska programátor v dc sehnat práci? Všude je to samá infixní notace :(

[Hynek (Pichi) Vychodil]

No vždyť je to úplně jednoduché.

• sadlarla duplikuje horní dvě hodnoty na zásobníku (ty mi zlikviduje následující porovnání)
• >b jestliže je horní číslo větší než dolní, je pořeba je prohodit r
• ~ dělení a zbytek po dělení
• d0=c duplikuj zbytek po dělení a porovnej jestli je nula, pokud je nula, je pod zbylou nulou největší společný dělitel (sz odstraní nulu a pq vytisken výsledek a ukončí program)
• opakuj znova

A to celé se poštvě na dvě hodnoty přečtené od uživatele. No možná se blamuju, ale mě to přijd jako největší společný dělitel.

[Hynek (Pichi) Vychodil]

Aha, takže se blamuju.

[Marek Bernát]

preco by sa mali vymenienat nejake hodnoty?
od coho mame modulo? :
int gcd(int a, int b){ if(b)return gcd(b,a%b); else return a; }
(Pani programatori v dc dufam prepacia odpornu non-RP notaciu )
btw, tiez som si uz stihol precitat man od dc a som nim nadseny, takze nebyt nedostatku pracovnych ponuk, hned by som konvertoval

[Hynek (Pichi) Vychodil]

Dík za nakopnutí. Jsem to ale ňouma.

dc -e '[rSadLar%d0<a]sa??laxsap'

Nebo v ukecanější formě.

dc -e '[rSadLar%d0<a]sa[a=]P?[b=]P?laxsa[result:]Pp'

P.S.: Všiměte, že vystačím s jediným registrem

[michal00]

hladas "Největší společný dělitel" alebo "nalezení nejmenšího společného dělitele" ?

to druhe je dost lahke: "return 1;" :)