Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 12, средняя оценка - 4.83
Jazz411
85 / 33 / 3
Регистрация: 12.03.2011
Сообщений: 234
Записей в блоге: 2
#1

Факториал 100 или N числа - C++

05.06.2012, 23:50. Просмотров 1560. Ответов 2
Метки нет (Все метки)

Доброго времени суток

Знаю что не 1 задаю этот вопрос, поэтому прежде чем создал тему внимательно прогуглил, но столкнулся с проблемой.

Я так понял что вычисление 100! можно как и 20!, то есть рекурсивно:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
#include "stdio.h"
 
__int64 factorial(__int64 n)
{
    return (n==0 ? 1 : n*factorial(n-1));
}
 
int main(int argc, char* argv[])
{
    for (int n=0; n<=16; n++)
        printf("%d! = %I64d\n",n,factorial(n));
    return 0;
}
При результатах больше 23 кажется идет переполнение. Предложение по дальнейшей реализации я нашел что можно записать число в массив но так и не понял как . Если кто делал или знает не поленитесь объяснить мне
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
05.06.2012, 23:50     Факториал 100 или N числа
Посмотрите здесь:

Вычислить факториал 100! - C++
Необходимо вычислить факториал 100! и представить его в виде массива из 158 элементов, один элемент - 1 цифра числа. Само число очень...

Нужно вычислить факториал 33, 100 и 1000 как можно проще - C++
Нужно вычислить фактариал 33, 100 и 1000 как можно проще

В интервале от 1 до 100, вывести все числа, кроме делящихся на три или имеющих в записи цифру три - C++
вывести цикл от 1 до 100, так чтобы числа имеющие 3 или которые можно разделить на 3 не выводились. пробовал через массивы, но нужно по...

Двумерный целочисленный массив A(m;n) задается с экрана, либо генерируется в пределах от -100 до 100. Найти числа b1,b1,.bm, равные наименьшим значен - C++
Двумерный целочисленный массив A(m;n) задается с экрана, либо генерируется в пределах от -100 до 100. Найти числа b1,b1,..bm, равные...

Дан целочисленный массив А задается с экрана либо генерируется в пределах -100 до 100. Найти числа b1 b2 …bn равные суммам элементов строк - C++
Дан целочисленный массив А(m,n) задается с экрана либо генерируется в пределах -100 до 100. Найти числа b1 b2 …bn равные суммам элементов...

факториал числа - C++
Почему вместо факториала компилятор выводит число 1 #include&lt;iostream&gt; using namespace std; int main() { int number; cout &lt;&lt;...

Факториал числа - C++
Напишите функцию для нахождения факториала числа. Результат возвращайте через заголовок функции. Объясните, что означает вернуть...

Факториал числа - C++
Помогите пожалуйста мне надо найти (5!)!

факториал числа n - C++
Как сделать в данной программе так, что бы она высчитывала факториал лишь в диапазоне от 1 до 12. Заранее спасибо. #include &lt;iostream&gt; ...

Факториал числа - C++
Мне надо найти факториал числа 100 . Помогите пажалуста.


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
diagon
Higher
1928 / 1194 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
06.06.2012, 07:23     Факториал 100 или N числа #2
Цитата Сообщение от Jazz411 Посмотреть сообщение
Я так понял что вычисление 100! можно как и 20!, то есть рекурсивно:
100! будет очень долго считаться с помощью рекурсии. Лучше делать это в цикле.

Чтобы посчитать такой факториал, нужно реализовать длинную арифметику, а именно - умножение длинного числа на короткое.
taras atavin
Ушёл с форума.
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
06.06.2012, 07:49     Факториал 100 или N числа #3
Цитата Сообщение от Jazz411 Посмотреть сообщение
Я так понял что вычисление 100! можно как и 20!, то есть рекурсивно:
Нет. Во-первых 20! влазит хотя бы в 64 бита, а 100! не влезет и в 128, а во-вторых рекурсия хороша как раз при небольшом числе вложенных вызовов, а чем их больше, тем больше будет и отставание от явного цикла, который есть переход сразу к подставновке значений, которые могли быть получены в рекурсивных вызовах, и перерасход памяти. И это ещё больше сказывается на больших данных, а длинная арифметика - как раз то самое и есть.

Добавлено через 12 минут
А максимум, что влазит в 128 бит, это 33 в знаковом формате и 34! в беззнаковом. В 256 бит влазит максимум 57!, в 512 97! в знаковом формате и 98! в беззнаковом, а 100! требует 525, или 526 бит, а с учётом размера байта 528 бит, или 66 байт. 101! уже не лезет и в 528 бит ни в знаковом, ни в беззнаковом формате.

Добавлено через 1 минуту
А по-хорошему рекурсивный факториал и до 6! надо заменять явным циклом.

Добавлено через 2 минуты
При числе шагов больше 5-ти рекурсия имеет смысл только на иерархических данных и для задач, не имеющих не рекурсивных постановок. Пример - обработка деревьев.

Добавлено через 4 минуты
А до 170! нужны уже 1020, или 1021 бит, а с учётом размера байта 1024 бита, но 171! уже не лезит и в 1024 ни в знаковом, ни в беззнаковом формате.
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru