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

@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.

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

Новые блоги и статьи Все статьи Все блоги /
Модель здравосоХранения 6. ESG-повестка и устойчивое развитие; углублённый анализ кадрового бренда anaschu 31.03.2026 В прикрепленном документе раздумья о том, как можно поменять модель в будущем	10 пpимет, которые всегда сбываются Maks 31.03.2026 1. Чтобы, наконец, пришла маршрутка, надо закурить. Если сигарета последняя, маршрутка придет еще до второй затяжки даже вопреки расписанию. 2. Нaдоели зима и снег? Не надо переезжать. Достаточно. . .	Перемещение выделенных строк ТЧ из одного документа в другой Maks 31.03.2026 Реализация из решения ниже выполнена на примере нетипового документа "ВыдачаОборудованияНаСпецтехнику" с единственной табличной частью "ОборудованиеИКомплектующие" разработанного в конфигурации КА2. . . .	Functional First Web Framework Suave DevAlt 30.03.2026 Sauve. IO Апнулись до NET10. Из зависимостей один пакет, работает одинаково хорошо как в режиме проекта так и в интерактивном режиме. из сложностей - чисто функциональный подход. Решил. . .
Автоматическое создание документа при проведении другого документа Maks 29.03.2026 Реализация из решения ниже выполнена на нетиповых документах, разработанных в конфигурации КА2. Есть нетиповой документ "ЗаявкаНаРемонтСпецтехники" и нетиповой документ "ПланированиеСпецтехники". В. . .	Настройка движения справочника по регистру сведений Maks 29.03.2026 Решение ниже реализовано на примере нетипового справочника "ТарифыМобильнойСвязи" разработанного в конфигурации КА2, с целью учета корпоративной мобильной связи в коммерческом предприятии. . . .	Автозаполнение реквизита при выборе элемента справочника Maks 27.03.2026 Программный код из решения ниже на примере нетипового документа "ЗаявкаНаРемонтСпецтехники" разработанного в конфигурации КА2. При выборе "Спецтехники" (Тип Справочник. Спецтехника), заполняется. . .	Сумматор с применением элементов трёх состояний. Hrethgir 26.03.2026 Тут. https:/ / fips. ru/ EGD/ ab3c85c8-836d-4866-871b-c2f0c5d77fbc Первый документ красиво выглядит, но без схемы. Это конечно не даёт никаких плюсов автору, но тем не менее. . . всё может быть. . .

@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,361
	14.06.2015, 16:05
	Ну ясно же что это длинная арифметика, большие числа хранить скорее всего придется в строке или в массиве цифр, зачем здесь список? 0

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