Mensajes

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.

Tienes un array, ejemplo: a = [1,2,3,4,5,6,7]
Sea x = 5

Código (c) [Seleccionar] Expandir

¿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...

[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)).]

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.

Código (c) [Seleccionar] Expandir


#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("Ingrese 'x': ");
scanf("%d", &x);
printf("Tamaño del array (>=2): ");
scanf("%d", &tam);
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]);
}

printf("\n\n");
for(contador=0; contador<tam; contador++)
printf("%d  ", a[contador]);

/* ********************************************** */
b = f2(a, x, tam); /* solo cambiar "f1" por "f2" para cambiar de algoritmos */
if(b == TRUE)
printf("\n\nHay solucion\n");
else
printf("\n\nNo hay solucion\n");
/* ********************************************** */

free(a);
a=NULL;

system("pause");
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

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.

Código (c) [Seleccionar] Expandir


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++)
                       printf("%c", a[j]);
               printf("\n");
               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++)
printf("%c", a[j]);
printf("\n");
tam_actual++;
}
}

void descomponer3(char *a)
{
int unsigned tam_actual = 2;
int unsigned i, j, x=0;

while(x<(strlen(a)-1))
{
for(i=0; i<(strlen(a)-1); i++)
{
for(j=x; j<tam_actual; j++)
printf("%c", a[j]);
printf("\n");
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;

while(x<(strlen(a)-1))
{
for(i=0; i<(strlen(a)-1); i++)
{
for(j=x; j<tam_actual; j++)
fputc(a[j], file);
fputs("\n", file);
tam_actual++;
}
tam_actual=2;
x++;
}

fclose(file);
}


Saludos.

EDIT: Aprendí a usar la función GeSHi. Gracias Leo Gutierrez.

Para ver qué es un palindromo, véase Palindromo. Posteen más soluciones.

Código (c) [Seleccionar] Expandir


/* 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 ultPos = strlen(a)-1;
       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));
       printf("Palabra: "); scanf("%s", a);

       es_palindromo(a);

       free(a); a=NULL;

       system("pause");
       return 0;
}


Saludos.

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

Código (c) [Seleccionar] Expandir


#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)) )
{
printf("%d  ", fib(i));
j++;
}
i++;
}

printf("\n\n");
system("pause");
return 0;
}

int fib(double n)
{
double a = 1/sqrt(5);
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;
}


Extrae los primeros n números primos. No es para nada óptimo, pero bueno está demás decir que obtener primos es un tema en desarrollo. Véase: Great Internet Mersenne Prime Search

Código (c) [Seleccionar] Expandir


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

#define FALSE 0
#define TRUE !FALSE
typedef int Bool;

int longitud(void);
Bool es_primo(int num);

int main()
{
       int n = longitud();
       
       int i, num=2;
for(i=0; i<n;)
{
               if(es_primo(num))
               {
printf("%d  ", num);
i++;
       }

       num++;
}

printf("\n\n");
       system("pause");

       return 0;
}

Bool es_primo(int num)
{
       Bool b = TRUE;
       int i, divisores=0;
       for(i=1; i<=num; i++)
       {
               if(num%i == 0)
                       divisores++;
               if(divisores > 2)
               {
                       return b=FALSE;
               }
}

return b;
}

int longitud(void)
{
       int n;
       printf("Cantidad de primos: ");
       scanf("%d", &n);
       return n;
}


Saludos.



Links Relacionados:

* Desarrollar un algoritmo para generar los primeros K primeros números primos de la serie Fibonacci.

programacion c++ numeros primos
http://foro.elhacker.net/empty-t215844.0.html

[C\C++] Dudilla con un codigo para ver si un numero es primo
http://foro.elhacker.net/empty-t186450.0.html

[C++] Pseudo Random Encryption Algorithm 1.0 RC2 by APOKLIPTICO.
http://foro.elhacker.net/empty-t233347.0.html

Esquema RSA
http://foro.elhacker.net/empty-t254640.0.html

Algoritmo numeros primos [Batch]
http://foro.elhacker.net/empty-t251824.0.html

[Batch] Algoritmo de Numeros Primos
http://foro.elhacker.net/empty-t235233.0.html

[batch] Problema extraño
http://foro.elhacker.net/empty-t219922.0.html

[batch] Descomposicion factorial
http://foro.elhacker.net/empty-t222322.0.html

Calcular numeros primos
http://foro.elhacker.net/empty-t252389.0.html

Numero no-primo terminando en 13?
http://foro.elhacker.net/empty-t252440.0.html

En la sección:

PELICULAS GRATIS

Inetfilm
-->http://inetfilm.com

Watchmovies
--> http://welcome.to/watchmovies

Film.com
-->http://www.film.com/festivals

Atom Films
--> http://www.atomfilms.com/

Internet Archive
--> http://www.archive.org/details/movies

ILoaded
--> http://www.iloaded.com

Podrías agregar:  http://sdd-fanatico.blogspot.com/ una web donde hay peliculas, series, anime. Y son descargas directas y sin vueltas.

Saludos.

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.