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

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

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

Author24 — интернет-сервис помощи студентам
Помогите написать программу,котороя щитает большые фактуриалы(100!,200! и тд)
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
02.09.2011, 15:32
Ответы с готовыми решениями:

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

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

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

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

39
Эксперт С++
4267 / 2241 / 203
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
03.09.2011, 09:49 21
Author24 — интернет-сервис помощи студентам
Длинная арифметика это всегда интересно, так как реализовать по разному можно. Скажите, а никто не пробовал при вычислении больших факториалов взять за основание системы счисления степень двойки, то есть работать только со сдвигами, а уже после перевести полученное число по снованию степени 10? Возможно так быстрее будет, но руки не доходят проверить...
0
Эксперт JavaЭксперт С++
8384 / 3616 / 419
Регистрация: 03.07.2009
Сообщений: 10,709
03.09.2011, 09:53 22
Цитата Сообщение от iama Посмотреть сообщение
что оптимальное умножение длинного на короткое можно сделать не больше, чем за size
В зависимости от способа хранения длинного. Если оно представлено одним числом, то не более чем за n, если массивом(как у меня), то мне его сложность будет О((Kx - Ny)*n), где Kx - количество задействованных элементов, Ny - количество младших нулей, n - основание факториала. И следует заметить, что K и N все время увеличивается
1
1405 / 647 / 135
Регистрация: 11.08.2011
Сообщений: 2,299
Записей в блоге: 2
03.09.2011, 12:06 23
Цитата Сообщение от 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 24
Цитата Сообщение от KING1994 Посмотреть сообщение
long double +/- 1,1810e-4932-+/-1,1810e+4932(надеюсь ети позначки вам знакомы)-ето диапазон значений лонг дабл
Не все компиляторы это поддерживают.
0
6 / 6 / 0
Регистрация: 18.07.2011
Сообщений: 77
04.09.2011, 23:09  [ТС] 25
Ну вот посидел немного написал порогу которая щитает любые фактуриалы за принципом умножения и додавание в столбец вот код:
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
1405 / 647 / 135
Регистрация: 11.08.2011
Сообщений: 2,299
Записей в блоге: 2
04.09.2011, 23:13 26
Работает медленно, на acmp.ru есть задача, про факториалы - вычислить факториал n (n<=1000), во времени ограничение - 1 секунда. А тут на 1000 работает уж точно больше. Вывод: надо писать версию 2.0 - модифицированную
0
6 / 6 / 0
Регистрация: 18.07.2011
Сообщений: 77
04.09.2011, 23:15  [ТС] 27
Dani,я студент 1 курс)мне препод поставил задачу я выполнил) 1000!щитает около 15-20 сек)конешно буду улучшать свои навыки)
0
1405 / 647 / 135
Регистрация: 11.08.2011
Сообщений: 2,299
Записей в блоге: 2
04.09.2011, 23:21 28
Цитата Сообщение от KING1994 Посмотреть сообщение
конешно буду улучшать свои навыки)
В этом вся суть
0
1360 / 988 / 119
Регистрация: 30.07.2010
Сообщений: 5,297
05.09.2011, 08:17 29
KING1994, я вообще школота, но у меня 100000! считает меньше чем за 10 секунд.
0
Эксперт С++
5043 / 2622 / 241
Регистрация: 07.10.2009
Сообщений: 4,310
Записей в блоге: 1
05.09.2011, 10:29 30
Цитата Сообщение от Thinker Посмотреть сообщение
Длинная арифметика это всегда интересно, так как реализовать по разному можно. Скажите, а никто не пробовал при вычислении больших факториалов взять за основание системы счисления степень двойки, то есть работать только со сдвигами, а уже после перевести полученное число по снованию степени 10? Возможно так быстрее будет, но руки не доходят проверить...
Для 32-битных машин, я брал за основание 2^16, для 64 - 2^32. Так, само собой, быстрее.
Только делал не через сдвиги. Но все равно быстрее, а памяти так вообще в разы меньше надо
1
TheAthlete
05.09.2011, 11:48
  #31

Не по теме:

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

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

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

В итоге считать в таких случаях проще как-то в HEX - количество памяти совпадает с количеством разрядов
0
1360 / 988 / 119
Регистрация: 30.07.2010
Сообщений: 5,297
05.09.2011, 18:23 38
Цитата Сообщение от fasked Посмотреть сообщение
В итоге считать в таких случаях проще как-то в HEX - количество памяти совпадает с количеством разрядов
Естественно, хранить удобней, даже операции арифметические выполнять удобней.
А вот выводить - не удобней
0
Эксперт С++
5043 / 2622 / 241
Регистрация: 07.10.2009
Сообщений: 4,310
Записей в блоге: 1
05.09.2011, 18:30 39
Цитата Сообщение от iama Посмотреть сообщение
Естественно, хранить удобней, даже операции арифметические выполнять удобней.
операции по-моему вообще пофигу не в уме же считаем, все машинка делает сама.
Цитата Сообщение от iama Посмотреть сообщение
А вот выводить - не удобней
так как я занимался длинной арифметикой исключительно в криптографическом плане, то ... я ни разу не видел длинных десятичных чисел
0
Эксперт С++
4267 / 2241 / 203
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
06.09.2011, 10:37 40
Цитата Сообщение от fasked Посмотреть сообщение
Для 32-битных машин, я брал за основание 2^16, для 64 - 2^32. Так, само собой, быстрее.
Это все и так понятно. Думал кто-нибудь на время тестировал когда степень 10^m и степень 2^n.
0
06.09.2011, 10:37
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
06.09.2011, 10:37
Помогаю со студенческими работами здесь

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

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

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

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


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

Или воспользуйтесь поиском по форуму:
40
Ответ Создать тему
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru