Рубрики

Головоломка с двумя кувшинами

Вы на берегу реки. Вам предоставляются м литровой бутыли и п литровой бутыли , где-<т <п. Оба кувшина изначально пустые. Кувшины не имеют маркировки, позволяющей измерять меньшие количества. Вы должны использовать кувшины для измерения d литров воды, где d <n. Определите минимальное количество операций, которые необходимо выполнить, чтобы получить литр воды в одном кувшине.
Операции, которые вы можете выполнить:

  1. Пустой кувшин
  2. Наполнить кувшин
  3. Налейте воду из одного кувшина в другой, пока один из кувшинов не станет пустым или полным .

Есть несколько способов решения этой проблемы, включая BFS и DP. В этой статье обсуждается арифметический подход к решению проблемы. Задача может быть смоделирована с помощью диофантова уравнения вида mx + ny = d, которое разрешимо тогда и только тогда, когда gcd (m, n) делит d. Также решение x, y, для которого выполняется уравнение, может быть дано с использованием алгоритма расширенного Евклида для GCD .
Например, если у нас есть кувшин J1 объемом 5 литров (n = 5) и еще один кувшин J2 объемом 3 литра (m = 3), и мы должны измерить 1 литр воды, используя их. Соответствующее уравнение будет 5n + 3m = 1. Прежде всего, эта проблема может быть решена, поскольку gcd (3,5) = 1, которая делит 1 (подробное объяснение см. В этом ). Используя алгоритм расширенного Евклида, мы получаем значения n и m, для которых выполняется уравнение: n = 2 и m = -3. Эти значения n, m также имеют некоторый смысл, например, здесь n = 2, а m = -3 означает, что мы должны заполнить J1 дважды и очистить J2 трижды.
Теперь, чтобы найти минимальное количество операций, которые нужно выполнить, мы должны решить, какой кувшин должен быть заполнен первым. В зависимости от того, какой кувшин выбран для наполнения, а какой — для опорожнения, у нас есть два разных решения, и минимум из них будет нашим ответом.

Раствор 1 (Всегда наливайте из кувшина объемом в литр в кувшин объемом n литров)

  1. Наполните кувшин объемом 1 м и опорожните его в кувшин объемом 1 л.
  2. Когда м-литровый кувшин опустеет, заполните его.
  3. Всякий раз, когда n-литровый кувшин становится полностью пустым.
  4. Повторите шаги 1, 2, 3, пока кувшин объемом n литров или кувшин объемом 1 литр не будет содержать d литров воды.

Каждый из шагов 1, 2 и 3 считается одной операцией, которую мы выполняем. Допустим, алгоритм 1 решает задачу в С1 без операций.

Решение 2 (Всегда наливайте из n литрового кувшина в m литровый кувшин)

  1. Заполните n-литровый кувшин и опорожните его в m-литровый кувшин.
  2. Всякий раз, когда n-литровый кувшин станет пустым, заполните его.
  3. Всякий раз, когда м-литровый кувшин становится полностью пустым.
  4. Повторите шаги 1, 2 и 3 до тех пор, пока в кувшине объемом n литров или в кувшине объемом не будет больше литров воды.

Допустим, решение 2 решает задачу в С2 без операций.

Теперь наше окончательное решение будет минимальным из C1 и C2.

Теперь мы покажем, как работают оба решения. Предположим, что есть 3-литровый кувшин и 5-литровый кувшин для измерения 4 литров воды, поэтому m = 3, n = 5 и d = 4 . Соответствующее диофантово уравнение будет 3m + 5n = 4. Мы используем пару (x, y) для представления количества воды в 3-литровом кувшине и 5-литровом кувшине соответственно на каждом этапе розлива.

Используя Решение 1, последовательные этапы заливки:

(0,0)->(3,0)->(0,3)->(3,3)->(1,5)->(1,0)->(0,1)->(3,1)->(0,4)

Следовательно, количество операций, которые вам нужно выполнить, равно 8.

Используя Решение 2, последовательные этапы заливки:

(0,0)->(0,5)->(3,2)->(0,2)->(2,0)->(2,5)->(3,4)

Следовательно, количество операций, которые вам нужно выполнить, равно 6.

Поэтому мы бы использовали решение 2 для измерения 4 литров воды за 6 операций или ходов.

На основе объяснения здесь приведена реализация на C ++.

// C ++ программа для подсчета минимального количества шагов
// требуется отмерить д литров воды с помощью кувшинов
// м литров и n литров.
#include <bits/stdc++.h>

using namespace std;

  
// Сервисная функция для возврата GCD из 'a'
// и 'b'.

int gcd(int a, int b)

{

    if (b==0)

       return a;

    return gcd(b, a%b);

}

  
/ * fromCap - Емкость кувшина, из которого

              вода заливается

   toCap - емкость кувшина, до которой

              вода заливается

   d - сумма для измерения * /

int pour(int fromCap, int toCap, int d)

{

    // Инициализируем текущее количество воды

    // в исходной и целевой кувшинах

    int from = fromCap;

    int to = 0;

  

    // Инициализируем количество необходимых шагов

    int step = 1; // Нужно заполнить "из" кувшина

  

    // разорвать цикл, когда любой из двух

    // кувшины имеют литр воды

    while (from != d && to != d)

    {

        // Находим максимальную сумму, которая может быть

        // налил

        int temp = min(from, toCap - to);

  

        // Выливаем «временные» литры из «от» до «до»

        to   += temp;

        from -= temp;

  

        // Увеличиваем количество шагов

        step++;

  

        if (from == d || to == d)

            break;

  

        // Если первый кувшин станет пустым, заполните его

        if (from == 0)

        {

            from = fromCap;

            step++;

        }

  

        // Если второй кувшин заполнен, очистите его

        if (to == toCap)

        {

            to = 0;

            step++;

        }

    }

    return step;

}

  
// Возвращает количество минимальных шагов, необходимых для
// мера д литр

int minSteps(int m, int n, int d)

{

    // Чтобы убедиться, что m меньше n

    if (m > n)

        swap(m, n);

  

    // Для d> n мы не можем измерить воду

    // используя кувшины

    if (d > n)

        return -1;

  

    // Если gcd из n и m не делит d

    // тогда решение невозможно

    if ((d % gcd(n,m)) != 0)

        return -1;

  

    // Возвращаем минимум два случая:

    // а) Вода из n литрового кувшина наливается в

    // м литровый кувшин

    // б) наоборот "а"

    return min(pour(n,m,d),   // н к м

               pour(m,n,d));  // м в п

}

  
// Код драйвера для проверки выше

int main()

{

    int n = 3, m = 5, d = 4;

  

    printf("Minimum number of steps required is %d",

           minSteps(m, n, d));

  

    return 0;

}

Minimum number of steps required is 6

Эта статья предоставлена Мадхур Моди. Если вам нравится GeeksforGeeks и вы хотите внести свой вклад, вы также можете написать статью и отправить ее по почте на contrib@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

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

Рекомендуемые посты:

Головоломка с двумя кувшинами

0.00 (0%) 0 votes