La résolution de la cruche d'eau problème

Strictement pour 2 Cruche Problème

Q = A * x + B * y

Q = Litres dont vous avez besoin.

Remarque: Le Q doit être un multiple de Pgcd(A,B) sinon, il n'y a pas de solution. Si Pgcd(A,B) == 1, Il existe une solution pour Tout Q.

1) Méthode 1 :
Étendue d'Euclide l'Algorithme permettra de résoudre plus rapidement que n'importe quel Algorithme Graphique.

2) Méthode 2:
Voici un Approche Naïve. (à noter que cela peut jeter 2 solutions, Vous aurez à choisir ce qui est plus court)

Le Problème en question peut être simplement résolu par repeatedly de Remplissage d'un seau Un à l'autre seau B (l'ordre n'importe pas) jusqu'à ce qu'il se remplit avec le montant que vous voulez...ofcoz, lorsqu'un seau fillsup, videz-la et continuez.

    A = 3, B = 4 and Q = 2

À plusieurs reprises Remplir Un->B

    A B
   ######
    0 0
    4 0
    1 3
    1 0
    0 1
    4 1
    2 3 <-Solution

Permet d'essayer et observer ce qui se passe si nous allons dans l'autre sens,
Remplissez B->Un

A  B
#####
0  0
0  3
3  0
3  3
4  2 <- Solution

Dans ce cas de remplissage B->Un nous donne l'objectif de l'état plus vite qu'Un->B

Générique N Cruches
Voici une intéressante papier

OriginalL'auteur st0le

Ce type de problème est souvent prête à la programmation dynamique techniques. J'ai ofetn vu ce problème spécifique utilisé comme exemple dans les opérations de recherche en cours. Une belle étape-par-étape, la description est ici.

OriginalL'auteur mtnygard

J'ai rencontré ce problème lors d'un de mes études. Comme vous, et comme st0le dit ici, j'ai trouvé comme réponse au problème de l'algorithme d'Euclide Étendu. Mais cette réponse ne satisfait pas moi, parce que je pense que c'est une réponse quantitative, pas une qualitatif (qui est, l'algorithme ne permet pas de dire ce que l'étape à franchir pour atteindre le résultat).

Je crois que j'ai trouvé une autre solution au problème qui est toujours d'atteindre le résultat avec le nombre minimum d'étapes.

Ici, il est:

1. Problème de vérification de la faisabilité:
   • Q est un multiple de la base de données CENTRALE(A,B);
   • Q <= max(A,B).

2. Choisir le service à la cruche (qui est, celui qui vous permettra de la remplir à la pompe). En supposant que A > B (vous pouvez trouver facilement la cruche qui est le plus grand):

   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
   

3. démarrer le processus de remplissage:

   • remplir avec la pompe, le service à la cruche (si vide)

   • remplir l'autre cruche à l'aide de la service un

   • vérifier la plénitude de l'autre cruche et, dans le cas où, le vide

   • arrêter lorsque la plus grande cruche contient Q

Ci-dessous vous trouverez une très naïve de la mise en œuvre de l'algorithme en c++. Hésitez pas à le réutiliser, ou d'améliorer ce que vous avez besoin.

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

Je ne sais pas si il y a de tout concept mathématique derrière le processus que j'ai décrit pour choisir la bonne cruche de réduire le nombre d'étapes nécessaires, je l'utilise comme une heuristique.

J'espère que cela peut vous aider.

OriginalL'auteur iluke