Problema con algoritmo

-

-Itachi- #1 Ene '07

Buenas noches, estaba yo haciendo unos ejercicios de programación nocturnos, cuando he llegado a uno extraño, que no había visto nunca.
Se trata de una función definida recursivamente, en la que ya he conseguido resolver una parte.
Sin embargo, la otra me trae de cabeza.

La función es tal que asi:
0; si N < 0;
1; si N = 0;
(X + Y ) *F(X2; Y 2;N div 2); si N mod 2 = 1;
F(X2; Y 2;N div 2) + X * Y * F(X2; Y 2; (N div 2) - 1); si N mod 2 = 0:

Trata de hacer un sumatorio de potencias, es en el último caso donde me da problemas.
Ah, no se pueden usar acciones ni funciones, si no sería sencillo.

¿Alguna idea?

-

-Itachi- #2 Ene '07

He podido resolver ootr oparecido, pero es en la suma de F(x2,y2,ndiv2)+xyF(x2,y2,ndiv2)-1) donde me atasco.
Por ahora, el algoritmo va tal que asi:

var x,s,y:real; n:integer;
begin
s:=1;
writeln('introduce x');
readln(x);
writeln('Introduce y');
readln(y);
writeln('introduce n');
readln(n);

while n<>0 do
begin
if (n mod 2=1) then begin
s:=s(x+y); x:=xx; y:=yy; n:=(n div 2);
end
else begin
s:=(sxy); x:=xx; y:=y*y; n:=(n div 2)-1;
end;

end;
readln;

writeln('El resultado de la suma de la progresi¢n es', s);

readln;
end.

LOc0 #3 Ene '07

Edito. Tienes que pasar de recursivo a iterativo. Mmm...

Salu2

-

-Itachi- #4 Ene '07

En la segunda condición, no sé que poner.
El uso de la función dos veces con distintos valores de n en la misma condición me lia.

LOc0 #5 Ene '07

No me hagas mucho caso pero creo que necesitas un bucle while independiente por cada llamada a f().

Me piro a sobar. Sorry si no te he servido de mucho, pero a estas horas no está la cabeza para ciertas cosas

Salu2

-

-Itachi- #6 Ene '07

Gracias de todas maneras ^^.

LOc0 #7 Ene '07

Ni caso. Mañana lo miraré tranquilamente.

Salu2

-

-Itachi- #8 Ene '07

Ahahaha, idea feliz y obvia.

Se pueden separar los dos sumandos, hacer cada uno por su lado y volverlos a sumar al final .

EDIT mañanero: No funciona tampoco asi xD.De esa manera solo funciona el caso n=2, el resto falla xD.

javithelong #9 Ene '07

He creido entender que tu problema es esta línea:
F(X2; Y 2;N div 2) + X * Y * F(X2; Y 2; (N div 2) - 1); si N mod 2 = 0:

No entiendo lo de X2 Y2, pero vamos, si tienes que hacer iterativa esa suma de 2 recursiones, tienes que hacer 2 bucles con las mismas condiciones que el 1º (ya que es la misma función) pero una para cada recursión. Intenta algo asi:

while( blablabla) {
----> metes aqui en una variable el resultado de toda la iteración de la 1ª recursion (ej: aux1:integer)
}
while (blablabla){
----> metes aqui el resultado de la 2ª iteración (ej: aux2:integer)
}
Y aqui haces aux1+aux2

Todo esto dentro del bucle grande, claro. No se si me he expresado con claridad, o si funcionará ^^, pero así a primera vista es lo que se me ha ocurrido.

Saludos

EDIT: Si es lo que dices que has hecho en #8 comprueba que esté el código correcto con un debugger.

-

-Itachi- #10 Ene '07

#9 Eso es lo que he hecho xD, dos bucles separados, y sin embargo no sale, ya que tendríamos el doble del valor de s al multipilcar por el caso de nmod2=1 dos veces :S.

LOc0 #11 Ene '07

Tienes que USAR UNA TABLA e ir calculando todos los valores desde el n=0 hasta n=N.

Salu2

-

-Itachi- #12 Ene '07

#11 Ya lo pensé, le pregunté al profesor y me dice que no, que tiene su solución sin tablas xDD.
Es la reencarnación de Hitler ese hombre.

javithelong #13 Ene '07

Oie, y te deja usar variables? o algo? xD

Pues colega, si consigues la solución ponla, porque no se me ocurre nada más :s

Un comentario na mas:
0; si N < 0;
1; si N = 0;
Tienes puesto al principio un par de ifs para salir en esos casos? en plan

if (n=0) s=s+1; break;
if (n<0) break;

(o tampoco puedes usar breaks xD)

EDIT: No recuerdo sin en pascal habia breaks... supongo que habrá algo parecido...

-

-Itachi- #14 Ene '07

Si, claro que deja usar variables xD.
Ya posetearé el resultado cuando lo obtenga :S (Esperemos que sea pronto)

gF #15 Ene '07

y no lo puedes resorver mediante un algoritmo recursivo?

m0rG #16 Ene '07

#15

"Ah, no se pueden usar acciones ni funciones, si no sería sencillo."

A ver si leemos mejor xD.

Usuarios habituales