Jump to content

[Desafio] Factorial recursivo


neon_prannock

Recommended Posts

Desta vez, no IRC (#p@p) o desafio era escrever a função que calcula o factorial de um número, recursivamente. Desta forma também podemos demonstrar a muitos programador o método de resolução de algoritmos recursivo que, infelizmente, muitos ainda desconhecem.

E aqui estão os códigos:

Common Lisp:

(defun fact (n)
  (if (= n 0)
      1
      (* n (fact (1- n)))))

Scheme:

(define (fact n)
  (if (= n 0)
      1
      (* n (fact (- n 1)))))

C/C++:

int fact(int n)
{
  return !n ? 1 : n * fact(n-1);
}

C++ (c/ templates):

template<int N> class Factorial {
public:
   enum { value = N * Factorial<N-1>::value };
};

template<> class Factorial<1> {
public:
   enum { value = 1 };
};

Ruby:

def fact( num )
  return 1 if num==0
  num * fact( num-1)
end

Python:

def fact(num):
  if num == 0:
    return 1
  else:
    return num * fact( num-1 )

Java:

import java.math.BigInteger;
class Factorial {
    public static BigInteger fact(BigInteger n) {
        if(n.equals(BigInteger.ZERO))
            return BigInteger.ONE;
        return n.multiply(fact(n.subtract(BigInteger.ONE)));
    }
}

Prolog:

factorial(0,1).
factorial(N,Value) :- NMINUS1 is N-1, factorial(NMINUS1,ValueNMINUS1), Value is N*ValueNMINUS1. 

Dylan:

define method factorial(n :: <integer>)
  if (n == 0)
     1
  else
     n * factorial (n - 1)
  end if
end method factorial

Haskell:

fact 0 = 1
fact n = n * (fact (n - 1))

Visual Basic 6:

Private Function Fact(num As Integer)
If num = 0 Then
    Fact = 1
    Else
        Fact = num * Fact(num - 1)
End If
End Function


Apresentem também esta função nas vossas linguagens para se ir adicionando...

PS: o geshi faz falta 😉

Link to comment
Share on other sites

  • 4 weeks later...

"curti" o algoritmo que usaste

só experimentei em scheme

experimenta la fazer

(fact 50000)

vai no mínimo "comer" uns 50 MB de RAM

e assim?

(define (fact n)
 (factaux n 1))

(define (factaux n total)
(if (zero? n)
    total
    (factaux (sub1 n) (* n total))))

bem menos

🙂

se calhar se usarmos ciclos (caso a linguagem o permita) ainda gasta menos memória e é mais eficiente...

Link to comment
Share on other sites

  • 1 year later...

Aqui fica um exercícizito.

Calcular todos os factoriais de X! a Y! 😄

Aqui ficam duas soluções em Python, ambas iterativas.

A primeira:

x = 1
y = 100
while x < y:
j = 1
ii = 1
while ii <= x:
	j *= ii
	ii += 1
print j
x += 1

A segunda (na verdade, foi o que eu escrevi depois de ter pensado melhor no anterior 😄 ) mas que só funciona para x = 1 (quando pensei no exercício não era para dar X, apenas Y):

x = 1
y = 100
j = 1
while x < y:
j *= i
print j
x += 1

Não peças ajuda por PM! A tua dúvida vai ter menos atenção do que se for postada na secção correcta do fórum!

Link to comment
Share on other sites

Podias simplesmente passar o while interior para fora, e com o teu j *= i chegavas à mesma solução.

Foi o que eu fiz na segunda.


Agora uma solução recursiva (sim Warrior, esta é para ti 😁):

def factAte(x, y, i = None):
if i == None:
	i = factAte(1, x-1, 1)
	print i
else:
	i *= x
	print i
if x <= y:
	factAte(x+1, y, i)
return i

Não peças ajuda por PM! A tua dúvida vai ter menos atenção do que se for postada na secção correcta do fórum!

Link to comment
Share on other sites

Bem eu hoje iniciei-me no C++ e até puxei conversa sobre isto no canal então cá vai o que fiz

#include <iostream>
using namespace std;

long factorial(long x)
{
  if (x > 1)
   return (x * factorial(x-1));
  else
   return (1);
}
int main()
{
    long de,ate;
    cout << "De: ";
    cin >> de;
    cout << "Ate: ";
    cin >> ate;
    while (de <= ate)
    {
          cout << de << "! = " << factorial(de) << endl;
          de++;
    }
    cin.get();
    cin.get();
    return 0;
}

Pode não estar da melhor forma mas também ainda não sei muita coisa 😄 e também isto tem limite pois se meteres pa i de 1 a 20 ele "chora" logo apartir de determinada altura 😄

e em c#:

static void Main(string[] args)
        {
            long de, ate;
            Console.WriteLine("De: ");
            de = long.Parse(Console.ReadLine());
            Console.WriteLine("Ate: ");
            ate = long.Parse(Console.ReadLine());
            while (de <= ate)
            {
                long fact = factorial(de);
                Console.WriteLine("{0}! = {1}",de,fact);
                de++;
            }
            Console.ReadLine();
        }
        static long factorial(long x)
        {
            if (x > 1)
                return (x * factorial(x - 1));
            else
                return (1);
        }
Link to comment
Share on other sites

Pode não estar da melhor forma mas também ainda não sei muita coisa 😄 e também isto tem limite pois se meteres pa i de 1 a 20 ele "chora" logo apartir de determinada altura 👍

Pois chora. Se olhares para o teu algoritmo vês que é bastante ineficiente, porque estás sempre a calcular todo o factorial.

Imagina que fazes de 5 a 6.

Para o 5 vais fazer 1 * 2 * 3 * 4 * 5 e para o 6 vais fazer 1 * 2 * 3 * 4  * 5 * 6, o que não é boa ideia, podes simplesmente pegar no resultado do 5 e multiplicares pelo 6. Estás a perceber o esquema?

E deixo aqui a versão em Haskell 😛

factoriais x y = scanl (*) inicio [succ x..y]
   where inicio = product [1..x]

"Give a man a fish and he will eat for a day; Teach a man to fish and he will eat for a lifetime. The moral? READ THE MANUAL !"

Sign on a computer system consultant's desk

Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
×
×
  • Create New...

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.