[Algorytmy] 2 wiaderka

[tomaszek92]

Witam
Mam problem z napisaniem algorytmu do następującego zadania: mamy basen z nieskończoną ilością wody i dwa wiadra o pojemnościach x,y-naturalne. Trzeba napełnić inny basen dokładnie z- naturalne litrami wody. Algorytm ma mówić, czy da się to zrobić dla dowolnych wprowadzonych x,y,z, a jeśli tak to w jaki sposób.
Jedyne co to udało mi się ustalić, że NWD(x,y) musi się równać wielokrotności liczby z.

[Afish]

Poczytaj o rozszerzonym algorytmie Euklidesa.

[daro256]

Proponuję takie rozwiązanie (kod poniżej). Zakładam, że wiadro1 jest większe niż wiadro2. W programie można to łatwo ustalić, a potrzebne jest to aby zacząć od większego wiadra... Zmienne nazywam inaczej niż x,y,z aby było bardziej przejrzyście.

Kod: Zaznacz cały

int wiadro1, wiadro2, basen; // zmienne z pojemnościami
int licznik1 = 0, licznik2 = 0; //liczniki wiader
int pomoc; //zmienna pomocnicza

if(basen%wiadro1==0) // % oznacza dzielenie modulo
  //sprawa zalatwiona pierwszym wiadere
else if(basen%wiadro2==0)
  //sprawa załatwiona drugim wiadrem
else
{
  pomoc = basen-wiadro1; //zaczynamy od większego wiadra
  licznik1++; //zwiekszamy licznik od wiadra1
  while (pomoc > 0)
  {
    if(pomoc%wiadro1==0) //sprawdzamy czy to co zostalo dzieli sie przez poj wiadra1
    {
      pomoc = pomoc - wiadro1;
      licznik1++; //jezeli tak uzywamy wiekszego wiadra i zwiekszamy odpowiedni licznik
    }
    else if(pomoc%wiadro2==0) //to samo co wyzej tylko ze dla mniejszego wiadra
    {
      pomoc = pomoc - wiadro2;
      licznik2++;
    }
    else
    {
      licznik1--;
      break;
 //jezeli powyzsze dwa warunki nie zostaly spelnione oznacza to ze nie da sie zrealizowac zadania za pomoca podanych wiader, wiec przerywamy petle
    }
  }
}

Po zakończeniu działania programu, wartości liczników będą nas informować o tym jak zrealizować zadanie, jeżeli pozostaną one na pozycjach zerowych, tzn. że nie da się zrealizować zadania.
Nie powinno być problemu z przetłumaczeniem programu na schemat blokowy.