Форум программистов, компьютерный форум CyberForum.ru

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

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

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

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

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

Факториалы! - 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) { ...

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

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
M128K145
Эксперт С++
8283 / 3502 / 143
Регистрация: 03.07.2009
Сообщений: 10,706
02.09.2011, 16:11     Большие факториалы #2
факториал 3000 или вам именно на CLR надо?

Не по теме:

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

KING1994
-68 / 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! щитает незнаю почему((
iama
1249 / 974 / 49
Регистрация: 30.07.2010
Сообщений: 5,297
02.09.2011, 22:26     Большие факториалы #4
Цитата Сообщение от KING1994 Посмотреть сообщение
Правда оно ток до 170! щитает незнаю почему((
хм... Может, в double просто больше не помещается?

Не по теме:

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

KING1994
-68 / 6 / 0
Регистрация: 18.07.2011
Сообщений: 77
02.09.2011, 22:29  [ТС]     Большие факториалы #5
long double +/- 1,1810e-4932-+/-1,1810e+4932(надеюсь ети позначки вам знакомы)-ето диапазон значений лонг дабл
iama
1249 / 974 / 49
Регистрация: 30.07.2010
Сообщений: 5,297
02.09.2011, 22:31     Большие факториалы #6
KING1994, не задумывались, почему гугл не возвращает факториалов чисел, больших 170?
KING1994
-68 / 6 / 0
Регистрация: 18.07.2011
Сообщений: 77
02.09.2011, 22:33  [ТС]     Большие факториалы #7
если честно я даже не искал))но все же 200! тоже входят в диапазон значений.
iama
1249 / 974 / 49
Регистрация: 30.07.2010
Сообщений: 5,297
02.09.2011, 22:35     Большие факториалы #8
KING1994, а сколько значащих разрядов помещаются в double?
KING1994
-68 / 6 / 0
Регистрация: 18.07.2011
Сообщений: 77
02.09.2011, 22:36  [ТС]     Большие факториалы #9
4932 вроде
iama
1249 / 974 / 49
Регистрация: 30.07.2010
Сообщений: 5,297
02.09.2011, 22:38     Большие факториалы #10
KING1994, хм, как же они в 64 бита-то поместились...
Матчасть
M128K145
Эксперт С++
8283 / 3502 / 143
Регистрация: 03.07.2009
Сообщений: 10,706
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
iama
1249 / 974 / 49
Регистрация: 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
M128K145
Эксперт С++
8283 / 3502 / 143
Регистрация: 03.07.2009
Сообщений: 10,706
02.09.2011, 23:44     Большие факториалы #13
iama, ошибаетесь посмотрите внимательно на код - n*size не будет, для 100000! необходимо 450+K разрядов, это 150+K элементов массива, в которых не более 3 разрядов. Количество задействованных элементов увеличивается. Если на первых 6 шагах достаточно только 1 элемента массива, то дальше - больше. На последнем шаге это будет (150+Kx - Ny) умножений, где x - задействованные элементы массива, y - младшие нулевые разряды, поэтому ваши расчеты сложности алгоритма не верны
grizlik78
Эксперт С++
1903 / 1435 / 109
Регистрация: 29.05.2011
Сообщений: 2,990
03.09.2011, 00:16     Большие факториалы #14
Ну по-крайней мере GMP справляется с таким факториалом (100000!) меньше чем за три секунды. Хотя своё, конечно, интереснее

Добавлено через 27 минут
А вот эта реализация за 20 секунд, что тоже неплохо для столь небольшого кода. Так что есть ещё куда расти
M128K145
Эксперт С++
8283 / 3502 / 143
Регистрация: 03.07.2009
Сообщений: 10,706
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 разрядов
grizlik78
Эксперт С++
1903 / 1435 / 109
Регистрация: 29.05.2011
Сообщений: 2,990
03.09.2011, 00:32     Большие факториалы #16
Цитата Сообщение от M128K145 Посмотреть сообщение
Кстати, в 100000! ровно 456569 разрядов
А это уже странно. Так как у меня двумя разными способами (с помощью GMP и кодом от diagon) получаются одинаковые числа, в которых 456574 разряда

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

Добавлено через 3 минуты
Да и код, вроде, о том же говорит. Как это я сразу в код посмотреть не догадался?
M128K145
Эксперт С++
8283 / 3502 / 143
Регистрация: 03.07.2009
Сообщений: 10,706
03.09.2011, 00:39     Большие факториалы #17
grizlik78, да, вышла небольшая очепятка, ровно пять разрядов теряются из-за строго неравенства
iama
1249 / 974 / 49
Регистрация: 30.07.2010
Сообщений: 5,297
03.09.2011, 09:05     Большие факториалы #18
Цитата Сообщение от M128K145 Посмотреть сообщение
посмотрите внимательно на код
ааа, так вы об авторском коде я даже и не читал я просто говорил, что оптимальное умножение длинного на короткое можно сделать не больше, чем за size.
diagon
Higher
1927 / 1193 / 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 цифр) =\
Мистика в общем.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
03.09.2011, 09:38     Большие факториалы
Еще ссылки по теме:

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

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

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

большие массивы - C++
Кто-нибудь сталкивался с большими V данных? Программа ничего сложного из себя не представляет - посчитать по формуле в каждой точке....

Не большие операции с массивом. - C++
Доброго дня. Ни как не могу понять в чем причина не исполнения следующей программы. Код ищет минимальный и максимальный элементы в...


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

Или воспользуйтесь поиском по форуму:
iama
1249 / 974 / 49
Регистрация: 30.07.2010
Сообщений: 5,297
03.09.2011, 09:38     Большие факториалы #20
Цитата Сообщение от diagon Посмотреть сообщение
А БПФ же за O(nlogn) работает, т.е. он медленнее будет?
Давайте на примере прикинем. При n = 100000 и, если храним число по 9 десятичных разрядов на элемент структуры, размер массива - ~50000. Множим в столбик + аккуратно писаные переносы - size - 50000. А O(n*logn) даст явно большее число. Вполне возможно, что больше и выйдет. Но, понятно, все зависит от реализации.
Yandex
Объявления
03.09.2011, 09:38     Большие факториалы
Ответ Создать тему
Опции темы

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