Pozoruhodná úloha

4.11.2007 19:14 | Co mě zaujalo | poslední úprava: 4.11.2007 19:15

Dnes odpoledne se na blogu Marka Stopky objevily dvě úlohy, při jejich řešení jsem si vzpomněl na jinou úlohu. Je docela profláklá, ale stejně pro ty, co ji neznají, zde je zadání:

Máme dvě čísla, obě jsou větší než 1 a menší než 100. Adamovi řekneme jejich součet a Evě jejich součin.

Eva: Já nevím jaká to jsou čísla.
Adam: Já věděl, že to nebudeš vědět.
Eva: Už to vím.
Adam: Já už taky.

Jaká to jsou čísla?

       

Komentáře

[Jiří Veselský]

Dijkstra, jak známo, tuto úlohu vyřešil z hlavy - viz HTML či PDF. A přestože jsem ji kdysi zvládl vyřešit taky (byť ne z hlavy), odkazovaný Dijkstrův text to bezpochyby vysvětluje lépe, než bych splácal já...

[Radek Miček]

Odkazovaný text znám, ale z hlavy to též nevyřeším - ostatně mě myšlenka řešit to bez tužky a papíru ani nenapadla

[zde]

Nojo, v noci nespí. Není divu že pak přes den píše bláboly.

http://en.wikipedia.org/wiki/Considered_harmful

[disorder]

http://lemonodor.com/images/dijkstra-quick-n-dirty-s.jpg

[zde]

Jejda, tak se mu musím omluvit. Wikiquote tvrdí že "goto considered harmfull" nepochází od Dijkstry, ale od Wirtha. To byl ještě o jeden level větší pojídač koláčů

[disorder]

zase chyba

The March 1968 ACM letter's famous title, "Go To Statement Considered Harmful", [1] was not the work of Dijkstra, but of Niklaus Wirth, then editor of Communications of the ACM.

(http://www.cs.utexas.edu/users/EWD/transcriptions/EWD02xx/EWD215.html)

no, ty si skac kam chces, ja mam rad svoje backtrace :P

[Tomáš Srnka]

2 a 2 ?

[disorder]

mal by si mrknut na to dijkstrovo riesenie. to tvoje odporuje uz len tej prvej poziadavke, ktoru by som snad vedel sformulovat aj ja ;)

no, ja som z toho hlupy. nieco co Dijkstra riesil 6h v hlave, ja si ani netrufam :)

[Robo]

6 hodin? To uz by som skorej vyriesil testovanim kazdej kombinacie ;)

[disorder]

rucne? v tom by si sa stratil rychlejsie nez on prisiel na podstatu problemu :)

[miro]

Riesenie by nasiel rychlo, 17 nie je az tak daleko (ak by teda zacal od najmensieho suctu)

Prve dve vlastnosti sa odvodia ihned (ze Evine cislo nie je sucinom dvoch prvocisel, a ze Adamove cislo nie je suctom dvoch prvocisel) Pomocou tychto vlastnosti sa postupuje pomerne rychlo. Urcite rychlejsie nez za 6 hodin (asi tak pol hodinu, s papierom samozrejme :)

[disorder]

on chcel testovat kazdu kombinaciu, takze:

1) ziadne vlastnosti neodvodzuje

2) musel by dokazat unikatnost, takze musi testovat vsetky a nemoze sa zastavit ked najde jedno riesenie

[miro]

Tak to hej, keby neprisiel ani na tie prve dve nutne podmienky, tak by to mal tazke. Dokaz jednoznacnosti sa tyka uz len korektnosti zadania. Mozem na zaciatku predpokladat, ze zadanie je korektne a jednoznacnost predpokladat... A keby to tak nebolo a nahodou sa to dozviem, zadanie potom otrepat zadavatelovi o hlavu :)

[Tomáš Srnka]

este sa tak naucit citat zadanie...

[vencour]

Fíííha, konečně mi svitlo, je nutné najít dvě jednoznačná čísla, čili v tom součinu musí být nějaké prvočislo ... dobrý

Právě kvůli jednoznačnosti