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

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

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

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

02.09.2011, 15:32. Просмотров 2401. Ответов 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
M128K145
Эксперт JavaЭксперт С++
8320 / 3540 / 143
Регистрация: 03.07.2009
Сообщений: 10,708
02.09.2011, 16:11 #2
факториал 3000 или вам именно на CLR надо?

Не по теме:

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

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

Не по теме:

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

0
KING1994
-68 / 6 / 0
Регистрация: 18.07.2011
Сообщений: 77
02.09.2011, 22:29  [ТС] #5
long double +/- 1,1810e-4932-+/-1,1810e+4932(надеюсь ети позначки вам знакомы)-ето диапазон значений лонг дабл
0
iama
1254 / 979 / 49
Регистрация: 30.07.2010
Сообщений: 5,297
02.09.2011, 22:31 #6
KING1994, не задумывались, почему гугл не возвращает факториалов чисел, больших 170?
0
KING1994
-68 / 6 / 0
Регистрация: 18.07.2011
Сообщений: 77
02.09.2011, 22:33  [ТС] #7
если честно я даже не искал))но все же 200! тоже входят в диапазон значений.
0
iama
1254 / 979 / 49
Регистрация: 30.07.2010
Сообщений: 5,297
02.09.2011, 22:35 #8
KING1994, а сколько значащих разрядов помещаются в double?
0
KING1994
-68 / 6 / 0
Регистрация: 18.07.2011
Сообщений: 77
02.09.2011, 22:36  [ТС] #9
4932 вроде
0
iama
1254 / 979 / 49
Регистрация: 30.07.2010
Сообщений: 5,297
02.09.2011, 22:38 #10
KING1994, хм, как же они в 64 бита-то поместились...
Матчасть
1
M128K145
Эксперт JavaЭксперт С++
8320 / 3540 / 143
Регистрация: 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
1254 / 979 / 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
0
M128K145
Эксперт JavaЭксперт С++
8320 / 3540 / 143
Регистрация: 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
Эксперт С++
1982 / 1475 / 126
Регистрация: 29.05.2011
Сообщений: 3,048
03.09.2011, 00:16 #14
Ну по-крайней мере GMP справляется с таким факториалом (100000!) меньше чем за три секунды. Хотя своё, конечно, интереснее

Добавлено через 27 минут
А вот эта реализация за 20 секунд, что тоже неплохо для столь небольшого кода. Так что есть ещё куда расти
0
M128K145
Эксперт JavaЭксперт С++
8320 / 3540 / 143
Регистрация: 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
03.09.2011, 00:16
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
03.09.2011, 00:16
Привет! Вот еще темы с ответами:

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

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

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

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


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

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

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