Я столкнулся с этой проблемой во время одного из моих исследований. Как вы и сказали здесь, я нашел в качестве ответа на проблему алгоритм Расширенного Евклида. Но этот ответ меня не устраивает, потому что я думаю, что это количественный ответ, а не качественный (то есть алгоритм не говорит, какой шаг предпринять, чтобы достичь результата).
Мне кажется, я нашел другое решение проблемы, которое всегда достигает результата с минимальным количеством шагов.
Вот оно:
- Проверьте выполнимость проблемы:
- Q кратно MCD (A, B);
- Q равно <= max (A, B). </li>
Выберите сервисный кувшин (то есть тот, который вы заправите с помощью насоса). Предположим, A> B (вы можете легко найти, какой кувшин больше):
if(Q is multiple of B)
return B
a_multiplier = 1
b_multiplier = 1
difference = A - B
a_multiple = A
b_multiple = B
while(|difference| differs Q)
if b_multiple < a_multiple
b_multiple = b_multiplier + 1
b_multiple = b_multiplier * B
else
a_multiple = a_multiplier + 1
a_multiple = a_multiplier * A
difference = a_multiple - b_multiple
if(difference < 0)
return B
else
return A
начать процесс заполнения:
заполнить насосом сервисный кувшин (если он пуст)
заполнить другой кувшин, воспользовавшись услугой
проверить наполненность другого кувшина и, в случае, опустошить его
остановка, когда в большом кувшине содержится Q
Ниже вы найдете очень наивную реализацию алгоритма в c ++. Не стесняйтесь использовать его или улучшать по мере необходимости.
#include <cstdio>
#include <cstdlib>
#include <cstring>
unsigned int mcd(unsigned int a, unsigned int b) {
// using the Euclide's algorithm to find MCD(a,b)
unsigned int a_n = a;
unsigned int b_n = b;
while(b_n != 0) {
unsigned int a_n1 = b_n;
b_n = a_n % b_n;
a_n = a_n1;
}
return a_n;
}
unsigned int max(unsigned int a, unsigned int b) {
return a < b ? b : a;
}
unsigned int min(unsigned int a, unsigned int b) {
return a > b ? b : a;
}
void getServiceJugIndex(unsigned int capacities[2], unsigned int targetQty, unsigned int &index) {
unsigned int biggerIndex = capacities[0] < capacities[1] ? 1 : 0;
unsigned int smallerIndex = 1 - biggerIndex;
if(targetQty % capacities[smallerIndex] == 0) {
// targetQty is a multiple of the smaller jug, so it's convenient to use this one
// as 'service' jug
index = smallerIndex;
return;
}
unsigned int multiples[2] = {capacities[0], capacities[1]};
unsigned int multipliers[2] = {1, 1};
int currentDifference = capacities[0] - capacities[1];
while(abs(currentDifference) != targetQty) {
if(multiples[smallerIndex] < multiples[biggerIndex])
multiples[smallerIndex] = capacities[smallerIndex] * ++multipliers[smallerIndex];
else
multiples[biggerIndex] = capacities[biggerIndex] * ++multipliers[biggerIndex];
currentDifference = multiples[biggerIndex] - multiples[smallerIndex];
}
index = currentDifference < 0 ? smallerIndex : biggerIndex;
}
void print_step(const char *message, unsigned int capacities[2], unsigned int fillings[2]) {
printf("%s\n\n", message);
for(unsigned int i = max(capacities[0], capacities[1]); i > 0; i--) {
if(i <= capacities[0]) {
char filling[9];
if(i <= fillings[0])
strcpy(filling, "|=====| ");
else
strcpy(filling, "| | ");
printf("%s", filling);
} else {
printf(" ");
}
if(i <= capacities[1]) {
char filling[8];
if(i <= fillings[1])
strcpy(filling, "|=====|");
else
strcpy(filling, "| |");
printf("%s", filling);
} else {
printf(" ");
}
printf("\n");
}
printf("------- -------\n\n");
}
void twoJugsResolutor(unsigned int capacities[2], unsigned int targetQty) {
if(capacities[0] == 0 && capacities[1] == 0) {
printf("ERROR: Both jugs have 0 l capacity.\n");
return;
}
// 1. check feasibility
// 1.1. calculate MCD and verify targetQty is reachable
unsigned int mcd = ::mcd(capacities[0], capacities[1]);
if ( targetQty % mcd != 0 ||
// 1.2. verify that targetQty is not more than max capacity of the biggest jug
targetQty > max(capacities[0], capacities[1])) {
printf("The target quantity is not reachable with the available jugs\n");
return;
}
// 2. choose 'service' jug
unsigned int serviceJugIndex;
getServiceJugIndex(capacities, targetQty, serviceJugIndex);
unsigned int otherJugIndex = 1 - serviceJugIndex;
unsigned int finalJugIndex = capacities[0] > capacities[1] ? 0 : 1;
// 3. start fill process
unsigned int currentFilling[2] = {0, 0};
while(currentFilling[finalJugIndex] != targetQty) {
// 3.1 fill with the pump the service jug (if needed)
if(currentFilling[serviceJugIndex] == 0) {
currentFilling[serviceJugIndex] = capacities[serviceJugIndex];
print_step("Filling with the pump the service jug", capacities, currentFilling);
}
// 3.2 fill the other jug using the service one
unsigned int thisTimeFill = min(currentFilling[serviceJugIndex], capacities[otherJugIndex] - currentFilling[otherJugIndex]);
currentFilling[otherJugIndex] += thisTimeFill;
currentFilling[serviceJugIndex] -= thisTimeFill;
print_step("Filling the other jug using the service one", capacities, currentFilling);
// 3.3 check fullness of the other jug and, in case, empty it
if(currentFilling[otherJugIndex] == capacities[otherJugIndex]) {
currentFilling[otherJugIndex] = 0;
print_step("Empty the full jug", capacities, currentFilling);
}
}
printf("Done\n");
}
int main (int argc, char** argv) {
if(argc < 4)
return -1;
unsigned int jugs[] = {atoi(argv[1]), atoi(argv[2])};
unsigned int qty = atoi(argv[3]);
twoJugsResolutor(jugs, qty);
}
Я не знаю, есть ли какая-то математическая концепция в процессе, который я описал, чтобы выбрать правильный кувшин, чтобы минимизировать количество необходимых шагов, я использую его как эвристику.
Надеюсь, это поможет вам.