Logigram (2)

download logigram program
download Delphi-7 project

Dit is een nieuw logigram probleem en een vernieuwd programma.

Probleem

5 personen kopen elk een artikel voor een bepaald bedrag en betalen in maandelijkse termijnen.

personenBoy,Frankie,Marleen,Shirley,Sylvester
artikelenCV-ketel,open haard,computer,televisie,home cinema set
bedragen 2500,2700,3000,3300,3600
termijnen4,5,6,8,9

gegevens
1) Iemand betaalt 500 per maand gedurende 5 maanden
2) Sylvester koopt geen open haard en betaalt in 4 termijnen. De open haard kost 3600.
3) Shirley koopt de TV
4) de home cinema set wordt niet in 9 termijnen betaald
5) Boy's bedrag was niet 3000 en ook niet 3600
6) Frankie kocht geen CV ketel en betaalde 2700 maar niet in 8 termijnen
7) De CV ketel werd in 6 termijnen betaald

Wie kocht welk artikel tegen welke prijs en afschrijvingstermijnen?

Programma

De oplossing wordt gezocht met een Delphi-programma.
Dat ziet er zo uit:



Het algoritme

De personen blijven op hun plaats staan maar per kolom (artikel, bedrag,termijnen)
wijzigt de volgorde van de elementen.
Bij elke volgorde bekijken we of er conflicten zijn.
Zo ja, dan gaan we naar de volgende volgorde, zo nee dan is een oplossing gevonden.

Data formats

Programmeren komt neer op het manipuleren van data. 
 
type Tstring5 =  array[0..4] of string;
     TItem    = record
                  rij : byte;           //plaats in de tabel hierboven
                  kolom : byte;
                 end;
     TgameStatus = (gsBegin,gsZoeken,gsOplossing,gsEinde);
Item levert de coördinaten in de tabel.
De gamestatus geeft aan waar we mee bezig zijn. 
const Spersonen   : Tstring5 =          
                   ('Boy','Frankie','Marleen','Shirley','Sylvester');
      SArtikel    : Tstring5 =
                   ('CVketel','openhaard','computer','televisie','homecinemaset');
      SBedrag     : Tstring5 =
                   ('2500','2700','3000','3300','3600');
      STermijn    : Tstring5 =
                   ('4','5','6','8','9');

      SHeader     : Tstring5 =
                    ('persoon','artikel','prijs','termijnen','');

      cvketel       : TItem = (rij:0; kolom:1);      //plaats in de tabel
      openhaard     : TItem = (rij:1; kolom:1);
      computer      : TItem = (rij:2; kolom:1);
      televisie     : TItem = (rij:3; kolom:1);
      homecinemaset : TItem = (rij:4; kolom:1);
      E2500         : TItem = (rij:0; kolom:2);
      E2700         : TItem = (rij:1; kolom:2);
      E3000         : TItem = (rij:2; kolom:2);
      E3300         : TItem = (rij:3; kolom:2);
      E3600         : TItem = (rij:4; kolom:2);
      Termijn4      : TItem = (rij:0; kolom:3);
      Termijn5      : TItem = (rij:1; kolom:3);
      Termijn6      : TItem = (rij:2; kolom:3);
      Termijn8      : TItem = (rij:3; kolom:3);
      Termijn9      : TItem = (rij:4; kolom:3);

      Boy       = 0;  //persoon = rij 
      Frankie   = 1;
      Marleen   = 2;
      Shirley   = 3;
      Sylvester = 4;
Voorbeelden:
televisie = (1,3); €3000 = (2,2); 9 termijnen = (3,4)

Permutaties

Permutatie is een ander woord voor de volgorde van verschillende elementen.
5 elementen zijn op 5! = 5.4.3.2.1 = 120 verschillende volgorden te leggen.
Aan een permutatie kennen we een rangnummer toe, zodat alle permutaties systematisch
doorlopen kunnen worden door dat rangnummer te verhogen.
De elementen zijn (0,1,2,3,4) en dat is de permutatie met rangnummer 0.
Hier een deel van de lijst met permutaties

rangpermutatie
00,1,2,3,4
10,1,2,4,3
20,1,3,2,4
30,1,3,4,2
.......
1184,3,2,0,1
1194,3,2,1,0

Om overbodig rekenwerk te vermijden maken we eenmalig een lijst met alle permutaties.
Array permutatie[0..4,0..119] bevat de elementen 0..4 in de kolommen en elke rij is een permutatie.



Hierboven staat hoe het berekenen van de permutaties in zijn werk gaat
met als voorbeeld het rangnummer 41.
Tegelijk wordt ook een array[0..4,0..119] Xpermutaties gemaakt, dat aangeeft op welke rij een element staat.
Dus permutatie[3,41] = 2 want het derde element bij rangnummer 41 is de 2.
Xpermutatie[3,41] = 1 want element 3 staat in rij 1.

Merk op, dat 24 = 4! en 6 = 3!, het aantal volgorden van de resterende elementen.

Array Pcount[1..3] of byte zijn de 3 rangnummers van de permutaties in de kolommen 1..3.
Elk rangnummer wijst dus naar een rij van array permutatie of Xpermutatie.

Stel nu dat we tijdens het zoekproces willen weten wie in 9 termijnen afbetaalt.
9 termijnen = (3,4) dus bekijken we het permutatie rangnummer van kolom 3, dat is bv 41.
Permutatie 41 = (1,3,4,2,0) en dan de plaats waar de 4 staat, dat is rij 2.
Dus persoon 2 (Marleen) betaalt in 9 termijnen bij deze permutatie.

De functie Persoon(item) levert bij gegeven stand van de permutatie rangnummers de persoon.
Om te controleren of aan de voorwaarden is voldaan:

(persoon(E2500) = persoon(termijn5))true als bedrag van €2500 in 5 termijnen wordt betaald
(Sylvester <> persoon(openhaard))true als Sylvester de open haard niet kocht
(persoon(E2700) = Frankie)true als Frankie €2700 betaalde

Enzovoorts.

Het zoekproces bestaat uit het systematisch ophogen van de Pcount tellertjes,
van (0,0,0)......(119,119,119)
en te stoppen als ergens aan alle voorwaarden is voldaan.
Overflow van het kolom 3 rangnummer tellertje geeft aan dat er geen oplossing is.
Bij een goede opgave is er slechts 1 oplossing.