W wej\u015bci\u00f3wce na bankiet z poprzedniego wpisu nie\u00a0kry\u0142 si\u0119 \u017caden\u00a0podst\u0119p. Wbrew przypuszczeniom Andrzeja zadanie by\u0142o po prostu proste. Mo\u017ce podst\u0119pnie b\u0119dzie teraz, czyli przed kolejnym matbankietem pot\u0119gowym. Przedtem jednak powr\u00f3\u0107my na chwil\u0119 do minionego.<\/p>\n
Aby okre\u015bli\u0107 minimaln\u0105 liczb\u0119 krok\u00f3w warunkuj\u0105cych dotarcie „na piechot\u0119” od x do x^n, stosuje si\u0119 zwykle prosty schemat: k-krotne podnoszenie do kwadratu kolejnych kwadrat\u00f3w x (x^2^k), czyli mno\u017cenie ich\u00a0przez siebie, a\u017c do znalezienia si\u0119 w okolicach x^n. Nast\u0119pnie, je\u015bli to konieczne, wykonywane jest mno\u017cenie lub dzielenie przez pot\u0119g\u0119 obliczon\u0105 wcze\u015bniej lub dodatkowo. Oczywistym jest, \u017ce do celu nie dotrze si\u0119 szybciej, ni\u017c w [log2<\/sub>n<\/span>] krokach (nawias kwadratowy oznacza cz\u0119\u015b\u0107 ca\u0142kowit\u0105 warto\u015bci logarytmu). Dla n=1000 [log2<\/sub>n<\/span>] = 9, jednak dzia\u0142a\u0144 potrzeba\u00a0dwunastu\u00a0– dziesi\u0119ciu mno\u017ce\u0144 do x^1024, nast\u0119pnie dodatkowego mno\u017cenia tworz\u0105cego x^24 i wreszcie dzielenia „cofaj\u0105cego”. W\u0119dr\u00f3wka by\u0142aby nieco bardziej skomplikowana i trwa\u0142aby d\u0142u\u017cej (ile co najmniej krok\u00f3w?), gdyby dzia\u0142ania ograniczy\u0107 tylko do mno\u017ce\u0144. Jednak to i tak pestka w por\u00f3wnaniu z analogicznym jak poprzednio\u00a0warunkiem,\u00a0kt\u00f3ry nale\u017ca\u0142o spe\u0142ni\u0107, chc\u0105c dosta\u0107 si\u0119 na trzeci bankiet u szalonego matematyka.<\/p>\n Tym razem matematyk za\u017cyczy\u0142 sobie wpisania na zaproszeniu minimalnej liczby dzia\u0142a\u0144 (mno\u017ce\u0144 i dziele\u0144), kt\u00f3re nale\u017cy wykona\u0107, aby obliczy\u0107 warto\u015b\u0107 x^170. Konieczne by\u0142o tak\u017ce podanie przyk\u0142adu z tym minimum.<\/em><\/p>\n Prosz\u0119 spr\u00f3bowa\u0107 znale\u017a\u0107 t\u0119 liczb\u0119, wspieraj\u0105c j\u0105 oczywi\u015bcie\u00a0przyk\u0142adowym ci\u0105giem dzia\u0142a\u0144 –\u00a0nawet je\u015bli na bankiet nie maj\u0105 Pa\u0144stwo ochoty.<\/p>\n","protected":false},"excerpt":{"rendered":" W wej\u015bci\u00f3wce na bankiet z poprzedniego wpisu nie\u00a0kry\u0142 si\u0119 \u017caden\u00a0podst\u0119p. Wbrew przypuszczeniom Andrzeja zadanie by\u0142o po prostu proste. Mo\u017ce podst\u0119pnie b\u0119dzie teraz, czyli przed kolejnym matbankietem pot\u0119gowym. Przedtem jednak powr\u00f3\u0107my na chwil\u0119 do minionego. Aby okre\u015bli\u0107 minimaln\u0105 liczb\u0119 krok\u00f3w warunkuj\u0105cych dotarcie „na piechot\u0119” od x do x^n, stosuje si\u0119 zwykle prosty schemat: k-krotne podnoszenie do […]<\/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\/244"}],"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=244"}],"version-history":[{"count":0,"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/posts\/244\/revisions"}],"wp:attachment":[{"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/media?parent=244"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/categories?post=244"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/tags?post=244"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}