04. N brojeva/kod/NBROJEVA.MOD

   1 MODULE NBrojeva;
   2
   3   FROM IO IMPORT
   4     WrLn, WrCard, RdCard, WrStr;
   5
   6   CONST
   7     MaxNiz = 50;
   8     MaxSuma = 500;
   9
  10   VAR
  11     n, Suma, SumaPola: CARDINAL;
  12     Broj: ARRAY [1 .. MaxNiz] OF CARDINAL;
  13     Iskor: ARRAY[1 .. MaxNiz] OF BOOLEAN;
  14     Mat: ARRAY[0 .. MaxSuma], [0 .. MaxNiz] OF CARDINAL;
  15    (*   Mat[i, j] je suma brojeva u resenju ako je maksimalna *)
  16    (* dozvoljena suma brojeva u resenju jednaka 'i' i ako se  *)
  17    (* koristi samo prvih 'j' brojeva.                         *)
  18
  19   PROCEDURE Unos;
  20     VAR
  21       i: CARDINAL;
  22   BEGIN
  23     WrStr('Unesite n: ');
  24     n:= RdCard();
  25     Suma:= 0;
  26     FOR i:= 1 TO n DO
  27       WrStr('Unesite ');
  28       WrCard(i, 1);
  29       WrStr('. broj: ');
  30       Broj[i]:= RdCard();
  31       Suma:= Suma + Broj[i];
  32       Iskor[i]:= FALSE;
  33     END;
  34     SumaPola:= Suma DIV 2;
  35   END Unos;
  36
  37   PROCEDURE Resi;
  38     VAR
  39       i, j, Pom: CARDINAL;
  40   BEGIN
  41     FOR i:= 0 TO SumaPola DO
  42       Mat[i, 0]:= 0;  (* Koristi se prvih 0 brojeva *)
  43     END;
  44     FOR j:= 1 TO n DO
  45       Mat[0, j]:= 0;  (* Maksimalna dozvoljena suma brojeva u resenju je 0 *)
  46     END;
  47     FOR i:= 1 TO SumaPola DO
  48       (* Maks. dozvoljena suma brojeva u resenju je i *)
  49       FOR j := 1 TO n DO
  50         (* U resenju mogu ucestvovati prvih j brojeva *)
  51         Mat[i, j]:= Mat[i, j - 1];
  52         IF Broj[j] <= i THEN
  53           Pom:= Mat[i - Broj[j], j - 1] + Broj[j];
  54           IF Pom > Mat[i, j] THEN
  55             Mat[i, j]:= Pom;
  56           END;
  57         END;
  58       END;
  59     END;
  60   END Resi;
  61
  62   PROCEDURE IspisiPrvu;
  63     VAR
  64       i, j: CARDINAL;
  65   BEGIN
  66     WrStr('Zbir prve grupe brojeva je ');
  67     WrCard(Mat[SumaPola, n], 1);
  68     WrLn;
  69     WrStr('Prvu grupu brojeva cine brojevi:');
  70     WrLn;
  71     i:= SumaPola;
  72     j:= n;
  73     REPEAT
  74       WHILE (j > 0) AND (Mat[i, j] = Mat[i, j - 1]) DO
  75         DEC(j);
  76       END;
  77       IF j > 0 THEN
  78         WrCard(Broj[j], 8);
  79         Iskor[j]:= TRUE;
  80         i:= i - Broj[j];
  81         DEC(j);
  82       END;
  83     UNTIL j = 0;
  84   END IspisiPrvu;
  85
  86   PROCEDURE IspisiDrugu;
  87     VAR
  88       i, j: CARDINAL;
  89   BEGIN
  90     WrLn;
  91     WrStr('Zbir druge grupe brojeva je ');
  92     WrCard(Suma - Mat[SumaPola, n], 1);
  93     WrLn;
  94     WrStr('Drugu grupu brojeva cine brojevi:');
  95     WrLn;
  96     FOR i := 1 TO n DO
  97       IF NOT Iskor[i] THEN
  98         WrCard(Broj[i], 8);
  99       END;
 100     END;
 101   END IspisiDrugu;
 102
 103 BEGIN
 104   Unos;
 105   IF SumaPola > MaxSuma THEN
 106     WrStr('Ulazni podaci su suvise veliki.');
 107   ELSE
 108     Resi;
 109     IspisiPrvu;
 110     IspisiDrugu;
 111   END;
 112 END NBrojeva.