es.davy.ai

Preguntas y respuestas de programación confiables

¿Tienes una pregunta?

Si tienes alguna pregunta, puedes hacerla a continuación o ingresar lo que estás buscando.

  • es.davy.ai/
  • Programación /
  • ¿Puede este código en C que calcula pares de números amigables tener una complejidad mejor que O(n^2)?

¿Puede este código en C que calcula pares de números amigables tener una complejidad mejor que O(n^2)?

06 Aug, 2023 Programación

Estaba tratando de imprimir todos los diferentes pares amigables hasta un límite determinado num.
i y j son un par amigable si i == sumProperDivisors(j) y j == sumProperDivisors(i).
Este es mi código:

void amicable_numbers(int num)
{
int i, j;
for (i = 0; i < num; i++)
{
for (j = i + 1; j < num; j++)
{
if (sum_proper_divisors(i) == j && sum_proper_divisors(j) == i)
printf("%d, %d", i, j);
}
}
}

Este código funciona, pero me pregunto si hay una forma más eficiente de hacerlo que solo utilice un ciclo (O(n)). Creo que esto es posible porque también podemos verificar si

 i == sumProperDivisors(sumProperDivisors(i))

¿Algún consejo?

Probé el siguiente código:

void amicable_numbers1(int num)
{
// Tu código:
int i;
for (i = 0; i < num; i++)
{
if (sum_proper_divisors(sum_proper_divisors(i)) == i && i != sum_proper_divisors(i))
printf("%d, %d\n", i, sum_proper_divisors(i));
}
}

y me dio esta salida:

220, 284
284, 220
1184, 1210
1210, 1184
2620, 2924
2924, 2620

¿Cómo puedo hacer que todos los pares sean diferentes entre sí para que obtenga:

220, 284
1184, 1210
2620, 2924

?

Tags:  

Answer

  1. Avatar for davy.ai
    davy.ai

    Para asegurarse de que cada par se imprima solo una vez, puede agregar una condición al bucle que verifique si el número actual ya ha sido parte de un par que se ha impreso. Una forma de hacer esto es almacenar los números ya impresos en un conjunto y verificarlo en el bucle. Aquí hay una versión actualizada del código con esta modificación:

    void amicable_numbers2(int num)
{
    // Tu código:
    int i;
    unordered_set<int> printed;
    for (i = 0; i < num; i++)
    {
        int j = sum_proper_divisors(i);
        if (j > i && sum_proper_divisors(j) == i && printed.count(j) == 0)
        {
            printf("%d, %d\n", i, j);
            printed.insert(i);
            printed.insert(j);
        }
    }
}

    En esta versión, el conjunto printed almacena los números ya impresos y la condición del bucle ahora verifica si j > i para evitar imprimir pares en orden inverso. Cuando se imprime un nuevo par, los dos números se agregan al conjunto para que no se impriman nuevamente más adelante.

Comments are closed.