kodovi/MaxNiza.MOD

   1 MODULE MaxNiza;
   2 FROM InOut IMPORT WriteString,ReadString,
   3            WriteInt,WriteCard,WriteLn;
   4 FROM FIO IMPORT File, Open, Close, RdInt,EOF;
   5 FROM Str IMPORT Length;
   6
   7 CONST
   8   MaxN = 100;
   9 TYPE
  10   Interval = [1..MaxN];
  11 VAR
  12   X : ARRAY Interval OF INTEGER;
  13   f: File;
  14   N:CARDINAL;
  15   ime : ARRAY [1..50] OF CHAR;
  16
  17 PROCEDURE MaxNiza3();
  18 (* Trece resenje: O(n^2).
  19    Koristi pomocni niz u kome je na i-tom mestu
  20    suma podniza x[1..i] *)
  21 VAR
  22   Max, Suma : INTEGER;
  23   d,g,i,Ood,Doo : Interval;
  24   Pom : ARRAY [0..MaxN] OF INTEGER;
  25   brojOp : CARDINAL;
  26 BEGIN
  27   brojOp := 0;
  28   Pom[0] := 0;
  29   Ood := 1;
  30   Doo := 1;
  31   FOR i := 1 TO N DO
  32     Pom[i] := Pom[i-1] + X[i];
  33     INC(brojOp);
  34   END;
  35   Max := 0;
  36   FOR d := 1 TO N DO
  37     FOR g := d TO N DO
  38       Suma := Pom[g] - Pom[d-1];
  39       INC(brojOp);
  40       IF Suma > Max THEN
  41         Max := Suma;
  42         Ood := d;
  43         Doo := g
  44       END
  45     END
  46   END;
  47   WriteLn;
  48   WriteString(' Maksimum je ');
  49   WriteInt(Max,3);
  50   WriteString(' u intervalu od ');
  51   WriteCard(Ood,3);
  52   WriteString(' do ');
  53   WriteCard(Doo,3);
  54   WriteLn;
  55   WriteString('Broj racunskih operacija: ');
  56   WriteCard(brojOp,1);
  57   WriteLn;
  58 END MaxNiza3;
  59
  60 PROCEDURE MaxNiza4();
  61 (* Cetvrto resenje. Najbolje moguce: O(n)  *)
  62 VAR
  63   Max, MaxDovde : INTEGER;
  64   i,d,Ood,Doo : Interval;
  65   brojOp : CARDINAL;
  66 BEGIN
  67   Ood := 1;
  68   Doo := 1;
  69   brojOp := 0;
  70   d := 1;
  71   Max := 0;
  72   MaxDovde := 0;
  73   FOR i := 1 TO N DO
  74     IF MaxDovde = 0 THEN
  75       d := i
  76     END;
  77     MaxDovde := MaxDovde + X[i];
  78     INC(brojOp);
  79     IF MaxDovde < 0 THEN
  80       MaxDovde := 0
  81     END;
  82     IF MaxDovde > Max THEN
  83       Ood := d;
  84       Doo := i;
  85       Max := MaxDovde
  86     END
  87   END;
  88   WriteLn;
  89   WriteString(' Maksimum je ');
  90   WriteInt(Max,3);
  91   WriteString(' u intervalu od ');
  92   WriteCard(Ood,3);
  93   WriteString(' do ');
  94   WriteCard(Doo,3);
  95   WriteLn;
  96   WriteString('Broj racunskih operacija: ');
  97   WriteCard(brojOp,1);
  98   WriteLn;
  99 END MaxNiza4;
 100
 101 BEGIN
 102   WriteString('ime fajla?');
 103   ReadString(ime);
 104   IF Length(ime)= 0 THEN
 105     ime := 'br1.txt';
 106   END;
 107   WriteString(' Unos niza X ');
 108   WriteLn;
 109   f := Open(ime);
 110   N:=0;
 111   EOF:=FALSE;
 112   WHILE NOT EOF DO
 113     INC(N);
 114     X[N] := RdInt(f);
 115     WriteCard(N,1);
 116     WriteString(' - ');
 117     WriteInt(X[N],1);
 118     WriteLn;
 119   END;
 120   Close(f);
 121   WriteString("metod 3");
 122   MaxNiza3();
 123   WriteString("metod 4");
 124   MaxNiza4();
 125 END MaxNiza.