Регистрирайте сеРегистрирайте се

Терзанията на влюбения студент (студент по математика)


 
   Форум за математика Форуми -> Забавна математика
Предишната тема :: Следващата тема  
Автор Съобщение
dgs
Редовен


Регистриран на: 23 Jun 2008
Мнения: 228

Репутация: 25Репутация: 25Репутация: 25
гласове: 13

МнениеПуснато на: Fri Jan 08, 2010 7:32 pm    Заглавие: Терзанията на влюбения студент (студент по математика)

Студент по математика се влюбил в красивата и богата принцеса на местното царство.
Но нейния баща (царят) бил строг и леко зъл. Мразел счетоводителите си защото го послъгвали. Мразел и програмистите, защото постоянно му се гътвали компютърните системи. ... неква фобия имал имал към тия хора.

Принцесата тъкмо е порастнала достатъчно и е започнала нетърпеливо да се оглежда за партньори.
Царят току-що е обявил новината, че след три дни ще има изпит за кандидат-съпрузите за принцесата и изпита ще е с математическа насоченост. Нашия студент първоначално се зарадвал, но после започнал да се колебае дали да отиде, защото царят измъчван от фобията си е определил следните условията за изпита:
- на кандидатите ще се предостави само молив и тетрадка, никакви лаптопи, никакви калкулатори
- ще бъде казано число N межди 8000 и 9999
- трябва да се намери последната ненулева цифра на N! (ЕН факториел)
- ще бъде отпуснат 1 час за решаване и смятане
- който не се справи, отива на бесилката

И така, нашия студент има цели три дни за да реши дали да отиде на изпита.

Как мислите, ще отиде ли ? ... Носи му се славата на отличник, но дали това ще му помогне да вземе решението да отиде ?

ПП.
Бях допуснал правописна грешка в заглавието за което се извинявам. Оправих я.


Последната промяна е направена от dgs на Sat Jan 09, 2010 12:43 am; мнението е било променяно общо 2 пъти
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
Реклама







Пуснато на:     Заглавие: Реклама

Върнете се в началото
martosss
VIP Gold


Регистриран на: 17 Mar 2007
Мнения: 3937
Местожителство: Somewhere over the rainbow
Репутация: 424.2Репутация: 424.2
гласове: 213

МнениеПуснато на: Fri Jan 08, 2010 7:40 pm    Заглавие:

е, на практика задачата му е да запомни 2000 цифри, не смятам, че това е чак толкова трудна задача.
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
dgs
Редовен


Регистриран на: 23 Jun 2008
Мнения: 228

Репутация: 25Репутация: 25Репутация: 25
гласове: 13

МнениеПуснато на: Fri Jan 08, 2010 7:58 pm    Заглавие:

Царя си е мислел (аз също), че това е невъзможно - за три дни да се запомнят две хиляди числа.

Добре, щом го можеш, приемаме че ще отидеш.

Но какво да прави твоя приятел състудент, който се влюбил в по-малката дъщеря ?
За нея също бил обявен изпит след още три дена, но царят впечатлен от твоите възможности да помниш, тоя път променил условието за N - за новия изпит числото N е в интервала от 80 000 до 99 000 (от осемдесет хиляди, до деветдесет и девет хиляди).

Той също е отличник, а евентуално и ти ако му помогнеш някак си - да вземе да отиде, а ?
Или май е по-добре да си стои в къщи ?
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
Vladi_mnt
Редовен


Регистриран на: 17 Apr 2009
Мнения: 113

Репутация: 8.3Репутация: 8.3Репутация: 8.3Репутация: 8.3Репутация: 8.3Репутация: 8.3Репутация: 8.3Репутация: 8.3
гласове: 5

МнениеПуснато на: Fri Jan 08, 2010 9:04 pm    Заглавие:

Не знам дали ще отиде => не съм решил задачата. Но пък искам да попитам, понеже тази задача я има във форума, но като задача по информатика, оттам ли е взета? Защото ако ползваме 1 алгоритъм ще стане лесна, само малко хамалски сметки... Question които пък не знам дали 1 час няма да е малко за тях.... Question Question но пък той е отличник... но пък не знаем изчислителната му мощ ....
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
dgs
Редовен


Регистриран на: 23 Jun 2008
Мнения: 228

Репутация: 25Репутация: 25Репутация: 25
гласове: 13

МнениеПуснато на: Fri Jan 08, 2010 10:03 pm    Заглавие:

Вчера написах тамън три поста там в задачата в "Компютърни изчисления", но днес реших да ги изтрия за да мога тук да публикувам тази задача.
Там бях допуснал две-три второстепенни грешки в разсъжденията, но пък в самите разсъждения напипах две-три ценни идеи които позволяват формулирането на тази задача.
Кой чел - чел, кой нечел - нечел.

Честно казано, не мисля че онези алгоритми там са постижими с молив и тетрадка в рамките на един час.
Представяш ли си как с молива за един час ще извъртиш цикъл от 1 до N (N=9999) - за една секунда трябва да правиш повече от две от стъпките на цикъла (1 час = 3600 секунди)

Аз основно за това и писах в "Компютърни изчисления" - за да покажа колко са неефективни публикуваните алгоритми там. В смисъл, че може да се постигне далеч по-голяма ефективност, но с малко повече математика (всъщност с аритметика), а не с програмиране.
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
Baronov
Напреднал


Регистриран на: 05 Jun 2008
Мнения: 316

Репутация: 55.4
гласове: 39

МнениеПуснато на: Fri Jan 08, 2010 10:29 pm    Заглавие:

Можем да приложим друг подход от програмирането. Идеята е да разделим интервала на известен брой равни интервали и да помним резултата в началото на всеки интервал.
Разделяме интервала на [tex]k=\sqrt{20000}[/tex] интервала, всеки с дължина к. Помним решението в точките на делене + разликата между степените на 2 и 5 до този момент. Това са < 1000 числа, които би трябвало да може да запомним(!). Сега като царя ни каже число, намираме в кой интервал е и почвайки от началото на интервала прилагаме добре познатия ни вече алгоритъм, започвайки от началото на интервала. По този начин ни трябват (горе-долу) 2*к операции, което е по-малко от 1000 и може би може да се направи за 1 час.

Това разбира се може да се променя много, в зависимост от "времето" и "паметта" с които разполагаме. Това е чисто програмистка идея, без грам математика, ама задачата така поставена си е програмистка, просто времевото ограничение и ограничението по памет са необичайно дефинирани.
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
martosss
VIP Gold


Регистриран на: 17 Mar 2007
Мнения: 3937
Местожителство: Somewhere over the rainbow
Репутация: 424.2Репутация: 424.2
гласове: 213

МнениеПуснато на: Fri Jan 08, 2010 11:07 pm    Заглавие:

Реално погледнато, ако аз успея да реша тази задача и се оженя за дъщерята на краля за 3 дни ще направя връзки и ще знам кое число ще каже царя, та ще подскажа на моя приятел, за да го уредя. Другият вариант е да направя бунт, да убия краля и да стана аз крал, при което и моят приятел получава автоматично по-малката дъщеря Mr. Green

А идеята на Баронов намалява значително нужната памет, лошото е, че трябва да смятаме колко двойки и петици има във всяко следващо число след това, което сме запомнили, а това при 88 000 си е бая сметка. Освен това ако разделим на интервали по √20 000 и царят ни каже някое число от края на интервала ще ни се стъжни живота(трябва да сметнем 140 числа от "отправното"). И все пак това би ни спестило доста памет.
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
Baronov
Напреднал


Регистриран на: 05 Jun 2008
Мнения: 316

Репутация: 55.4
гласове: 39

МнениеПуснато на: Sat Jan 09, 2010 12:06 am    Заглавие:

martosss написа:


А идеята на Баронов намалява значително нужната памет, лошото е, че трябва да смятаме колко двойки и петици има във всяко следващо число след това, което сме запомнили, а това при 88 000 си е бая сметка.


Това го смятаме с компютър за 1 сек. през трите дни, които имаме, за да се подготвим.
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
dgs
Редовен


Регистриран на: 23 Jun 2008
Мнения: 228

Репутация: 25Репутация: 25Репутация: 25
гласове: 13

МнениеПуснато на: Sat Jan 09, 2010 1:29 am    Заглавие:

Доколкото разбирам, говорим за добре известен и приложим метод от програмирането.
Обаче точно този метод ми е бяло петно в главата и ми е малко трудно да го коментирам в момента. Ако някъде в Интернет има нещо публикувано (за метода), моля пуснете някой линк за да не се чувствам като абориген.

Добре,
в крайна сметка въоръжени с този метод и нужната подготовка за него, бихте ли отишли на изпита или не ?
Доколкото разбирам сметките не са малко и при една дребна междинна грешка, съответно неверен краен резултат и хоп - на бесилото.


Виждам, че си падате по принцесите, та да взема да помогна малко с една друга идея ("по-математическа"), която в крайна сметка ако се развие добре, ... току виж всички се затичаме за изпита.

Идеята генерално е такава:
N!=1.2.3.4.5....(N-2).(N-1).N
Има ли начин да групираме множителите от 1 до N, в две-три (или малко повече) произведения, така че на всяко от тия произведения лесно да намерим последните две ненулеви цифри ?
Нещо такова:
N! = P1.P2.P3.P4
и съответно на всяко от тия три-четири на брой P-та да можем лесно да изчислим с молив и тетрадка последните две ненулеви цифри.

Защото, ако ги знаем тия две ненулеви цифри на всяко от P-тата, лесно ще намерим последната ненулева цифра на N! ... нали не бъркам дотук ?

Ако например P1 е произведението на всички числа завършващи на 5 и по-малки от N,
то имаме следното:
1. P1= 5.15.25.35.45.55.65.75.85. ...
2. N!=P1.”ощенещо”
2. С малко аритметика (нали за това имаме три дни) лесно се доказва, че ако N>=15, то последните две цифри на P1 са или 25 или 75 (тук даже не говорим за „ненулеви” цифри)
4. Пак с малко аритметика можем да се убедим, че ако знаем точната стойност на N, съвсем набързо можем да изчислим кои точно са тези две последни цифри – дали са 25 или 75.

Остана множителя „Още нещо”. Имам идея какво да го правя и него (ще го разбия на два три подможителя на първо време), но мисля да спра дотук с писането. ... Ако се наложи, пак ще се включа.
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
Baronov
Напреднал


Регистриран на: 05 Jun 2008
Мнения: 316

Репутация: 55.4
гласове: 39

МнениеПуснато на: Sat Jan 09, 2010 12:33 pm    Заглавие:

Интересна идея, но за съжаление няма да стане така. Ти допускаш, че ако знаеш последните 2 (ненулеви) цифри на а и последните 2 ненулеви цифри на b, то ще знаеш последната ненулева цифра на произведението ab. За съжаление това не е вярно. Ето ти няколко примера:
25*4=100
25*12=300
75*2=150.
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
Vladi_mnt
Редовен


Регистриран на: 17 Apr 2009
Мнения: 113

Репутация: 8.3Репутация: 8.3Репутация: 8.3Репутация: 8.3Репутация: 8.3Репутация: 8.3Репутация: 8.3Репутация: 8.3
гласове: 5

МнениеПуснато на: Sat Jan 09, 2010 8:00 pm    Заглавие:

В сайта http://cs.maycamp.com/ има алгоритъм за намиране на последната ненулева цифра ( + броя нули ) във N! N<=50 000. Баронов, твърдението на dgs е вярно, но с едно доуточнение Wink
Аз така поспорих с 1 от основателите на сайта Слави Маринов, че алгоритъмът му е грешен, понеже и аз смятах като Баронов. Но бях пропуснал изречение от анализа: " Произведението на всички останали числа (получени като махнем двойките и петиците, които образуват десятки) по модул 10 ни дава последната цифра. "
Тоест, по този метод примерите на Баронов стават:
rezult = 1; 25*4 = ( 2*5 ) * ( 2*5 ) които десетки махаме, rezult=1 си остава непроменено => 25*4 завършва на 1
rezult=1; 25*12 = 2*2*3*5*5 = (2*5)*(2*5)*3 rezult*3=3
rezult=1; 75*2 = 2*5*5*3 rezult*5*3=15, 15 % 10 = 5 Wink
Именно от алго-арената ми хрумна този алгоритъм и това е всъщност методът, който мислех да предложа Smile
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
Baronov
Напреднал


Регистриран на: 05 Jun 2008
Мнения: 316

Репутация: 55.4
гласове: 39

МнениеПуснато на: Sat Jan 09, 2010 8:21 pm    Заглавие:

Vladi_mnt написа:
В сайта http://cs.maycamp.com/ има алгоритъм за намиране на последната ненулева цифра ( + броя нули ) във N! N<=50 000. Баронов, твърдението на dgs е вярно, но с едно доуточнение Wink
Аз така поспорих с 1 от основателите на сайта Слави Маринов, че алгоритъмът му е грешен, понеже и аз смятах като Баронов. Но бях пропуснал изречение от анализа: " Произведението на всички останали числа (получени като махнем двойките и петиците, които образуват десятки) по модул 10 ни дава последната цифра. "
Тоест, по този метод примерите на Баронов стават:
rezult = 1; 25*4 = ( 2*5 ) * ( 2*5 ) които десетки махаме, rezult=1 си остава непроменено => 25*4 завършва на 1
rezult=1; 25*12 = 2*2*3*5*5 = (2*5)*(2*5)*3 rezult*3=3
rezult=1; 75*2 = 2*5*5*3 rezult*5*3=15, 15 % 10 = 5 Wink
Именно от алго-арената ми хрумна този алгоритъм и това е всъщност методът, който мислех да предложа Smile


Хаха е аз съм дал егати примерите... 2-цифрени числа
Методът на dgs, както го е описал, все още ми се струва грешен. Ето ти истински пример:
325*112=36400, а 25*12=300, т.е. ако знаеш само последните 2 цифри на числата няма как да намериш последната ненулева цифра на произведението им.

За съжаление не успях да разбера какво точно предлагаш ти. Това изречение, което цитираш на всички ни е ясно и то дава линеен алгоритъм за намиране на последната ненулева цифра на n!. Такъв алгоритъм, обаче е бавен за тази задача, тъй като имаме само един час на разположение БЕЗ компютър, което означава около 1000 операции и то, ако сме някаква машина за смятане.
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
dgs
Редовен


Регистриран на: 23 Jun 2008
Мнения: 228

Репутация: 25Репутация: 25Репутация: 25
гласове: 13

МнениеПуснато на: Sat Jan 09, 2010 10:33 pm    Заглавие:

Ах ти Baronov, убиец такъв, с какво лекота ме изпрати на бесилката.
Признавам си, заслужил съм си го Embarassed Embarassed

Но пък имам три дни, дано да успея да измисля нещо друго до изпита (друго и вярно) за да се измъкна от бесилката.

Ще помагате ли ?
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
dgs
Редовен


Регистриран на: 23 Jun 2008
Мнения: 228

Репутация: 25Репутация: 25Репутация: 25
гласове: 13

МнениеПуснато на: Sun Jan 10, 2010 5:02 am    Заглавие:

На път съм да отърва бесилката – по-точно, да отида на изпита и да го изкарам, а не да отърва бесилката защото съм си стоял в къщи. Благодарение на Baronov разбира се, че навреме ме светна за грубата грешка, която обаче се оказва поправима, макар и трудно поправима.
Тук е мястото да отбележа, че контрапримера на Baronov може да важи само ако някой от множителите се дели на 5. Ако никой от множителите не се дели на 5 и ако знаем последната цифра на множителите (тия последни цифри няма как да са 0), то ще знаем и последната цифра на произведението (също няма как да е 0)

И така, мисля, че с молив и химикалка, за един час мога да изчисля последната ненулева цифра на факториела на четири или пет цифрено число. Лошото обаче е, че за да го опиша как точно може да се проведе изчислението, ще ми трябват далеч повече часове и няколко дълги поста. Но пък възнамерявам накрая да направя и демонстрация на алгоритъма, с реални примери с четири или пет цифрени числа.

Може би е най-добре първо да опиша сбъркания алгоритъм – тъй като на практика коригираме негов проблем и после като описвам новия променен алгоритъм, ще стане по-ясно защо се налагат някои действия.

Няколко означения които често ще ползвам в постовете:
1. В контекста на факториела на някакво число A, с P5 ще означавам произведението на всички множители на A!, които завършват на 5, т.е.
P5=5.15.25.35.45.55.65.75. …
По същия начин, в контекста на A!, с P0 ще означавам произведението на всички множители на A!, които завършват на 0, т.е.
P0=10.20.30.40.50.60…
И с P ще означавам всички останали множители на A!
Т.е. A! = P.P0.P5

2. Нека за удобство N е четирицифрено (като в първоначалния вариант на условието)
Нека означим:
N4=N
N3=[N4/10] – целочислено делене, т.е. махнали сме най-дясната цифра на N4
N2=[N3/10] – целочислено делене, т.е. махнали сме най-дясната цифра на N3
N1=[N2/10] – целочислено делене, т.е. махнали сме най-дясната цифра на N2



И така, дадено ни е числото N (N=N4 – четирицифрено) и трябва да намерим неговата последна ненулева цифра.

1. Първата основна идея на сбъркания алгоритъм е (тая идея си остава вярна), че N4! се представя като произведение на няколко множителя, като единия от тях е N3!
N4! = P. P5. P0 = P.P5. N3!.100000000000000000000000…0000000
Съответно
N3! = P. P5. P0 = P.P5. N2!.1000000000000000…0000000
N2! = P. P5. P0 = P.P5. N1!.100000000…00000
N1!=N1!
N1! е едноцифрено и няма какво да го мъчим да го разбиваме на множители – директно си го смятаме с молива и тетрадката.
2. Втората основна идея в сбъркания алгоритъм е, че знаем последните цифри на P. Тая идея също си остава вярна. По-надолу ще опиша в детайли как се с молив и тетрадка лесно се изчисляват последните цифри на P
3. Третата основна идея също остава вярна (но безполезна) – знаем как лесно с молив и тетрадка да изчислим последните цифри на P5
4. Четвъртата основна идея всъщност е невярна (Baronov показа защо). Самата идея е, че с молив и тетрадка в няколко стъпки ще стигнем до последната ненулева цифра на N4!
- Първа стъпка: с молива и тетрадката изчисляваме N1! – нищо сложно, защото N1 е едноцифрено
- Втора стъпка:
разглеждаме N2! = P. P5. P0 = P.P5. N1!.100000000…00000
С молива и тетрадката изчисляваме последните цифри на P и P5,
Знаем последните цифри на P, P5 и N1! ==> можем с молива и тетрадката да изчислим последните ненулеви цифри на N2!
Всъщност това червеното "==>" е невярното нещо в алгоритъма
- Трета стъпка: същата като втората, но за N3! ... и същата грешка
- Четвърта стъпка: същата като третата, но за N4! ... и същата грешка


Как при тия стъпки се изчисляват последните цифри на P и P5.
На пръв поглед , това произведение P изглежда много страшно. Но всъщност въобще не е така и с лекота могат да бъдат изчислени последните две цифри на ръка - това е един от най-интересните (според мен) елементи в този алгоритъм.
Нека е дадено N и нека M e най-голямото число делящо се на 10 и по-малко от N
Нека разделим множителите на P на две части – тия които са по-големи от M (не повече от осем на брой) и тия които са по-малки от M
Нека да разгледаме произведението на осем поредни множителя по-малки от М и такива че първия от тях да завършва на 1
(k.10+1).(k.10+2).(k.10+3).(k.10+4).(k.10+6)(k.10+7) (k.10+8 )(k.10+9)
Можем лесно да докажем (чрез разкриване на скобите и хамалски сметки), че
76 = ((k.10+1).(k.10+2).(k.10+3).(k.10+4).(k.10+6)(k.10+7) (k.10+8 )(k.10+9) ) mod 100
Числото 76 има едно много хубаво свойство
76.76=5776 ==> (76.76) mod 100 = 76
(ЗАБЕЛЕЖКА извън темата: само три числа по-малки от 100 имат това свойство – това са 1, 25 и 76)
==>
P mod 100 = (76. (произведението на множителите по-големи от M)) mod 100
==> лесно с молив и тетрадка ще изчислим последните две цифри на P

Намирането на последните две цифри на P5 става още по-лесно, но мисля да не се задълбочавам по следните две причини:
- В променения алгоритъм P5 ще отпадне
- Мисля, че всеки от четящите тук е в състояние да установи че при N>15 тези последни две цифри са или 25 или 75 и се променят циклично според големината на числото N по следния начин 75,75,25,25,75,75,25,25,75,75,25,25,…

И понеже стана доста късно, мисля да спрем поста дотук. За променения алгоритъм ще пиша в отделен пост, а ако някой има въпроси по написаното до момента, да ги задава смело.
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
Покажи мнения от преди:   
   Форум за математика Форуми -> Забавна математика Часовете са според зоната GMT + 2 Часа
Страница 1 от 1

 
Идете на:  
Не Можете да пускате нови теми
Не Можете да отговаряте на темите
Не Можете да променяте съобщенията си
Не Можете да изтривате съобщенията си
Не Можете да гласувате в анкети
Може да прикачвате файлове
Може да сваляте файлове от този форум
Copyright © 2005-2021 math10.com.