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

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

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

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

05.06.2012, 23:50. Просмотров 1527. Ответов 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 числа
Посмотрите здесь:

Из массива JJ(100) в массив NN(100) перенести числа (элементы массива) сначала нечетные, а затем четные. C++
C++ Вычислить факториал 100!
C++ Нужно вычислить факториал 33, 100 и 1000 как можно проще
C++ Дан целочисленный массив А задается с экрана либо генерируется в пределах -100 до 100. Найти числа b1 b2 …bn равные суммам элементов строк
C++ Факториал числа
Факториал числа C++
Генерировать и вывести на экран массив с целого числа n случайных чисел от -100 до 100 C++
C++ факториал числа
C++ Двумерный целочисленный массив A(m;n) задается с экрана, либо генерируется в пределах от -100 до 100. Найти числа b1,b1,.bm, равные наименьшим значен
Факториал числа C++
C++ Рекурсия: факториал числа
C++ В интервале от 1 до 100, вывести все числа, кроме делящихся на три или имеющих в записи цифру три

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
diagon
Higher
1924 / 1190 / 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 ни в знаковом, ни в беззнаковом формате.
Yandex
Объявления
06.06.2012, 07:49     Факториал 100 или N числа
Ответ Создать тему
Опции темы

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