Mamy pięć monet A, B, C, D, E, których ciężary są parami różne. Dysponując bardzo czułą wagą szalkową, pozwalającą porównać ze sobą ciężary dwóch monet, uszereguj je od najlżejszej do najcięższej. Waga jest delikatnym i kosztownym urządzeniem. Pierwszych siedem porównań możemy wykonać za darmo. Ósme kosztuje 1 złoty, a każde następne porównanie jest 125 razy droższe od poprzedniego. Decyzję o tym, które porównanie wykonać w danej chwili, możemy podejmować w zależności od wyników poprzednich pomiarów. Zaprojektuj algorytm sortujący monety, tak aby koszt ważenia był jak najmniejszy.

Zadanie

Pascal

Kod źródłowy programu jest zapisany w następujących plikach:
UMONETA.PAS - definicja typu Tmoneta,
UWAGA.PAS - funkcja lzejsza i procedura wynik,
USORT.PAS - miejsce na Twoje rozwiązanie,
MONETY.PAS - główna część programu

Procedura sortujMonety powinna korzystać z typu TMoneta, zdefiniowanego w pliku UMONETA.PAS:

unit UMoneta;
interface
   type
      TMoneta = (A, B, C, D, E);
   {Z pozostałych deklaracji, zawartych w tym pliku, korzystać nie wolno.}
implementation
   {...}

unit UWaga;
interface
   uses UMoneta;
   function lzejsza(m1,m2:TMoneta):boolean;
   {Przyjmuje wartość true jeśli moneta m1 jest lżejsza od monety m2, w przeciwnym
    przypadku przyjmuje wartość false.}
   procedure wynik(m1,m2,m3,m4,m5:TMoneta);
   {Gdy monety zostaną już uszeregowane od najlżejszej do najcięższej, należy wywołać
    procedurę wynik . Parametry m1, m2, m3, m4, m5 oznaczają monety uszeregowane od
    najlżejszej do najcięższej. Zwróć uwagę, że ta procedura musi być wywołana dokładnie
    jeden raz w trakcie działania sortujMonety.}
implementation
   {...}

unit USort;
interface
   uses UMoneta,UWaga;
   procedure sortujMonety;
implementation
   {Poniżej jest miejsce na kod Twojego rozwiązania. Typy, zmienne, 
    funkcje oraz procedury, które zadeklarujesz muszą być lokalne 
    dla tego modułu.}
   procedure sortujMonety;
   begin
   end;

Język C

Kod źródłowy programu jest zapisany w następujących plikach: UMONETA.H, UMONETA.C - definicja typu: Tmoneta,
UWAGA.H, UWAGA.C - funkcja lzejsza i procedura wynik,
USORT.H, USORT.C - miejsce na Twoje rozwiązanie,
MONETY.C - główna część programu

Procedura sortujMonety powinna korzystać z typu TMoneta, zdefiniowanego w pliku UMONETA.H:

typedef enum {A, B, C, D, E} TMoneta;

/* Z pozostałych deklaracji, zawartych w tym pliku, korzystać nie wolno. */

extern int lzejsza (TMoneta m1, TMoneta m2);
   /* Przyjmuje wartość 1 (prawda) jeśli moneta m1 jest lżejsza od monety m2, w
      przeciwnym przypadku przyjmuje wartość 0 (fałsz). */

extern void wynik (TMoneta m1, TMoneta m2, TMoneta m3, TMoneta m4, TMoneta m5);
   /* Gdy monety zostaną już uszeregowane od najlżejszej do najcięższej, należy wywołać
      procedurę wynik . Parametry m1, m2, m3, m4, m5 oznaczają monety uszeregowane od
      najlżejszej do najcięższej. Zwróć uwagę, że ta procedura musi być wywołana  dokładnie
      jeden raz w trakcie działania sortujMonety. */

#include "usort.h"

/* Tu mogą być umieszczone zmienne i funkcje pomocnicze */
void sortujMonety()
{
/* To jest miejsce na twoje rozwiązanie */
/* Można wywołać tylko funkcje lzejsza(...) i wynik(...) 
   oraz własne funkcje z tego modułu. */
}