Задача 338: За любителите на аритметиката и информатиката (накуп)
Вчера, публикувах задачата с доста предизвикателни коментари. Днес, (след като преспах) установявам че доста съм надценил сложността и сега коментарите ми изглеждат излишно самонадеяни и звучат глупаво. Затова ги изтривам с лека ръка (а и все още никой не е писал след мен)
Самата задача е такава:
Да се намери алгоритъм за намиране на последната ненулева цифра на N! (ЕН фактуриел), където N е голямо, да речем повече от 1000.
Доколкото виждам, съществуват поне десетина алгоритъма.
Всеки да се чувства добре дошъл да напише някакъв (в свободен текст или както му е удобно).
Ще се ценят такива, при които циклите са къси, рекурсиите са плитки, не се работи с прекалено големи числа и т.н., т.е. гони се "оптимизация" (на алгоритъма).
Re:За любителите на аритметиката и информатиката (накуп)
Имам голямо желание малко да променя и поокрася условието така:
Влюбили сте се в красивата принцеса на местното царство.
Но нейния баща (царят) е строг и леко зъл. Мрази счетоводителите си защото го послъгват. Мрази и програмистите, защото постоянно му се гътват компютърните системи. ... неква фобия има към тия хора.
Принцесата вече е порастнала достатъчно и се оглежда нетърпеливо за партньри.
Току-що, царят е обявил, че след два дни ще има изпит за кандидатите за принцесата и вие се колебаете дали да отидете, защото царят измъчван от фобията си е определил следните условията за изпита:
- ще ви се предостави само молив и тетрадка, никакви лаптопи, никакви калкулатори
- ще бъде казано число N межди 8000 и 9999
- трябва да се намери последната ненулева цифра на N! (ЕН факториел)
- ще бъде отпуснат 1 час за решаване и смятане
- който не се справи, отива на бесилката
И така, имате цели два дни за да решите дали да отидете на изпита.
И това е въпроса на задачата - ще отидете ли ?
Re:За любителите на аритметиката и информатиката (накуп)
Нещо се мъча да направя с 2 и 5, но не ми се получава докрай...а може и да бъркам
Елиминирам нулите - те са толкова, колкото пъти в умножението участват числа кратни на 2 и на 5. Числата кратни на 2 са повече, така че броим само числата кратни на 5.
Т.е. нулите са n, ако в N! участват n числа кратни на 5 => последната цифра е N!/(2^n*5^n) mod 10 и е четно число.
После търсим колко е n. T.e. делим N n пъти на 5 до резултат <= 4 (тук не ми трябва цикъл или рекурсия, защото 9999 < 5^5, т.е. няма да деля повече от 5 пъти - не е трудно)
Остава въпроса как да намерим N!/(2^n*5^n) като функция на 2 и 5. За целта представяме N!/(2^n*5^n) като {N!/(2^m*5^n) * 2^(m-n)} или 2^(m-n) mod 10 ни дава последната цифра. Само че не мога да се сетя как да намеря m или 2^(m-n)
P.S. Намерих си грешка, но не помага да намеря резулатата...
представяме N!/(2^n*5^n) mod 10 като {N!/(2^m*5^n) mod 10 * 2^(m-n) mod 10} mod 10, за да намерим последната цифра...забравят се елементарни правила...:stupid:
Re:За любителите на аритметиката и информатиката (накуп)
Я, кой бил тук !
Edin_Lud, от много време не си се появявал, радвам се че пишеш тук в задачата. ... Бе знаех си аз, че с принцеси по-лесно се събира аудитория.
А иначе по задачата, добре си го подкарал по принцип. Сега остава да поодялкаш туй-унуй и да го изпипаш докрай (някак си)
Re:За любителите на аритметиката и информатиката (накуп)
@Edin_Lud,
броя на множителите 2, които участват в n! би трябвало да е
[n/2] + [n/4] + [n/8] + ...
Това е функцията скобка, или целочислено деление.
Разбира се, това важи не само за 2, а и за всяко друго просто число. Примерно 5.
Имам предложение как задачата може да се смята на ръка
Но и то е с цикъл, понеже за да сметна n!, последователно пресмятам всички по-малки.
Всъщност пресмятам само последната ненулева цифра на всички 1!, 2!, ... (n-1)!
Налага се да го правя само защото за да сметна последната ненулева на n! ми е нужно да знам последната ненулева на (n-1)!
Разлагам n на прости множители така:
n = 2p.5q.m, като m не се дели нито на 5, нито на 2.
Сега различавам 3 случая:
1. p > q
n = (2q.5q).m.2p-q
Търсената последна цифра получавам като умножа предната по m.2p-q
2. p = q
Търсената последна цифра получавам като умножа предната по m
3. p < q
Тук вместо да умножавам по 5, предпочитам да си мисля, че умножавам по 10 и деля на 2.
Затова първо предната последна цифра умножавам по m и после полученото деля на 2 (q-p) пъти.
Но как деля число на 2, щом знам само последната му цифра?
Ако последната цифра е била примерно 6, разделеното число може да завършва или на 3, или на 8. И как да избера кое?
Ами ето как - в случая, във вички n!, дори да им премахнем нулите отзад, ще са четни.
А всички двусмислени деления на 2 ме карат да избирам между едно четно и едно нечетно винаги.
Така че просто при всяко делене на 2 избирам четния вариант за отговор.
Това е.
Освен това мисля, че ако напишем отговорите на всички задачи един след друг, ще забележим цикличност.
Заради "принципа на чекмеджетата", понеже имаме краен брой цифри, а безкраен брой задачи.
Ако успея да видя при кое n нещата започват да се повтарят, ще пиша допълнително.
Това ще помогне да решаваме задачата дори за особено големи n.
P.S.
За последното изглежда не съм права.
Re:За любителите на аритметиката и информатиката (накуп)
А на мен ми се налага да призная, че в моя алгоритъм се появи един недостатък, който ме праща директно на бесилото.
Остава ми единствено да перефразирам мисълта „Пътя към ада е осеян с добри намерения” на „Пътя към бесилката е осеян с добри намерения”.
Последните ми „предсмъртни” думи са, че попаднах в капана на една красива и изкусителна идея. Толкова е великолепна, че си заслужава да я разкажа, но предупреждавам, че е фалшива.
И така, имаме
N!=1.2.3.4.5.6.7.8.9….(N-1).N
Разделяме множителите на три групи от които правим три отделни произведения.
Първата я означавам с P5 – тук са всички числа, по-малки от N и завършващи с цифрата 5
P5=5.15.25.35.45.55.65.75. …
Втората я означавам с P0 – тук са тук са всички числа, по-малки от N и завършващи с цифрата 0
P0=10.20.30.40.50.60…
Третата група P са всички останали числа по-малки от N
Т.е. имаме
N! = P.P0.P5
Сега, като разгледаме всяко едно от тези P-та, забелязваме следните три неща, (които евентуално при интерес ще опиша в детайли в отделен пост):
1. За P
На пръв поглед , това произведение P изглежда много страшно. Но всъщност въобще не е така и с лекота могат да бъдат изчислени последните две цифри на ръка. Бих казал, че P е най-безпроблемния от трите множителя P.P0.P5.
2. За P5
При N>15, последните две цифри на P5 са винаги или 25 или 75, при това, ако ни е известна точната стойност на N, с лекота можем да изчислим на ръка кои точно цифри са – 25 или 75
3. За P0 имаме
P0=10[N/10].N1!,
Тук N1 е числото което се получава като на числото N махнем най-дясната цифра.
Разкошно, нали – рекурсия при която скъсяваме порядъка. При нашата конкретна задача, дълбочината на тази рекурсия ще бъде най-много 4.
Т.е., ще имаме N, N1, N2, N3, където N3 е едноцифрено и без проблеми можем на ръка да сметнем N3! .
Т.е., прилагаме следния алгоритъм за да изчислим на ръка последната ненулева цифра на N!
1. За едноцифреното N3 изчисляваме на ръка N3! или поне последната цифра
2. Сега гледаме N2! – разлагаме го на съответните P, P0, P5 за двуцифреното N2
N2! = P.P0.P5
И на P, и на P0, и на P5 знаем последните две ненулеви цифри ==> знаем последната цифра на N2!
(червеното ==> на горния ред всъщност е невярното в моя алгоритъм)
3. Сега гледаме N1! – разлагаме го на съответните P, P0, P5 за трицифреното N1
N1! = P.P0.P5
Знаем последните две ненулеви цифри на P и на P5, знаем последната ненулева цифра на P0 ==> знаем последната цифра на N1!
4. Остана четирицифреното N, за което правим аналогичните (и неверни) сметки.
…
Красиво, но невярно
Re:За любителите на аритметиката и информатиката (накуп)
Edin_Lud,
Ако комбинирам твоята идея с моя псевдоалгоритъм, май ще ми се размине бесилката.
ПП.
Но няма като теб да вадя всички петици в самостоятелен множител - част от петиците ще си ги оставя в общия кюп, за да мога да направя множител, който е фактуриел на число с по-малък порядък.
Re:За любителите на аритметиката и информатиката (накуп)
Така като гледам, сама си говоря :)
Та, понеже MitkoS е отправил задачата към любителите на аритметиката и информатиката, а то до тоя момент само сметки имаше, затова реших да направя и едно скриптче, което да работи по описаната идея. Тук:
http://bibi.li/factoriel.html
Преди да измислим самата идея, нямаше смисъл от компютърно смятане, освен по дърварския начин, но той щеше да е адски бавен при тия огромни резултати.
Иначе човек може да види всички цифри на някое n! в тоя сайт:
http://www.wolframalpha.com/input/?i=6543%21
Re:За любителите на аритметиката и информатиката (накуп)
Ако някой очаква някакъв коментар от мен като автор (на условието) , то такъв коментар няма да има - Bibi e споменала по-горе, че решението е колективно, а аз бях част от колектива (снощи).
Обаче това последното си е 100% нейно дело, за което и свалям шапка. ... и не само затова де.
Re:За любителите на аритметиката и информатиката (накуп)
Моя е грешката, че не го казах. Ама защото се радвах, че вече е решена поне по един начин и...
А всъщност то MitkoS я направи. Тия "съображения" са негово откритие, а без тях нямаше никаква смислена идея, по която да се умува.
Опитах да я опиша. Все още има доста неточности и полуизказани неща. Ако Krusteva се появи, ще има за какво да ме мъмри, та обещавам да поправя обясненията, докато не е станало късно.
А на MitkoS багодарности и за условието, и за решението! :bravo
Re:За любителите на аритметиката и информатиката (накуп)
Хайде стига си скромничила ... това тук не е конкурс "Мис Логически задачи"
Ако знаех, че така здраво ще я захапеш тази задача, щях да дам условието за принцове, а не за принсеси.
По-нагоре казах, че нямам коментари, ама всъщност имам.
Това "мъчното" с двойките може да отпадне. Не е нужно да имаме последователно "делене" на 2. Нищо че е най-много три-пъти. Защото последния знак на 2m е известен при известно m и просто за двата дни ще "научим наизуст" една табличка 4x4 състояща се само от четни едноцифрени числа.
Re:За любителите на аритметиката и информатиката (накуп)
Както и в много предишни изяви, вие двамата ме оставяте безмълвен.
Една съвсем проста за вас задачка, която ме занимаваше преди мно-о-о-го години:
Най-бърз алгоритъм за подреждане по случаен начин на първите N последователни естествени числа. Така, че времето за изпълнение да расте пропорционално на N, а не много по-стръмно.
Навремето аз измислих един такъв, но може би има и по-бърз.
Забележка: На времето пробвахме с Бъзик интерпретатор, така, че времената за изпълнение се различаваха забележимо. (BASIC, де).