Отмерьте один литр, используя две емкости и бесконечную подачу воды.

Опубликовано: 21 Января, 2022

Имеются два сосуда вместимостью «а» и «б» соответственно. У нас безграничное водоснабжение. Приведите эффективный алгоритм, позволяющий сделать ровно 1 литр воды в одной из емкостей. Вы можете вылить всю воду из любого сосуда в любой момент. Предположим, что «a» и «b» взаимно просты.

Ниже приведены шаги:
Пусть V1 - сосуд вместимостью «a», V2 - сосуд вместимостью «b», а «a» меньше, чем «b».
1) Выполните следующие действия, пока количество воды в V1 не равно 1.
…. а) Если V1 пуст, то полностью заполните V1
…. б) Перелейте воду из V1 в V2. Если V2 становится полным, оставьте оставшуюся воду в V1 и слейте V2.
2) V1 будет иметь 1 литр после завершения цикла на шаге 1. Возврат.

Following is C++ implementation of the above algorithm.

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;
}

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 + "
");
  
                // 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 + "
");
        }
  
        // 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

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 + "
");
  
                // 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 + "
");
        }
  
        // 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

Выход:

 Судно 1: 3 Судно 2: 0
Сосуд 1: 3 Сосуд 2: 3
Сосуд 1: 3 Сосуд 2: 6
Судно 1: 2 Судно 2: 0
Сосуд 1: 3 Сосуд 2: 2
Сосуд 1: 3 Сосуд 2: 5
Судно 1: 1 Судно 2: 0

Как это работает?

Чтобы доказать, что алгоритм работает, нам нужно доказать, что после определенного количества итераций в цикле while мы получим 1 литр в V1.
Пусть «a» - вместимость сосуда V1, а «b» - вместимость V2. Поскольку мы неоднократно переносим воду из V1 в V2 до тех пор, пока V2 не заполнится, у нас будет вода «a - b (mod a)» в V1, когда V2 станет полным в первый раз. Как только V2 наполняется, он опорожняется. У нас будет вода «a - 2b (mod a)» в V1, когда V2 заполнится второй раз. Мы повторяем вышеуказанные шаги и получаем воду «a - nb (mod a)» в V1 после того, как сосуд V2 наполняется и опорожняется «n» раз. Нам нужно доказать, что значение «a - nb (mod a)» будет равно 1 для конечного целого числа «n». Чтобы доказать это, рассмотрим следующее свойство взаимно простых чисел.
Для любых двух взаимно простых целых чисел «a» и «b» целое число «b» имеет мультипликативный обратный по модулю «a». Другими словами, существует целое число «y» такое, что «b * y ≡ 1 (mod) a» (см. 3-й пункт здесь). После итераций '(a - 1) * y' у нас будет вода 'a - [(a-1) * y * b (mod a)]] в V1, значение этого выражения будет' a - [(a - 1) * 1] mod a ', который равен 1. Итак, алгоритм сходится, и мы получаем 1 литр в V1.

Эта статья составлена Аашишем Барнвалом. Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по теме, обсужденной выше.

Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.

Отмерьте один литр, используя две емкости и бесконечную подачу воды.

C++

Java

C#

РЕКОМЕНДУЕМЫЕ СТАТЬИ