| Предишната тема :: Следващата тема |
| Автор |
Съобщение |
martosss
VIP Gold
Регистриран на: 17 Mar 2007
Мнения: 3937
Местожителство: Somewhere over the rainbow
  
гласове: 213
|
 Пуснато на: Sun Nov 15, 2009 9:09 pm Заглавие: факториел |
|
|
| Има ли начин за намиране на последната ненулева цифра от факториела на някакво число(N<5000) без да се смята самият факториел?
|
|
| Върнете се в началото |
|
 |
Реклама
|
| Пуснато на: Заглавие: Реклама |
|
|
|
|
|
| Върнете се в началото |
|
|
mkmarinov
Напреднал
Регистриран на: 08 Nov 2008
Мнения: 358
Местожителство: Враца
гласове: 32
|
| Пуснато на: Sun Nov 15, 2009 9:31 pm Заглавие: |
|
|
Директна формула не мога да ти дам (може и да има, може и да няма).
Представяш числото в каноничен вид, като отделяш степените на десятката и ги премахваш. След това започваш да умножаваш (и вземаш остатъка по модул 10 за следващото умножение).
|
|
| Върнете се в началото |
|
|
martosss
VIP Gold
Регистриран на: 17 Mar 2007
Мнения: 3937
Местожителство: Somewhere over the rainbow
гласове: 213
|
| Пуснато на: Sun Nov 15, 2009 9:47 pm Заглавие: |
|
|
добре, ама като имаш примерно 3500! е кофти да тръгна да го представям в каноничен вид... трябва ми да му взема последната ненулева цифра, в програма на С++  принципно вече го направих за числа <15 625, като ги разгледам по мод 100 000, ама е много тегаво, няма ли по-добър начин? 
Не ми е ясно това представяне в каноничен вид как ще стане, можеш ли да ми дадеш код?
|
|
| Върнете се в началото |
|
|
ins-
Фен на форума
Регистриран на: 03 Oct 2007
Мнения: 567
Местожителство: Роман, София
гласове: 28
|
| Пуснато на: Sun Nov 15, 2009 11:09 pm Заглавие: |
|
|
| Задачата е "хитра" ... давана е преди години на конкурс по програмиране. За да я решиш използвай свойствата на деление с остатък (mod).
|
|
| Върнете се в началото |
|
|
martosss
VIP Gold
Регистриран на: 17 Mar 2007
Мнения: 3937
Местожителство: Somewhere over the rainbow
гласове: 213
|
| Пуснато на: Sun Nov 15, 2009 11:13 pm Заглавие: |
|
|
 кажете нещо по-насочващо, защото това ми е ясно, въпросът е по кой модул да сравнявам...
|
|
| Върнете се в началото |
|
|
ins-
Фен на форума
Регистриран на: 03 Oct 2007
Мнения: 567
Местожителство: Роман, София
гласове: 28
|
| Пуснато на: Sun Nov 15, 2009 11:22 pm Заглавие: |
|
|
| 10 ... но много пъти
|
|
| Върнете се в началото |
|
|
ins-
Фен на форума
Регистриран на: 03 Oct 2007
Мнения: 567
Местожителство: Роман, София
гласове: 28
|
| Пуснато на: Sun Nov 15, 2009 11:35 pm Заглавие: |
|
|
1.2.3.4.5.6.7.8.9.10.11 = ?
Последната различна от нула цифра на:
1! = (1 mod 10)
2! = (1 mod 10) * (2 mod 10)
3! = (1 mod 10) * (2 mod 10) * (3 mod 10)
4! = ((1 mod 10) * (2 mod 10) * (3 mod 10) * (4 mod 10)) mod 10 - тук има тънък момент ... извършваш операцията над произведението всеки път когато превиши 10 ... може да ти се наложи и в цикълче да влезеш или да се направиш на мъж и да ползваш рекурсия.
Идеята е следната намираш последната различна от "0" цифра на (n-1)! = A. С помощта на цикъл или рекурсия и операцията mod 10. Намираш последната различна от "0" цифра на n = B. Ако А*B > 10 извършваш mod 10. Намереното е необходимата ти цифра.
Ако имаш въпроси - питай.
|
|
| Върнете се в началото |
|
|
mkmarinov
Напреднал
Регистриран на: 08 Nov 2008
Мнения: 358
Местожителство: Враца
гласове: 32
|
| Пуснато на: Mon Nov 16, 2009 12:32 am Заглавие: |
|
|
| martosss написа: |
Не ми е ясно това представяне в каноничен вид как ще стане, можеш ли да ми дадеш код? |
Ето ти един алгоритъм за разлагане на число на прости множители (писал съм го отдавна; не гарантирам, че точно този код ще ти сработи, но е нещо подобно):
| Код: | int mn[MAXM]; //mnojiteli
int power[MAXM]; //stepen na suotv. mnojitel
int i = -1; // iterator na masivite
int k = 2; //delitel
void simpleDiv(unsigned n)
{
if(n==1) return;
if((n%k) == 0) {
if(mn[i] != k) i++;
mn[i] = k;
power[i]++;
simpleDiv(n/k);
}
if(n%k) {
k++;
simpleDiv(n);
}
}
|
.
Ти трябва да отделиш десетките (т.е. намаляваш power[5], power[2] с по min(power[5],power[2])), след това правиш каквото ins казва  .
//Не знам дали ще е по-бързо с разлагане или без.
|
|
| Върнете се в началото |
|
|
martosss
VIP Gold
Регистриран на: 17 Mar 2007
Мнения: 3937
Местожителство: Somewhere over the rainbow
гласове: 213
|
| Пуснато на: Mon Nov 16, 2009 9:04 am Заглавие: |
|
|
| ins- написа: |
Идеята е следната намираш последната различна от "0" цифра на (n-1)! = A. С помощта на цикъл или рекурсия и операцията mod 10. Намираш последната различна от "0" цифра на n = B. Ако А*B > 10 извършваш mod 10. Намереното е необходимата ти цифра. |
Добре, ето ви един свеж пример
имаме да намерим примерно на 25! последната ненулава цифра.
По вашия метод имаме, че
посл. ненул. цифра на 24! е 6(намерили сме я някак си, аз лично с калкулатора)
последната цифра на 25, тоест 5
след което да умножим 6 по 5 да получим 30...сега по гореописания метод(който тука куца, защото след като сме получили 10k разглеждане по мод 10 няма да ни помогне) по-скоро трява да намерим пак последната ненулева цифра, която обаче НЕ Е 4, а е 3 Както виждате, за да намерим последната цифра на 25! този трик не работи.
620448401733239439360000 - 24!
15511210043330985984000000 - 25!
Друг прост пример, ако последната цифра ви е 2 и умножавате по 5, то резултатът е 10, значи цифрата е 1
Ако последните две цифри са 12 обаче, то резултатът е 60, тоест 6
Извод - когато минаваме в по-старши разряд трява да следим и него, защото в противен случай се получават бози.
Сега вече се надявам да са се поизяснили нещата и да сте разбрали, че с мод 10 по този начин не става.
| mkmarinov написа: | Ти трябва да отделиш десетките (т.е. намаляваш power[5], power[2] с по min(power[5],power[2])), след това правиш каквото ins казва .
//Не знам дали ще е по-бързо с разлагане или без. |
Това е добра идея, обаче за целта първо трябва да имам числото 24!=.... и това многоточие от 15-20 цифри да го разложа на множители... Това е крайно неприятно.
Аз ако трябва да смятам на колко точно е равен факториелът ще го сметна, след което ще деля n пъти на 10(като търся посл. цифра да дава остатък по модул 10, различен от 0) и ще взема последната цифра - така хем намирам броя нули след тази цифра(това в оригиналната задача също се търси ), хем намирам и търсената цифра.
Аз обаче съм нагъл и искам без да смятам на колко точно е равен факториелът, да намеря тази цифра.
За броя нули след нея ми е лесно - дели се числото, примерно за 45!, на 5, докато се получи 0 и резултатите се прибавят(целочислено деление). Така получаваме 45:5=9, 9:5=1, значи 9+1=10 нули Както виждате тази задача не представлява голям научен интерес, затова и не съм я пуснал(така или иначе я реших и тук).
Сега, обаче, идва тежкият въпрос как да намерим последната цифра...
Ако може и за това да дадете някоя интересна идея, ще е добре(не че ще ми свърши работа, просто ми е интересно има ли такъв алгоритъм, който не включва намирането на стойността на факториела.).
Иначе благодаря за разлагането, то също може да ми е полезно да го знам като метод
|
|
| Върнете се в началото |
|
|
allier
Начинаещ
Регистриран на: 14 Aug 2008
Мнения: 65
гласове: 6
|
| Пуснато на: Mon Nov 16, 2009 11:43 am Заглавие: |
|
|
Lesno moje da se izmisli neshto koeto da smqta poslednata cifra. Eto kakvo se setih, sigurno moje i po lesno:
Puskash edin cikul ot 1 do n, kato na vseki hod pazish broya na dvoikite i na peticite, ostanlite mnojiteli si gi umnojavash s mod za posledna cifra.
V kraya, vadish ot broya na dvoikite broya na peticite, i umnojvash dvoikite s otdelen cikul s mod (ili puk direktno broya na dvoikite mod 4 kakto sa po ostatuci).
Poslednata cifra e proizvedenieto na tezi dve chisla - ednoto koeto idva ot cikula, i drugoto koeto idva ot ostavashtite dvoiki.
|
|
| Върнете се в началото |
|
|
mkmarinov
Напреднал
Регистриран на: 08 Nov 2008
Мнения: 358
Местожителство: Враца
гласове: 32
|
| Пуснато на: Mon Nov 16, 2009 3:43 pm Заглавие: |
|
|
| martosss написа: |
| mkmarinov написа: | Ти трябва да отделиш десетките (т.е. намаляваш power[5], power[2] с по min(power[5],power[2])), след това правиш каквото ins казва .
//Не знам дали ще е по-бързо с разлагане или без. |
Това е добра идея, обаче за целта първо трябва да имам числото 24!=.... и това многоточие от 15-20 цифри да го разложа на множители...
|
Не трябва да смяташ факториела. Просто смяташ кои са множителите на числата от 1 до n и после им събираш степените . Това естествено ще иска малка промяна на функцията simpleDiv().
Този алгоритъм може да се подобри значително с динамично оптимиране.
|
|
| Върнете се в началото |
|
|
krainik
Фен на форума
Регистриран на: 01 May 2009
Мнения: 697
гласове: 44
|
| Пуснато на: Mon Nov 16, 2009 4:03 pm Заглавие: |
|
|
| ins- написа: | | Задачата е "хитра" ... давана е преди години на конкурс по програмиране. За да я решиш използвай свойствата на деление с остатък (mod). |
Не думай
|
|
| Върнете се в началото |
|
|
martosss
VIP Gold
Регистриран на: 17 Mar 2007
Мнения: 3937
Местожителство: Somewhere over the rainbow
гласове: 213
|
| Пуснато на: Mon Nov 16, 2009 9:37 pm Заглавие: |
|
|
| Да, методът на allier ми харесва, благодаря
|
|
| Върнете се в началото |
|
|
Vladi_mnt
Редовен
Регистриран на: 17 Apr 2009
Мнения: 113
гласове: 5
|
| Пуснато на: Tue Nov 17, 2009 2:41 pm Заглавие: |
|
|
Добре, аз имам един въпрос и заради него насочих вниманието на Марто, който беше така любезен да постне проблема тук( БЛАГОДАРРРРРРРРЯЯЯЯ МАРТО! ). Та, значи, ето ми парчето програма, което ми намира броя нули и последната ненулева цифра:
| Код: | void Last_digit(int n, int& count, int& digit)
{
long fakt=1;
for(int i=1; i<=n; i++)
{
fakt*=i;
while(fakt%10==0) { fakt/=10; count++; }
fakt%=10;
}
digit=fakt;
} |
Та, при изпълнение на тестовете ми дава грешни отговори за числа по-големи или равни на 28. Да, но аз мисля че алгоритъмът ми е верен и бачка. Помагайте! ( т.е. кажете ми къде ми е грешката, ако имам такава )
|
|
| Върнете се в началото |
|
|
garion
Напреднал
Регистриран на: 10 Jan 2008
Мнения: 373
гласове: 13
|
| Пуснато на: Tue Nov 17, 2009 4:12 pm Заглавие: |
|
|
| Виж малко по-нагоре поста на martoss, който ти е обяснил как се проваля този алгоритъм
|
|
| Върнете се в началото |
|
|
Vladi_mnt
Редовен
Регистриран на: 17 Apr 2009
Мнения: 113
гласове: 5
|
| Пуснато на: Tue Nov 17, 2009 9:26 pm Заглавие: |
|
|
OK, а защо следният код работи безупречно в интервала [0;50000]:
| Код: | void Last_digit(int n, int& count, int& digit)
{
long fakt=1;
for(int i=1; i<=n; i++)
{
fakt*=i;
while(fakt%10==0) { fakt/=10; count++; }
fakt%=1000000; WARNING
}
digit=fakt%10;
} |
Това нещо //WARNING// не мога да си го обясня ( все си мисля че нулите трябва да са log5 от числото n ). Възможно ли е да е така? И ако да - защо?
|
|
| Върнете се в началото |
|
|
krainik
Фен на форума
Регистриран на: 01 May 2009
Мнения: 697
гласове: 44
|
| Пуснато на: Tue Nov 17, 2009 9:48 pm Заглавие: |
|
|
| Броя на нулите е точно [tex]\sum_{i=1}^{\infty} \lfloor \frac{n!}{5^i}\rfloor[/tex]. Това, че сумата е безкрайна не трябва да ни плаши, тъй като след определен член нататък са нули.
|
|
| Върнете се в началото |
|
|
garion
Напреднал
Регистриран на: 10 Jan 2008
Мнения: 373
гласове: 13
|
| Пуснато на: Wed Nov 18, 2009 9:29 am Заглавие: |
|
|
| Vladi_mnt написа: | OK, а защо следният код работи безупречно в интервала [0;50000]:
| Код: | void Last_digit(int n, int& count, int& digit)
{
long fakt=1;
for(int i=1; i<=n; i++)
{
fakt*=i;
while(fakt%10==0) { fakt/=10; count++; }
fakt%=1000000; WARNING
}
digit=fakt%10;
} |
Това нещо //WARNING// не мога да си го обясня ( все си мисля че нулите трябва да са log5 от числото n ). Възможно ли е да е така? И ако да - защо? |
Дай да го видим какво казва тоя warning.
А по другия въпрос - АКО работи наистина безупречно то това е че използваш достатъчно последни цифри, които ти го гарантират, но първо трябва да си абсолютно сигурен че наистина работи - например сигурен ли си каква е да речем последната цифра на 4738! че да можеш да го провериш????
|
|
| Върнете се в началото |
|
|
martosss
VIP Gold
Регистриран на: 17 Mar 2007
Мнения: 3937
Местожителство: Somewhere over the rainbow
гласове: 213
|
| Пуснато на: Wed Nov 18, 2009 10:04 am Заглавие: |
|
|
| аз го проверих с разглеждане на 5 цифри и работеше до 15624(следващата цифра е 5^6), иначе методът на аллиер според мен ще работи с най-малко сметки.
|
|
| Върнете се в началото |
|
|
Vladi_mnt
Редовен
Регистриран на: 17 Apr 2009
Мнения: 113
гласове: 5
|
| Пуснато на: Wed Nov 18, 2009 7:01 pm Заглавие: |
|
|
| garion написа: | | Vladi_mnt написа: | OK, а защо следният код работи безупречно в интервала [0;50000]:
| Код: | void Last_digit(int n, int& count, int& digit)
{
long fakt=1;
for(int i=1; i<=n; i++)
{
fakt*=i;
while(fakt%10==0) { fakt/=10; count++; }
fakt%=1000000; WARNING
}
digit=fakt%10;
} |
Това нещо //WARNING// не мога да си го обясня ( все си мисля че нулите трябва да са log5 от числото n ). Възможно ли е да е така? И ако да - защо? |
Дай да го видим какво казва тоя warning.
А по другия въпрос - АКО работи наистина безупречно то това е че използваш достатъчно последни цифри, които ти го гарантират, но първо трябва да си абсолютно сигурен че наистина работи - например сигурен ли си каква е да речем последната цифра на 4738! че да можеш да го провериш???? |
Ами, точно за числото което даде няма как да съм сигурен, но при всички тестови примери от състезанието ми дава верен отговор.
|
|
| Върнете се в началото |
|
|
krainik
Фен на форума
Регистриран на: 01 May 2009
Мнения: 697
гласове: 44
|
| Пуснато на: Thu Nov 19, 2009 2:42 pm Заглавие: |
|
|
Интересно задача на същата тематика е следната:
Ако означим с [tex]d_{n}[/tex] последната ненулева цифра на [tex]n![/tex], то редицата [tex]d_{1},d_{2},...[/tex] не е периодична.
|
|
| Върнете се в началото |
|
|
martosss
VIP Gold
Регистриран на: 17 Mar 2007
Мнения: 3937
Местожителство: Somewhere over the rainbow
гласове: 213
|
| Пуснато на: Thu Nov 19, 2009 8:56 pm Заглавие: |
|
|
| еми да, защото постоянно ти се умножава по по-големи и по-големи числа, някои от които примерно са прости... няма как
|
|
| Върнете се в началото |
|
|
krainik
Фен на форума
Регистриран на: 01 May 2009
Мнения: 697
гласове: 44
|
| Пуснато на: Thu Nov 19, 2009 9:32 pm Заглавие: |
|
|
| Да, перфектно доказателство няма що. На никой не му пука дали умножаваш с просто или съставно - за последната цифра ти трябва остатъка по модул 10. Моля ти се, следващия път поне се опитай да вникнеш в условието,а не да се излагаш с такива постове.
|
|
| Върнете се в началото |
|
|
mkmarinov
Напреднал
Регистриран на: 08 Nov 2008
Мнения: 358
Местожителство: Враца
гласове: 32
|
| Пуснато на: Thu Nov 19, 2009 11:27 pm Заглавие: |
|
|
Естествено че не е.
Нека [tex]n!=2^p.10^q.r[/tex], където r не се дели нито на 2, нито на 5, нито на 10. Очевидно [tex]p>q[/tex] => [tex]\frac{n!}{10^q}=2^{p-q}.r[/tex]. Това е точно n!, само че без нулите накрая. Ако редицата е периодична, трябва да има някое n, за което [tex]2^{p-q}.r=1 \equiv 1! (mod 10)[/tex], но това е невъзможно.
|
|
| Върнете се в началото |
|
|
krainik
Фен на форума
Регистриран на: 01 May 2009
Мнения: 697
гласове: 44
|
| Пуснато на: Thu Nov 19, 2009 11:39 pm Заглавие: |
|
|
| И защо трябва да има такова [tex]n[/tex]? Например, редицата 2,4,6,8,0,2,.. е периодична, но няма член единица в себе си. Освен това няма нужда да пишеш, че [tex]r[/tex] не се дели нито на 2, нито на 5, нито на 10. От първите две следва третото. Предполагам, че и в каноничното разлагане на [tex]n![/tex] си написал 10 вместо 5 по погрешка.
|
|
| Върнете се в началото |
|
|
r2d2
VIP
Регистриран на: 28 Feb 2007
Мнения: 1936
Местожителство: in the galaxy (Far Far Away)
гласове: 179
|
| Пуснато на: Thu Nov 19, 2009 11:57 pm Заглавие: |
|
|
Реших да се науча да пиша програми. Ето какво сътворих. Мисля, че работи.
Моля за коментари.
| Код: |
// new.cpp : Pokazva poslednata nenuleva cifra na n!
//
#include "stdafx.h"
#include <iostream>
int main()
{
using namespace std;
cout << "enter a number" << endl;
int fact;
int br2=0,br5=0,rest=1;
cin >> fact;
int i,n1;
for (i=2;i<=fact;i++)
{
n1=i;
while (n1%10 == 0) n1 /=10; //mahni poslednite nuli
while (n1%2 == 0) //kolko stepeni na 2 ostavat
{n1 /=2;
br2++;
}
while (n1%5 == 0) //kolko stepeni na 5 ostavat
{n1 /=5;
br5++;
}
rest *= n1%10;
rest = rest%10;
}//4isloto e vyv vid 2^br2 * 5^br5 *rest
br2 -=br5; //mahni nuli
br5 = br5%2; // 5^k = 5 mod10
br2 = br2%4;
if (br2 == 1) rest *=2; //2^(4k+1=2) mod10
else if (br2 == 2) rest *=4;
else if (br2 == 3) rest *=8;
else rest *=6;
cout << fact <<"! ima posledna zna4e6ta cifra " << rest%10 <<endl;
return 0;
}
|
[/code]
| Description: |
|
| Големина на файла: |
6.37 KB |
| Видяна: |
8610 пъти(s) |
|
|
|
| Върнете се в началото |
|
|
Baronov
Напреднал
Регистриран на: 05 Jun 2008
Мнения: 316
гласове: 39
|
| Пуснато на: Fri Nov 20, 2009 3:38 am Заглавие: |
|
|
| r2d2 написа: | Реших да се науча да пиша програми. Ето какво сътворих. Мисля, че работи.
Моля за коментари.
| Код: |
// new.cpp : Pokazva poslednata nenuleva cifra na n!
//
#include "stdafx.h"
#include <iostream>
int main()
{
using namespace std;
cout << "enter a number" << endl;
int fact;
int br2=0,br5=0,rest=1;
cin >> fact;
int i,n1;
for (i=2;i<=fact;i++)
{
n1=i;
while (n1%10 == 0) n1 /=10; //mahni poslednite nuli
while (n1%2 == 0) //kolko stepeni na 2 ostavat
{n1 /=2;
br2++;
}
while (n1%5 == 0) //kolko stepeni na 5 ostavat
{n1 /=5;
br5++;
}
rest *= n1%10;
rest = rest%10;
}//4isloto e vyv vid 2^br2 * 5^br5 *rest
br2 -=br5; //mahni nuli
br5 = br5%2; // 5^k = 5 mod10
br2 = br2%4;
if (br2 == 1) rest *=2; //2^(4k+1=2) mod10
else if (br2 == 2) rest *=4;
else if (br2 == 3) rest *=8;
else rest *=6;
cout << fact <<"! ima posledna zna4e6ta cifra " << rest%10 <<endl;
return 0;
}
|
[/code] |
Test Case Arguments : fact = 1
Expected = 1
Received = 6
Result : Baronov has successfully challenged r2d2's 250 point problem for 25 points.
|
|
| Върнете се в началото |
|
|
r2d2
VIP
Регистриран на: 28 Feb 2007
Мнения: 1936
Местожителство: in the galaxy (Far Far Away)
гласове: 179
|
| Пуснато на: Fri Nov 20, 2009 9:31 am Заглавие: |
|
|
Да!
Написаното пресмята последната зна4еща цифра за числата от 2 нагоре.
|
|
| Върнете се в началото |
|
|
martosss
VIP Gold
Регистриран на: 17 Mar 2007
Мнения: 3937
Местожителство: Somewhere over the rainbow
гласове: 213
|
| Пуснато на: Fri Nov 20, 2009 9:32 am Заглавие: |
|
|
| r2d2 написа: |
rest *= n1%10;
rest = rest%10;
br5 = br5%2; // 5^k = 5 mod10 |
Първото мисля можете да го запишете като една команда:
rest=(rest*(n1%10))%10;
а второто като че ли изобщо е излишно - след като извадите петиците, те вече не ви трябват.
Иначе решението е добро - по модела на allier
|
|
| Върнете се в началото |
|
|
mkmarinov
Напреднал
Регистриран на: 08 Nov 2008
Мнения: 358
Местожителство: Враца
гласове: 32
|
| Пуснато на: Fri Nov 20, 2009 11:10 am Заглавие: |
|
|
| krainik написа: | | И защо трябва да има такова [tex]n[/tex]? Например, редицата 2,4,6,8,0,2,.. е периодична, но няма член единица в себе си. Освен това няма нужда да пишеш, че [tex]r[/tex] не се дели нито на 2, нито на 5, нито на 10. От първите две следва третото. Предполагам, че и в каноничното разлагане на [tex]n![/tex] си написал 10 вместо 5 по погрешка. |
За десетките и петиците си прав.
Такова n трябва да има защото първият член на редицата трябва да се повтаря през дадения период.
|
|
| Върнете се в началото |
|
|
|
Меню
Регистрирайте се
