Вычисление факториала через двусвязный список

@MichaelNV · Регистрация: 04.03.2011

Студворк — интернет-сервис помощи студентам

Здравствуйте!

Помогите, пожалуйста, с решением задачи: вычислить факториал 100!, используя двусвязный динамический список.
По какому алгоритму должен вычисляться факториал? Т.е. вначале список заполняется значениями от 1 до 100, затем нужно по нему пробежаться и перемножить все значения. Но как пробегаться? Сразу с двух концов к центру?
Или каким то иным способом это делается?

Код, который есть:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <iostream>
 
using namespace std;
 
int main()
{
    struct Node {
        int value;
        Node* prev;
        Node* next;
        Link(const int& v, Link* p = 0, Link* n = 0)
            : value(v), prev(p), next(n) {}
    };
 
    Link* insert(Link* p, Link* n) {
        if (n==0) return p;
        if (p==0) return n;
        n->next = p;
        if (p->prev) p->prev->next = n;
        n->prev = p->prev;
 
        p->prev = n;
        return n;
    }  
 
    return 0;
}

@kolobok919 · 14.06.2015, 14:25

Вот вам две версии факториала:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
typedef unsigned long long ULONG;
 
ULONG Factorial(ULONG value)
{
    ULONG result = 1;
 
    while(value > 1)
        result *= value--;
 
    return result;
}
 
ULONG Factorial2(ULONG value)
{
    return value <= 1 ? 1 : value * Factorial2(value - 1);
}

Если хотите считать 100! используйте аналогичные функции, но заменить ULONG на тип для работы с большими числами.

@MichaelNV · 14.06.2015, 14:34 **[ТС]**

kolobok919, спасибо! Но как мне использовать для решения задачи двусвязные динамические списки? Потому что именно это требуется в задаче.

@kolobok919 · 14.06.2015, 14:39

Сообщение от MichaelNV

kolobok919, спасибо! Но как мне использовать для решения задачи двусвязные динамические списки? Потому что именно это требуется в задаче.

Зачем?

@MichaelNV · 14.06.2015, 14:47 **[ТС]**

Таково условие задачи. Да и какой тип может содержать значение факториала 100! или 1000!?

@kolobok919 · 14.06.2015, 15:14

Сообщение от MichaelNV

Да и какой тип может содержать значение факториала 100! или 1000!?

По всей видимости, класс, созданный самостоятельно вами либо используйте библиотеку для работу с большими числами. А если использовать C/C++ не обязательно, то можно взять Python. Там по умолчанию целые числа негограниченной длины.

Добавлено через 36 секунд
А если C#, то BigInteger из System.Numerics.

@castaway · 14.06.2015, 15:18

Сообщение от MichaelNV

Да и какой тип может содержать значение факториала 100! или 1000!?

Увы, но таких типов нет в языке C++.

@kolobok919 · 14.06.2015, 15:28

Сообщение от castaway

Увы, но таких типов нет в языке C++.

А вот и нет. Во первых есть куча других библиотек, во вторых BigInteger в C++ есть (.NET)

@MichaelNV · 14.06.2015, 15:29 **[ТС]**

Сообщение от castaway

Увы, но таких типов нет в языке C++.

castaway, вот поэтому для реализации задачи требуется воспользоваться двусвязным динамическим списком. Подскажете как это сделать?

@kolobok919 · 14.06.2015, 15:31

Сообщение от MichaelNV

castaway, вот поэтому для реализации задачи требуется воспользоваться двусвязным динамическим списком. Подскажете как это сделать?

@castaway · 14.06.2015, 15:38

kolobok919,
1. Сторонние библиотеки не являются частью языка С++
2. .NET это извращенная пародия на язык С++, и языком С++ её назвать никак нельзя
3. Речь о стандартных (фундаментальных) типах

В стандартные типы языка С++ на современных архитектурах факториал 100 не влезет!

@MichaelNV · 14.06.2015, 15:51 **[ТС]**

Вы, пожалуйста, скажите, можете помочь разобраться с тем как используя именно список реализовать задачу, а не использовать типы для хранения огромных значений?

@kolobok919 · 14.06.2015, 15:57

Сообщение от MichaelNV

Вы, пожалуйста, скажите, можете помочь разобраться с тем как используя именно список реализовать задачу, а не использовать типы для хранения огромных значений?

Я не встречал никогда использование списков для вычисления факториала. Скажите для начала, что должны вам дать списки? Вы хотите хранить полученное значение разбитое на элементы списка? Или что?

@MichaelNV · 14.06.2015, 16:02 **[ТС]**

kolobok919, да, это позволит хранить значение любой величины.

Новичок · 14.06.2015, 16:05

Ну ясно же что это длинная арифметика, большие числа хранить скорее всего придется в строке или в массиве цифр, зачем здесь список?

@MichaelNV · 14.06.2015, 16:09 **[ТС]**

Новичок, воспринимайте это как способ реализации и условия задачи.

@kolobok919 · 14.06.2015, 16:09

Сообщение от MichaelNV

kolobok919, да, это позволит хранить значение любой величины.

Можно подробнее. Я бы, например, сделал иначе - реализовал бы класс, в котором числа хранились бы в массиве int или char.

Новичок · 14.06.2015, 16:22

Сообщение от kolobok919

Я бы, например, сделал иначе - реализовал бы класс, в котором числа хранились бы в массиве int или char.

Да так любой нормальный человек сделал бы.

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве 8Observer8 02.02.2026 Содержание блога Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .	Философия технологии iceja 01.02.2026 На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .	SDL3 для Web (WebAssembly): Вывод текста со шрифтом TTF с помощью SDL3_ttf 8Observer8 01.02.2026 Содержание блога В этой пошаговой инструкции создадим с нуля веб-приложение, которое выводит текст в окне браузера. Запустим на Android на локальном сервере. Загрузим Release на бесплатный. . .	SDL3 для Web (WebAssembly): Сборка C/C++ проекта из консоли 8Observer8 30.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .
SDL3 для Web (WebAssembly): Установка Emscripten SDK (emsdk) и CMake для сборки C и C++ приложений в Wasm 8Observer8 30.01.2026 Содержание блога Для того чтобы скачать Emscripten SDK (emsdk) необходимо сначало скачать и уставить Git: Install for Windows. Следуйте стандартной процедуре установки Git через установщик. . . .	SDL3 для Android: Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 29.01.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами. Версия v3 была полностью переписана на Си, в. . .	Инструменты COM: Сохранение данный из VARIANT в файл и загрузка из файла в VARIANT bedvit 28.01.2026 Сохранение базовых типов COM и массивов (одномерных или двухмерных) любой вложенности (деревья) в файл, с возможностью выбора алгоритмов сжатия и шифрования. Часть библиотеки BedvitCOM Использованы. . .	SDL3 для Android: Загрузка PNG с альфа-каналом с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 28.01.2026 Содержание блога SDL3 имеет собственные средства для загрузки и отображения PNG-файлов с альфа-каналом и базовой работы с ними. В этой инструкции используется функция SDL_LoadPNG(), которая. . .

@MichaelNV 0 / 0 / 0 Регистрация: 04.03.2011 Сообщений: 13
	14.06.2015, 14:34 [ТС]
	kolobok919, спасибо! Но как мне использовать для решения задачи двусвязные динамические списки? Потому что именно это требуется в задаче. 0

@MichaelNV 0 / 0 / 0 Регистрация: 04.03.2011 Сообщений: 13
	14.06.2015, 14:47 [ТС]
	Таково условие задачи. Да и какой тип может содержать значение факториала 100! или 1000!? 0

@castaway 4986 / 3093 / 456 Регистрация: 10.11.2010 Сообщений: 11,170 Записей в блоге: 10
	14.06.2015, 15:38
	kolobok919, 1. Сторонние библиотеки не являются частью языка С++ 2. .NET это извращенная пародия на язык С++, и языком С++ её назвать никак нельзя 3. Речь о стандартных (фундаментальных) типах В стандартные типы языка С++ на современных архитектурах факториал 100 не влезет! 0

@MichaelNV 0 / 0 / 0 Регистрация: 04.03.2011 Сообщений: 13
	14.06.2015, 15:51 [ТС]
	Вы, пожалуйста, скажите, можете помочь разобраться с тем как используя именно список реализовать задачу, а не использовать типы для хранения огромных значений? 0

@MichaelNV 0 / 0 / 0 Регистрация: 04.03.2011 Сообщений: 13
	14.06.2015, 16:02 [ТС]
	kolobok919, да, это позволит хранить значение любой величины. 0

Новичок 1682 / 1098 / 489 Регистрация: 17.07.2012 Сообщений: 5,360
	14.06.2015, 16:05
	Ну ясно же что это длинная арифметика, большие числа хранить скорее всего придется в строке или в массиве цифр, зачем здесь список? 0

@MichaelNV 0 / 0 / 0 Регистрация: 04.03.2011 Сообщений: 13
	14.06.2015, 16:09 [ТС]
	Новичок, воспринимайте это как способ реализации и условия задачи. 0