Este es el tutorial mas avanzado de c++ para olimpiadas. Si ya sabes c++ por ahi algunas cosas ya las conoces, si no sabes nada de c++ empeza por el tutorial basico en el otro tutorial.
Al igual que en el tutorial anterior me presento soy Ariel Nowik 5to año de ort almagro capital federal (son 6 años en ort), participe 2 veces en cym.
Al terminar el tutorial, tendras la teoria suficiente para resolver cualquier problema. (¡El resto son ideas!) Sin embargo, todo esto no es ni una minima parte del potencial total que el lenguaje c++ ofrece. Todos estos conocimientos además, no son solo validos para c++, si bien en en diferente forma, estan todos presentes en casi todos los lenguajes conocidos (python,php,java,javascript,c#,as3, y más). No obstante, los arrays de c++, segun mi experiencia solo los vi en c y c++ existir. (En los demas lenguajes se usan exclusivamente vectores en general)
Funciones
Una funcion es un conjunto de lineas de codigo archivados con un sobrenombre, que pueden ser llamadas todas en uno invocando al sobrenombre. Tiene dos caracteristicas fundamentales que son los valores de entrada a la funcion, que son variables del tipo correspondiente segun la funcion, pueden ser en cualquier cantidad y en cualquier tipo, con los que uno regula como quiere que la funcion ejecute los comandos, y uno o 0 valores de devolucion, que son los datos que la funcion nos da como respuesta y podemos almacenar en otra variable del tipo correspondiente. En tutoriales anteriores usamos funciones como pow(double a,double b), que era una funcion que se le entraba con valor a un double, como valor b un double y como resultado nos daba un double que era a elevado a la b, que podiamos almacenar en una variable de tipo double o int (aunque era redondeada si tenia coma al hacer esto).
Una funcion se crea 2 veces en c++ para ser utilizada. El prototipo y la implementacion, el prototipo es solo que entra y que sale de la funcion expresado en una linea (las funcioens siempre se declaran afuera del int main()!!!), mientras que la implementacion es lo mismo que el prototipo, pero con los comandos que contiene. Debe hacerse un prototipo para que el compilador de c++ pueda entender el programa bien, no porque sea mejor o de algun beneficio, en muchos lenguajes no son nescesarios, en c++ si.
//Prototipo tipo_de_dato_de_devolucion nombre_de_funcion( tipo_de_dato dato_1 , tipo_de_de_dato dato_2 , ... ); //Implementacion tipo_de_dato_de_devolucion nombre_de_funcion( tipo_de_dato dato_1 , tipo_de_de_dato dato_2 , ... ){ //codigo }
Siempre los prototipos se escriben antes del int main(){}, los comandos del programa, y la implementacion despues del int main(){}, no hay una razon real porque sea asi, es solo para que el compilador del c++ pueda entenderlo bien.
En la implementacion de la funcion, ademas de ejecutarse un codigo, debe tambien correrse el comando return seguido de una variable del tipo del dato que la funcion da como respuesta, como es la segunda caracteristica fundamental de la funcion que es el valor que la funcion dará como respuesta, cuando se corre el return la funcion termina inmediatamente y se da como resultado ese valor ignorando el codigo que pueda llegar a seguir. Hay una posiblidad de omitir ese return y es si la funcion devuelve 0 datos, que como dice arriba es posible. Para ese caso en vez de poner antes de hacer el prototipo y la implementacion un tipo de dato, se escribe simplemente void.
Pasemos a la practica, ejemplo de una funcion
#include <iostream> #include <stdlib.h> #include <stdio.h> //en linux para el getchar() solamente #include <math.h> using namespace std; /* Prototipo */ double hipotenusa_del_triangulo( double catetoA, double catetoB); int main(){ int h = 5; cout<<hipotenusa_del_triangulo( 3.0 , 4.0 ) <<endl ; cout<<hipotenusa_del_triangulo( 3.0 , 5.0 ) <<endl ; cout<<hipotenusa_del_triangulo( 6.0 , 8.0 ) <<endl ; system("pause"); } /* implementacion*/ double hipotenusa_del_triangulo( double catetoA, double catetoB){ double multA = catetoA * catetoA; double multB = catetoB * catetoB; double suma = multA + multB; return sqrt ( suma ); //sqrt es la funcion de raiz cuadrada de math.h }
SALIDA
5 5.83095 10 Presione alguna tecla para continuar ...
El beneficio de usar funciones es que podes ejecutar varias veces el mismo codigo escribiendo menos, como se ve en el ejemplo la hipotenusa de un triangulo de catetos 3 y 4 es 5, la de uno con 3 y 5 es 5.8 y la de uno con
6 y 8 es 10. Si no lo conoces la formula de la hipotenusa de triangulos rectangulos es la raiz cuadrada de la suma de cada cateto elevado al cuadrado, o sea multiplicado por si mismo. Cabe resaltar que la funcion creada, hipotenusa_del_triangulo solo tiene acceso a las variables que hayan sido reservadas (=creadas) dentro del contenido de las llaves de la funcion, no puede acceder a ninguna variable fuera de ese mundo, por ejemplo, no puede leer la variable h. Asimismo la funcion main tampoco puede leer las variables de hipotenusa_del_triangulo, como multA,multB y suma. Todas estas variables que fueron las que usamos en los tutoriales son locales, solo se pueden leer y escribir en el conjunto de llaves local. El proximo tema que veremos seran las variables globales, que, en contraste con las locales, pueden ser leidas y modificadas en cualquier lugar del programa, tanto en el int main(){} como en cualquier funcion. Esto justificaria por ejemplo que una funcion no devuelva nada y sea void a veces. Hay una discusion sobre si las variables globales son correctas usarlas. En estos programas de olimpiadas que no llegan a la complejidad extrema de proyectos gigantes, no habra problemas en usarlas y serviran para simplificar programas en muchos casos.
Variables locales y globales
En c++ hasta ahora vimos asignacion de variables a un tipo. Hasta ahora, todas las que vimos las creamos de manera local, es decir, solo podian ser leidas y escritas en codigo dentro de las {} donde fue asignada. Es decir, por ejemplo desde las funciones no podian ser accedidas. Las variables globales se pueden leer y escribir a lo largo de todo el programa cuando se desee. Ejemplo
#include <iostream> #include <stdlib.h> #include <stdio.h> //en linux para el getchar() solamente #include <math.h> using namespace std; /*Creamos una variable global*/ int variable_global = 5; /* Prototipo */ void funcion_sumar(); int main(){ int variable_local = 5; /* variable local */ for (int x = 0;x < 5;x++){ funcion_sumar(); } cout<<variable_global<<endl; cout<<variable_local<<endl; system("pause"); } /* implementacion */ void funcion_sumar(){ int variable_local = 5; variable_local ++; variable_global += 1; }
SALIDA
10 5 Presione alguna tecla para continuar ...
Como vemos las variables globales se crean siempre antes de todo, antes de los protipos de las funciones. Como el objetivo de nuestra funcion es editar una variable global, tiene sentido hacer que no devuelva valores, con void. Con este programa se deberia notar la diferencia entre variables locales y globales.
Arrays
ahora aprenderemos un nuevo de estructura de c++. Imaginemos que queremos almacenar en un programa 100 numeros. ¿creamos 100 ints? por supuesto que no, se hace muy largo. C++ nos ofrece un tipo de dato array que sirve para hacer listas de datos con tamaño fijo (no se pueden agregar mas valores a la lista en el transcurso del programa).
Para crear un array (=reservar espacio en la memoria para el array) se escribe
tipo_de_dato nombre_array[cantidad_de_valores];
ejemplo:
int lista[100];
Con lo quie tenemos una lista con 100 valores tipo int. ¿Como leemos/escribimos estos valores?
escribiendo el_nombre_del_array[numero_de_variable_a_leer], donde numero_de_variable_a_leer es una variable entera que va de 0 a la longitud del array menos 1, en este caso 100. por ejemplo con un array de longitud 4, tenemos 4 valores a modificar o leer,
el valor 0, el 1, el 2, y el 3.
Ejemplo arrays:
#include <iostream> #include <stdlib.h> #include <stdio.h> //en linux para el getchar() solamente #include <math.h> using namespace std; /*Creamos un array global*/ int array_global[5]; /* Prototipo */ void mostrar_array_global(); int main(){ /*creamos un array local*/ double array_local[3]; for (int v = 0;v < 3;v++){ array_local[v] = 2-v; array_local[v] ++; } for (int x = 0;x < 5;x++){ array_global[x] = x * 2; } for (int j = 0;j < 3;j++){ cout<< array_local[j] << endl; } mostrar_array_global(); system("pause"); } /* implementacion */ void mostrar_array_global(){ cout<<"Array global:"<<endl; for (int w = 0;w < 5;w++){ cout<<array_global[w]<<endl; } }
SALIDA
3 2 1 Array global: 0 2 4 6 8 Presione una tecla para continuar . . .
Como vemos creamos dos arrays, uno como variable local y uno como variable global. Al local le damos una longitud de 3. Luego en el primer for hacemos que el valor de cada item del array (que van del 0 al 2), y le aseigamos de valor 2-v y al item luego le sumamos 1. Para el indice 0 del array tenemos 2-0 + 1 = 3, para el segundo 2 - 1 + 1 = 2, y para el tercero 2 - 2 + 1 = 1 Por eso se muestra 3, 2 y 1. Para el array reservado (=creado) como variable global, le damos a cada uno de sus items, el valor de x*2, es decir el numero de indice * 2, entonces el item 0 del array tiene 0, el item 1 del array tiene 2, el item 2 tiene 6 y el item 8. Son 5 items del 0 al 5 como corresponde.
Con todo esto se deberia entender el funcionamiento de los arrays. Los arrays no son solo para ints, tambien sirven para double, string o cualquier otro tipo al igual que las funciones.
Vectores
Imaginemos que tenemos una cantidad de datos, pero, la cantidad de datos no esta definida. En tal caso se recurre a los vectores, que funcionan de la misma manera que los arrays, pero, su longitud puede variar mientras corre el programa. Uno tambien puede usar siempre vectores en vez de arrays, pero si uno solo usa arrays, la cantidad de memoria que utilizara el programa es fija y esta asegurado, en cambio con vectores, uno no sabe cuanta memoria (cantidad de variables) puede llegar a usar el programa. Para usar vectores se debe agregar al principio del programa, y el using namespace std debe estar tambien. En los vectores uno crea primero una lista de valores vacia, y le va agregando/eliminado valores y al mismo tiempo se leen cuando se desea. Ahora haremos una descripcion de las operaciones sobre vectorse que c++ nos ofrece. En c puro no hay vectores ni tampoco cout por lo tanto hay que asegurase que se guarda el archivo como .cpp
Un vector se crea como
vector <tipo_de_datos a almacenar> nombre_vector;
Para acceder a un dato de un vector se hace igual que con los arrays
nombre_vector[numero_de_dato] = algo; o algo = nombre_vector[numero_de_dato]
pero cuidado, si accedemos a un numero_de_dato que no existe (mayor a la longitud), el programa en ese punto se cerrara. Si se debugea se puede ver en que punto crasheo sino no. De todas formas con un uso correcto de vectores no crasheara.
Para agregarle un valor al vector
nombre_vector.push_back ( dato ); //dato tiene que ser del tipo_de_datos_a_almacenar del vector
Para eliminarle al vector un dato
nombre_vector.erase( nombre_vector.begin() + numero_de_dato);
Para borrar el ultimo dato del vector
nombre_vector.pop_back();
Para leer el ultimo/Primer valor de un vector
variable = nombre_vector.back() //ultimo valor variable2 = nombre_vector.front() //primer valor //variable y variable2 son del tipo del vector
Para leer la longitud de un vector
tamanio = nombre_vector.size(); //tamanio es un int.
Para eleminar todos los valores de un vector
nombre_vector.clear();
Y hay muchas mas funciones, en la pagina del c++ estan todas.
Ahora veremos un ejemplo donde calculamos los numeros primos del 2 al 50, y los compuestos. Mostramos primeros los primos y luego los compuestos. Ambos conjuntos los almacenamos en dos vectores
#include <iostream> #include <stdlib.h> #include <stdio.h> //en linux para el getchar() solamente #include <vector> //usaremos vectores! using namespace std; //En este programa vamos a hacer un vector donde almacenaremos los numeros primos del 1 al 100. y uno de los que no son primos vector <int> numeros_primos; vector <int> numeros_compuestos; bool es_primo(int numero); //Funcion para revisar si un numero es primo, devuelve 1 si es cierto, 0 si no lo es void mostrar_numeros_primos(); //Funcion que nos muestra el contenido del vector de primos en un momento determinado del programa void mostrar_numeros_compuestos(); //Funcion que nos muestra el contenido del vector de compuestos en un momento determinado del programa int main(){ for (int n = 2;n < 50;n++){ bool primo = es_primo(n); if (primo){ numeros_primos.push_back( n ); }else{ numeros_compuestos.push_back( n ); } } //mostramos los vectores mostrar_numeros_primos(); mostrar_numeros_compuestos(); system("pause"); //en linux es cout<<"Presione una tecla para continuar ..."<<endl; while (getchar() != '\n'){}; } bool es_primo(int numero){ //Esta funcion no tiene eficiencia maxima para no complicar, pero hay varias cosas que se pueden hacer para reducir el tiempo que demora for (int divido = 2;divido < numero;divido ++){ if (numero % divido == 0){ return false; //no es primo, se puede dividir por un numero != 1 y != a numero } } return true; //si es primo } void mostrar_numeros_primos(){ cout<<"Numeros primos :"<<endl; for (int v = 0;v < numeros_primos.size();v++){ //recorro todos los valores del vector, de 0 a el .size() del vector, es decir, su ultimo valor+1 cout << numeros_primos[v] << endl; } } void mostrar_numeros_compuestos(){ cout<<"Numeros compuestos :"<<endl; for (int v = 0;v < numeros_compuestos.size();v++){ //recorro todos los valores del vector, de 0 a el .size() del vector, es decir, su ultimo valor+1 cout << numeros_compuestos[v] << endl; } }
SALIDA:
Numeros primos : 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 Numeros compuestos : 4 6 8 9 10 12 14 15 16 18 20 21 22 24 25 26 27 28 30 32 33 34 35 36 38 39 40 42 44 45 46 48 49 Presione una tecla para continuar ...
Matrices
Imaginemos que queremos guardar un tablero de ajedrez en la memoria. Un array es una lista de valores, pero en una sola dimension, por lo tanto no nos sirve. Con las matrices, que en realidad son arrays de arrays podemos armar tablas de valores. Usando la misma logica tambien podemos hacer matrices de tres dimensiones, cuatro, cinco e infinito, usando la imaginacion, pero por ahora solo trabajaremos con matrices de 2 dimesiones.
¿Como creamos (=reservamos espacio en la memoria) para una matriz?
tipo_de_dato nombre_de_matriz[ancho][alto]; //creamos matriz
¿Como accedemos y/o editamos un valor de la matriz bidimensional (=de dos dimensiones)?
nombre_de_matriz[columna][fila]; //este valor podemos o leerlo o escribirlo como querramos, de la misma forma que con los arrays de antes.
Ahora vemos un ejemplo donde almacenaremos una tabla de multiplicar clasica.
#include <iostream> #include <stdlib.h> //para el system("pause"); #include <stdio.h> //en linux para getchar() using namespace std; int mapa[11][11]; //creamos una matriz de 11x11, ya que la tabla de multiplicar va del 0 al 10, que son 0 1 2 3 4 5 6 7 8 9 10, que son 11 numeros contando el 0 /* Prototipo */ void mostrar_mapa(); int main(int argc, char** argv) { for (int columna = 0;columna < 11;columna ++){ //recorro desde la columna 0 hasta la columna 10 incluyendo for (int fila = 0;fila < 11;fila ++){ //por cada columna calculo el valor de la celda de la tabla, siempre es (por la definicion de la tabla de multiplicar), fila * columna. mapa [ columna ] [ fila ] = columna * fila; //asigno el valor de la columna columna, fila fila, el valor de fila*columna, eso entonces a cada celda particular de la tabla } } mostrar_mapa(); //mostramos la tabla generada system("pause"); } /* Implementacion */ void mostrar_mapa(){ for (int fila = 0;fila < 11;fila ++){ //por cada fila for (int columna = 0;columna < 11;columna ++){ //por cada columna de cada fila bool menor_100 = mapa[ columna ][ fila ] < 100; //guardo si es menor a 100 su valor bool menor_10 = mapa[ columna ][ fila ] < 10; //guardo si es menor a 10 su valor if (menor_10){ //para visualizar mejor si es menor a 10, agregamos dos espacios ( ej: estos 3 valores ocupan el mismo espacio 3 ,33 ,333 ) cout<< mapa[ columna ][ fila ]<<" "; //esto me imprime el valor de mapa[ columna ][ fila ] sumado a dos espacios (sin saltar de a la proxima linea en el proximo cout) }else if(menor_100){ //si es mejor a 100 agregamos solo un espacio (gastamos dos numeros, agregamos un solo espacio) cout<< mapa[ columna ][ fila ]<<" "; //esto me imprime el valor de mapa[ columna ][ fila ] sumado a un espacio (sin saltar de a la proxima linea en el proximo cout) }else{ //si es mayor o igual a 100 (3 cifras), no agregamos espacios cout<< mapa[ columna ][ fila ]; } //notar que como no usamos endl, el contenido se escribe todo en la misma linea } cout<<""<<endl; //pasamos a la proxima linea de escritura } }
SALIDA
0 0 0 0 0 0 0 0 0 0 0 0 1 2 3 4 5 6 7 8 9 10 0 2 4 6 8 10 12 14 16 18 20 0 3 6 9 12 15 18 21 24 27 30 0 4 8 12 16 20 24 28 32 36 40 0 5 10 15 20 25 30 35 40 45 50 0 6 12 18 24 30 36 42 48 54 60 0 7 14 21 28 35 42 49 56 63 70 0 8 16 24 32 40 48 56 64 72 80 0 9 18 27 36 45 54 63 72 81 90 0 10 20 30 40 50 60 70 80 90 100 Presione una tecla para continuar ...
Si lees los comentarios y pensas se deberia entender. Creamos una matriz de 11x11 (es decir los indices de filas y columas van del 0 al 10), y a cada uno de los valores de la matriz (es decir a cada uno de los 121 valores), le asignamos de valor su numero de columna* su numero de final. De esta forma cumplimos con la definicion de tabla de multiplicar y generamos una. Despues mostramos la tabla de multiplicar. Usamos de manera diferente el cout tambien en esta ocasion. Cabe resaltar que si se usa el cout sin agregar el endl, el proximo cout mostrara el texto a mostrar en la misma linea, y si se agrega cout«algo«otra_cosa se muestra algo junto a otra cosa. Con todo eso se deberia entender como funciona el cout mas completamente.
Espero que hayas entendido el tema, el proximo tema son matrices con vectores. Luego vendran mas cosas, hay muchisimos temas mas que tengo para enseñar todavia!
Matrices con vectores
Ahora veremos otro tema parecido. La matriz que hicimos antes la hicimos con arrays, por lo tanto, su tamaño era estatico, todas las filas y columnas tenian tamaño fijo. Con matrices basadas en vectores.
Para crear una matriz de enteros usaremos, que nos crea un vector de tipo de dato vector para ints.
vector <vector <int> > nombre_matriz;
donde iniciamos una tabla (=matriz) de 0 filas y 0 columas.
Para agregarle una linea a la tabla hacemos, por ejemplo
vector <int> linea; linea.push_back( 5 ); //a la linea le agregamos un 5 linea.push_back( 2 ); //a la linea le agregamos un 2 nombre_matriz.push_back(linea); //a la tabla le agregamos la linea
Cabe resaltar que la matriz como todo vector tiene una funcion size (nombre_vector.size()) que nos da la cantidad de lineas que contiene (=longitud del vector), y cada uno de las lineas del vector, que como todo vector se accede como nombre_matrz[ numero_de_fila ], tiene tambien su .size() y tambien se puede accede a cada uno de sus valores con nombre_matrz[ numero_de_fila ][ numero_de_columna]. Al igual que cuando vimos antes vectores hay que recordar que si intentamos acceder a un numero_de_fila que no existe (numero_de_fila>=nombre_vector.size()), el programa se cerrara (un debugger marcaria esa linea como error), como tampoco podemos acceder a un valor de una de las lineas que no existe (numero_de_valor_de_la_fila>=nombre_vector[numero_de_fila].size().
Ahora veremos un ejemplo donde calculamos los divisores de los numeros 0 al 10, y los mostramos por cada numero
#include <iostream> #include <stdlib.h> //para el system pause #include <stdio.h> //en linux necesario para getchar(); #include <vector> //usaremos vectores! using namespace std; vector < vector <int> > datos_divisores; //creamos el vector donde almacenamos los datos de divisores /* Prototipos */ void mostrar_vector(); vector <int> obtener_divisores(int numero); //devuelve un vector<int>! int main(){ for (int n = 1;n <= 10;n++){ /* Calculamos los divisores desde 1 hasta 10 y los almacenamos en el vector */ vector <int> divisores = obtener_divisores( n ); //Esta funcion devuelve un vector<int> con los divisores datos_divisores.push_back( divisores ); //agregamos esa linea (=lista) a los datos de divisores } mostrar_vector(); //mostramos el vector system("pause"); //en linux el cout<<"Presione una tecla para continuar..."; while (getchar()!='\n'){}; } vector <int> obtener_divisores(int numero){ vector <int> divisores; //creamos el vector donde almacenaremos los divisores for (int d = 1;d <= numero;d++){ //revisamos todos los numeros de 1 al numero if (numero % d == 0){ //si el numero puede dividise por d divisores.push_back( d ); //lo agrego al vector el numero que divide. } } return divisores; //devuevlo el vector } void mostrar_vector(){ //funcion para mostrar graficamente el vector (la matriz) for (int v = 0;v < datos_divisores.size();v++){ //por cada linea de la matriz if (v+1 < 10){ //esto es para que si es menor que 10, que ocupe el mismo espacio, y se vea mejor cout<<v+1<<" : {"; }else{ cout<<v+1<<": {"; } //ej 10: y 9 :, ocupan el mismo espacio for (int vv = 0;vv < datos_divisores[v].size();vv++){ //por cada divisor almacenado en la linea cout<<datos_divisores[v][vv]; //lo muestro sin hacer espacio if (vv != datos_divisores[v].size() - 1){ //si no es el ultimo no agrego la coma para que se vea mejor cout<<" , "; } } cout<<"}"<<endl; } }
SALIDA
1 : {1} 2 : {1 , 2} 3 : {1 , 3} 4 : {1 , 2 , 4} 5 : {1 , 5} 6 : {1 , 2 , 3 , 6} 7 : {1 , 7} 8 : {1 , 2 , 4 , 8} 9 : {1 , 3 , 9} 10: {1 , 2 , 5 , 10} Presione una tecla para continuar . . .
Como vemos tenemos que el uno tiene de divisores el 1, el 2 tiene de divisores el 1 y el 2, el 3 el 1 y el 3, el 4 tiene de divisores 1, 2 y 4, y asi.
Si no entendiste bien lo del cout con y sin endl, proba vos para entenderlo, porque aqui lo volvi a usarlo, y de manera mas complicada. El programa consiste en crear un vector de vectores (=matriz de vectores), y por los numeros del 1 al 10, agregarle lineas (que son vectores), con los divisores del numero correspondiente, y luego mostrarlo. Considero importante que entiendan el algoritmo para mostrarlo masomenos lindo la matriz. En realidad en teoria solo con la teoria de vector se puede hacer este ejemplo, considerando que un vector es un tipo de dato tambien y se puede hacer un vector de cualquier tipo de dato (incluyendo de vectores). Tambien hay que notar que hicimos una funcion que no devuelve como dato ni un int, ni un void, devuelve un vector de enteros, esto tambien es posible. Si tienen otras dudas pueden preguntar en los comentarios.
Con todo esto se deberia haber entendio matrices con vectores (=vector de vectores), es imporante que tengan en cuenta que al igual que con los arrays, se pueden hacer vectores de mas de dos dimensiones, de 3,4,5, y mas (habria que escribir
vector <vector <vector <vector <int> > >, segun corresponda, (=vector de tipo dato vector de tipo dato vector de tipo de dato vector de tipo de dato int).
Recursividad
En programacion, y en la vida en general, una solucion de un problema con rescursividad, significa un procedmimiento de un problema, que se requiere llamarse a si mismo para funcionar. Es decir, una funcion que se llama a si misma (si, se puede). Sin embargo, si sucediece algo asi, nunca se terminaria de resolver el problema, porque se llamaria asi mismo indefinidamente. Por eso decimos, que siempre la recursividad tiene un limite, un punto en el cual una de las llamadas al procedimiento no vuelve a llamarlo a si mismo.
Hay muchos problemas que pueden ser resueltos con o sin recursividad, es decir poseen alternativas de ambos lados. Sin embargo, la solucion recursiva suele ser a veces más facil de idear.
Este será el problema que resolveremos mediante recursividad
El algoritmo de Ecluides es una forma de obtener el maximo comun divisor de dos numeros (es decir, el numero mas mas grande que divide sin resto dos numeros), que consiste en restar el mas grande de los dos numeros por el menor hasta que ambos numeros sean iguales. Realizar una solucion recursiva del problema fuente: ocw. udl. cat /enginyeria-i-arquitectura/programacio-2/problemes-2/2-problemas-de-recursividad.pdf (sin espacios)
Nota: no vamos a demostrar porque se comple el algoritmo, solo vamos a "traducirlo" a lenguaje c. Buscandolo en internet probablemente habra muchos sitios que lo demuestren de diversas formas.
Es decir
-el numero mas grande, se convierte en la resta del mas grande y el mas chico
-el numero mas chico sigue igual
-si son iguales, ese es el maximo comun divisor, y la solucion
-si no, entonces repito el algoritmo con los dos numeros que me quedaron, y el resultado que me de la solucion
Entonces, el codigo para resolver el problema seria
#include <iostream> #include <stdlib.h> //para el system pause #include <stdio.h> //en linux necesario para getchar(); #include <vector> //usaremos vectores! using namespace std; /*** Prototipo ***/ int mcd(int A,int B); /*** Main ***/ int main(){ cout << mcd(412,184) << endl; cout << mcd( 12, 25) << endl; cout << mcd( 56, 34) << endl; system("pause"); } /*** Implementacion ***/ int mcd(int A,int B){ if (A > B){ //como a > b entonces le resto a A, B A = A - B; } if (B > A){ //como b > a entonces le resto a A, B B = B - A; } if (A == B){ //si son iguales ya consegui el mcd return A; //devuelvo A, pero tambien podria devolver B, son ambos iguales }else{ return mcd(A,B); //entonces devuelvo el resultado de los dos numeros que quedaron } }
SALIDA
4 1 2 Presione cualquier tecla para continuar ...
¿Como funciono? Seguiremos el primer caso. Tenemos 412 y 184.
Como 412 es mayor a 184, el 412 se transforma en 228 (412-184). Y como no son iguales, se devuelve la solucion de mcd(228,184).
Dentro de ese mcd, como 228 es mayor a 184, el 228 se transforma en 44 (448-184). Como no son iguales, se devuelve la solucion de mcd(44,184)
Dentro de ese mcd, como 184 es mayor a 44, el 184 se transforma en 104 (184-44). Como no son iguales se devuelve la solucion de mcd(44,104)
Dentro de ese mcd, como 104 es mayor a 44, el 104 se transorma en 60 (104-44). Como no son iguales se devuelve la solucion de mcd(44,60)
Dentro de ese mcd, como 60 es mayor a 44, el 60 se transforma en 16 (60-44). Como no son iguales se devuelve la solucion de mcd(44,16)
Dentro de ese mcd, como 44 es mayor a 16, el 44 se transforma en 28 (44-16). Como no son iguales se devuelve la solucion de mcd(28,16)
Dentro de ese mcd, como 28 es mayor a 16, el 28 se transforma en 12 (28-12). Como no son iguales se devuelve la solucion de mcd(12,16)
Dentro de ese mcd, como 16 es mayor a 12, el 16 se transforma en 4 (16-12). Como no son iguales se devuelve la solucion de mcd(12,4)
Dentro de ese mcd, como 12 es mayor a 4, el 12 se transforma en 8 (12-4). Como no son iguales se devuelve la solucion de mcd(8,4)
Dentro de ese mcd, como 8 es mayor a 4, el 8 se transforma en 4 (8-4). Son iguales! entonces esta es la solucion del problema, y devolvemos 4, que es la solucion del problema.
Cabe resaltar que tambien se puede resolver el problema con un for, es verdad, pero hay problemas mucho mas rebuscados, que es mejor encararlos con recursividad.
Aun no se ha terminado el articulo, falta mostrar ejemplos mas complejos de recursividad, pero la base esta!
Otro problema con recursividad
Este es otro problema interesante y mas complicado, que ademas a mi parecer la solucion recursiva es la más sencilla de pensar.
En el ajedrez un caballo se mueve en L (dos casillas en un eje, y una casilla en el restante). Un tablero de ajedrez mide 8x8. Dar todos los lugares a donde un caballo puede estar en 5 movimientos.
[[html]]
Insert any HTML code, including widgets and video or audio players
[[/html]]