Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
 
Рейтинг 4.79/14: Рейтинг темы: голосов - 14, средняя оценка - 4.79
KING1994
-18 / 6 / 0
Регистрация: 18.07.2011
Сообщений: 77
1

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

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

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

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

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

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

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

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

39
M128K145
Эксперт JavaЭксперт С++
8326 / 3547 / 420
Регистрация: 03.07.2009
Сообщений: 10,708
02.09.2011, 16:11 2
факториал 3000 или вам именно на CLR надо?

Не по теме:

Вообще-то это называется "факториал"

1
KING1994
-18 / 6 / 0
Регистрация: 18.07.2011
Сообщений: 77
02.09.2011, 22:21  [ТС] 3
оч спасибо)

Добавлено через 4 часа 0 минут
Кстати я нашел альтернативный вариант решения,но помогите пожалуйста как вычислить остачу для double переменных ибо %програма не читает и выбивает ошыбку(( вот мой код:
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
#include "stdafx.h"
#include<iostream>
#include<conio.h>
#include<math.h>
using namespace std;
long double i,j=1,a,sum=1,sum1,sum2,m[1000000],n[1000000];int step,ost,h=0,r,t,g=0;
 
int _tmain(int argc, _TCHAR* argv[])
{
    cin>>a;
    for(i=0;i<a;i++,j++)
    {
        sum*=j;
    }
    cout<<sum<<endl<<endl;
    while(sum>0)
    {
     step=10;
     ost=sum%step;sum-=g;sum/=10;
     m[h]=ost;
     cout<<m[h]<<endl;h++;
    }
    cout<<endl;
    for(r=0,t=h-1;r<h;r++,t--)
    {
    n[r]=m[t];
    cout<<n[r]<<"\t";
    }
 getch();
 return 0;
}
Добавлено через 8 минут
Для типа int оно роботает отлично,записывая каждый новый розряд в новый елемент массива,но для дабл компилятор не читает символа%как мне вычеслить остачу от деления на 10 без етого символа?

Добавлено через 23 минуты
Cпасибо ненадо уже нашел fmod();
вот мой код:
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
#include "stdafx.h"
#include<iostream>
#include<conio.h>
#include<math.h>
using namespace std;
long double i,j=1,a,sum=1,sum1,sum2,m[1000000],n[1000000];int step,ost,h=0,r,t,g=0;
 
int _tmain(int argc, _TCHAR* argv[])
{
    cin>>a;
    for(i=0;i<a;i++,j++)
    {
        sum*=j;
    }
    cout<<sum<<endl<<endl;
    while(sum>0)
    {
     step=10;
     ost=fmod(sum,step);sum-=ost;sum/=10;
     m[h]=ost;
     cout<<m[h]<<endl;h++;
    }
    cout<<endl;
    for(r=0,t=h-1;r<h;r++,t--)
    {
    n[r]=m[t];
    cout<<n[r]<<" ";
    }
 getch();
 return 0;
}
Добавлено через 1 час 29 минут
Правда оно ток до 170! щитает незнаю почему((
0
iama
1326 / 979 / 119
Регистрация: 30.07.2010
Сообщений: 5,297
02.09.2011, 22:26 4
Цитата Сообщение от KING1994 Посмотреть сообщение
Правда оно ток до 170! щитает незнаю почему((
хм... Может, в double просто больше не помещается?

Не по теме:

сарказм, если чо

0
KING1994
-18 / 6 / 0
Регистрация: 18.07.2011
Сообщений: 77
02.09.2011, 22:29  [ТС] 5
long double +/- 1,1810e-4932-+/-1,1810e+4932(надеюсь ети позначки вам знакомы)-ето диапазон значений лонг дабл
0
iama
1326 / 979 / 119
Регистрация: 30.07.2010
Сообщений: 5,297
02.09.2011, 22:31 6
KING1994, не задумывались, почему гугл не возвращает факториалов чисел, больших 170?
0
KING1994
-18 / 6 / 0
Регистрация: 18.07.2011
Сообщений: 77
02.09.2011, 22:33  [ТС] 7
если честно я даже не искал))но все же 200! тоже входят в диапазон значений.
0
iama
1326 / 979 / 119
Регистрация: 30.07.2010
Сообщений: 5,297
02.09.2011, 22:35 8
KING1994, а сколько значащих разрядов помещаются в double?
0
KING1994
-18 / 6 / 0
Регистрация: 18.07.2011
Сообщений: 77
02.09.2011, 22:36  [ТС] 9
4932 вроде
0
iama
1326 / 979 / 119
Регистрация: 30.07.2010
Сообщений: 5,297
02.09.2011, 22:38 10
KING1994, хм, как же они в 64 бита-то поместились...
Матчасть
1
M128K145
Эксперт JavaЭксперт С++
8326 / 3547 / 420
Регистрация: 03.07.2009
Сообщений: 10,708
02.09.2011, 22:43 11
Цитата Сообщение от KING1994 Посмотреть сообщение
Кстати я нашел альтернативный вариант решения
это не альтернативный вариант, это бред, который написал ребенок из ясельной группы. Я не знаю, пусть там бы еще афинные преобразования автор влепил бы, пару численных методов, еще кучу мусора, ведь и так перфоманс наглухо убитый, парой часов больше, парой часов меньше, чего уж там мелочиться. Для сравнения, мой код считает 100000! за полтора часа. Можете посмотреть за сколько это выполнит "альтернативный" вариант
Все вычисление уложилось в эти строки
C++
1
2
3
4
5
6
        cin>>a;
        for(i=0;i<a;i++,j++)
        {
                sum*=j;
        }
        cout<<sum<<endl<<endl;
но все равно нереально кучеряво. К тому же точность такого вычисления очень и очень слабая. 170! - это потолок для double
0
iama
1326 / 979 / 119
Регистрация: 30.07.2010
Сообщений: 5,297
02.09.2011, 23:14 12
M128K145, что-то медленно, асимптотика должна быть вроде http://www.cyberforum.ru/cgi-bin/latex.cgi?\Theta(n*size(array)), на 100 000 должна работать не дольше 10 секунд, размер массива очень большим не выйдет, если брать 32-битные числа и основание http://www.cyberforum.ru/cgi-bin/latex.cgi?10^9
0
M128K145
Эксперт JavaЭксперт С++
8326 / 3547 / 420
Регистрация: 03.07.2009
Сообщений: 10,708
02.09.2011, 23:44 13
iama, ошибаетесь посмотрите внимательно на код - n*size не будет, для 100000! необходимо 450+K разрядов, это 150+K элементов массива, в которых не более 3 разрядов. Количество задействованных элементов увеличивается. Если на первых 6 шагах достаточно только 1 элемента массива, то дальше - больше. На последнем шаге это будет (150+Kx - Ny) умножений, где x - задействованные элементы массива, y - младшие нулевые разряды, поэтому ваши расчеты сложности алгоритма не верны
0
grizlik78
Эксперт С++
1990 / 1480 / 194
Регистрация: 29.05.2011
Сообщений: 3,063
03.09.2011, 00:16 14
Ну по-крайней мере GMP справляется с таким факториалом (100000!) меньше чем за три секунды. Хотя своё, конечно, интереснее

Добавлено через 27 минут
А вот эта реализация за 20 секунд, что тоже неплохо для столь небольшого кода. Так что есть ещё куда расти
0
M128K145
Эксперт JavaЭксперт С++
8326 / 3547 / 420
Регистрация: 03.07.2009
Сообщений: 10,708
03.09.2011, 00:16 15
grizlik78, я ж не спорю Это решение в лоб, есть же еще более быстрые приближенные вычисления. Тем более в моем способе используется слишком много арифметики и он реализован на массиве.
К примеру на той же Java(а этот способ был изначально написан на Java, а потом переписан на C# и C++) можно использовать встроенные типы, например BigInteger. Тогда время вычисления сокращается до 44 секунд
Java
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
import java.math.BigInteger;
import java.util.Date;
 
/**
 * The Class Main.
 * 
 * Created on: 02.09.2011
 * 
 * @author: M128K145
 */
public class Main {
 
   /**
    * The main method.
    * 
    * @param args
    *           the arguments
    */
   public static void main(String args[]) {
      Date start = new Date();
      BigInteger fact = BigInteger.ONE;
      for (int i = 1; i < 100000; ++i)
         fact = fact.multiply(new BigInteger(i + ""));
      Date end = new Date();
      System.out.println("Result: " + fact.toString());
      System.out.println("Time: " + (end.getTime() - start.getTime()));
 
   }
}
Кстати, в 100000! ровно 456569 разрядов
0
grizlik78
Эксперт С++
1990 / 1480 / 194
Регистрация: 29.05.2011
Сообщений: 3,063
03.09.2011, 00:32 16
Цитата Сообщение от M128K145 Посмотреть сообщение
Кстати, в 100000! ровно 456569 разрядов
А это уже странно. Так как у меня двумя разными способами (с помощью GMP и кодом от diagon) получаются одинаковые числа, в которых 456574 разряда

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

Добавлено через 3 минуты
Да и код, вроде, о том же говорит. Как это я сразу в код посмотреть не догадался?
1
M128K145
Эксперт JavaЭксперт С++
8326 / 3547 / 420
Регистрация: 03.07.2009
Сообщений: 10,708
03.09.2011, 00:39 17
grizlik78, да, вышла небольшая очепятка, ровно пять разрядов теряются из-за строго неравенства
0
iama
1326 / 979 / 119
Регистрация: 30.07.2010
Сообщений: 5,297
03.09.2011, 09:05 18
Цитата Сообщение от M128K145 Посмотреть сообщение
посмотрите внимательно на код
ааа, так вы об авторском коде я даже и не читал я просто говорил, что оптимальное умножение длинного на короткое можно сделать не больше, чем за size.
0
diagon
Higher
1937 / 1203 / 120
Регистрация: 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
1326 / 979 / 119
Регистрация: 30.07.2010
Сообщений: 5,297
03.09.2011, 09:38 20
Цитата Сообщение от diagon Посмотреть сообщение
А БПФ же за O(nlogn) работает, т.е. он медленнее будет?
Давайте на примере прикинем. При n = 100000 и, если храним число по 9 десятичных разрядов на элемент структуры, размер массива - ~50000. Множим в столбик + аккуратно писаные переносы - size - 50000. А O(n*logn) даст явно большее число. Вполне возможно, что больше и выйдет. Но, понятно, все зависит от реализации.
1
03.09.2011, 09:38
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
03.09.2011, 09:38

Вычисление по формуле. Факториалы
Не знаю как это решить, помогите плиз Напишите программу вычисления примера...

Факториалы и условие его выполнения
Неправильно считает факториал. 1)Если факториал меньше 0 вывод 0. 2)Если...

Обьясните, почему код так странно считает факториалы
Добрый день, ув. форумчане. Есть код, считающий факториалы:#include &quot;stdio.h&quot;...


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

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

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