Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.92/13: Рейтинг темы: голосов - 13, средняя оценка - 4.92
0 / 0 / 0
Регистрация: 03.02.2017
Сообщений: 10
1

Самый быстрый алгоритм Факториала

10.02.2017, 14:32. Показов 2675. Ответов 12

Всем привет ! Как можно реализовать факториал за log(n) . Помогите плиз ! Знаю ,что можно рекурсией . Но этот алгоритм не быстрый. Помогите !
0

Помощь в написании контрольных, курсовых и дипломных работ здесь.

Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
10.02.2017, 14:32
Ответы с готовыми решениями:

Самый быстрый алгоритм на с++ для поиска изображений с погрешностью
Подскажите самый быстрый алгоритм для поиска одного изображения на другом с погрешностью. То есть...

Самый быстрый способ решения задачи a+b
несколько раз ходил на олимпиады, во многих из них в пробном туре даётся задача а+б, решаю её...

Найдите самый быстрый поезд и его скорость
Помогите с кодом, пожалуйста! Между двумя крупнейшими городами нашей страны Санкт-Петербургом и...

Какой самый быстрый способ решения СЛАУ?
Доброго дня. Помогите выбрать СЛАУ(системы линейных алгебраических уравнений), которым СЛАУ будет...

12
131 / 157 / 87
Регистрация: 06.04.2016
Сообщений: 992
10.02.2017, 14:34 2
А логарифм какой? Десятичный или натуральный?
0
0 / 0 / 0
Регистрация: 03.02.2017
Сообщений: 10
10.02.2017, 14:40  [ТС] 3
точно не известно . Через рекурсию делаю ,даёт Time limit . Есть ли какой то быстрый алгоритм ?
0
131 / 157 / 87
Регистрация: 06.04.2016
Сообщений: 992
10.02.2017, 14:53 4
Цитата Сообщение от Program style Посмотреть сообщение
Как можно реализовать факториал за log(n).
- за log(n) чего? Операций?

Добавлено через 13 минут
Ну Вы значит какой-то логарифм считаете? А какой именно?
У меня в C++Builder6 так обозначается натуральный логарифим, но я подумал что здесь может быть и десятичный.
0
Don't worry, be happy
17164 / 10048 / 1934
Регистрация: 27.09.2012
Сообщений: 25,035
Записей в блоге: 1
10.02.2017, 14:59 5
Кэшируйте и получите за O(1).
0
131 / 157 / 87
Регистрация: 06.04.2016
Сообщений: 992
10.02.2017, 15:03 6
Вот оригинальный(наивный) и быстрые алгоритмы:
https://habrahabr.ru/post/255761/.
0
0 / 0 / 0
Регистрация: 03.02.2017
Сообщений: 10
10.02.2017, 15:05  [ТС] 7
Я видел эту статью ,но у меня выходит такая ошибка error: 'BigInteger' does not name a type.
0
131 / 157 / 87
Регистрация: 06.04.2016
Сообщений: 992
10.02.2017, 19:34 8
Ну подставь любой тип(int, float или double), там же главное суть понять, что они разбиваются до тех пор пока не останется пара(см. второй алгоритм сверху).
0
2 / 2 / 1
Регистрация: 09.10.2016
Сообщений: 29
10.02.2017, 19:49 9
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int ProdTree(int l, int r)
{
    if (l > r)
        return 1;
    if (l == r)
         return l;
    if (r - l == 1)
        return (int)l * r;
    int m = (l + r) / 2;
    return ProdTree(l, m) * ProdTree(m + 1, r);
}
        
int FactTree(int n)
{
    if (n < 0)
        return 0;
    if (n == 0)
        return 1;
    if (n == 1 || n == 2)
        return n;
    return ProdTree(2, n);
}
0
Любитель чаепитий
3578 / 1679 / 518
Регистрация: 24.08.2014
Сообщений: 5,697
Записей в блоге: 1
10.02.2017, 20:01 10
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 <iostream>
#include <unordered_map>
 
int main()
{
    std::unordered_map<int, int> factorials
    {
        {0, 1}, 
        {1, 1}, 
        {2, 2}, 
        {3, 6}, 
        {4, 24}, 
        {5, 120}, 
        {6, 720}, 
        {7, 5040}, 
        {8, 40320}, 
        {9, 362880}, 
        {10, 3628800}, 
        {11, 39916800}, 
        {12, 479001600}, 
        {13, 6227020800}, 
        {14, 87178291200}, 
        {15, 1307674368000}
    };
    
    int n{};
    
    std::cin >> n;
    
    std::cout << factorials[n];
}
0
Падаван С++
445 / 259 / 89
Регистрация: 11.11.2014
Сообщений: 908
10.02.2017, 20:11 11
Program style, вот пример переделаный из решенных задач, вместо фибоначи в compile time считаем факториал
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
#include <iostream>
#include <stdint.h>
 
namespace Constants {
    const unsigned long long FactorialSize = 32;
}
 
template<int t> struct Elem {
    static const unsigned long long value = t * Elem<t - 1>::value;
};
template<> struct Elem<0> {
    static const unsigned long long value = 0;
};
template<> struct Elem<1> {
    static const unsigned long long value = 1;
};
template<int r, int t> struct Table : Table<r + 1, t - 1> {
    Table() { values[t] = Elem<t>::value; }
};
template<int r> struct Table<r, 0> {
    unsigned long long values[r + 1];
    Table() { values[0] = Elem<0>::value; }
    const unsigned long long& operator[](int i) const { return values[i]; }
};
 
typedef Table<0, Constants::FibSize> Fibonachi;
 
int main(int argc, char *argv[]) {
    Fibonachi fArray;
 
    std::cout << sizeof(unsigned long long) << std::endl;
 
    for (size_t i(0); i < Constants::FactorialSize; ++i)
        std::cout << fArray[i] << std::endl;
 
 
 
    std::cin.ignore();
    return 0;
}
0
Don't worry, be happy
17164 / 10048 / 1934
Регистрация: 27.09.2012
Сообщений: 25,035
Записей в блоге: 1
10.02.2017, 20:18 12
GbaLog-, Зачем unordered_map?
Достаточно массива.
0
Любитель чаепитий
3578 / 1679 / 518
Регистрация: 24.08.2014
Сообщений: 5,697
Записей в блоге: 1
11.02.2017, 07:23 13
Цитата Сообщение от Croessmah Посмотреть сообщение
Зачем unordered_map?
Достаточно массива.

Мыслями уже во сне был.
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
11.02.2017, 07:23

Самый быстрый способ дополнить вектор массивом
есть вектор заполненный нулями: vector&lt;int&gt; v(100000); есть большой массив: int ar;...

Считать квадратную матрицу. Какой самый быстрый способ это сделать?
Какие самые быстрые способы считывания в с++? Пример : мне надо считать квадратную матрицу. Какой...

Самый быстрый способ посчитать сумма элементов матрицы, находящихся в матрице
Здравствуйте форумчане! Подскажите мне самый быстрый способ нахождении суммы элементов матрицы,...

как заполнить вектор векторов прямо в программе (самый быстрый метод)
почему не работает? #include&lt;cstdio&gt; #include &lt;vector&gt; using namespace std; vector&lt;int&gt; a;...


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

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

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