{"id":5200,"date":"2013-11-10T07:16:30","date_gmt":"2013-11-10T06:16:30","guid":{"rendered":"http:\/\/penszko.blog.polityka.pl\/?p=5200"},"modified":"2013-11-10T07:25:51","modified_gmt":"2013-11-10T06:25:51","slug":"raz-dwa","status":"publish","type":"post","link":"https:\/\/blog.polityka.pl\/penszko\/2013\/11\/10\/raz-dwa\/","title":{"rendered":"Raz-dwa"},"content":{"rendered":"

Je\u015bli chodzi o stopie\u0144 z\u0142o\u017cono\u015bci, zadania matematyczno-rozrywkowe mo\u017cna z grubsza podzieli\u0107, jak problemy obliczeniowe, na dwa rodzaje: jedne rozwi\u0105zuje si\u0119 g\u0142ow\u0105, drugie komputerem (pomijam to, \u017ce g\u0142owa potrzebna jest do napisania programu). Podzia\u0142 jest nieostry, bo – przynajmniej teoretycznie – z wieloma zadaniami mo\u017cna upora\u0107 si\u0119 i tak, i tak. Wszystko zale\u017cy od tego, czy komu\u015b starczy ch\u0119ci, cierpliwo\u015bci i ambicji, aby pokona\u0107 przeszkod\u0119 „na piechot\u0119”, czy te\u017c dojdzie do wniosku, \u017ce gra jest niewarta \u015bwieczki i lepiej zatrudni\u0107 sztuczny m\u00f3zg. S\u0105 te\u017c oczywi\u015bcie takie zadania, o kt\u00f3rych z g\u00f3ry mo\u017cna powiedzie\u0107, \u017ce komputer ich nie ruszy, a cz\u0142owiek da sobie rad\u0119 albo takie, o kt\u00f3rych od razu wiadomo, \u017ce zabiera\u0107 si\u0119 do nich nie ma sensu bez komputerowego wsparcia. Te drugie pojawiaj\u0105 si\u0119 na stronach z wyzwaniami dla programist\u00f3w – najciekawsz\u0105 jest zapewne Project Euler<\/a>.<\/p>\n

Tak sobie m\u0119drkuj\u0119 w zwi\u0105zku z dwoma zadaniami.
\nJednym jest to zamieszczone w poprzednim wpisie – ni takie, ni siakie, bo z jednej strony szukanie maksa na piechot\u0119 wydaje si\u0119 ciekawe, ale nie ma pewno\u015bci, \u017ce cel si\u0119 osi\u0105gnie, wi\u0119c kusz\u0105ce jest napisanie programu; z drugiej strony, gdyby maks by\u0142 podany, to do odpowiadaj\u0105cego mu rozmieszczenia cyfr w diagramie nie tak trudno by\u0142oby dotrze\u0107 – praktycznie wystarczy p\u00f3\u0142 godziny d\u0142ubaniny.
\nDrugie zadanie, kt\u00f3re pochopnie zamie\u015bci\u0142em w pa\u017adziernikowym \u015awiecie Nauki<\/em>, jest – wbrew pozorom – nie do ruszenia na piechot\u0119. Nawet napisanie programu nie wydaje si\u0119 proste, ale tu mog\u0119 si\u0119 myli\u0107, bo nie jestem mocny w te klocki. Przedstawi\u0119 w skr\u00f3cie w czym rzecz.<\/p>\n

Oto rzadka linijka optymalna „raz-dwa” k<\/em>|d<\/em> dla k<\/em>=1 i d<\/em>=8<\/strong>:<\/p>\n

\"\"<\/a><\/p>\n

k<\/em>=1<\/strong> poniewa\u017c jest na niej tylko jedna<\/strong> kreska (dlatego te\u017c jest rzadka<\/strong>); d<\/em>=8<\/strong> poniewa\u017c mo\u017cna ni\u0105 odmierzy\u0107 ka\u017cd\u0105 ca\u0142kowit\u0105<\/strong> liczb\u0119 centymetr\u00f3w od 1 do 8<\/strong> cm (zak\u0142adaj\u0105c, \u017ce 1 cm stanowi na niej jednostk\u0119, czyli ca\u0142a ma d\u0142ugo\u015b\u0107 4 cm), przyk\u0142adaj\u0105c linijk\u0119 w czasie pomiaru jedno<\/strong>– lub dwu<\/strong>krotnie (dlatego jest „raz-dwa<\/strong>„). Na przyk\u0142ad:
\n2 cm – przyk\u0142adamy dwukrotnie odcinek 0_1;
\n3 cm – przyk\u0142adamy 1_4;
\n7 cm – 0_4 i 1_4.<\/p>\n

Linijka jest optymalna<\/strong>, poniewa\u017c z jednej strony 8 jest najwi\u0119kszym d<\/em>, gdy kreska jest tylko jedna, a z drugiej dla d<\/em>=8 kresek nie mo\u017ce by\u0107 mniej.<\/p>\n

Wspomniane zadanie w \u015awiecie nauki<\/em> polega\u0142o na skonstruowaniu rzadkiej linijki minimalnej „raz-dwa” 4|d<\/em><\/strong> – takiej, aby d<\/em> by\u0142o jak najwi\u0119ksze. Inaczej m\u00f3wi\u0105c, na linijce powinny znale\u017a\u0107 si\u0119 cztery kreski podzia\u0142ki umieszczone w takich miejscach, aby mo\u017cna ni\u0105 by\u0142o odmierzy\u0107 ka\u017cd\u0105 ca\u0142kowit\u0105 liczb\u0119 centymetr\u00f3w od 1 do maksymalnego d<\/em>, przyk\u0142adaj\u0105c linijk\u0119 raz lub dwa razy.
\nBardziej abstrakcyjnie zadanie mo\u017cna sformu\u0142owa\u0107 tak:
\nWybieramy pi\u0119\u0107 liczb ca\u0142kowitych dodatnich i uzupe\u0142niamy ten zbi\u00f3r dziesi\u0119cioma liczbami – dodatnimi r\u00f3\u017cnicami mi\u0119dzy ka\u017cd\u0105 par\u0105 wybranych liczb. W ten spos\u00f3b tworzymy zbi\u00f3r A<\/em> z\u0142o\u017cony z pi\u0119tnastu liczb. Jakie pi\u0119\u0107 liczb nale\u017ca\u0142oby wybra\u0107 na pocz\u0105tku, aby dodaj\u0105c parami liczby ze zbioru A<\/em> (w gr\u0119 wchodz\u0105 tak\u017ce dwukrotno\u015bci ka\u017cdej z nich), mo\u017cna by\u0142o utworzy\u0107 ka\u017cd\u0105 liczb\u0119 ca\u0142kowit\u0105 od 1 do najwi\u0119kszego mo\u017cliwego d<\/em>.<\/p>\n

Osobom, kt\u00f3re, jak ja, nie s\u0105 mocne w programowaniu, proponuj\u0119 utworzy\u0107 na piechot\u0119 linijk\u0119 „raz-dwa” o dwa oczka mniejsz\u0105, czyli 2|d<\/em> z najwi\u0119kszym d<\/em>. Nawet w\u00f3wczas zadanie nie jest proste.<\/p>\n

\"\"<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"

Je\u015bli chodzi o stopie\u0144 z\u0142o\u017cono\u015bci, zadania matematyczno-rozrywkowe mo\u017cna z grubsza podzieli\u0107, jak problemy obliczeniowe, na dwa rodzaje: jedne rozwi\u0105zuje si\u0119 g\u0142ow\u0105, drugie komputerem (pomijam to, \u017ce g\u0142owa potrzebna jest do napisania programu). Podzia\u0142 jest nieostry, bo – przynajmniej teoretycznie – z wieloma zadaniami mo\u017cna upora\u0107 si\u0119 i tak, i tak. Wszystko zale\u017cy od tego, czy […]<\/p>\n","protected":false},"author":3,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"_links":{"self":[{"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/posts\/5200"}],"collection":[{"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/users\/3"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/comments?post=5200"}],"version-history":[{"count":17,"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/posts\/5200\/revisions"}],"predecessor-version":[{"id":5217,"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/posts\/5200\/revisions\/5217"}],"wp:attachment":[{"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/media?parent=5200"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/categories?post=5200"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/tags?post=5200"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}