факториал |
1. Пользуйтесь тегами кода. - [code] ... [/code]
2. Точно указывайте язык, название и версию компилятора (интерпретатора).
3. Название темы должно быть информативным.
В описании темы указываем язык!!!
факториал |
first_day |
14.12.2007 16:34
Сообщение
#1
|
Пионер Группа: Пользователи Сообщений: 86 Пол: Мужской Реальное имя: Илья Репутация: 1 |
Нужно найти первую ненулевую цифру справа.
#include <iostream> До 25! считает все верно, на 25! глюк. Дальше некоторые факториалы не совпадают, предел тоже (1000000) не совпадает... Может кто подскажет почему? -------------------- Я бы изменил мир, да Бог не дает исходников.
|
volvo |
14.12.2007 17:01
Сообщение
#2
|
Гость |
Вообще-то года три назад в сети проскакивал вот этот алгоритм:
#include <iostream>А у тебя - все нормально, надо просто брать остаток не от деления на 100, а от деления на 1000: for(i=2;i<=n;i++), тогда все работает... Сообщение отредактировано: volvo - 14.12.2007 17:02 |
first_day |
14.12.2007 17:07
Сообщение
#3
|
Пионер Группа: Пользователи Сообщений: 86 Пол: Мужской Реальное имя: Илья Репутация: 1 |
беру остаток 1000 - несовпадения просто начинаются позже...
-------------------- Я бы изменил мир, да Бог не дает исходников.
|
Michael_Rybak |
14.12.2007 17:51
Сообщение
#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, которую нужно пропустить (т.е. количество нулей в конце ответа), а вычисляя факториал - пропускают. Можно и так. |
first_day |
14.12.2007 19:38
Сообщение
#5
|
Пионер Группа: Пользователи Сообщений: 86 Пол: Мужской Реальное имя: Илья Репутация: 1 |
Если я правильно понял - то вот так:
#include <iostream> А как подсчитать пропавшие двойки? Сообщение отредактировано: first_day - 14.12.2007 19:49 -------------------- Я бы изменил мир, да Бог не дает исходников.
|
first_day |
14.12.2007 21:55
Сообщение
#6
|
Пионер Группа: Пользователи Сообщений: 86 Пол: Мужской Реальное имя: Илья Репутация: 1 |
#include <iostream> Что не так? -------------------- Я бы изменил мир, да Бог не дает исходников.
|
Michael_Rybak |
14.12.2007 23:25
Сообщение
#7
|
Michael_Rybak Группа: Модераторы Сообщений: 1 046 Пол: Мужской Реальное имя: Michael_Rybak Репутация: 32 |
Молодчина.
Небольшой недочет - в последнем цикле тоже нужно брать по модулю 10 все время. Тогда все правильно будет. |
first_day |
15.12.2007 0:13
Сообщение
#8
|
Пионер Группа: Пользователи Сообщений: 86 Пол: Мужской Реальное имя: Илья Репутация: 1 |
Спасибо огромное , похоже, все получилось.
-------------------- Я бы изменил мир, да Бог не дает исходников.
|
Текстовая версия | 10.06.2024 13:07 |