kms - fórum o príkladoch

9. príklad 1. letnej série 2009/2010

Zadanie:
Jefo si myslí, že určite každého z vás nadchne nasledúca úloha. Chceme zapísať čísla $1,\ 2,\dots ,\ 100$ za sebou v takom poradí, aby pre každé číslo platilo, že má pred sebou len také čísla, ktoré sú od neho väčšie, alebo len také čísla, ktoré sú od neho menšie. Koľkými spôsobmi to vieme urobiť?

Poznámka: Keby sme takto zapisovali za sebou iba čísla $1,\ 2,\ 3,\ 4,\ 5$ ; tak vyhovujúce poradie je napríklad $4,\ 5,\ 3,\ 2,\ 1$ .

Naspäť na príklady | Napíš príspevok

mišof - 08. 03. 2010 - 20:34:01 z dial-95-105-152-199-orange.orange.sk

2petržlen: hej, presne to som mal na mysli :)

cituj ma

petržlen <petrzlen~kms~sk> - 08. 03. 2010 - 11:56:31 z kms.sk

mišof napísal:
Ale daj pokoj ty kopec :D veď rovno povedať bijekciu na {0,1}^(N-1) je výrazne ľahšie ako kopať do tých kopcov, nie? :)

Len pre ujasnenie. Jedným smerom (postupnosť, na binárny vektor) je to jasné.
Druhým smerom to vyhodnocujem od konca vektora. $0$ hovorí že mám "pred" (menšie indexy) sebou len menšie čísla. $1$ hovorí že len vačšie. Inicializujem max= $N$ , min= $1$ . Ak narazím na $0$ (idem od konca) tak vypíšem max a zmenším max o 1 . Ak na $1$ , tak vypíšem min a zvýšim min o 1. Pekné...

cituj ma

JeFo - 04. 03. 2010 - 21:48:13 z 158.195.211.91

škrečok napísal:

kamilama napísal:
petrzlnen, fakt si si myslel ze nas tato uloha nadchne? :D

to si myslel jefo, nie petržlen :)

po pravde, ja som tu ulohu nezratl, lebo ma nenadchla

cituj ma

kamilama - 04. 03. 2010 - 13:57:34 z 158.196.244.87.in-addr.arpa

no tak sorry, bol to jeffo ale v nejakom priklade bol aj petrzlen. Myslim

cituj ma

mišof - 04. 03. 2010 - 03:01:28 z dial-95-105-152-199-orange.orange.sk

Ale daj pokoj ty kopec :D veď rovno povedať bijekciu na {0,1}^(N-1) je výrazne ľahšie ako kopať do tých kopcov, nie? :)

cituj ma

petržlen <petrzlen~kms~sk> - 03. 03. 2010 - 13:03:19 z kms.sk

kamilama napísal:
petrzlnen, fakt si si myslel ze nas tato uloha nadchne? :D

Jasné že kopce, si môžeš kresliť intervali ktoré klesajú a ktoré stúpajú a potom ukážeš, že ich nie je veľa :) ... vyzerá ale, že to bolo celkom ľahké.

############/\/\##############
#######/\##/####\######/\#####
/\/\/\/##\/######\/\/\/##\/\/\

cituj ma

škrečok - 03. 03. 2010 - 08:02:02 z 158.195.197.206

kamilama napísal:
petrzlnen, fakt si si myslel ze nas tato uloha nadchne? :D

to si myslel jefo, nie petržlen :)

cituj ma

kamilama - 02. 03. 2010 - 23:04:23 z 158.196.244.87.in-addr.arpa

petrzlnen, fakt si si myslel ze nas tato uloha nadchne? :D

cituj ma

Syseľ - 26. 02. 2010 - 18:42:14 z gw-sa3.salamon.sk

S akými kopcami?

cituj ma

petržlen <petrzlen~kms~sk> - 26. 02. 2010 - 11:33:03 z 158.195.205.45

Tak ako ste sa popasovali s kopcami?

cituj ma