Задача Антифакториал

Question

Помогите найти ошибку. Задача: дано число a, проверить является ли оно факториалом числа n, вывести это число. Если такого числа n нет то вывести -1. Задачу надо решить рекурсией.

#include <iostream>

using namespace std;

int fac(int k, int n){
    if (n == 1)
        return k;
    if (n % k == 0){
        k++;
        return fac(k, n / k);
    }
    return -1;
}
int main(){
  int a;
  cin >> a;
  cout << fac(1, a);
}

Answer 1

Если диапазон вкладывается в "обычные" числа, без длинной арифметики - то все не просто просто, а очень просто:

unsigned long long isFact(unsigned long long N)
{
    unsigned long long f = 1;
    for(unsigned long long i = 1; f < N; ++i)
    {
        if ((f *= i) == N) return i;
    }
    return 0;
}

Если факториал - выводит число, если нет - 0...

Нате рекурсией...

unsigned long long isFactR(unsigned long long N, unsigned long long d = 2)
{
    if (d==2 && N==1) return 1;
    if (N == d) return d;
    if (N%d == 0) return isFactR(N/d,d+1);
    return 0;
}

Answer 2

Ваша ошибка в этом коде.

if (n % k == 0){ 
    k++; 
    return fac(k, n / k); 
}

Надо сделать так:

if (n % k == 0){ 
    return fac(k+1, n / k); 
}

И исправить точку выхода

if (n == 1) return k - 1;

Answer 3

Если говорить про вашу задачу, то не правильно увеличиваете К.Вы сначала проверяете, а потом уже увеличиваете и делите на это к. Вот так должно работать:

    #include <iostream>

using namespace std;

int fac(int k, int n) {
    k++;
    if (n == 1)
        return k;
    if (n % k == 0) {

        return fac(k, n / k);
    }
    return -1;
}
int main() {

    int a;
    cin >> a;
    cout << fac(1, a) - 1;

    //system("pause");
    //return 0;
}

БЛОГ НА HUSL

Задача Антифакториал

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