Recursividad

Iniciado por Abanda_9, 28 Mayo 2010, 21:04 PM

0 Miembros y 1 Visitante están viendo este tema.

Abanda_9

Hola!! soy nueva en el foro y no entiendo muy bien la programacion...la actividad en la cual tengo dudas es en la siguiente:


Dado un vector ordenado crecientemente A[1...n], n>=1, diseña un algoritmo que calcule de forma recursiva la longitud de la escalera más larga, es decir, la longitud de la secuencia más larga de valores consecutivos que se encuentre en A.


No tengo el codigo porque ni siquiera se que poner ya que el tema de recursividad se me da bastante mal, asi que agradeceria que alguien me explicara el codigo paso a paso para futuras actividades...

Gracias de antemano!!

Ari Slash

para entender la recursividad primero hay que entender la recursividad

[L]ord [R]NA

El codigo es  bien sencillo, recursividad es cuando desde dentro de una funcion, esta se llama a si misma. Por las reglas si no publicas un codigo minimo desde donde guiarte no se puede hacer nada.

Akai

Pon algo de código y entonces te ayudaremos, una de las normas es que nos e hacen tareas.

Aun así, te explicaré un poco sobre recursividad:

http://es.wikipedia.org/wiki/Algoritmo_recursivo

Básicamente, un algoritmo recursivo es aquel que se llama a si mismo hasta que llega a un caso base, en el que para la recursión. Por ponerte el ejemplo de un factorial, el descrito en la wikipedia:

para n=5, y por tanto cálculo de 5! -> se intenta realizar 5*4!-> se llama a 4!
se intenta calcular 4*3! -> se llama a 3!
se intenta calcular 3*2! -> se llama a 2!
se intenta calcular 2*1! -> se llama a 1!
1 es <= que uno, asi que se devuelve un 1
se realiza 2*1!, ya que 1! ha devuelto un 1.
se realiza 3*2! ya que 2! ha devuelto 2*1, 2
se realiza 4! ya que 3! ha devuelto 6, (3*2)
y se realiza 5! ya que 4! ha devuelto 24 (4*6)

tal como ves, la recursión se basa en un camino de ida (donde se realizan llamadas recursivas hasta que se llega al caso base (o solución sencilla del problema) y luego esta solución recorre un camino de vuelta.

Abanda_9

A ver, aqui os dejo hasta donde he podido llegar. Se que me falta lo mas importante, pero no consigo tenerlo...

No se si estoy cometiendo alguna locura con el codigo, asi que si hay algun error muy grave perdonadme T_T

-------------------

He hecho un fichero con varios modulos:
El primero se llama ordenacion y he puesto lo siguiente (lo he probado y funciona bien)---


#include <stdio.h>
#include <stdlib.h>
#include "burbujamejorada.h"

//Cabecera: burbuja_mejorado(E/S vect:v, E entero: n)
//Precondicion: n>0 y n pertence a los numeros naturales. V es un vector de n elementos.
//Postcondicion: Vector v con los elementos ordenados ascendentemente.

void burbuja_mejorado(int *vector, int tam)
{
     int i,j,aux,no_interc;
     i=0;
     do{
         no_interc=1;
         for(j=0;j<tam-i-1;j++){
                      if(vector[j]>vector[j+1]){
                                      aux=vector[j+1];
                                      vector[j+1]=vector[j];
                                      vector[j]=aux;
                                      no_interc=0;}}
         i++;
     }while(no_interc==1);
}
     

Otro modulo que genere un vector aleatorio (que tambien funciona correctamente)----

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include "generar_vector.h"


int generar_vector_aleatorio(int *vector,int tam){
    int i;
    srand(time());
    for(i=0;i<tam;i++)
                      {
                      vector=rand();
                      }
                      }


Otro módulo con el vector ya ordenado crecientemente (este no se si funciona porque no me ha dado tiempo a comprobarlo):

#include <stdio.h>
#include <stdlib.h>
#include "vector_creciente.h"


vector_creciente(int vector, int tam)

{
int aux,i ;

generar_vector_aleatorio(vector,tam);
burbuja_mejorada(vector,tam);

for(i=0;i<tam;i++){
                   vector[aux]=vector[tam-i];
                   vector[tam-i]=vector;
                   vector=vector[aux];
                   }
                   }
                   


Y ahora, me centro en el principal, no se si hacer una funcion a parte ni como podria ser o si hay alguna manera mas facil... ni idea :( :::


#include <stdio.h>
#include <stdlib.h>
#include "principal.h"

int main(){
    int vector,tam,cont;
   
    printf("tamaño del vector");
    scanf("%i",&tam);
   
    vector= (int*) malloc (tam*sizeof(int));
           
    vector_creciente(vector,tam);
   

Desde aqui ya no se como seguir... ni siquiera se como expresarlo de otra manera T_T o si hay alguna forma muchisimo más rapida que esta...