Consulta sobre macros y buenas prácticas

[aguml]

Hola amigos, me plantearon resolver un ejercicio matemático y como estaba fuera de mis conocimientos matemáticos lo resolví por fuerza bruta así:
#include <stdio.h>
#define PCERDOS 8000
#define PVACAS 40000
#define PGALLINAS 100
#define TOTAL 200000
#define Seguir() (gallinas + cerdos + vacas) <= 100 && (gallinas * PGALLINAS + cerdos * PCERDOS + vacas * PVACAS) <= TOTAL
#define Encontrado() (cerdos + vacas + gallinas == 100) && (cerdos * PCERDOS + vacas * PVACAS + gallinas * PGALLINAS) == TOTAL

int main()
{
int cerdos = 0, vacas = 0, gallinas = 0;

while (Seguir())
{
while (Seguir())
{
while (Seguir())
{
if (Encontrado())
{
printf("Vacas: %d\nCerdos: %d\nGallinas: %d\n", vacas, cerdos, gallinas);
return 0;
}
gallinas++;
}
gallinas = 0;
cerdos++;
}
cerdos = 0;
vacas++;
}
return 0;
}

Mi duda es fácil, para las pruebas de lo bucles se usan condiciones muy largas y repetitivas así que cree dos macros (Seguir y Encontrado). Mi duda es si es una buena práctica o por el contrario es muy mala. A ver si podéis aclararme las ideas.

[Alejandro]

¿Funciona?

No conozco el enunciado del problema, pero me parece que, o bien hay alguna condición más que no nos muestras, o el programamador tendrá que ingeniárselas para ir buscando una solución, si existiera. De cualquier manera, yo escapo de las macros casi como del corona virus.

[Rafael Ontivero]

Las macros son el mal, son peor que Bill Gates para un fundamentalista linuxero… En el caso que planteas, una clase, variables miembro y una llamada a función en el comparador. El compilador ya optimizará todo eso.

Veo tu problema, que es el planteamiento incorrecto del tema. No necesitas tanto comparador. Haz tres bucles for, anídalos y luego una sola condición de comparación para encontrado, y propagas el break o mejor aún que aquí me van a crucificar: un goto hacia afuera de todos los bucles.

Peeero, si en lugar de eso, llamas a una función que devuelva el valor correcto, haces un return en lugar de un break, y si las variables son miembro, no necesitas pasarlas:

class mates
{
auto cerdos=0, gallinas=0, vacas=0;
Void calcula()
{
For(...
For(...
For(…
{
If (condicion)
Return
}
};

Algo así, cuando calcula() retorne sabrás la solución de cerdos, gallinas y vacas.

Cualquier variación sobre eso podría ser válida (pasar las gallinas y lo demás como referencias no constantes…)

Ahora bien, si quieres ser pro de verdad, plantea la ecuación que tienes que resolver, transfórmala en algo más lineal y entonces las resuelves algorítmicamente.

> --
> --
> ¿Eres miembro de "CyC++ Buenos Aires" verdad? Si no lo eres, has recibido este mesaje por error.
> En caso de duda visita "http://groups.google.com/group/cppba"
> ---
> Has recibido este mensaje porque estás suscrito al grupo "CyC++ Buenos Aires" de Grupos de Google.
> Para cancelar la suscripción a este grupo y dejar de recibir sus mensajes, envía un correo electrónico a cppba+un...@googlegroups.com.
> Para ver este debate en la Web, visita https://groups.google.com/d/msgid/cppba/5f84d867-0980-48a9-8bb5-08c633847ecfo%40googlegroups.com.

[aguml]

El enunciado dice que un granjero compró 100 animales con 200000 pesetas. Si las vacas valen 40000 cada una, los cerdos 8000 y las gallinas 100 ¿Cuántos de cada compró?
Mi código funciona y podría ajustarse mucho mas.

[Alejandro Comes]

Asi como está, tienes 2 ecuaciones con 3 incógnitas. 

De todos modos, las macros dividen a la humanidad en tres grandes grupos, los que las usan y los que no. 

En C las encuentras por doquier, en C++ son la señal del malo en calzoncillos.

On Sun, 12 Jul 2020, 12:12 aguml, <ag...@hotmail.com> wrote:

El enunciado dice que un granjero compró 100 animales con 200000 pesetas. Si las vacas valen 40000 cada una, los cerdos 8000 y las gallinas 100 ¿Cuántos de cada compró?
Mi código funciona y podría ajustarse mucho mas.

--
--
¿Eres miembro de "CyC++ Buenos Aires" verdad? Si no lo eres, has recibido este mesaje por error.
En caso de duda visita "http://groups.google.com/group/cppba"
---

Has recibido este mensaje porque estás suscrito a un tema del grupo "CyC++ Buenos Aires" de Grupos de Google.
Para cancelar la suscripción a este tema, visita https://groups.google.com/d/topic/cppba/k3zKM1GtZy4/unsubscribe.
Para cancelar la suscripción a este grupo y a todos sus temas, envía un correo electrónico a cppba+un...@googlegroups.com.
Para ver este debate en la Web, visita https://groups.google.com/d/msgid/cppba/a5d7b53a-f301-4ecf-a517-bb33589484f5o%40googlegroups.com.

[Nicolás Gómez]

O (n^3) 😭

--
--
¿Eres miembro de "CyC++ Buenos Aires" verdad? Si no lo eres, has recibido este mesaje por error.
En caso de duda visita "http://groups.google.com/group/cppba"
---

Has recibido este mensaje porque estás suscrito al grupo "CyC++ Buenos Aires" de Grupos de Google.
Para cancelar la suscripción a este grupo y dejar de recibir sus mensajes, envía un correo electrónico a cppba+un...@googlegroups.com.
Para ver este debate en la Web, visita https://groups.google.com/d/msgid/cppba/5f84d867-0980-48a9-8bb5-08c633847ecfo%40googlegroups.com.

[Eduardo]

Y puede optimizarse bastante. 

De la relación  vacas+cerdos+gallinas=100  solo tiene sentido iterar 2 variables ya que  gallinas=100-vacas-cerdos

A su vez sustituyendo gallinas en la ecuación  vacas*PVACAS+cerdos*PCERDOS+gallinas*PGALLINAS = TOTAL

resulta:  vacas*(PVACAS-PGALLINAS)+cerdos*(PCERDOS-PGALLINAS) = (TOTAL-100*PGALLINAS)

Siendo que  PGALLINAS<PCERDOS<PVACAS si  (TOTAL-100*PGALLINAS)<0    el problema no tiene solución y si ==0  la solución obviamente son 100 gallinas.

Te queda  cerdos*(PCERDOS-PGALLINAS) = (TOTAL-100*PGALLINAS) - vacas*PVACAS 

---->  cerdos*B = C - vacas*A

por lo que solamente te queda un bucle de vacas donde tenés que comparar  MOD(C - vacas*A , B)==0       (MOD : módulo o residuo o resto)

[Alejandro Comes]

#include <iostream>

int main()
{
    // v + c + g = 100
    // v*40000 + c*8000 + g*100 = 200000

    // y me permito añadir dos condiciones más:
    // - no hay fracción de animal, ni cerdo sin cola ni gallina desplumada.
    // - tampoco se aceptan todas vacas ni todos cerdos ni todas gallinas.
   
    // dependiendo de los valores adoptados, puede haber una solución única, varias o ninguna...

    const int precio_vaca = 40000;
    const int precio_cerdo = 8000;
    const int precio_gallina = 100;
    const int animales = 100;
    const int dinero_total = 200000;

    int dinero_restante = dinero_total;
    int v = dinero_total / precio_vaca; // máxima cantidad de vacas posibles
    int c = 0;
    int g = 0;
    const int cerdos_por_vaca = precio_vaca / precio_cerdo;
    const int gallinas_por_cerdo = precio_cerdo / precio_gallina;

    bool al_menos_una = false;

    while (v > 0) {

        dinero_restante = dinero_total - v * precio_vaca;
        c = dinero_restante / precio_cerdo;

        if (c == 0) {
            --v;                     // sale una vaca
            c += cerdos_por_vaca;    // entran 5 cerdos
           
            if (v == 0)
                break;
        }

        g = (dinero_restante % precio_cerdo) * gallinas_por_cerdo;

        while (c > 0) {

            if (g == 0) {
                --c;                      // sale un cerdo
                g += gallinas_por_cerdo;  // entran 80 gallinas

                if (c == 0)
                    break;
            }

            if (v + c + g == animales) {
                std::cout << "v == " << v << "; c == " << c << "; g == " << g << '\n';
                al_menos_una = true;
            }

            --c; // falló, un cerdo menos.
        }

        --v; // falló; una vaca menos.
    }

    if(!al_menos_una)
        std::cout << "imposible\n";
}

--

--
¿Eres miembro de "CyC++ Buenos Aires" verdad? Si no lo eres, has recibido este mesaje por error.
En caso de duda visita "http://groups.google.com/group/cppba"
---

Has recibido este mensaje porque estás suscrito a un tema del grupo "CyC++ Buenos Aires" de Grupos de Google.
Para cancelar la suscripción a este tema, visita https://groups.google.com/d/topic/cppba/k3zKM1GtZy4/unsubscribe.
Para cancelar la suscripción a este grupo y a todos sus temas, envía un correo electrónico a cppba+un...@googlegroups.com.
Para ver esta conversación en el sitio web, visita https://groups.google.com/d/msgid/cppba/ff77fd5c-05ce-4f4b-a01c-0ba956a94ef3o%40googlegroups.com.

[Daniel Gutson]

Hola Aguml (nombre?)

El problema y la pregunta son muy interesantes. Te contesto un poquito indignado por las respuestas que les noté un tono que no me gustó. 

Por un lado, el uso de macros en C++ es de muy mala práctica porque (montón de bibliografía), por ejemplo

#define cuadrado(n) n*n

Cuánto vale cuadrado(1+1)?

Si hubiese sido una función no habría problemas (qué problema?).

Las únicas macros que yo considero válidas porque no tienen cómo hacerse en C++ son las x-macros (wikipedia).

Te propongo a vos encontrar mejores soluciones con la ayuda que te voy a dar y te las voy observando:

1) hacé una versión de tu programa que en vez de macros use lambdas (que Seguir sea una lambda) y mostrame el código 

2) hacé otra versión que en vez de 3 whiles anidados use uno solo, pista: considerando como un carry flag

3) solamente estás considerando una solución pero puede haber varias. El problema se trata de resolver una ecuación diofántica. Mostrame una tercer implementación que muestre todas las soluciones con el algoritmo de solución de ecuación diofántica. Acá es donde más vas a aprender. Y el resto también!

El dom., 12 jul. 2020 12:12 p. m., aguml <ag...@hotmail.com> escribió:

El enunciado dice que un granjero compró 100 animales con 200000 pesetas. Si las vacas valen 40000 cada una, los cerdos 8000 y las gallinas 100 ¿Cuántos de cada compró?
Mi código funciona y podría ajustarse mucho mas.

--
--
¿Eres miembro de "CyC++ Buenos Aires" verdad? Si no lo eres, has recibido este mesaje por error.
En caso de duda visita "http://groups.google.com/group/cppba"
---

Has recibido este mensaje porque estás suscrito al grupo "CyC++ Buenos Aires" de Grupos de Google.
Para cancelar la suscripción a este grupo y dejar de recibir sus mensajes, envía un correo electrónico a cppba+un...@googlegroups.com.

Para ver este debate en la Web, visita https://groups.google.com/d/msgid/cppba/a5d7b53a-f301-4ecf-a517-bb33589484f5o%40googlegroups.com.

[RFOG]

>>  x-macros 

Tu siempre liado con el porno... Te vas a quedar sin médula espinal. :-D

Para ver esta conversación en el sitio web, visita https://groups.google.com/d/msgid/cppba/CAFdMc-2hagZTqiS55mSYyX%2BWjXSJoZKyJDC%3Df3%3D39Kvq07EdOA%40mail.gmail.com.

[Daniel Gutson]

Pd: el problema entra dentro de lo que se conoce como integer constraint solving, de lo que programación lineal se desprende si bien no es el caso porque sirve para optimizar sistemas y acá no se trata de optinizar.

[Jorge Atala]

Estaba un poco aburrido, asi que me meto en la discusion, te voy a pasar la solucion analitica del problema para que vos implementes el mejor algoritmo, y de paso lo generalices para problemas similares. Primero voy a eliminar uno de los animales de la ecuacion para poder graficar en 2D y que se entienda mas facil el grafico. Elijo a la vaca porque es la mas cara. Bien, el rango de posibles cantidades de vacas que puede comprar sin pasarse de precio es [0,5], asi que el rango de posibles valores que me da la suma de chanchos y gallinas es [95,100] eso me da seis rectas si grafico chanchos y gallinas en el eje cartesiano.

Es imṕortante notar que cualquier resultado posible esta contenido en esas rectas. Ahora, de acuerdo a cuantas vacas compre, hay 6 valores posibles para lo que gaste en chanchos mas gallinas (0, 40k, 80k, 120k, 160k y 200k) Entonces ahora reduzco la cantidad de soluciones a las intersecciones de esas rectas, 6x6=30, tengo 30 valores para validar solamente, de los cuales tengo que elegir aquellos en los que la cantidad de chanchos y gallinas sea entero (esta parte te la dejo resolver a vos). Graficamente me quedaria esto: 

Para ver esta conversación en el sitio web, visita https://groups.google.com/d/msgid/cppba/CAFdMc-2YR60DtEiE0CbofOfEeSbF_xZ%2B%2B1N80-kDND8%3DQPLG0w%40mail.gmail.com.

[Daniel Gutson]

Sugerencia: para resolverlo de esta manera, asumiendo cualquier precio de los animales, recomiendo usar recursividad para la combinatoria.

Es otra implementación interesante.

(compararla con la de las ecuaciones diofánticas)

Para ver esta conversación en el sitio web, visita https://groups.google.com/d/msgid/cppba/CAK16hfReaFX%3Dv13B8xidNGCDWDb5gnkEzRuOSib3UXhaK1s_BQ%40mail.gmail.com.

--

Who’s got the sweetest disposition?
One guess, that’s who?
Who’d never, ever start an argument?
Who never shows a bit of temperament?
Who's never wrong but always right?
Who'd never dream of starting a fight?
Who get stuck with all the bad luck?

[Daniel Gutson]

Creo que este algoritmo depende de los valores de los precios. No funciona para cualquier triplete de valores aún preservando

Precios

Vaca > cerdo > gallina

Has recibido este mensaje porque estás suscrito al grupo "CyC++ Buenos Aires" de Grupos de Google.

Para cancelar la suscripción a este grupo y dejar de recibir sus mensajes, envía un correo electrónico a cppba+un...@googlegroups.com.
Para ver esta conversación en el sitio web, visita https://groups.google.com/d/msgid/cppba/CAKXqm%2BvKddv3-qwwvZAKohCzY07cZDArmonqrgMJzXhJeh2sKA%40mail.gmail.com.

[Alejandro Comes]

Al menos ya encontré un error. Si no les parece una completa basura después lo corrijo

Para ver esta conversación en el sitio web, visita https://groups.google.com/d/msgid/cppba/CAFdMc-0Zs7Fke%3D%3DXi%3DDftfu2OC0KTD9eZAr8ENc5Pr6pdx5sxg%40mail.gmail.com.

[Alejandro Comes]

Creo que está. Puse un segundo juego de valores que me parece más interesante.

#include <iostream>

int main()
{
    // v + c + g = 100
    // v*40000 + c*8000 + g*100 = 200000

    // y me permito añadir dos condiciones más:
    // - no hay fracción de animal, ni cerdo sin cola ni gallina desplumada.
    // - tampoco se aceptan todas vacas ni todos cerdos ni todas gallinas.

    // dependiendo de los valores adoptados, puede haber una solución única, varias o ninguna...

    /*const int precio_vaca = 40000;

    const int precio_cerdo = 8000;
    const int precio_gallina = 100;
    const int animales = 100;

    const int dinero_total = 200000;*/

    const int precio_vaca = 100;
    const int precio_cerdo = 30;
    const int precio_gallina = 5;

    const int animales = 100;

    const int dinero_total = 5795;

    int dinero_restante = dinero_total;
    int v = dinero_total / precio_vaca; // máxima cantidad de vacas posibles
    int c = 0;
    int g = 0;
    const int cerdos_por_vaca = precio_vaca / precio_cerdo;
    const int gallinas_por_cerdo = precio_cerdo / precio_gallina;

    bool al_menos_una = false;

    while (v > 0) {

        dinero_restante = dinero_total - v * precio_vaca;
        c = dinero_restante / precio_cerdo;

        if (c == 0) {
            --v;                     // sale una vaca
            c += cerdos_por_vaca;    // entran 5 cerdos

            if (v == 0)
                break;
        }

        if ((dinero_restante % precio_cerdo) % precio_gallina)  // no hay céntimos
            continue;

        g = (dinero_restante % precio_cerdo) / precio_gallina;

       
        if (g == 0) {
            --c;                      // sale un cerdo
            g += gallinas_por_cerdo;  // entran 80 gallinas
        }

        while (c > 0) {

            if (v + c + g == animales) {
                std::cout << "v == " << v << "; c == " << c << "; g == " << g << '\n';
                al_menos_una = true;
            }

            --c;                        // sale un cerdo
            g += gallinas_por_cerdo;   // entran 80 gallinas

            if (g > animales - v - c)
                break;

        }

        --v; // sale una vaca
    }

    if (!al_menos_una)
        std::cout << "imposible\n";
}

Para ver esta conversación en el sitio web, visita https://groups.google.com/d/msgid/cppba/CAFdMc-0Zs7Fke%3D%3DXi%3DDftfu2OC0KTD9eZAr8ENc5Pr6pdx5sxg%40mail.gmail.com.

[Daniel Gutson]

Probá con valores coprimos.

Podés no estar recorriendo todo el espacio de soluciones.

Para ver esta conversación en el sitio web, visita https://groups.google.com/d/msgid/cppba/CAKXqm%2BuHF4dVi%3DngKSg1OmokWXPkiz1FJZSUWeSSLu0zQoLgTA%40mail.gmail.com.

[Alejandro Comes]

con valores coprimos se fué todo al tacho...

Pero bien, gracias a Diofanto supongo que quedó:

#include <iostream>

int main()
{
    // v + c + g = 100
    // v*40000 + c*8000 + g*100 = 200000

    // y me permito añadir dos condiciones más:
    // - no hay fracción de animal, ni cerdo sin cola ni gallina desplumada.
    // - tampoco se aceptan todas vacas ni todos cerdos ni todas gallinas.

    // dependiendo de los valores adoptados, puede haber una solución única, varias o ninguna...

    /*const int V = 40000;
    const int C = 8000;
    const int G = 100;

    const int animales = 100;
    const int dinero_total = 200000;*/

    /*const int V = 100;
    const int C = 30;
    const int G = 5;

    const int animales = 100;

    const int dinero_total = 5795;*/

    const int V = 3;
    const int C = 7;
    const int G = 5;
    const int animales = 5;
    const int dinero_total = 25;


    int B = 0;                // dinero restante
    int v = dinero_total / V; // máxima cantidad de vacas posibles
    int A = animales - v;     // cerdos + gallinas

    int c = 0;
    int g = 0;

    while (v > 0) {

        B = dinero_total - v * V;
        A = animales - v;


        if ((B - C * A) % (G - C) == 0) {  // sólo soluciones enteras

            g = (B - C * A) / (G - C);
            c = A - g;

            if ((v > 0 && c > 0 && g > 0))  // sólo soluciones positivas

            {
                std::cout << "v == " << v << "; c == " << c << "; g == " << g

                          << "\tPrecio == " << V * v + C * c + G * g << '\n';
            }
        }

        --v;
    }

}

Para ver esta conversación en el sitio web, visita https://groups.google.com/d/msgid/cppba/CAFdMc-23-tRQuwopU3i%2BCQMe%3DS2uuR2e5QPm5Za%2BZrmw1uKwtg%40mail.gmail.com.

[Carlos Cattaneo]

No hace falta un programa para resolver dicho problema:

Se reduce a:

399*V + 79*C = 1900

Y por lo tanto, la solución es V = 1; C = 19. De donde, G = 80.

Para ver esta conversación en el sitio web, visita https://groups.google.com/d/msgid/cppba/CAKXqm%2BuFSrS%2Bb-RpFfg7FS_%3Dj-eU%3Djc9zc8kj%2B2sc%2BHwEk4UjQ%40mail.gmail.com.

[Daniel Gutson]

La idea es, como siempre aprovechar para que resulte educativo, confeccionar una solución general.

Te propongo postear la tuya.

Para ver esta conversación en el sitio web, visita https://groups.google.com/d/msgid/cppba/CAN_JHjnKrz91D28MLmizBv7nPkF2%3DwowjjQf-ALZbOR6TV9QsA%40mail.gmail.com.

[Daniel Gutson]

El mar., 14 de jul. de 2020 a la(s) 15:29, Alejandro Comes (aco...@gmail.com) escribió:

con valores coprimos se fué todo al tacho...

Pero bien, gracias a Diofanto supongo que quedó:

Bien, tiene pinta. Tirás unas líneas explicando las cuentas?

 

Para ver esta conversación en el sitio web, visita https://groups.google.com/d/msgid/cppba/CAKXqm%2BuFSrS%2Bb-RpFfg7FS_%3Dj-eU%3Djc9zc8kj%2B2sc%2BHwEk4UjQ%40mail.gmail.com.

[Alejandro Comes]

Bien, tiene pinta. Tirás unas líneas explicando las cuentas?

Sí. Como se tienen 2 ecuaciones con tres incógnitas, el truco es variar una de ellas (en este caso v) e ir calculando el sistema restante de 2 ecuaciones con 2 incógnitas.

Si fueran números reales se tendría una familia de infinitos sistemas, pero como se restringe a valores enteros de v (también de c y g), los sistemas quedan finitos.

Entonces, variando v, de uno en uno, se van calculando las soluciones para c y v, que ahora son únicas-

De esas soluciones sólo se seleccionan sólo las que den enteros mayores que cero.

Para resolver el sistema de dos ecuaciones yo usé "sustitución" (que es el único que me acuerdo... es que pasaron unos añitos..), pero puede usarse cualquiera. En este caso yo puse a cerdos en términos de gallinas (o fue al revés, bueno, cualquiera de las dos).

Así:

con A == animales - v;  (animales restantes después de descontar v; o sea, c+g)

y    B == C*c + G*g;     (costo de los cerdos más las gallinas)

el sistema para cada una de las v queda:

(1)   c + g = A;

(2)   C*c + G*g = B

Acá resolví haciendo,

de (1)    c = A-g;

y sustituyendo este c en (2), quedó:

C*(A-g) + G*g = B;

de ahí despejé g:

g = (B - C * A) / (G - C);

Y ya con g, en (1):

c = A - g;

Eso es. De estas soluciones para g y c, me quedé con las que dieron g entero, y por consecuencia c también.

Después también me quedé sólo con v, g y c positivos. (Bueno, controlar que v también sea positivo está de más, porque ya arrancamos con esa condición).

Y un comentario; para tener un menor número de iteraciones conviene ir iterando sobre el animal más caro.

Para ver esta conversación en el sitio web, visita https://groups.google.com/d/msgid/cppba/CAFdMc-1yxBd%2BFMEMfq7%2B0xEyJwxQBjHWEJ3vk8U1N7gh-nAkvA%40mail.gmail.com.

[Carlos Cattaneo]

Sigo sin verle el lado educativo, más allá de la matemática empleada.

Una vez que el problema se redujo a:

399*V + 79*C = 1900

Es claramente una ecuación diofántica cuya solución general está explicada en:

https://es.wikipedia.org/wiki/Ecuaci%C3%B3n_diof%C3%A1ntica

En nuestro caso particular se agregan las condiciones de contorno 

0 <= V <= 100

0 <= C <= 100

0 <= G <= 100

Con respecto a la pregunta de sobre las macros, mi opinión es que en C++ moderno no deberíamos usar el preprocesador para hacer lo que se puede hacer con constexpr o funciones inline, etc.

Pero sigo pensando que el preprocesador aún tiene usos válidos. 

Es parte del arsenal de metaprogramming (ver por ejemplo: https://www.boost.org/doc/libs/1_73_0/libs/preprocessor/doc/index.html)

Saludos,

Carlos

Para ver esta conversación en el sitio web, visita https://groups.google.com/d/msgid/cppba/CAFdMc-3EzG7jaFj7m%3DSiPBYemsUMFi2Q4jarp6QKkweY1VkyPQ%40mail.gmail.com.

[Daniel Gutson]

En dónde usaste la solución de la ecuación diofántica, y en qué se diferenciande la solución de Jorge con sus rectas?

Te pregunto para darte letra. 

Para ver esta conversación en el sitio web, visita https://groups.google.com/d/msgid/cppba/CAKXqm%2BuT7qOu9NZ9a4ti7%3DCw1CTF-wxSWsa74j%3DWhgYh_RsTgg%40mail.gmail.com.

[Alejandro Comes]

 Bueno, ejém... No, la verdad es que no había leído el artículo en Wikipedia sobre la Ecuación Diofántica, sólo me había quedado con la idea de que estas ecuaciones son de la forma ax + by = c y que tienen coeficientes enteros y soluciones enteras. Mi algoritmo es el desarrollo de esa idea.

Ahora veo que la propiedad que menciona el artículo sobre que

"Una condición necesaria y suficiente para que ax + by = c con a, b, c perteneciente a los enteros, tenga solución, es que el máximo común divisor de a, y b, divida a c."

Podría haberla usado como optimización, para no buscar inútilmente lo que no hay.

Y sobre la solución de Jorge, creo que es una interpretación gráfica equivalente, se pueden dibujar las familias de rectas para v finito y calcular sus abscisas y ordenadas. Creo que me gusta más para darle una representación menos formal y más intuitiva, pero al final supongo que todos vamos a hacer más o menos lo mismo.

Para ver esta conversación en el sitio web, visita https://groups.google.com/d/msgid/cppba/CAFdMc-1%3D%3DVvO%3Dmb8KU1qGCY5tQXne%3Dj%2BY%2B2FiF2JMYLxVZmhLQ%40mail.gmail.com.

[Daniel Gutson]

Fijate que el MCD no se usa solamente para saber si tiene solución o no. Por ejemplo, se podría usar para mejorar tu algoritmo y que busque más rápido?

Para ver esta conversación en el sitio web, visita https://groups.google.com/d/msgid/cppba/CAKXqm%2BtjBi7L4NN6bR2Hx7HEahLnRiVMRgWJ87TmcMYYjCS5GA%40mail.gmail.com.

[Carlos Cattaneo]

Sólo quise acercar un poco de teoría. 

Como dice en: https://es.wikipedia.org/wiki/Ecuaci%C3%B3n_diof%C3%A1ntica

La ecuación diofántica {\displaystyle Ax+By=C\,} o identidad de Bézout tiene solución si y solo si d = mcd(A, B)

Eso es porque toda combinación lineal (entera) de de enteros de los enteros A y B es un múltiplo de mcd(A, B).

El mcd() se puede calcular con el Algoritmo de Euclides, que en términos nuestros se expresa fácilmente con la función recursiva:

mcd(A, B) = mcd(B, A % B)

mcd(A, 0) = A

para A > B

Hay una versión extendida del algoritmo de euclides que tira además una solución (x1, y1) de

A*x1 + B*y1 = mcd(A, B)

Multiplicando miembros con C / mcd(A, B) se obtiene una solución particular de la ecuación de arriba.

Luego como sigue diciendo el art. de wikipedia

Supongamos la ecuación diofántica {\displaystyle \scriptstyle Ax+By=C\,}. Solo tiene solución si {\displaystyle \scriptstyle \mathrm {mcd} (A,B)=d|C\,}. Para buscar el {\displaystyle \scriptstyle \mathrm {mcd} (A,B)} empleamos el algoritmo de Euclides. Si una ecuación diofántica tiene solución, necesariamente tiene infinitas soluciones y todas son de la forma:

{\displaystyle {\begin{cases}x=x_{1}+\lambda {\cfrac {B}{d}}\\y=y_{1}-\lambda {\cfrac {A}{d}}\end{cases}}}

Donde {\displaystyle \scriptstyle d=\mathrm {mcd} (A,B)} y {\displaystyle \scriptstyle x_{1}} e {\displaystyle \scriptstyle y_{1}} son una solución particular de la ecuación.

Donde las soluciones se expresan en término de un solo parámetro lambda.

En el caso particular del problema propuesto: 

399*V + 79*C = 1900

Es obvio que mcd(399, 79) = 1, ya que 79 es primo. Y por lo tanto la ecuación tiene solución para cualquier valor de C. Y además de la solución particular me salió al primer tanteo así que no necesité a Euclides.

Este problema en particular tiene esta ventaja y además de la ventaja adicional de las condiciones de contorno entre 0 y 100. 

Generalizarlo es bastante más complejo. Yo empezaría intenta de obtener lo más rápido posible una estimación de un valor mínimo y máximo de lambda y luego itero en lambda en ese rango de valores (un solo loop).

Como seguro le ha pasado alguna vez a todos los programadores, estoy con un pico de trabajo en este momento y tengo que terminar aquí mi intervención en el grupo.

Sólo agrego otro aspecto interesante de las ecuaciones diofánticas generales (las que estábamos analizando era lineales). 

Bueno, resulta que se ha demostrado que en el caso general no existe un algoritmo que pueda decidir si tiene solución o no una ecuación diofántica arbitraria.

Ver: https://en.wikipedia.org/wiki/Hilbert%27s_tenth_problem#:~:text=Sets%20of%20natural%20numbers%2C%20of,Diophantine%20set%20is%20non%2Dempty.

Saludos,

Carlos

Para ver esta conversación en el sitio web, visita https://groups.google.com/d/msgid/cppba/CAFdMc-08OWMQa-rDwLKbA1BmypW_C46hO4gj203aK7Pp0xgO5w%40mail.gmail.com.

[Daniel Gutson]

El mar., 14 de jul. de 2020 a la(s) 18:56, Carlos Cattaneo (carlosca...@gmail.com) escribió:

Sigo sin verle el lado educativo, más allá de la matemática empleada.

En mostrar todas las maneras en que se puede implementar. No vi ninguna recursiva por ejemplo.

 

Para ver esta conversación en el sitio web, visita https://groups.google.com/d/msgid/cppba/CAN_JHjmGAYb9J09qaDEwOUi%2BUc6hJwo4gU50ZFHQTuJz5CQd7Q%40mail.gmail.com.