Foro de elhacker.net

Como se puede resolver el siguiente problema:


El factorial de un n ́mero n entero positivo se define recursivamente

n = 0: n! = 1
n = 1: n! = 1
n > 1: n × (n − 1)!


Diseñe un algoritmo con un solo bucle que resuelva el siguiente problema

n, fact: entero
{Pre ≡ n = N ∧ N > 0}
factorial
{Post ≡ f act = N !}
Siendo el invariante del bucle el predicado siguiente

                 (i-1)!n!
Inv ≡ fact=-------------  ∧ i≤j+1 ∧ n=N
                      j!


El n ́mero de iteraciones del bucle no debe superar n div 2 + 1.

Da una funcion de cota.


Los pasos que sigon son:
1- Buscar la condicion de continuacion (INV ^ NOT(B) = POST)
B = ?
me sale que si i<>1 y j<>0 se cumple

2-inicializar:
fact = 1
n lo tienes que leer del teclado.
j = n
i = 1
pero asi (i-1)! no sierve para nada.

3-Avanzar:
j := j - 1
porque j = n y tiene que acabar en 0
pero asi el numero de iteraciones creo que no sera n div 2 +1

4- Restablezer:
Las operaciones que hay que realizar para que fact = N!

Alguna idea o algo?
GRACIAS.

El hecho de que el factorial se defina como una función matemática recursiva, no implica que en algoritmia lo tengas que hacer así.

En programación, lo que más se aproximaría a su definición recursiva, sería utilizar recursividad:

int factorial(int n){
if (n<=1)
return 1;
else
return n*factorial(n-1)}

Pero que esa sea la forma más fácil de hacerlo, no te tiene que encerrar ahí, puesto que hacerlo con un bucle es más rápido que utilizar recursividad.

Da lo mismo si yo me hago un bucle de este estilo:

factorial=n;
for(i=n-1;i>=1;i--)
factorial=factorial*i

Mismo resultado si no me he equivocado yo en algo

O incluso yendo hacia adelante, en vez de recursivamente:

factorial=1;
for(i=2;i<=n;i++)
factorial=factorial*i;

Todo esto para decirte, que no te encierres en una única forma de hacerlo.

Tienes que calcular (i-1)! n! y j! ? Pregunto por el (i-1)!

Por otro lado, no se si lo he entendido bien, pero j y n son valores fijos, quiero decir, no van a iterarse, verdad?

puedes calcular su factorial directamente con un bucle como los puestos arriba y guardarte ese resultado en una variable antes de hacer nada más

y en caso de tener que calcular siempre el factorial de (i-1), en tu bucle de operaciones, puedes anidar un bucle para calcular dicho factorial (en caso de ser necesario, que no se si lo es. Ya digo que tengo en duda que se necesite calcular el n! * (i-1)! )

Hola,
Gracias por responder.

Yo el factorial siempre lo he hecho como dices tu.
Pero este metodo que te he escrito es una proposicion, un ejercicio. Me pide usar ese invariante.

N es un valor fijo, y "j" e "i" si van a iterarse. Creo.

Vale, acabo de echarle un ojo más a fondo (que antes andaba medio dormido)

El factorial de algo, en principio se calcula en tiempo n iteraciones:
n*(n-1)! --> n*(n-1)*(n-2)! y así.


Ejemplo: 6!
6*5! --> 6*5*4! --> 6*5*4*3! --> 6*5*4*3*2! --> 6*5*4*3*2*1

Pero a ti te limitan a (n/2)+1. iteraciones Posible solución?

Recorres a la vez por ambos lados.

fact=1
primera iteracion:
fact=fact=6*1

segunda:
fact=fact *5*2

tercera:
fact=fact*3*4

Iteraciones para el factorial de 6? 3.

En cambio, si tienes una n impar, tienes un número impar de términos en el factorial que podría causar que volvieses a multiplicar un término, por lo que si N fuese impar, en vez de desarrollar el factorial hasta 1, lo dejas en 2.

Factorial de 7:

fact=1
Primera iteración:
fact=fact*7*2

segunda:
fact=fact*6*3

tercera:
fact=fact*5*4

y en código, podría ser algo así:

if (n%2==0) // numero par
  empieza=1;
else
  empieza=2;
 
factorial=1;
 
for(i=0;i<n/2;i++)
  factorial=factorial*(n-i)*(i+empieza);
 

Y si no me he equivocado al trasladarlo a código, con eso desarrollas un factorial en n/2 iteraciones.

A partir de aquí, creo que ya puedes continuar por tu cuenta.

EDIT: vale, ya, que estaba probando si realmente funcionaba el código

Gracias, es lo que buscaba.