Задача найти F(N)

Question

Написал такой код, проходит 4 теста всего. Условие: F(N) = N * F(N - 1) * F(N - 2)* ... * F(1). F(1) = 1.

Ввод Число N (1 ≤ N < 20).

Вывод Значение F(N).

Пример ввода 1
1

Пример вывода 1
1

Пример ввода 2
2

Пример вывода 2
2

Пример ввода 3
3

Пример вывода 3
6

#include <stdio.h>
#include <stdlib.h>

unsigned long long func(int num)
{
    unsigned long long znach = num;
    while (num > 1)
    {
        znach = znach * func(num - 1);
        num -= 1;
    }
    return znach;
}
int main()
{
    int n;
    scanf_s("%d", &n);

    printf("%d\n", func(n));
    system("pause");
    return 0;
}

Answer 1

Без длинной арифметики не обойтись. Для вычисления можно заметить, что n-й член равен квадрату предыдущего, делённому на n-1, и умноженному на n. Для некоторого сокращения промежуточных чисел лучше сразу разделить

res = 1;
for (int i = 2; i<=n; i++) 
   res = (res / (i-1)) * i * res;

Однако длинное деление мы не любим, поэтому лучше от него избавиться, сохраняя "недоделанный" промежуточный результат:

big res = 1;
for (int i = 2; i<=n; i++) {
   res = res * res * (i-1);
return res * n;

Для контроля - код на Python, где длинная арифметика встроена (обрезал на значении, которое ещё влезает в строку)

def f(n):
    res = 1
    for i in range(2, n + 1):
        res = res * res * (i-1)
    return res * n

for i in range(1, 9):
    print(f(i))

1
2
6
48
2880
9953280
115579079884800
15266884236590834264309760000
262212473580148912869121218589990322256745385164800000000

Answer 2

На С++ представляем число просто в виде vector<unsigned int> и расписываем длинную арифметику. Поскольку прямая рекурсия в этом случае убьет любые надежды даже при обычной арифметике, применяем мемоизацию.

#include <vector>
#include <iostream>
#include <iomanip>
#include <algorithm>

using namespace std;

using ullong = unsigned long long int;

class tooLong
{
public:
    static const unsigned int magic = 1000000000, digs = 9;
    tooLong(unsigned int n = 0)
    {
        while(n)
        {
            a.push_back(n % tooLong::magic);
            n /= tooLong::magic;
        }
        if (a.empty()) a.push_back(0);
    };

    friend tooLong operator *(const tooLong& a, const tooLong& b);
    friend ostream& operator <<(ostream&os, const tooLong& a);

    bool operator !() const { return !(a.size() == 1 && a[0] == 0); }

private:
    vector<unsigned int> a;
    static vector<unsigned int> sum(const vector<unsigned int>& a, const vector<unsigned int>& b,
                                    unsigned int shift_b = 0);
    static vector<unsigned int> mul(const vector<unsigned int>& a, unsigned int b);


};

vector<unsigned int> tooLong::sum(const vector<unsigned int>& a, const vector<unsigned int>& b,
                                  unsigned int shift_b)
{
    size_t sz = max(a.size(),b.size()+shift_b);
    vector<unsigned int> r(sz);
    unsigned int c = 0;
    for(unsigned int i = 0; i < sz; ++i)
    {
        r[i] = (i < a.size() ? a[i] : 0) +
            (i < shift_b ? 0 : i < b.size()+shift_b ? b[i-shift_b] : 0)
            + c;
        c = r[i] / tooLong::magic;
        r[i] %= tooLong::magic;
    }
    if (c) r.push_back(c);
    return r;
}

vector<unsigned int> tooLong::mul(const vector<unsigned int>& a, unsigned int b)
{
    vector<unsigned int> r;
    ullong c = 0;
    for(int i = 0; i < a.size(); ++i)
    {
        ullong s = ullong(a[i]) * ullong(b) + c;
        c = s / magic;
        s %= magic;
        r.push_back((unsigned int)s);
    }
    while(c)
    {
        r.push_back(c % magic);
        c /= magic;
    }
    return r;
}


tooLong operator *(const tooLong& aa, const tooLong& bb)
{
    vector<unsigned int> r;
    const vector<unsigned int>& a = (aa.a.size() > bb.a.size()) ? bb.a : aa.a;
    const vector<unsigned int>& b = (aa.a.size() > bb.a.size()) ? aa.a : bb.a;

    for(int i = 0; i < a.size(); ++i)
    {
        vector<unsigned int> s = tooLong::mul(b,a[i]);
        r = tooLong::sum(r,s,i);
    }
    tooLong res;
    res.a = r;
    return res;
}

ostream& operator <<(ostream&os, const tooLong& a)
{
    os << a.a[a.a.size()-1];
    os << setfill('0');
    for(int i = (int)a.a.size()-2; i >= 0; --i)
         os << setw(tooLong::digs) << a.a[i];
    return os;
}


tooLong F(int N)
{
    static tooLong L[21] = {0};
    if ( !L[N] ) return L[N];
    tooLong R = 1;
    if (N == 1) return R;
    for(int m = 1; m < N; ++m)
        R = R*F(m);
    L[N] = R*N;
    return L[N];
}

int main()
{
    int N;
    cin >> N;
    cout << F(N);
}

Если хочется посмотреть, как выглядит F(19) - без проблем: https://ideone.com/iWM549 - для 20 результат слишком большой, не показывает. Тест https://ipc.susu.ru/5344-5.html код проходит без проблем.

P.S. Интересно, что вариант MBo работает немного дольше (понятно, не в смысле питоновский файл :), а измененный алгоритм расчета на С++)...

БЛОГ НА HUSL

Задача найти F(N)

Ответы (2 шт):