Помощь - Поиск - Пользователи - Календарь
Полная версия: факториал
Форум «Всё о Паскале» > Современный Паскаль и другие языки > Ада и другие языки
first_day
Нужно найти первую ненулевую цифру справа.

#include <iostream>
using namespace std;
int main ()
{
int x=1,i,n;
cin>>n;
for(i=2;i<=n;i++)
{
x=x*i;
if (x%10==0)
while (x%10==0)
x=x/10;
x=x%100;
}
cout<<x%10;
return 0;
}


До 25! считает все верно, на 25! глюк. Дальше некоторые факториалы не совпадают, предел тоже (1000000) не совпадает... Может кто подскажет почему?
volvo
Вообще-то года три назад в сети проскакивал вот этот алгоритм:

#include <iostream>
using namespace std;
int main ()
{
int n;
cin >> n;

int k = n / 5;
int s = 0;
while(k) {
s += k;
k /= 5;
}

int t = 1;
for(int i = 2; i <= n; i++) {
int j = i;
while(!(j % 5)) j /= 5;

while(s > 0 && !(j % 2)) {
j /= 2; s -= 1;
}
t = t * (j % 10) % 10;
}
cout << t << endl;
return 0;
}

А у тебя - все нормально, надо просто брать остаток не от деления на 100, а от деления на 1000:
	for(i=2;i<=n;i++)
{
x=x*i;
if (x%10==0)
while (x%10==0)
x=x/10;
x=x%1000;
}
, тогда все работает...
first_day
беру остаток 1000 - несовпадения просто начинаются позже...
Michael_Rybak
Когда ты берешь остаток по модулю 1000, ты фактически утверждаешь следующее: первая_ненулевая_цифра_справа (x * y) = первая_ненулевая_цифра_справа ((x mod 1000) * y) для любых x, y.

Это утверждение, конечно, неверно.

Чтобы понять почему, рассмотри сначала то же утверждение, но вместо 1000 поставь 10. Сразу станет очевидно.

Проще всего сделать так. Понятно, что проблема в двойках и пятерках. Когда считаешь факториал, сохраняй только последнюю цифру, но при этом никогда не умножай на 2 или 5 (т.е. сначала дели очередной множитель на 2 и 5, пока делится).

Получив последнюю цифру результата таким способом, остается домножить ее на недостающую степень двойки (понятно, что двоек всегда пропадет больше, чем пятерок).

В решении, приведенном volvo, делают наоборот - сначала считают степень 10, которую нужно пропустить (т.е. количество нулей в конце ответа), а вычисляя факториал - пропускают. Можно и так.
first_day
Если я правильно понял - то вот так:
#include <iostream>
using namespace std;
int main ()
{
int n,i,q,x=1;
cin>>n;
for(i=1;i<=n;i++)
{
q=i;
while (q%5==0)
q=q/5;
while (q%2==0)
q=q/2;
x=x*q;
x=x%10;
}
cout<<x;
return 0;
}

А как подсчитать пропавшие двойки?
first_day
#include <iostream>
using namespace std;
int main ()
{
int n,i,q,x=1,count1=0,count2=0,st=0;
cin>>n;
for(i=1;i<=n;i++)
{
q=i;
while (q%5==0)
{
q=q/5;
count1++;
}
while (q%2==0)
{
q=q/2;
count2++;
}
x=x*q;
x=x%10;
}
st=count2-count1;
for(i=1;i<=st;i++)
x=x*2;
x=x%10;
cout<<x;
return 0;
}

Что не так?
Michael_Rybak
Молодчина.

Небольшой недочет - в последнем цикле тоже нужно брать по модулю 10 все время. Тогда все правильно будет.
first_day
Спасибо огромное good.gif , похоже, все получилось. smile.gif
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.