0

Написал такой код, проходит 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;
}
13
  • а как нам читать условие задачи _ микроскопом? Вы выполняете и цикл и циклический вызов.... 10 июл 2020 в 7:08
  • 2
    посчитать факториал?
    – KoVadim
    10 июл 2020 в 7:09
  • как по мне, то ошибка здесь system("pause");
    – KoVadim
    10 июл 2020 в 7:10
  • Не факториал значение в 4 уже разное
    – Jool
    10 июл 2020 в 7:11
  • По мне ошибка то что 20! не помещяется в long long 10 июл 2020 в 7:12

2 ответа 2

4

На С++ представляем число просто в виде 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 работает немного дольше (понятно, не в смысле питоновский файл :), а измененный алгоритм расчета на С++)...

3

Без длинной арифметики не обойтись. Для вычисления можно заметить, что 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

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.