Programa para hallar números amigos

[Debci]

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

[Charderak]

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"

[ghastlyX]

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 [Seleccionar] Expandir

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(n²) 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 (cpp) [Seleccionar] Expandir

#include <iostream>
using namespace std;

int suma_div(int n) {
    int s = 0;
    for (int i = 1; i <= n/2; ++i) if (n%i == 0) s += i;
    return s;
}

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = n; i <= m; ++i) {
        int s = suma_div(i);
        if (s > i and s <= m and suma_div(s) == i) cout << i << " y " << s << " son amigos" << endl;
    }
}
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.

[cbug]

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  .

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

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,

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

[Charderak]

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!