{"id":918,"date":"2010-09-02T07:23:02","date_gmt":"2010-09-02T06:23:02","guid":{"rendered":"http:\/\/penszko.blog.polityka.pl\/?p=918"},"modified":"2010-09-02T07:23:02","modified_gmt":"2010-09-02T06:23:02","slug":"liczby-trunkowe","status":"publish","type":"post","link":"https:\/\/blog.polityka.pl\/penszko\/2010\/09\/02\/liczby-trunkowe\/","title":{"rendered":"Liczby trunkowe"},"content":{"rendered":"

Postanowi\u0142em uog\u00f3lni\u0107 owczo-baranie zadanie z poprzedniego wpisu. Pozostan\u0119 zatem jeszcze chwil\u0119 w\u015br\u00f3d \u0142amig\u0142\u00f3wek algorytmicznych, czyli takich, kt\u00f3rych gruntowne rozgryzienie bez komputera jest praktycznie niemo\u017cliwe lub bardzo \u017cmudne. Ciekawa, obszerna i stale rosn\u0105ca kolekcja takich problem\u00f3w i problemik\u00f3w, najcz\u0119\u015bciej obliczeniowych, dost\u0119pna jest na Project Euler<\/a>. To strona nale\u017c\u0105ca do najpopularniejszych w\u015br\u00f3d adept\u00f3w programowania, traktowana jako zbi\u00f3r znakomitych \u0107wicze\u0144. Niekt\u00f3re z zamieszczonych na niej zada\u0144 mo\u017cna jednak i warto nadgryza\u0107 bez komputera. Mo\u017cliwa do napocz\u0119cia „na piechot\u0119” jest r\u00f3wnie\u017c poni\u017csza \u0142amig\u0142\u00f3wka, wzorowana na owczo-baraniej.<\/p>\n

Dany jest iloczyn liczb naturalnych:
\na<\/em> * b<\/em> = c<\/em>
\na<\/em> to liczba n<\/em>-cyfrowa,
\nb<\/em> to najmniejsza\u00a0– dla danego a<\/em>\u00a0– taka liczba, \u017ce c<\/em> sk\u0142ada si\u0119 z jednakowych cyfr.
\nProsz\u0119 znale\u017a\u0107 najwi\u0119ksze b<\/em> dla danego n<\/em>. Inaczej m\u00f3wi\u0105c, nale\u017cy wybra\u0107 najwi\u0119kszy mno\u017cnik spo\u015br\u00f3d najmniejszych znalezionych dla wszystkich n<\/em>-cyfrowych a<\/em>, gdy n<\/em> jest \u015bci\u015ble okre\u015blone.<\/p>\n

Oczywi\u015bcie, nie dla ka\u017cdej mno\u017cnej\u00a0istnieje taki mno\u017cnik, aby iloczyn sk\u0142ada\u0142 si\u0119 z jednakowych cyfr. Naj\u0142atwiej zauwa\u017cy\u0107, \u017ce odpadaj\u0105 mno\u017cne zako\u0144czone zerem.<\/p>\n

Dla n<\/em> = 1 sprawa jest trywialna: b<\/em> = 1 dla ka\u017cdego a<\/em>.
\nDla n<\/em> = 2 mo\u017cna pog\u0142\u00f3wkowa\u0107 bez programowania,\u00a0ale przyda si\u0119 kalkulator.
\nNa starcie wypada wykre\u015bli\u0107 wszystkie a<\/em> z\u0142o\u017cone z dw\u00f3ch jednakowych cyfr, bo dla nich b<\/em> = 1. Odpadnie te\u017c sporo takich, kt\u00f3re dla \u017cadnego ca\u0142kowitego b<\/em> nie dadz\u0105 c<\/em>\u00a0– poza zako\u0144czonymi zerem b\u0119d\u0105 to na przyk\u0142ad\u00a0niekt\u00f3re liczby pierwsze<\/strong> oraz zako\u0144czone pi\u0105tk\u0105<\/strong>. By\u0107 mo\u017ce w\u0142a\u015bnie w\u015br\u00f3d nich\u00a0– ale tych, kt\u00f3re nie odpadn\u0105\u00a0– ukrywa si\u0119 najwi\u0119ksze b<\/em>. Sprawdzaj\u0105c na przyk\u0142ad liczby 2-cyfrowe z pi\u0105tk\u0105 z prawej strony szybko wpada si\u0119 na du\u017ce b<\/em> = 15873 dla a<\/em> = 35 (35 * 15873 = 555555).
\nCzy w\u015br\u00f3d pozosta\u0142ych dwucyfrowych liczb ukrywa si\u0119 a<\/em> z wi\u0119kszym b<\/em>? Pytanie jest „prowokacyjne”, bo nietrudno ustali\u0107, \u017ce tak. W og\u00f3le, wydaje si\u0119, \u017ce znalezienie najwi\u0119kszego\u00a0b<\/em> dla n<\/em> = 2 nie wymaga korzystania z komputera, tzn. mo\u017cna wpa\u015b\u0107 na pomys\u0142 gwarantuj\u0105cy\u00a0umiarkowanie wyboist\u0105 drog\u0119 do celu. A jakie s\u0105 rozwi\u0105zania dla wi\u0119kszych n<\/em>? To ju\u017c jest pytanie do programist\u00f3w.<\/p>\n

Liczba z\u0142o\u017cona z jednakowych cyfr okre\u015blana jest w niekt\u00f3rych j\u0119zykach z angielska\u00a0– repdigit<\/a>. Dla odmiany nazwa niemiecka pachnie alkoholem\u00a0\ud83d\ude42 –\u00a0schnapszahl<\/a> (zagadka: dlaczego?). Propozycje polskiego okre\u015blenia, niekoniecznie trunkowe, b\u0119d\u0105 mile widziane.<\/p>\n

Komentarze z prawid\u0142owymi<\/strong> rozwi\u0105zaniami uwalniane s\u0105 wieczorem w przeddzie\u0144 kolejnego wpisu. Wpisy pojawiaj\u0105 si\u0119 co 3-4 dni.<\/span><\/p>\n","protected":false},"excerpt":{"rendered":"

Postanowi\u0142em uog\u00f3lni\u0107 owczo-baranie zadanie z poprzedniego wpisu. Pozostan\u0119 zatem jeszcze chwil\u0119 w\u015br\u00f3d \u0142amig\u0142\u00f3wek algorytmicznych, czyli takich, kt\u00f3rych gruntowne rozgryzienie bez komputera jest praktycznie niemo\u017cliwe lub bardzo \u017cmudne. Ciekawa, obszerna i stale rosn\u0105ca kolekcja takich problem\u00f3w i problemik\u00f3w, najcz\u0119\u015bciej obliczeniowych, dost\u0119pna jest na Project Euler. To strona nale\u017c\u0105ca do najpopularniejszych w\u015br\u00f3d adept\u00f3w programowania, traktowana jako zbi\u00f3r […]<\/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\/918"}],"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=918"}],"version-history":[{"count":0,"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/posts\/918\/revisions"}],"wp:attachment":[{"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/media?parent=918"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/categories?post=918"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/tags?post=918"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}