|
Mostrar Mensajes
|
Páginas: 1 [2]
|
11
|
Programación / Ejercicios / Re: Problema: Búsqueda en Array
|
en: 30 Junio 2009, 09:31 am
|
Exactamente, es eso. Ése es el algoritmo en el que analizas todos los casos, y en ese caso te queda O(n^2) donde n es la cantidad de numeros ingresados.
La otra forma (que a mi se me ocurrió, seguro hay otras) es ordenar el array con quicksort que tiene costo n*log(n). Luego uso búsqueda binaria que tiene costo log(n), en el peor caso se hacen n veces búsqueda binaria por lo tanto tengo n*log(n). En total tengo n*log(n)+n*log(n)=2*n*log(n) que es del orden de O(n*log(n)) pues las constantes multiplicativas son despreciables para n suficientemente grande.
Aunque en realidad cabe destacar que quicksort tiene costo n*log(n) en el caso medio (que es lo más probable que suceda). En tal caso lo anterior es correcto. Pero en el peor caso quicksort tiene costo n^2 (por ejemplo si el array ya esta ordenado, el pivote no queda muy al centro que digamos...). Entonces tendría n*log(n) por la busqueda binaria y n^2 por quicksort, luego el algoritmo es n*log(n)+n^2 que es O(n^2). Pero esto en el peor caso, lo cual es mejor que usar brute force pues de esa forma me queda O(n^2).
Saludos.
|
|
|
12
|
Programación / Ejercicios / Re: Problema: Búsqueda en Array
|
en: 29 Junio 2009, 08:15 am
|
Tienes un array, ejemplo: a = [1,2,3,4,5,6,7] Sea x = 5 ¿Existen un a[i] y un a[j] tal que a[i]+a[j] = x? Verdadero. En particular, a[1]+a[2] = 5.
Si quieres puedes mostrar los índices, todas las soluciones, etc. Pero es simplemente decir "si" si hay al menos una solución ó "no" si no existe solución. Saludos. PD: uso la etiqueta code sino me imprime una parte en cursiva...
|
|
|
13
|
Programación / Ejercicios / Problema: Búsqueda en Array
|
en: 28 Junio 2009, 21:15 pm
|
Problema: Se recibe un arreglo X de numeros enteros definido en [0, n-1] y un entero x. Se quiere determinar si existen i, j en [0, n-1] tal que X + X[j] = x. Diseñe un algoritmo para resolver el problema cuya complejidad sea O(n*log(n)).
Plantear más soluciones. #include <stdio.h> #include <stdlib.h> #define FALSE 0 #define TRUE !FALSE typedef int Bool; /* Algoritmo O(n^2). Analizando todos los casos. */ Bool f1(int *a, int x, int tam); /* Algoritmo O(n*log(n)). Ordeno con quicksort y uso busqueda binaria "n" veces. Me queda 2*n*log(n) que es O(n*log(n))*/ Bool f2(int *a, int x, int tam); void quicksort(int *, int, int); void pivot(int *, int, int, int *); void swap(int *, int, int); int main() { int tam, contador, x; Bool b; printf("Tamaño del array (>=2): "); int *a = (int *) calloc (tam , sizeof(int)); for(contador=0; contador<tam; contador++) { printf("Ingrese el contenido de la celda %d: ", contador ); scanf("%d", &a [contador ]); } for(contador=0; contador<tam; contador++) /* ********************************************** */ b = f2(a, x, tam); /* solo cambiar "f1" por "f2" para cambiar de algoritmos */ if(b == TRUE) else printf("\n\nNo hay solucion\n"); /* ********************************************** */ a=NULL; return 0; } /* Algoritmo O(n^2). Analizando todos los casos. */ Bool f1(int *a, int x, int tam) { Bool b=FALSE; int i, j; for(i=0; i<tam; i++) for(j=0; j<tam; j++) if(a[j]+a[i] == x) return b=TRUE; /* solución encontrada */ return b; /* no hay solución */ } /* Algoritmo O(n*log(n)). Ordeno con quicksort y uso busqueda binaria "n" veces. */ Bool f2(int *a, int x, int tam) { quicksort(a, 0, tam-1); Bool b = FALSE; int izq=0, med, der=tam-1, k=0; while(izq<=der && !b && k<tam) { med = (izq+der)/2; if( x<(a[k]+a[med]) ) der = med; else if ( x>(a[k]+a[med]) ) izq = med; else if ( x==(a[k]+a[med]) ) return b=TRUE; /* hay solución */ k++; } return b; /* no hay solución */ } void quicksort(int *a, int izq, int der) { int piv; if(izq<der) { pivot(a, izq, der, &piv); /* { Para todo x en a: a[izq,piv] son <= a[piv] && */ /* Para todo x en a: a[piv+1,der] son > a[piv] } */ quicksort(a, izq, piv-1); quicksort(a, piv+1, der); } } void pivot(int *a, int izq, int der, int *piv) { int i = izq+1; int j = der; *piv = izq; while(i <= j) { /* { *piv<i<=j+1 && (Para todo x en a: a[izq,i]<=a[*piv]) && (Para todo x en a: a[j+1,der] > a[*piv]) } */ if(a[i] <= a[*piv]) i=i+1; else if(a[j] > a[*piv]) j=j-1; else if(a[i] > a[*piv] && a[j] <= a[*piv]) { swap(a, i, j); i = i+1; j = j+1; } } /* i vale j+1, (Para todo x en a: a[izq,j] <= a[*piv]) && (Para todo x en a: a[i,der] > a[piv] */ /* dejando el pivot en una posición más central */ swap(a, *piv, j); /* nueva posición para pivot */ *piv = j; } void swap(int *a, int i, int j) { int aux = a[i]; a[i] = a[j]; a[j] = aux; }
Saludos
|
|
|
14
|
Programación / Ejercicios / Re: Problema de strings: Palindromos.
|
en: 28 Junio 2009, 05:47 am
|
Un enunciado más complicado del problema: Una hilera de letras, o palabra, se llama palindromo cuando tiene más de una letra y leída de izquierda a derecha y de derecha a izquierda son iguales, por ejemplo, ababa.
Una hilera se llama i-palindromo cuando quitando el primer carácter de la izquierda se convierte en palindromo, por ejemplo casa.
Una hilera se llama d-palindromo cuando quitando el primer carácter de la derecha se convierte en palindromo, por ejemplo amad.
Llamaremos palabras distinguidas a aquellas que son palindromo, ipalindromo o d-palindromo.
El problema consiste en recibir una palabra y determinar los cortes, si los hubiera, que la descomponen en dos palabras distinguidas, e indicar para cada una de ellas de que tipo o tipos es.
Ejemplo 1: Si la entrada contiene: azarosos
La salida podría contener: azar d-palindromo osos i-palindromo d-palindromo etc.
Ejemplo 2: Si la entrada contiene: amarrar
La salida podría contener: ama palindromo rrar i-palindromo amar d-palindromo rar palindromo etc.
Yo hice un par de funciones que descompenen un string en substring (por asi decirlo) y que pueden ayudar un poco en la solución. Pruebenlas y comenten. void descomponer(char *a) { int unsigned tam_actual = strlen(a ); int unsigned i, j; for(i =0; i <(strlen(a )-1); i ++) { for(j=0; j<tam_actual; j++) tam_actual--; } } void descomponer2(char *a) { int unsigned tam_actual = 2; int unsigned i, j; for(i =0; i <(strlen(a )-1); i ++) { for(j=0; j<tam_actual; j++) tam_actual++; } } void descomponer3(char *a) { int unsigned tam_actual = 2; int unsigned i, j, x=0; { for(i =0; i <(strlen(a )-1); i ++) { for(j=x; j<tam_actual; j++) tam_actual++; } tam_actual=2; x++; } } El siguiente simplemente redirige la salida en un fichero: void descomponer4(char *a) { FILE *file = fopen("descomponer.txt","w"); int unsigned tam_actual = 2; int unsigned i, j, x=0; { for(i =0; i <(strlen(a )-1); i ++) { for(j=x; j<tam_actual; j++) tam_actual++; } tam_actual=2; x++; } }
Saludos. EDIT: Aprendí a usar la función GeSHi. Gracias Leo Gutierrez.
|
|
|
15
|
Programación / Ejercicios / Problema de strings: Palindromos.
|
en: 27 Junio 2009, 21:31 pm
|
Para ver qué es un palindromo, véase Palindromo. Posteen más soluciones. /* Algoritmo que te dice si una palabra es palindromo */ #include <stdio.h> #include <stdlib.h> #include <string.h> #define ES_PALIN printf("\n\nEs palindromo\n\n"); #define NO_PALIN printf("\n\nNo es palindromo\n\n"); #define FALSE 0 #define TRUE !FALSE typedef int Bool; void es_palindromo(char *a) { Bool b = TRUE; int i; for(i=0; i<strlen(a); i++, ultPos--) { if(a[i] != a[ultPos]) { b = FALSE; break; } } if(b) ES_PALIN else NO_PALIN; } int main() { char *a = (char *) calloc (20, sizeof(char)); es_palindromo(a); return 0; }
Saludos.
|
|
|
16
|
Programación / Ejercicios / Re: Algoritmia-Ejercicios introductorios.
|
en: 21 Junio 2009, 03:24 am
|
Edito: le agregue la opcion GeSHi, jeje. Ahora aprendi y queda mas lindo el código. Problema 8: Desarrollar un algoritmo para generar los primeros K primeros números primos de la serie Fibonacci. Ejemplo: K=6 1 2 3 5 13 89 #include <stdio.h> #include <stdlib.h> #include <math.h> #define FALSE 0 #define TRUE !FALSE typedef int Bool; int fib(double n); Bool es_primo(int num); int main() { int n ; printf("Cantidad de primos a obtener: "); scanf("%d", &n ); int i=0, j; for(j=0; j<n;) { if( es_primo(fib(i)) ) { j++; } i++; } return 0; } int fib(double n) { double b = (1+sqrt(5))/2; double c = (1-sqrt(5))/2; double fib_n = a *pow(b , n ) - a *pow(c , n ); return fib_n; } Bool es_primo(int num) { Bool b = TRUE; int i, divisores=0; if(num == 0) return b=FALSE; for(i=1; i<=num; i++) { if((num%i) == 0) divisores++; if(divisores > 2) { return b=FALSE; } } return b; }
|
|
|
19
|
Informática / Software / Re: Cursos "Guias "Libros Y Manuales De Todo Tipo En Descarga Directa Aqui!!!!
|
en: 11 Junio 2009, 23:32 pm
|
Cita de Diego Arenas por favor postear aqui mismo en el tema si andan en busca de algun curso manual etc me lo hacen saber aqui mismo y tratare de conseguirlo todo el material posteado aqui son subidas mias Tal vez tu encuentres el siguiente libro: Autor: WIRTH, N Titulo: "Algoritmos + Estructuras de Datos = Programas". Ediciones del Castillo, 1980 ISBN: 84-219-0172-9 Desde ya muchas gracias.
|
|
|
|
|
|
|