Форум программистов, компьютерный форум, киберфорум
Наши страницы

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

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 17, средняя оценка - 4.88
KING1994
-68 / 6 / 0
Регистрация: 18.07.2011
Сообщений: 77
#1

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

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

Помогите написать программу,котороя щитает большые фактуриалы(100!,200! и тд)
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
02.09.2011, 15:32
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Большие факториалы (C++):

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

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

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

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

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

Обьясните, почему код так странно считает факториалы - C++
Добрый день, ув. форумчане. Есть код, считающий факториалы:#include "stdio.h" #include "windows.h" __int64 factorial(__int64 n) { ...

39
grizlik78
Эксперт С++
1966 / 1459 / 120
Регистрация: 29.05.2011
Сообщений: 3,018
03.09.2011, 00:32 #16
Цитата Сообщение от M128K145 Посмотреть сообщение
Кстати, в 100000! ровно 456569 разрядов
А это уже странно. Так как у меня двумя разными способами (с помощью GMP и кодом от diagon) получаются одинаковые числа, в которых 456574 разряда

Добавлено через 8 минут
Разница в 5 разрядов наводит на мысль о том, что не было умножения на 100000

Добавлено через 3 минуты
Да и код, вроде, о том же говорит. Как это я сразу в код посмотреть не догадался?
1
M128K145
Эксперт С++
8297 / 3517 / 143
Регистрация: 03.07.2009
Сообщений: 10,706
03.09.2011, 00:39 #17
grizlik78, да, вышла небольшая очепятка, ровно пять разрядов теряются из-за строго неравенства
0
iama
1250 / 975 / 49
Регистрация: 30.07.2010
Сообщений: 5,297
03.09.2011, 09:05 #18
Цитата Сообщение от M128K145 Посмотреть сообщение
посмотрите внимательно на код
ааа, так вы об авторском коде я даже и не читал я просто говорил, что оптимальное умножение длинного на короткое можно сделать не больше, чем за size.
0
diagon
Higher
1930 / 1196 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
03.09.2011, 09:20 #19
Цитата Сообщение от iama Посмотреть сообщение
я просто говорил, что оптимальное умножение длинного на короткое можно сделать не больше, чем за size.
Это в столбик что ли, как у меня? Просто умножить каждый элемент массива, в котором длинное число лежит, на короткое число и, если результат будет больше основания, то просто перенести в следующий разряд?

Хм... А БПФ же за O(nlogn) работает, т.е. он медленнее будет?

Цитата Сообщение от grizlik78 Посмотреть сообщение
GMP справляется с таким факториалом (100000!) меньше чем за три секунды
Цитата Сообщение от grizlik78 Посмотреть сообщение
А вот эта реализация за 20 секунд
Мне просто непонятно, как GMP так быстро справляется.
То, что GMP на си, а у меня реализация на с++ - понятно, но не в 7 же раз из-за этого разница будет. Может, у них по 17 цифр в одном элементе лежит, а переполнение с помощью asm вставок контролируется(у меня только 9 цифр) =\
Мистика в общем.
0
iama
1250 / 975 / 49
Регистрация: 30.07.2010
Сообщений: 5,297
03.09.2011, 09:38 #20
Цитата Сообщение от diagon Посмотреть сообщение
А БПФ же за O(nlogn) работает, т.е. он медленнее будет?
Давайте на примере прикинем. При n = 100000 и, если храним число по 9 десятичных разрядов на элемент структуры, размер массива - ~50000. Множим в столбик + аккуратно писаные переносы - size - 50000. А O(n*logn) даст явно большее число. Вполне возможно, что больше и выйдет. Но, понятно, все зависит от реализации.
1
Thinker
Эксперт С++
4228 / 2202 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
03.09.2011, 09:49 #21
Длинная арифметика это всегда интересно, так как реализовать по разному можно. Скажите, а никто не пробовал при вычислении больших факториалов взять за основание системы счисления степень двойки, то есть работать только со сдвигами, а уже после перевести полученное число по снованию степени 10? Возможно так быстрее будет, но руки не доходят проверить...
0
M128K145
Эксперт С++
8297 / 3517 / 143
Регистрация: 03.07.2009
Сообщений: 10,706
03.09.2011, 09:53 #22
Цитата Сообщение от iama Посмотреть сообщение
что оптимальное умножение длинного на короткое можно сделать не больше, чем за size
В зависимости от способа хранения длинного. Если оно представлено одним числом, то не более чем за n, если массивом(как у меня), то мне его сложность будет О((Kx - Ny)*n), где Kx - количество задействованных элементов, Ny - количество младших нулей, n - основание факториала. И следует заметить, что K и N все время увеличивается
1
Dani
1393 / 637 / 57
Регистрация: 11.08.2011
Сообщений: 2,290
Записей в блоге: 2
Завершенные тесты: 1
03.09.2011, 12:06 #23
Цитата Сообщение от iama Посмотреть сообщение
KING1994, не задумывались, почему гугл не возвращает факториалов чисел, больших 170?
Гугл не возвращает, зато возвращает bing.

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

Добавлено через 1 минуту
Цитата Сообщение от Dani Посмотреть сообщение
Гугл не возвращает, зато возвращает bing.
Возвращает до 815!
0
ValeryLaptev
Эксперт С++
1042 / 821 / 48
Регистрация: 30.04.2011
Сообщений: 1,659
03.09.2011, 13:41 #24
Цитата Сообщение от KING1994 Посмотреть сообщение
long double +/- 1,1810e-4932-+/-1,1810e+4932(надеюсь ети позначки вам знакомы)-ето диапазон значений лонг дабл
Не все компиляторы это поддерживают.
0
KING1994
-68 / 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
Dani
1393 / 637 / 57
Регистрация: 11.08.2011
Сообщений: 2,290
Записей в блоге: 2
Завершенные тесты: 1
04.09.2011, 23:13 #26
Работает медленно, на ******** есть задача, про факториалы - вычислить факториал n (n<=1000), во времени ограничение - 1 секунда. А тут на 1000 работает уж точно больше. Вывод: надо писать версию 2.0 - модифицированную
0
KING1994
-68 / 6 / 0
Регистрация: 18.07.2011
Сообщений: 77
04.09.2011, 23:15  [ТС] #27
Dani,я студент 1 курс)мне препод поставил задачу я выполнил) 1000!щитает около 15-20 сек)конешно буду улучшать свои навыки)
0
Dani
1393 / 637 / 57
Регистрация: 11.08.2011
Сообщений: 2,290
Записей в блоге: 2
Завершенные тесты: 1
04.09.2011, 23:21 #28
Цитата Сообщение от KING1994 Посмотреть сообщение
конешно буду улучшать свои навыки)
В этом вся суть
0
iama
1250 / 975 / 49
Регистрация: 30.07.2010
Сообщений: 5,297
05.09.2011, 08:17 #29
KING1994, я вообще школота, но у меня 100000! считает меньше чем за 10 секунд.
0
fasked
Эксперт С++
4948 / 2528 / 180
Регистрация: 07.10.2009
Сообщений: 4,311
Записей в блоге: 1
05.09.2011, 10:29 #30
Цитата Сообщение от Thinker Посмотреть сообщение
Длинная арифметика это всегда интересно, так как реализовать по разному можно. Скажите, а никто не пробовал при вычислении больших факториалов взять за основание системы счисления степень двойки, то есть работать только со сдвигами, а уже после перевести полученное число по снованию степени 10? Возможно так быстрее будет, но руки не доходят проверить...
Для 32-битных машин, я брал за основание 2^16, для 64 - 2^32. Так, само собой, быстрее.
Только делал не через сдвиги. Но все равно быстрее, а памяти так вообще в разы меньше надо
1
05.09.2011, 10:29
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
05.09.2011, 10:29
Привет! Вот еще темы с ответами:

большие числа - C++
скажите пожалуйсто есть ли какая нибудь библиотека в си++ для работы с большими числами (до 10^18), если нет то может у кого класс...

Большие числа - C++
Здравствуйте. Как в С++ работать с большими числами (600851475143, например)? Честно гуглил, но там ничего толкового не нашел. ...

Большие числа в C - C++
можно ли в языке С работать с большими целыми? Существует ли некое подобие BigInteger C#?

Большие-маленькие - C++
На входе строка содержащая большие и маленькие буквы, необходимо большие сделать маленькими, а маленькие большими. Например...


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

Или воспользуйтесь поиском по форуму:
30
Ответ Создать тему
Опции темы

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