Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск  
 
 
Рейтинг 5.00/22: Рейтинг темы: голосов - 22, средняя оценка - 5.00
6 / 6 / 0
Регистрация: 18.07.2011
Сообщений: 77

Большие факториалы

02.09.2011, 15:32. Показов 5359. Ответов 39
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Помогите написать программу,котороя щитает большые фактуриалы(100!,200! и тд)
0
Programming
Эксперт
39485 / 9562 / 3019
Регистрация: 12.04.2006
Сообщений: 41,671
Блог
02.09.2011, 15:32
Ответы с готовыми решениями:

Факториалы...
Приветствую. Если напишу, что нужна помощь в решении задачи - сурово вас обману. Помощь не нужна - нужно решение. Язык - Си, среда Dev-C++ ...

Факториалы в while
можно ли хоть каким-то реализуемым способом засунуть внутрь условия цикла while факториалы? мне например надо чтобы "такой то х в...

Факториалы
Добрый день , не могу понять почему не работает программа . Вроде все сделал корректно , и результат показывает , только значения Y(x) и...

39
Эксперт С++
 Аватар для Thinker
4267 / 2241 / 203
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
03.09.2011, 09:49
Студворк — интернет-сервис помощи студентам
Длинная арифметика это всегда интересно, так как реализовать по разному можно. Скажите, а никто не пробовал при вычислении больших факториалов взять за основание системы счисления степень двойки, то есть работать только со сдвигами, а уже после перевести полученное число по снованию степени 10? Возможно так быстрее будет, но руки не доходят проверить...
0
Эксперт JavaЭксперт С++
 Аватар для M128K145
8384 / 3618 / 419
Регистрация: 03.07.2009
Сообщений: 10,709
03.09.2011, 09:53
Цитата Сообщение от iama Посмотреть сообщение
что оптимальное умножение длинного на короткое можно сделать не больше, чем за size
В зависимости от способа хранения длинного. Если оно представлено одним числом, то не более чем за n, если массивом(как у меня), то мне его сложность будет О((Kx - Ny)*n), где Kx - количество задействованных элементов, Ny - количество младших нулей, n - основание факториала. И следует заметить, что K и N все время увеличивается
1
1406 / 648 / 135
Регистрация: 11.08.2011
Сообщений: 2,299
Записей в блоге: 2
03.09.2011, 12:06
Цитата Сообщение от iama Посмотреть сообщение
KING1994, не задумывались, почему гугл не возвращает факториалов чисел, больших 170?
Гугл не возвращает, зато возвращает bing.

Добавлено через 55 секунд
http://www.wolframalpha.com/bing/?i=999!
Вот сайт для вычислений факториалов

Добавлено через 1 минуту
Цитата Сообщение от Dani Посмотреть сообщение
Гугл не возвращает, зато возвращает bing.
Возвращает до 815!
0
Эксперт С++
1069 / 848 / 60
Регистрация: 30.04.2011
Сообщений: 1,659
03.09.2011, 13:41
Цитата Сообщение от KING1994 Посмотреть сообщение
long double +/- 1,1810e-4932-+/-1,1810e+4932(надеюсь ети позначки вам знакомы)-ето диапазон значений лонг дабл
Не все компиляторы это поддерживают.
0
6 / 6 / 0
Регистрация: 18.07.2011
Сообщений: 77
04.09.2011, 23:09  [ТС]
Ну вот посидел немного написал порогу которая щитает любые фактуриалы за принципом умножения и додавание в столбец вот код:
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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include "stdafx.h"
#include <iostream>
#include<conio.h>
using namespace std;
long int vvid,m[1000000],n[1000000],h[1000000],q[1000000],sum,sum1,ost,ost1;int i,j=0,x,y,z,k=0,v,L,b,K,k1,w,c=0,r=0;
int main()
{
    cin>>vvid;
    m[999999]=1;n[999999]=1;j=999999;z=999999;h[999999]=0;b=j;
for(i=2,y=j;i<=vvid;i++)   
{
    y=j;z=j;v=j;L=j;b=j;w=j;K=j;
    if(i<=10)
       {
        do{m[z]*=i;z--;}while(z>=0);
            do 
            {
            if(m[y]>=10)
            {ost=m[y]%10;m[y]-=ost;m[y]/=10;m[y-1]+=m[y];m[y]=ost;}y--;
            }while(y>=0);
       }
     else if(i>=11)
         { 
            sum=i;
             sum=i;ost1=sum%10;sum1=(sum-ost1)/10;k=0;r=0;
            do{n[z]=m[z];n[z]*=ost1;z--;}while(z>=0);
            do 
            {
            if(n[y]>=10)
            {ost=n[y]%10;n[y]-=ost;n[y]/=10;n[y-1]+=n[y];n[y]=ost;}y--;
            }while(y>=0);
            do{h[b-1]=m[b];h[b]*=sum1;b--;}while(b>=0);
            do 
            {
            if(h[v]>=10)
            {ost=h[v]%10;h[v]-=ost;h[v]/=10;h[v-1]+=h[v];h[v]=ost;}v--;
            }while(v>=0);   
            do{q[w]=n[w]+h[w];m[w]=q[w];w--;}while(w>=0);
            do 
            {   
            if(m[K]>=10)
             {ost=m[K]%10;m[K]-=ost;m[K]/=10;m[K-1]+=m[K];m[K]=ost;}K--;
             }while(K>=0);
             
        }
}
while(m[c]==0)c++;
    cout<<endl;
    if(vvid>=11)
    {for(k1=c;k1<=j;k1++)
    cout<<m[k1];
    cout<<endl;}
    else if(vvid<=10)
        for(k1=c;k1<=j;k1++)cout<<m[k1];
    getch();
    return 0;
}
есть немного лишних переменных но я нехотел розбиратса)
0
1406 / 648 / 135
Регистрация: 11.08.2011
Сообщений: 2,299
Записей в блоге: 2
04.09.2011, 23:13
Работает медленно, на acmp.ru есть задача, про факториалы - вычислить факториал n (n<=1000), во времени ограничение - 1 секунда. А тут на 1000 работает уж точно больше. Вывод: надо писать версию 2.0 - модифицированную
0
6 / 6 / 0
Регистрация: 18.07.2011
Сообщений: 77
04.09.2011, 23:15  [ТС]
Dani,я студент 1 курс)мне препод поставил задачу я выполнил) 1000!щитает около 15-20 сек)конешно буду улучшать свои навыки)
0
1406 / 648 / 135
Регистрация: 11.08.2011
Сообщений: 2,299
Записей в блоге: 2
04.09.2011, 23:21
Цитата Сообщение от KING1994 Посмотреть сообщение
конешно буду улучшать свои навыки)
В этом вся суть
0
 Аватар для iama
1360 / 988 / 119
Регистрация: 30.07.2010
Сообщений: 5,297
05.09.2011, 08:17
KING1994, я вообще школота, но у меня 100000! считает меньше чем за 10 секунд.
0
Эксперт С++
 Аватар для fasked
5045 / 2624 / 241
Регистрация: 07.10.2009
Сообщений: 4,310
Записей в блоге: 5
05.09.2011, 10:29
Цитата Сообщение от Thinker Посмотреть сообщение
Длинная арифметика это всегда интересно, так как реализовать по разному можно. Скажите, а никто не пробовал при вычислении больших факториалов взять за основание системы счисления степень двойки, то есть работать только со сдвигами, а уже после перевести полученное число по снованию степени 10? Возможно так быстрее будет, но руки не доходят проверить...
Для 32-битных машин, я брал за основание 2^16, для 64 - 2^32. Так, само собой, быстрее.
Только делал не через сдвиги. Но все равно быстрее, а памяти так вообще в разы меньше надо
1
05.09.2011, 11:48

Не по теме:

Цитата Сообщение от KING1994 Посмотреть сообщение
Помогите написать программу,котороя щитает большые фактуриалы(100!,200! и тд)
в русском языке нет слова "щитает", есть слово "считает". Просьба писать нормальным русским языком без ошибок. А то во всех постах пишешь "щитает, щитаешь". Не "фактуриалы", а "факториалы"

2
 Аватар для iama
1360 / 988 / 119
Регистрация: 30.07.2010
Сообщений: 5,297
05.09.2011, 15:40
fasked, а процедуры ввода-вывода показать можете?
0
Эксперт С++
 Аватар для fasked
5045 / 2624 / 241
Регистрация: 07.10.2009
Сообщений: 4,310
Записей в блоге: 5
05.09.2011, 15:42
Цитата Сообщение от iama Посмотреть сообщение
а процедуры ввода-вывода показать можете?
Сейчас уже нет Исходники (как и все университетские) были утеряны. Но вообще преобразовывал в строку и обратно. Могу на досуге поковыряться и вспомнить, если интересно. Да мне и самому интересно
0
 Аватар для iama
1360 / 988 / 119
Регистрация: 30.07.2010
Сообщений: 5,297
05.09.2011, 17:39
fasked, просто я всю жизнь считаю, что вывод длинного числа, хранящегося по основанию https://www.cyberforum.ru/cgi-bin/latex.cgi?2^n - довольно сложная задача
0
Эксперт С++
 Аватар для fasked
5045 / 2624 / 241
Регистрация: 07.10.2009
Сообщений: 4,310
Записей в блоге: 5
05.09.2011, 17:51
iama, либо я что-то неправильно понял, либо Вы.
Тут смысл в том, что в одной ячейке массива хранится не одна десятичная цифра, а максимум https://www.cyberforum.ru/cgi-bin/latex.cgi?2^n - 1. И, грубо говоря, для хранения числа https://www.cyberforum.ru/cgi-bin/latex.cgi?12345678901234567890 требуется не двадцать байт памяти, а 16. Плюс при том же сложении, надо выполнить не 20 итераций цикла, а всего 5. Даже на таких грубых подсчетах в 4 раза быстрее. Но это я отошел от темы... Ну а при выводе, тоже самое число хранится в памяти следующим образом:
Code
1
0AD2h EB1Fh A98Ch AB54h
И собственно для преобразования в hex строку вообще ничего делать не надо, ну а для десятичной строки уже применять арифметику
0
 Аватар для iama
1360 / 988 / 119
Регистрация: 30.07.2010
Сообщений: 5,297
05.09.2011, 18:00
fasked, ааа, то есть основание таки будет не степень двойки, а максимальная степень десяти, помещающаяся в данных целочисленный тип, то есть, используя 32-битные беззнаковые числа мы можем хранить в каждой ячейке массива по 9 десятичных разрядов, вы это имеете в виду? Так я так всегда и пишу и с выводом удобно, и по памяти лучше, и размер массива меньше https://www.cyberforum.ru/cgi-bin/latex.cgi?\Leftrightarrow вычисления быстрее
0
Эксперт С++
 Аватар для fasked
5045 / 2624 / 241
Регистрация: 07.10.2009
Сообщений: 4,310
Записей в блоге: 5
05.09.2011, 18:10
Цитата Сообщение от iama Посмотреть сообщение
то есть основание таки будет не степень двойки
Так это и есть основание по-моему Основание это же максимальное возможное значение для одного разряда числа. Здесь получается один разряд числа соответствует одной ячейки массива. Да и все операции выполняются с разрядами (ячейками), а не их частями. Просто символов не хватит, чтобы нарисовать число по основанию https://www.cyberforum.ru/cgi-bin/latex.cgi?2^n. А железка все равно все битами хранит, ну или байтами... это как посмотреть

Цитата Сообщение от iama Посмотреть сообщение
в каждой ячейке массива по 9 десятичных разрядов
Ну вообще немного не так. Десятичная система неудобна в том плане, что в 1 байт памяти помещается число 255, а 256 уже не помещается.
То есть, если взять за основание 256, то 255 (dec) это число из одного разряда, а 256 (dec) уже из двух.

В итоге считать в таких случаях проще как-то в HEX - количество памяти совпадает с количеством разрядов
0
 Аватар для iama
1360 / 988 / 119
Регистрация: 30.07.2010
Сообщений: 5,297
05.09.2011, 18:23
Цитата Сообщение от fasked Посмотреть сообщение
В итоге считать в таких случаях проще как-то в HEX - количество памяти совпадает с количеством разрядов
Естественно, хранить удобней, даже операции арифметические выполнять удобней.
А вот выводить - не удобней
0
Эксперт С++
 Аватар для fasked
5045 / 2624 / 241
Регистрация: 07.10.2009
Сообщений: 4,310
Записей в блоге: 5
05.09.2011, 18:30
Цитата Сообщение от iama Посмотреть сообщение
Естественно, хранить удобней, даже операции арифметические выполнять удобней.
операции по-моему вообще пофигу не в уме же считаем, все машинка делает сама.
Цитата Сообщение от iama Посмотреть сообщение
А вот выводить - не удобней
так как я занимался длинной арифметикой исключительно в криптографическом плане, то ... я ни разу не видел длинных десятичных чисел
0
Эксперт С++
 Аватар для Thinker
4267 / 2241 / 203
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
06.09.2011, 10:37
Цитата Сообщение от fasked Посмотреть сообщение
Для 32-битных машин, я брал за основание 2^16, для 64 - 2^32. Так, само собой, быстрее.
Это все и так понятно. Думал кто-нибудь на время тестировал когда степень 10^m и степень 2^n.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
inter-admin
Эксперт
29715 / 6470 / 2152
Регистрация: 06.03.2009
Сообщений: 28,500
Блог
06.09.2011, 10:37

Факториалы!
В лабе нужно вычислить выражение, в котором находятся числа с факториалами в таком порядке: 1!+2!+...+К!, я не знаю как это описать в...

Факториалы
http://acm.timus.ru/problem.aspx?space=1&amp;num=1083 помогите решить эту задачу у меня мысль есть, но похоже неправильная. ...

Факториалы числа
Дано число N. Рассчитать и вывести первые N факториалов. (1!, 2! ... N!) Задача-то лёгкая, но есть одна загвоздка: переменная цикла и...

Рекурсия: вывести факториалы от 1 до 10
Нужно рекурсивно вывести все факториалы от 1-го до 10

Вычисление по формуле. Факториалы
Не знаю как это решить, помогите плиз Напишите программу вычисления примера y = a! + b! / a! - b! с помощью функции расчета х! = 1 *...


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

Или воспользуйтесь поиском по форуму:
40
Ответ Создать тему
Новые блоги и статьи
Транслитерация текста с кириллицы на латиницу
Maks 11.11.2026
Решил облегчить жизнь себе и коллегам админам при создании электронных почтовых ящиков для пользователей, в результате написал обработку "Транслитерация текста" с кириллицы на латиницу, а в ней. . .
Книги по геймдизайну, левел-дизайну, игровым механикам и проектированию игрового опыта
8Observer8 08.11.2026
Содержание блога | English Version 1. 2003 - 06 - Designing Virtual Worlds (1st Edition) Автор: Richard A. Bartle | Объем: 768 стр. Ссылки: Amazon . . .
Родители токсичные абьюзеры по отношению к своим детям ругают их оскорбляют не любят
zorxor 08.11.2026
Жить в атмосфере постоянных оскорблений, критики и холодности со стороны родителей — это тяжелое и болезненное испытание, которое оставляет глубокие эмоциональные раны. Токсичное и абьюзивное. . .
Как только я захожу к себе в свою комнату я сразу же с себя снимаю свои трусы. Ответ от Джемени ИИ.
zorxor 08.11.2026
Джемени, как только я захожу к себе в свою комнату я сразу же с себя снимаю свои трусы. Многие люди, возвращаясь домой, сразу переодеваются в максимально свободную одежду или вовсе предпочитают. . .
Паттерн очереди действий/команд (Action / Command Queue). Система очереди действий и кат-сцен с SDL3 Callbacks, cglm и OpenGL
8Observer8 07.11.2026
Содержание блога | English Version Руководство для начинающих по реализации паттерна очереди действий/ команд (Action / Command Queue) на C++ (C++20) с использованием официального SDL3 Callbacks. . .
Проверка полного ФИО в типовом справочнике
Maks 07.11.2026
Решение реализовано в конфигурации КА2, на примере справочника "КонтактныеЛицаПартнеров". Задача: Запрет инициалов. Не допускаеть использование сокращений вида "И. И. ", "И. И. ", "И И" и. . .
Про "Windows must die!"
kumehtar 04.11.2026
Знаете, чет накатило. . . . Когда-то это было почти боевым кличем: мол, нормальный человек сидит на DOS, OS/ 2 или Linux, а вот это вот - Must Die. А теперь человек произносит «мастдай» с усмешкой - и. . .
Красочные поля с номером страницы svg+background-image
russiannick 04.11.2026
Красочные поля с номером страницы не менее важны чем в эпоху бумажных книг. Посему спешу представить почтеннейшей публике этот важный инструмент который эти поля и формирует. В процессе разработки. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru