Solución al problema del vertido de agua
Llena A (3 litros) y vierte todo B.
Rellena A (3 litros) y usa el agua de A para llenar B. En este momento, A tiene 1 litro y B tiene 5 litros.
Vierte toda el agua de B y vierte 1 litro de agua de A en B. En este momento, A no tiene agua y B tiene un litro.
Llene nuevamente A (3 litros) y vierta toda el agua de A en b. En este momento, hay exactamente 4 litros de agua en b.
Evidentemente, existen otras soluciones a este tipo de problemas. Podemos inventar fácilmente otros problemas similares, como por ejemplo si es posible producir 5 litros de agua usando un vaso de agua de 7 litros y un vaso de agua de 13 litros, y si es posible producir 10 litros de agua usando un vaso de 9 litros. Vaso de agua de 1 litro y vaso de agua de 15 litros.
El problema de tres litros, cinco litros y cuatro litros es muy intuitivo y se puede construir una solución con un poco de reflexión. 13 litros, siete litros para sacar cinco litros, no parece intuitivo. Y hay otro problema que primero debe juzgarse si es factible antes de dar una solución.
¿Existe una solución general a este problema? La respuesta es sí. Tenga en cuenta que el paso aparentemente complicado de medir 4 litros de agua usando un recipiente de 3 litros y un recipiente de 5 litros se puede resumir simplemente como: verter toda la taza de A en B continuamente y vaciar B mientras B esté lleno.
En otras palabras, podemos resolver 3xmod5=43xmod5=4. Usando el algoritmo euclidiano extendido y su aplicación, podemos obtener fácilmente x=3x=3. En primer lugar, el problema tiene solución según el algoritmo euclidiano extendido. Cuando x = 3x = 3, la solución correspondiente es como se muestra en la figura anterior.
Luego mire 7 litros y 13 litros para obtener 5 litros, es decir, 7xmod13=57xmod13=5, 7, 137, 13 son primos relativos. Primero, juzgue que hay una solución, es decir, existe tal solución. ¿Cuál es el plan?
El primer paso es observar la ecuación de Bezu, es decir, 7 xmod 13 = 17 xmod 13 = 1. La solución en este momento es x = 2x = 2, es decir, vierte dos A en B, y A es mayor que 1 litro (1 litro).
El segundo paso: 7xmod13=57xmod13=5, en este momento x =(2x 5) 13 =(2x 5) 10x =(2x 5) 13 = 10.
¿Verter A lleno con 7 litros de agua en B? A (0 litros), B (7 litros)
¿Verter A lleno con 7 litros de agua en B hasta que B esté lleno? A (1L), B (13L)
¿B vacío? a (1 litro), B (0 litro)
¿Vierte un litro de agua de A a B? A (0 litros), B (1 litro) (los pasos 1, 2, 3 y 4 son una unidad)
¿Llenar A y verter B? A (0 litros), B (8 litros)
Llene nuevamente A y vierta B hasta llenar B. A (2 litros), B (13 litros)
¿Vacío b,? A (2 litros), B (0 litros)
¿Verter 2 litros de agua de A a B? A (0 litros), B (2 litros)
Hasta A (5 litros), B (0 litros);
Abstraemos aún más el problema y utilizamos los volúmenes aa y bb's taza de agua mide agua con un volumen de cc ¿Es realmente equivalente a resolver la ecuación A? xmodb=ca? xmodb=c. Si a, ba y b son primos relativos, se garantiza que el problema tiene solución.
Si c==mcd(a,b)c==mcd(a,b) o c==k? mcd(a,b)c==k? Mcd(a, b), xx se puede resolver mediante el algoritmo euclidiano extendido para obtener el plan de medición de agua final. Si cc no es divisible por mcd(a,b)mcd(a,b), entonces la ecuación no tiene solución, es decir, el problema no tiene solución. Por ejemplo, si un recipiente de 9 litros contiene 15 litros y recibe 10 litros de agua, 1010 no se puede dividir entre MCD (9, 15).