Czy tablica spełnia war trojkata

Duke
Użytkownik
Użytkownik
Posty: 267
Rejestracja: 30 kwie 2007, o 21:39
Płeć: Mężczyzna
Lokalizacja: z internetu
Podziękował: 47 razy
Pomógł: 2 razy

Czy tablica spełnia war trojkata

Post autor: Duke »

Witam miałem sprawdzić czy elementy tablicy T spelniaja warunek trojkata, tablica jest losowa. Czy to jest dobrze i czy da się szybciej, a jeśli się da ktoś mógłby to przekształicić?

Kod: Zaznacz cały

program war;
const
n=10;
var
T:array[1..n] of integer;
i,r,druga,trzecia:integer;
tak,wynik:boolean;
begin
   randomize;
   for i:=1 to n do
   begin
     r:=random(10)+1;
     T[i]:=r;
   end;
   for i:=1 to n do
   writeln(T[i]);
   writeln();
//rozwiazanie
i:=1;
druga:=2;
trzecia:=3;
tak:=false;
while i<=n-3 do
begin
druga:=i+1;
trzecia:=i+2;
   while (i<druga) and (druga<trzecia) and (trzecia<=n) do
   begin
     if (abs(druga-trzecia)<i) and (i<druga+trzecia) then
     tak:=true;
     if tak=false then
     wynik:=tak;

     druga:=druga+1;
     trzecia:=trzecia+1;
   end;
   i:=i+1;
end;
   writeln(wynik);






end.
matshadow
Użytkownik
Użytkownik
Posty: 941
Rejestracja: 17 gru 2007, o 21:48
Płeć: Mężczyzna
Lokalizacja: Kingdom Hearts
Podziękował: 6 razy
Pomógł: 222 razy

Czy tablica spełnia war trojkata

Post autor: matshadow »

Nie analizowałem kodu, ale nie wiem po co się bawić w while - wystarczą 3 for'y w sobie

Kod: Zaznacz cały

for(i=1...n-2)
{
      for(j=i+1...n-1)
      {
            for(k=j+1...n)
            {
                    sprawdzanie
            }
      }
}
Czytelniej to wygląda :)
A dwa, jak już zobaczysz, że wynik=false, to przerywasz dalsze działanie, bo nie ma sensu dalej sprawdzać - lepsza złożoność czasowa, choć pesymistycznie i tak koło \(\displaystyle{ n^3}\) :)
ODPOWIEDZ