IPB
ЛогинПароль:

> Внимание!

1. Пользуйтесь тегами кода. - [code] ... [/code]
2. Точно указывайте язык, название и версию компилятора (интерпретатора).
3. Название темы должно быть информативным.
В описании темы указываем язык!!!

Наладить общение поможет, если вы подпишитесь по почте на новые темы в этом форуме.

 
 Ответить  Открыть новую тему 
> факториал
сообщение
Сообщение #1


Пионер
**

Группа: Пользователи
Сообщений: 86
Пол: Мужской
Реальное имя: Илья

Репутация: -  1  +


Нужно найти первую ненулевую цифру справа.

#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) не совпадает... Может кто подскажет почему?


--------------------
Я бы изменил мир, да Бог не дает исходников.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


Гость






Вообще-то года три назад в сети проскакивал вот этот алгоритм:

#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;
}
, тогда все работает...

Сообщение отредактировано: volvo -
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Пионер
**

Группа: Пользователи
Сообщений: 86
Пол: Мужской
Реальное имя: Илья

Репутация: -  1  +


беру остаток 1000 - несовпадения просто начинаются позже...


--------------------
Я бы изменил мир, да Бог не дает исходников.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


Когда ты берешь остаток по модулю 1000, ты фактически утверждаешь следующее: первая_ненулевая_цифра_справа (x * y) = первая_ненулевая_цифра_справа ((x mod 1000) * y) для любых x, y.

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

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

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

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

В решении, приведенном volvo, делают наоборот - сначала считают степень 10, которую нужно пропустить (т.е. количество нулей в конце ответа), а вычисляя факториал - пропускают. Можно и так.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5


Пионер
**

Группа: Пользователи
Сообщений: 86
Пол: Мужской
Реальное имя: Илья

Репутация: -  1  +


Если я правильно понял - то вот так:
#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 -


--------------------
Я бы изменил мир, да Бог не дает исходников.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6


Пионер
**

Группа: Пользователи
Сообщений: 86
Пол: Мужской
Реальное имя: Илья

Репутация: -  1  +


#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;
}

Что не так?


--------------------
Я бы изменил мир, да Бог не дает исходников.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #7


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


Молодчина.

Небольшой недочет - в последнем цикле тоже нужно брать по модулю 10 все время. Тогда все правильно будет.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #8


Пионер
**

Группа: Пользователи
Сообщений: 86
Пол: Мужской
Реальное имя: Илья

Репутация: -  1  +


Спасибо огромное good.gif , похоже, все получилось. smile.gif


--------------------
Я бы изменил мир, да Бог не дает исходников.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 29.03.2024 1:31
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name