elhacker.net cabecera Bienvenido(a), Visitante. Por favor Ingresar o Registrarse
¿Perdiste tu email de activación?.

 

 


Tema destacado: Rompecabezas de Bitcoin, Medio millón USD en premios


+  Foro de elhacker.net
|-+  Programación
| |-+  Programación General
| | |-+  Programa para hallar números amigos
0 Usuarios y 1 Visitante están viendo este tema.
Páginas: 1 [2] Ir Abajo Respuesta Imprimir
Autor Tema: Programa para hallar números amigos  (Leído 19,188 veces)
Debci
Wiki

Desconectado Desconectado

Mensajes: 2.021


Actualizate o muere!


Ver Perfil WWW
Re: Programa para hallar números amigos
« Respuesta #10 en: 27 Junio 2010, 16:40 pm »

Fijate que nunca s y t llegan a ser iguales por eso no lanza el print.

Hay un error de planteamiento del algoritmo.

Depuralo con algun debugger y verás que nunca se cumple la condicion.

Saludos


En línea

Charderak

Desconectado Desconectado

Mensajes: 14


Ver Perfil
Re: Programa para hallar números amigos
« Respuesta #11 en: 27 Junio 2010, 18:56 pm »

Agradezco la ayuda, pero intentad ser un poco más concretos por favor, ya sé que hay un error en el algoritmo, por eso precisamente he creado el post.

En cuanto al depurador, no sé utilizarlo

Debci por qué dices que s y t nunca llegan a ser iguales? Si lo que hago es sumar los divisores de ambos números por separado y en caso de que la suma sea igual que me diga lo de que son "amigos"


En línea

ghastlyX
Ex-Staff
*
Desconectado Desconectado

Mensajes: 1.900



Ver Perfil
Re: Programa para hallar números amigos
« Respuesta #12 en: 27 Junio 2010, 19:10 pm »

Bueno, ante todo no conozco Fortran ni lo he usado nunca, pero en tu código, no tendrías que poner a 0 las variables s y t para cada nuevo valor de n?

Otra cosa, por lo que veo, tú quieres encontrar los números amigos en un intervalo [n,m] y en tu código lo que haces es iterar sobre el valor de n y lo comparas con m, que la dejas fija. Así, suponiendo que lo que te he dicho arriba esté bien, sólo miras si m es amigo de algún número dentro del intervalo, pero si el intervalo es [30,50], no miras nunca si 34 es amigo de 42, por poner un ejemplo.

Una forma de corregir el algoritmo sería hacer lo siguiente (te lo pongo en pseudocódigo):
Código:
i := n;
mientras i <= m
    s := suma_divisores(i);
    si s > i y s <= m
        t := suma_divisores(s);
        si t = i
            imprime i " y " s " son amigos";
        fsi
    fsi
    i := i + 1;
fsi
Con este algoritmo, la complejidad es del orden de O(n2) puesto que tal y como tú calculas los divisores necesitas otro bucle lineal para cada número. En C++, el código quedaría así más o menos (no lo he probado):
Código
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. int suma_div(int n) {
  5.    int s = 0;
  6.    for (int i = 1; i <= n/2; ++i) if (n%i == 0) s += i;
  7.    return s;
  8. }
  9.  
  10. int main() {
  11.    int n, m;
  12.    cin >> n >> m;
  13.    for (int i = n; i <= m; ++i) {
  14.        int s = suma_div(i);
  15.        if (s > i and s <= m and suma_div(s) == i) cout << i << " y " << s << " son amigos" << endl;
  16.    }
  17. }
Para mejorar la eficiencia, podrías hacer una Criba de Eratóstenes al inicio del código para calcular todos los primos hasta la raíz cuadrada de m y luego para calcular los divisores, factorizar con dichos primos el número y generar con un pequeño bactracking todos los divisores, pero aunque supongo que iría más rápido, el código sería un poco más largo.
En línea

cbug

Desconectado Desconectado

Mensajes: 147



Ver Perfil
Re: Programa para hallar números amigos
« Respuesta #13 en: 27 Junio 2010, 19:17 pm »

ghastlyX, creo que la programación funcional no es algo que tenga muy bien entendido él. Con lo de la inicialización según dijo, en fortran no se necesita  :xD.

Ahora bien, el error que le marcaba para revisar es lo que se citó:

Citar
sólo miras si m es amigo de algún número dentro del intervalo, pero si el intervalo es [30,50], no miras nunca si 34 es amigo de 42,

Citar
Fijate que nunca s y t llegan a ser iguales por eso no lanza el print.

Si pueden llegar a ser iguales para alguna entrada.

Charderak

Fijate lo que citó ghastlyX y su explicación.

Si no sabés utilizar un debugger, haz una prueba de escritorio :)
En línea

Charderak

Desconectado Desconectado

Mensajes: 14


Ver Perfil
Re: Programa para hallar números amigos
« Respuesta #14 en: 27 Junio 2010, 19:26 pm »

Vale, más o menos creo que me he enterado y por lo menos ya tengo idea de por dónde puede andar el fallo, así que creo que es cuestión de ponerme a probar con las ideas que me habéis dado y acabar dando con la tecla

Voy a ello y luego os cuento, muchas gracias! :)
En línea

Páginas: 1 [2] Ir Arriba Respuesta Imprimir 

Ir a:  

WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines