B a c k t r a c k i n g

Beispielprogramm 4:   bunte Reihe



PROGRAM  bunte_reihe;  { 15. Bundeswettbewerb Informatik 1996/97
                         1.Aufgabe, Hubert Deitemann, Warendorf, 23.9.1996
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Gegeben sind N Wimpel, die in M verschiedenen Farben gefärbt sind. Jede
Farbe kommt mit einer bestimmten Anzahl vor. Gesucht sind Anordnungen
der Wimpel zu einer Reihe, bei der benachbarte Wimpel unterschiedliche
Farben haben.

Beispiel: N=4, M=2;  jede Farbe kommt 2x vor
          Es gibt zwei Lösungen:  1.   1 2 1 2
                                  2.   2 1 2 1
          Die Reihe  1 1 2 2  ist z.B. keine Lösung

Es soll die Anzahl aller Lösungen bei einer bestimmten Eingabe ausgegeben
werden. Wenn bis zu 10 Lösungen existieren, sollen alle Lösungen ausgegeben
werden; existieren mehr Lösungen, dann nur die ersten 3.

Eingabedaten für ein Beispiel:  N=10, M=5, jede Farbe kommt 2x vor. }

CONST Nmax          = 20;                           {max. Zahl von Wimpeln}
      Mmax          = 10;                           {max. Zahl der Farben}
      Wmax          = 10;                           {max. Zahl Wimpel in einer Farbe }
TYPE  vektortyp     = ARRAY [0..Nmax] OF Integer;   {eine "bunte Reihe"}
      vorratstyp    = ARRAY [1..Mmax] OF Integer;   {Wimpel je Farbe}
      farbentyp     = ARRAY [1..Mmax] OF STRING[10];{Name jeder Farbe}
      loesungtyp    = ARRAY [1..10]   OF vektortyp; {bis zu 10 "Reihen"}
CONST auswahlanfang : Integer = 1;
VAR   auswahlende   : Integer;                      {ist gleich M}
      N             : Integer;                      {Anzahl der Wimpel}
      M             : Integer;                      {Anzahl der Farben}
      zaehler       : longint;                      {Anzahl der Lösungen}
      vorrat        : vorratstyp;                   {Anzahl der Wimpel je Farbe}
      farben        : farbentyp;                    {Name jeder Farbe}
      loesung       : loesungtyp;                   {bis zu 10 "Reihen"}
      vektor        : vektortyp;
      i, j          : Integer;

  PROCEDURE zahlein (VAR zahl: Integer; u,o: Integer; hinw: STRING);
  VAR s: STRING[5];                     {Zahleneingabeprozedur mit}
      c: Integer;                       {  Plausibilitätskontrollen}
  BEGIN
    REPEAT
      Write(hinw);  Readln(s);          {Hinweistext, String einlesen}
      IF s='' THEN c:=1 ELSE Val(s,zahl,c); {String s in Zahl umwandeln}
      IF (c<>0) OR (zahl<u) OR (zahl>o) {keine Zahl, außerhalb Bereich}
         THEN Writeln('Eingabefehler !')
    UNTIL (c=0) AND (zahl>=u) AND (zahl<=o) {bis die Zahl OK ist}
  END;

  { T }
  PROCEDURE try (stufe: Integer; vektor: vektortyp; vorrat: vorratstyp);
  VAR wahl         : Integer;
      neues_optimum: Boolean;
      lebend       : Boolean;
      neuvorrat    : vorratstyp;

    { T.1 }
    PROCEDURE vektor_bewerten;
    BEGIN
      IF vorrat[wahl]<=0       { gewählte Farbe nicht mehr im Vorrat }
        THEN lebend:=FALSE
        ELSE BEGIN
          neuvorrat:=vorrat;
          neuvorrat[wahl]:=neuvorrat[wahl]-1; { vom Farbvorrat entfernen }
          lebend:=(stufe=1) OR (vektor[stufe]<>vektor[stufe-1])
        END;
        neues_optimum:=lebend
    END;

    { T.2 }
    FUNCTION vollstaendig: Boolean;
    BEGIN  vollstaendig := (vektor[0]=N)  END;

    { T.3 }
    PROCEDURE loesung_speichern;
    BEGIN
      zaehler:=zaehler+1;
      IF zaehler<11 THEN loesung[zaehler]:=vektor
    END;

  BEGIN { T }
    FOR wahl:=auswahlanfang TO auswahlende DO
    BEGIN
      vektor[0]:=stufe;           { Stelligkeit setzen }
      vektor[stufe]:=wahl;        { Auswahl Objekt i treffen }
      vektor_bewerten;
      IF vollstaendig
        THEN BEGIN IF neues_optimum THEN  loesung_speichern             END
        ELSE BEGIN IF lebend        THEN  try(stufe+1,vektor,neuvorrat) END
    END
  END;

BEGIN
  { Überschrift und kurze Hinweise, Eingaben }
  Writeln; Writeln ('15.BW Inf., Aufgabe 1, "Bunte Reihe"'); Writeln;
  zahlein (M, 1, Mmax, 'Anzahl der Farben: ');
  auswahlende:=M;
  FOR i := 1 TO M DO
  BEGIN
    Write('Farbe ',i,': ');
    Readln(farben[i])                   {jeden Farbnamen eingeben}
  END; {FOR i}
  N:=0;                                 {wird die Gesamtzahl der Wimpel}
  FOR i := 1 TO M DO
  BEGIN                                 {pro Farbe die Anzahl eingeben}
    zahlein(vorrat[i],1,Wmax,'Anzahl der '+farben[i]+'en Wimpel: ');
    N:=N+vorrat[i];                     {Gesamtzahl inkrementieren}
  END; {FOR i}
  IF N>Nmax THEN                        {zuviele Wimpel ?}
  BEGIN
    Writeln('Obergrenze überschritten, Abbruch!');
    Halt                                {Notausgang}
  END;
  { Initialisierung, Lösungssuche }
  zaehler:=0;
  vektor[0]:=0;
  try (1,vektor,vorrat);
  { Ausgabe }
  Writeln;
  IF zaehler=0 THEN Writeln('Geht nicht !') {keine Lösung}
  ELSE  BEGIN                            {mindestens 1 Lösung}
    IF zaehler>10 THEN
    BEGIN                               {mehr als 10 Lösungen}
      Writeln(zaehler,' Lösungen');     {Anzahl der Lösungen ausgeben}
      Write('Beispiele für ');
      zaehler:=3                        {Zähler auf 3 kappen}
    END; {IF loesanzz>10}
    Writeln('Reihenfolgen:');
    FOR j:=1 TO zaehler DO
    BEGIN
      Write(j:2,'. ');                  {Nummer der Lösung ausgeben}
      FOR i:=1 TO N DO Write(farben[loesung[j][i]],' ');
      Writeln
    END;
  END
END.



HTML-Texte: Münzen 1 Münzen 2 ADT Stack Escher knapsac bunte Reihe salesman HAUPTTEXT
Paket mit Pascal-Dateien laden: BackPac.Zip   (47 K)

zur Informatik-Leitseite


© HMO, Neubearbeitung Januar 1998