Mida un litro usando dos recipientes y suministro de agua infinito

Hay dos recipientes de capacidades ‘a’ y ‘b’ respectivamente. Tenemos suministro de agua infinito. Dé un algoritmo eficiente para hacer exactamente 1 litro de agua en uno de los recipientes. Puedes tirar toda el agua desde cualquier recipiente en cualquier momento. Suponga que ‘a’ y ‘b’ son coprimos .
Los siguientes son los pasos: 
Sea V1 el recipiente de capacidad ‘a’ y V2 el recipiente de capacidad ‘b’ y ‘a’ es más pequeño que ‘b’. 
1) Haga lo siguiente mientras la cantidad de agua en V1 no sea 1. 
…. a) Si V1 está vacío, entonces llene completamente V1 
…. b) Transferir agua de V1 a V2. Si V2 se llena, mantenga el agua restante en V1 y vacíe V2 
2)V1 tendrá 1 litro después de la terminación del bucle en el paso 1. Regresar.
A continuación se muestra la implementación en C++ del algoritmo anterior. 
 

C++

/* Sample run of the Algo for V1 with capacity 3 and V2 with capacity 7
1. Fill V1:                             V1 = 3, V2 = 0
2. Transfer from V1 to V2, and fill V1: V1 = 3, V2 = 3
2. Transfer from V1 to V2, and fill V1: V1 = 3, V2 = 6
3. Transfer from V1 to V2, and empty V2: V1 = 2, V2 = 0
4. Transfer from V1 to V2, and fill V1: V1 = 3, V2 = 2
5. Transfer from V1 to V2, and fill V1: V1 = 3, V2 = 5
6. Transfer from V1 to V2, and empty V2: V1 = 1, V2 = 0
7. Stop as V1 now contains 1 litre.
 
Note that V2 was made empty in steps 3 and 6 because it became full */
 
#include <iostream>
using namespace std;
 
// A utility function to get GCD of two numbers
int gcd(int a, int b) { return b? gcd(b, a % b) : a; }
 
// Class to represent a Vessel
class Vessel
{
    // A vessel has capacity, and current amount of water in it
    int capacity, current;
public:
    // Constructor: initializes capacity as given, and current as 0
    Vessel(int capacity) { this->capacity = capacity; current = 0; }
 
    // The main function to fill one litre in this vessel. Capacity of V2
    // must be greater than this vessel and two capacities must be co-prime
    void makeOneLitre(Vessel &V2);
 
    // Fills vessel with given amount and returns the amount of water
    // transferred to it. If the vessel becomes full, then the vessel
    // is made empty.
    int transfer(int amount);
};
 
// The main function to fill one litre in this vessel. Capacity
// of V2 must be greater than this vessel and two capacities
// must be coprime
void Vessel:: makeOneLitre(Vessel &V2)
{
    // solution exists iff a and b are co-prime
    if (gcd(capacity, V2.capacity) != 1)
        return;
 
    while (current != 1)
    {
        // fill A (smaller vessel)
        if (current == 0)
            current = capacity;
 
        cout << "Vessel 1: " << current << " Vessel 2: "
            << V2.current << endl;
 
        // Transfer water from V1 to V2 and reduce current of V1 by
        // the amount equal to transferred water
        current = current - V2.transfer(current);
    }
 
    // Finally, there will be 1 litre in vessel 1
    cout << "Vessel 1: " << current << " Vessel 2: "
        << V2.current << endl;
}
 
// Fills vessel with given amount and returns the amount of water
// transferred to it. If the vessel becomes full, then the vessel
// is made empty
int Vessel::transfer(int amount)
{
    // If the vessel can accommodate the given amount
    if (current + amount < capacity)
    {
        current += amount;
        return amount;
    }
 
    // If the vessel cannot accommodate the given amount, then
    // store the amount of water transferred
    int transferred = capacity - current;
 
    // Since the vessel becomes full, make the vessel
    // empty so that it can be filled again
    current = 0;
 
    return transferred;
}
 
// Driver program to test above function
int main()
{
    int a = 3, b = 7; // a must be smaller than b
 
    // Create two vessels of capacities a and b
    Vessel V1(a), V2(b);
 
    // Get 1 litre in first vessel
    V1.makeOneLitre(V2);
 
    return 0;
}

C#

/* Sample run of the Algo for V1 with capacity 3 and V2 with capacity 7
1. Fill V1:                             V1 = 3, V2 = 0
2. Transfer from V1 to V2, and fill V1: V1 = 3, V2 = 3
2. Transfer from V1 to V2, and fill V1: V1 = 3, V2 = 6
3. Transfer from V1 to V2, and empty V2: V1 = 2, V2 = 0
4. Transfer from V1 to V2, and fill V1: V1 = 3, V2 = 2
5. Transfer from V1 to V2, and fill V1: V1 = 3, V2 = 5
6. Transfer from V1 to V2, and empty V2: V1 = 1, V2 = 0
7. Stop as V1 now contains 1 litre.
 
Note that V2 was made empty in steps 3 and 6 because it became full */
 
using System;
 
class GFG
{
 
    // A utility function to get GCD of two numbers
    static int gcd(int a, int b)
    {
        return b > 0 ? gcd(b, a % b) : a;
    }
 
    // Class to represent a Vessel
    class Vessel
    {
         
        // A vessel has capacity, and
        // current amount of water in it
        int capacity, current;
 
        // Constructor: initializes capacity
        // as given, and current as 0
        public Vessel(int capacity)
        {
            this.capacity = capacity;
            current = 0;
        }
 
        // The main function to fill one litre
        // in this vessel. Capacity of V2 must be
        // greater than this vessel and two capacities
        // must be coprime
        public void makeOneLitre(Vessel V2)
        {
            // solution exists iff a and b are co-prime
            if (gcd(capacity, V2.capacity) != 1)
                return;
 
            while (current != 1)
            {
                // fill A (smaller vessel)
                if (current == 0)
                    current = capacity;
 
                Console.Write("Vessel 1: " + current +
                            " Vessel 2: " + V2.current + "\n");
 
                // Transfer water from V1 to V2 and
                // reduce current of V1 by
                // the amount equal to transferred water
                current = current - V2.transfer(current);
            }
 
            // Finally, there will be 1 litre in vessel 1
            Console.Write("Vessel 1: " + current +
                        " Vessel 2: " + V2.current + "\n");
        }
 
        // Fills vessel with given amount and
        // returns the amount of water
        // transferred to it. If the vessel
        // becomes full, then the vessel
        // is made empty
        int transfer(int amount)
        {
            // If the vessel can accommodate the given amount
            if (current + amount < capacity)
            {
                current += amount;
                return amount;
            }
 
            // If the vessel cannot accommodate
            // the given amount, then store
            // the amount of water transferred
            int transferred = capacity - current;
 
            // Since the vessel becomes full, make the vessel
            // empty so that it can be filled again
            current = 0;
 
            return transferred;
        }
    }
 
    // Driver program to test above function
    public static void Main(String[] args)
    {
        int a = 3, b = 7; // a must be smaller than b
 
        // Create two vessels of capacities a and b
        Vessel V1 = new Vessel(a);
        Vessel V2 = new Vessel(b);
 
        // Get 1 litre in first vessel
        V1.makeOneLitre(V2);
    }
}
 
// This code is contributed by Rajput-Ji

Java

/* Sample run of the Algo for V1 with capacity 3 and V2 with capacity 7
1. Fill V1:                             V1 = 3, V2 = 0
2. Transfer from V1 to V2, and fill V1: V1 = 3, V2 = 3
2. Transfer from V1 to V2, and fill V1: V1 = 3, V2 = 6
3. Transfer from V1 to V2, and empty V2: V1 = 2, V2 = 0
4. Transfer from V1 to V2, and fill V1: V1 = 3, V2 = 2
5. Transfer from V1 to V2, and fill V1: V1 = 3, V2 = 5
6. Transfer from V1 to V2, and empty V2: V1 = 1, V2 = 0
7. Stop as V1 now contains 1 litre.
 
Note that V2 was made empty in steps 3 and 6 because it became full */
 
class GFG
{
 
    // A utility function to get GCD of two numbers
    static int gcd(int a, int b)
    {
        return b > 0 ? gcd(b, a % b) : a;
    }
 
    // Class to represent a Vessel
    static class Vessel
    {
         
        // A vessel has capacity, and
        // current amount of water in it
        int capacity, current;
 
        // Constructor: initializes capacity
        // as given, and current as 0
        public Vessel(int capacity)
        {
            this.capacity = capacity;
            current = 0;
        }
 
        // The main function to fill one litre
        // in this vessel. Capacity of V2 must be
        // greater than this vessel and two capacities
        // must be coprime
        void makeOneLitre(Vessel V2)
        {
            // solution exists iff a and b are co-prime
            if (gcd(capacity, V2.capacity) != 1)
                return;
 
            while (current != 1)
            {
                // fill A (smaller vessel)
                if (current == 0)
                    current = capacity;
 
                System.out.print("Vessel 1: " + current +
                            " Vessel 2: " + V2.current + "\n");
 
                // Transfer water from V1 to V2 and
                // reduce current of V1 by
                // the amount equal to transferred water
                current = current - V2.transfer(current);
            }
 
            // Finally, there will be 1 litre in vessel 1
            System.out.print("Vessel 1: " + current +
                        " Vessel 2: " + V2.current + "\n");
        }
 
        // Fills vessel with given amount and
        // returns the amount of water
        // transferred to it. If the vessel
        // becomes full, then the vessel
        // is made empty
        int transfer(int amount)
        {
            // If the vessel can accommodate the given amount
            if (current + amount < capacity)
            {
                current += amount;
                return amount;
            }
 
            // If the vessel cannot accommodate
            // the given amount, then store
            // the amount of water transferred
            int transferred = capacity - current;
 
            // Since the vessel becomes full, make the vessel
            // empty so that it can be filled again
            current = 0;
 
            return transferred;
        }
    }
 
    // Driver program to test above function
    public static void main(String[] args)
    {
        int a = 3, b = 7; // a must be smaller than b
 
        // Create two vessels of capacities a and b
        Vessel V1 = new Vessel(a);
        Vessel V2 = new Vessel(b);
 
        // Get 1 litre in first vessel
        V1.makeOneLitre(V2);
    }
}
 
// This code is contributed by 29AjayKumar

Python3

# Sample run of the Algo for V1 with capacity 3 and V2 with capacity 7
# 1. Fill V1:                             V1 = 3, V2 = 0
# 2. Transfer from V1 to V2, and fill V1: V1 = 3, V2 = 3
# 2. Transfer from V1 to V2, and fill V1: V1 = 3, V2 = 6
# 3. Transfer from V1 to V2, and empty V2: V1 = 2, V2 = 0
# 4. Transfer from V1 to V2, and fill V1: V1 = 3, V2 = 2
# 5. Transfer from V1 to V2, and fill V1: V1 = 3, V2 = 5
# 6. Transfer from V1 to V2, and empty V2: V1 = 1, V2 = 0
# 7. Stop as V1 now contains 1 litre.
 
# Note that V2 was made empty in steps 3 and 6 because it became full
     
# A utility function to get GCD of two numbers
def gcd(a,b):
    return gcd(b, a % b) if(b > 0) else a
     
     
# Class to represent a Vessel
class Vessel:
 
    # Constructor: initializes capacity
    # as given, and current as 0
    def __init__(self,capacity):
 
        self.capacity = capacity
        self.current = 0
 
    # The main function to fill one litre
    # in this vessel. Capacity of V2 must be
    # greater than this vessel and two capacities
    # must be coprime
    def makeOneLitre(self,V2):
 
        # solution exists iff a and b are co-prime
        if (gcd(self.capacity, V2.capacity) != 1):
            return
 
        while (self.current != 1):
         
            # fill A (smaller vessel)
            if (self.current == 0):
                self.current = self.capacity
 
            print(f"Vessel 1: {self.current} Vessel 2: {V2.current}")
 
            # Transfer water from V1 to V2 and
            # reduce current of V1 by
            # the amount equal to transferred water
            self.current = self.current - V2.transfer(self.current)
             
        # Finally, there will be 1 litre in vessel 1
        print(f"Vessel 1: {self.current} Vessel 2: {V2.current}")
 
    # Fills vessel with given amount and
    # returns the amount of water
    # transferred to it. If the vessel
    # becomes full, then the vessel
    # is made empty
    def transfer(self,amount):
 
        # If the vessel can accommodate the given amount
        if (self.current + amount < self.capacity):
            self.current += amount
            return amount
         
        # If the vessel cannot accommodate
        # the given amount, then store
        # the amount of water transferred
        transferred = self.capacity - self.current
 
        # Since the vessel becomes full, make the vessel
        # empty so that it can be filled again
        self.current = 0
 
        return transferred
 
# Driver program to test above function
a,b = 3,7 # a must be smaller than b
 
# Create two vessels of capacities a and b
V1 = Vessel(a)
V2 = Vessel(b)
 
# Get 1 litre in first vessel
V1.makeOneLitre(V2)
 
# This code is contributed by shinjanpatra

Javascript

<script>
/* Sample run of the Algo for V1 with capacity 3 and V2 with capacity 7
1. Fill V1:                             V1 = 3, V2 = 0
2. Transfer from V1 to V2, and fill V1: V1 = 3, V2 = 3
2. Transfer from V1 to V2, and fill V1: V1 = 3, V2 = 6
3. Transfer from V1 to V2, and empty V2: V1 = 2, V2 = 0
4. Transfer from V1 to V2, and fill V1: V1 = 3, V2 = 2
5. Transfer from V1 to V2, and fill V1: V1 = 3, V2 = 5
6. Transfer from V1 to V2, and empty V2: V1 = 1, V2 = 0
7. Stop as V1 now contains 1 litre.
   
Note that V2 was made empty in steps 3 and 6 because it became full */
     
    // A utility function to get GCD of two numbers
    function gcd(a,b)
    {
        return b > 0 ? gcd(b, a % b) : a;
    }
     
 // Class to represent a Vessel   
class Vessel
{
    // Constructor: initializes capacity
        // as given, and current as 0
    constructor(capacity)
    {
        this.capacity = capacity;
        this.current = 0;
    }
     
    // The main function to fill one litre
        // in this vessel. Capacity of V2 must be
        // greater than this vessel and two capacities
        // must be coprime
    makeOneLitre(V2)
    {
        // solution exists iff a and b are co-prime
            if (gcd(this.capacity, V2.capacity) != 1)
                return;
   
            while (this.current != 1)
            {
                // fill A (smaller vessel)
                if (this.current == 0)
                    this.current = this.capacity;
   
                document.write("Vessel 1: " + this.current +
                            " Vessel 2: " + V2.current + "<br>");
   
                // Transfer water from V1 to V2 and
                // reduce current of V1 by
                // the amount equal to transferred water
                this.current = this.current - V2.transfer(this.current);
            }
   
            // Finally, there will be 1 litre in vessel 1
            document.write("Vessel 1: " + this.current +
                        " Vessel 2: " + V2.current + "<br>");
    }
     
    // Fills vessel with given amount and
        // returns the amount of water
        // transferred to it. If the vessel
        // becomes full, then the vessel
        // is made empty
    transfer(amount)
    {
        // If the vessel can accommodate the given amount
            if (this.current + amount < this.capacity)
            {
                this.current += amount;
                return amount;
            }
   
            // If the vessel cannot accommodate
            // the given amount, then store
            // the amount of water transferred
            let transferred = this.capacity - this.current;
   
            // Since the vessel becomes full, make the vessel
            // empty so that it can be filled again
            this.current = 0;
   
            return transferred;
    }
}
 
// Driver program to test above function
let a = 3, b = 7; // a must be smaller than b
   
// Create two vessels of capacities a and b
let V1 = new Vessel(a);
let V2 = new Vessel(b);
 
// Get 1 litre in first vessel
V1.makeOneLitre(V2);
 
 
// This code is contributed by rag2127
</script>

Producción: 

Vessel 1: 3   Vessel 2: 0
Vessel 1: 3   Vessel 2: 3
Vessel 1: 3   Vessel 2: 6
Vessel 1: 2   Vessel 2: 0
Vessel 1: 3   Vessel 2: 2
Vessel 1: 3   Vessel 2: 5
Vessel 1: 1   Vessel 2: 0

¿Como funciona esto?  
Para probar que el algoritmo funciona, necesitamos probar que después de cierto número de iteraciones en el ciclo while, obtendremos 1 litro en V1. 
Sea ‘a’ la capacidad del buque V1 y ‘b’ la capacidad de V2. Dado que transferimos agua repetidamente de V1 a V2 hasta que V2 se llena, tendremos agua ‘a – b (mod a)’ en V1 cuando V2 se llena por primera vez. Una vez que V2 se llena, se vacía. Tendremos agua ‘a – 2b (mod a)’ en V1 cuando V2 esté lleno por segunda vez. Repetimos los pasos anteriores y obtenemos agua ‘a – nb (mod a)’ en V1 después de que el recipiente V2 se llene y vacíe ‘n’ veces. Necesitamos demostrar que el valor de ‘a – nb (mod a)’ será 1 para un entero finito ‘n’. Para probar esto, consideremos la siguiente propiedad de los números coprimos. 
Para dos enteros coprimos cualesquiera‘a’ y ‘b’, el entero ‘b’ tiene un módulo inverso multiplicativo ‘a’. En otras palabras, existe un entero ‘y’ tal que ‘b*y ≡ 1(mod)a’ (Ver el tercer punto aquí ). Después de ‘(a – 1)*y’ iteraciones, tendremos ‘a – [(a-1)*y*b (mod a)]’ agua en V1, el valor de esta expresión es ‘a – [(a – 1) * 1] mod a’ que es 1. Entonces el algoritmo converge y obtenemos 1 litro en V1.
Este artículo ha sido compilado por Aashish Barnwal . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
 

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *