[pascal] grafy :/

[noose]

witam :]

mam taka mala sprawe :]

mam zadanie na infe.... potrzebuje zrobic program ktory bedzie liczyl ile potrzeba torow kolejowych zeby polaczyc wszystkie miasta ze soba.... (tzn ma wybierac najtansze polaczenie :]). jezeli komus cos to mowi, to ma to byc 'zachlanny algorytm'....

 

napisalem takie cos, ale nie robi tego co powinien :( zaznacze w kodzie kawalek przez ktory robi sie ciekawa rzecz ;]

 

program kolejarz; uses crt;  const max = 20;  type t_miasta = array [1..max,1..max] of integer;   var i,j,n:integer;       miasta:t_miasta;         { Miasta }       gotowiec:t_miasta;       { Gotowa tablica } procedure ustaw (var miasta:t_miasta;n:integer);   var i,j:integer;    begin     for i:=1 to n do      for j:=1 to n do       miasta[i,j]:=random(255);   end;  procedure sprawdz(miasta:t_miasta;n:integer;var gotowiec:t_miasta);  var i,j:integer;      min,min_i,min_j:integer;      temp:t_miasta;   begin    for i:=1 to n do                             {TUTAJ JEST PROBLEM}     for j:=1 to n do      temp[i,j] := 0;[/b]                       {KONCZY SIE TUTAJ}    min := 255;    for i:=1 to n do     begin      for j:=1 to n do       begin        if miasta[i,j] < min then         begin          min := miasta[i,j];          min_i := i;          min_j := j;         end;        end;     temp[min_i,min_j]:=min;    end;   gotowiec:=temp;   end;  procedure wypisz(gotowiec:t_miasta;n:integer);   var i,j:integer;   begin    for i:=1 to n do     for j:=1 to n do      if (gotowiec[i,j] <> 0) then writeln('Polaczenie miedzy ',i,' oraz ',j,': ',gotowiec[i,j]);   end; { GťŕWNA CZ¨—Ź PROGRAMU }  begin   clrscr;   writeln('Podaj ilo˜† miast: ');   readln(n);   ustaw(miasta,n);    for i:=1 to n do      for j:=1 to n do      if (j = i) then miasta[i,j] := 0 else       if ((i <> j) AND (miasta[i,j] <> miasta[j,i]) AND (miasta[i,j] <> 0)) then        begin         writeln('Podaj odleglosc z miasta ',i,' do miasta ',j,': ');         readln(miasta[i,j]);         miasta[j,i] := miasta[i,j];        end;  for i:=1 to n do   begin    for j:=1 to n do     write(miasta[i,j]:4);    writeln;   end;   readkey;   clrscr;   writeln('Sprawdzanie miast...');   sprawdz(miasta,n,gotowiec);   writeln('Wypisanie:');   wypisz(gotowiec,n);   readkey;  end.

problem jest taki... jezeli nie bedzie tych 3 linijek to tablica gotowiec (a raczej temp, a potem gotowiec :P) zalepnia sie losowymi liczbami.... jezeli zrobie tamto to w ogole nie zwraca mi tablicy gotowiec :?

bede wdzieczny za wszelkie wskazowki dot poprawienia tego progsa....

 

pozdro :)

[spicum]

...CIACH...

  min := 255;              {1}    for i:=1 to n do      begin       for j:=1 to n do        begin         if miasta[i,j] < min then  {2}         begin           min := miasta[i,j];           min_i := i;           min_j := j;          end;         end;      temp[min_i,min_j]:=min;   {3}    end;    gotowiec:=temp;                 {4}

...CIACH...

 

 procedure wypisz(gotowiec:t_miasta;n:integer);    var i,j:integer;    begin     for i:=1 to n do      for j:=1 to n do       if (gotowiec[i,j] <> 0) then writeln('Polaczenie miedzy ',i,'  oraz ',j,': ',gotowiec[i,j]);          {5}   end;

Po koleji. Zerowanie tablicy temp jest jak najbardziej na miejscu. Te losowe smieci pojawiaja sie z tego ze kompilator ktorego uzywasz nie zeruje tablic przy inicjalizacji.

 

Patrzac na kod wypiski {5} mozna stwierdzic ze wypisze tylko wartosci niezerowe.

W {2} masz jak byk gwarancje ze do minimum wpiszesz zawsze 0 :!: patrz odleglosc miasta do niego samego (i=j) jest rowna 0 :!:

 

czyli {2}

if miasta[i,j] < min then  

:arrow:

if (i <> j) and (miasta[i,j] < min) then  

dalej idac w {3} przepisujesz min ktore jest ustawiane na 255 w {1} czyli poza obiema petlami :!: co powoduje ze jesli pod min znajdzie sie za pierwszym podejsciem najmniejsza odleglosc miedzy dowolnymi dwoma miastami to ta wartosc przepisze tylko raz (patrz wpisze sie n razy ale pod te same i , j). Czyli kawalek

min := 255;              {1}    for i:=1 to n do      begin       for j:=1 to n do        begin

:arrow:

   for i:=1 to n do      begin      min := 255;      for j:=1 to n do        begin

i dopiero teraz uzycie gotowiec {5} bedzie uzasadnione

 

Przerob kod wg wskazowek i zobacz czy o to Ci chodzilo :ploom:

 

UPDATE

Ciekawe - jeszcze niektore servery fpc maja :)

[noose]

dzieki :] dziala :]

jeszcze drobna poprawka i wrzuce tutaj rozwiazanie, zeby kazdy mogl sie pobawic grafami :]

 

edit: no prawie dziala :] nie chodzi jeszcze taka rzecz, ze kazde miasto powinno miec polaczenie z kazdym innym.... oraz jest taki problem ze jak wypisuje ostatnie polaczenie to pisze, ze ma wartosc 255 :?

 

program kolejarz; uses crt;  const max = 20;  type t_miasta = array [1..max,1..max] of integer;       t_miasta_b = array [1..max] of boolean;   var i,j,n:integer;       miasta:t_miasta;         { Miasta }       gotowiec:t_miasta;       { Gotowa tablica }       polaczenia:t_miasta_b; procedure ustaw (var miasta:t_miasta;n:integer);   var i,j:integer;    begin     for i:=1 to n do      for j:=1 to n do       miasta[i,j]:=random(255);   end;  procedure sprawdz(miasta:t_miasta;n:integer;var gotowiec:t_miasta);  var i,j:integer;      min,min_i,min_j:integer;      temp:t_miasta;   begin    for i:=1 to n do     for j:=1 to n do      begin       temp[i,j] := 0;       polaczenia[i]:=false;      end;    for i:=1 to n do     begin      min := 255;      for j:=1 to n do       begin        if ((miasta[i,j] < min) AND (miasta[i,j] <> 0) AND (polaczenia[i] = false) AND (polaczenia[j] = false)) then         begin          min := miasta[i,j];          min_i := i;          min_j := j;         end;        end;     temp[min_i,min_j]:=min;     polaczenia[i] := true;    end;   gotowiec:=temp;   end;  procedure wypisz(gotowiec:t_miasta;n:integer);   var i,j:integer;   begin    for i:=1 to n do     for j:=1 to n do      if (gotowiec[i,j] <> 0) then writeln('Polaczenie miedzy ',i,' oraz ',j,': ',gotowiec[i,j]);   end; { GťŕWNA CZ¨—Ź PROGRAMU }  begin   clrscr;   writeln('Podaj ilo˜† miast: ');   readln(n);   ustaw(miasta,n);    for i:=1 to n do      for j:=1 to n do      if (j = i) then miasta[i,j] := 0 else       if ((i <> j) AND (miasta[i,j] <> miasta[j,i]) AND (miasta[i,j] <> 0)) then        begin         writeln('Podaj odleglosc z miasta ',i,' do miasta ',j,': ');         readln(miasta[i,j]);         miasta[j,i] := miasta[i,j];        end;  for i:=1 to n do   begin    for j:=1 to n do     write(miasta[i,j]:4);    writeln;   end;   readkey;   clrscr;   writeln('Sprawdzanie miast...');   sprawdz(miasta,n,gotowiec);   writeln('Wypisanie:');   wypisz(gotowiec,n);   writeln;   writeln('Koniec programu');   readkey;  end.

[noose]

Ok jest rozwiazanie :]

programik od razu rysuje te grafy (moze nie w jakis cudowny sposob, ale rysuje :P)

 

program kolejarz; uses crt,graph;  const max = 20;  type t_miasta = array [1..max,1..max] of integer;       t_miasta_b = array [1..max] of byte;       t_wsp = array [1..max] of record                                       x,y:integer;                                 end;   var i,j,n:integer;       miasta:t_miasta;         { Miasta }       gotowiec:t_miasta;       { Gotowa tablica }       polaczenia:t_miasta_b; procedure ustaw (var miasta:t_miasta;n:integer);   var i,j:integer;    begin     for i:=1 to n do      for j:=1 to n do       miasta[i,j]:=random(255);   end;  procedure sprawdz(miasta:t_miasta;n:integer;var gotowiec:t_miasta; varpolaczenia:t_miasta_b);  var i,j:integer;      min,min_i,min_j:integer;      temp:t_miasta;   begin    for i:=1 to n do     for j:=1 to n do      begin       temp[i,j] := 0;       polaczenia[i]:=0;      end;    for i:=1 to n-1 do     begin      min := 255;      for j:=1+i to n do       begin        if ((miasta[i,j] < min) AND (miasta[i,j] <> 0) AND (polaczenia[i] = 0) AND(polaczenia[i+1] = 0)) then         begin          min := miasta[i,j];          min_i := i;          min_j := j;         end;        end;     temp[min_i,min_j]:=min;     polaczenia[min_i] := 1;    end;   gotowiec:=temp;   end;  procedure wypisz(gotowiec:t_miasta;n:integer);   var i,j:integer;   begin    for i:=1 to n do     for j:=1 to n do      if (gotowiec[i,j] <> 0) then writeln('Polaczenie miedzy ',i,' oraz ',j,':',gotowiec[i,j]);   end;  procedure rysuj(gotowiec:t_miasta;n:integer);   var i,j,karta,tryb:integer;       ekran:t_wsp;       t:string;   begin    karta:=detect;    initgraph(karta,tryb,'c:tpbgi');    for i:=1 to n do     begin      ekran[i].x:=random(getmaxx);      ekran[i].y:=random(getmaxy);     end;    for i:=1 to n do     begin      putpixel(ekran[i].x,ekran[i].y,red);      str(i,t);      outtextXY(ekran[i].x-2,ekran[i].y+2,t);     end;    for i:=1 to n do     for j:=1 to n do      begin       if (gotowiec[i,j] <> 0) then line(ekran[i].x,ekran[i].y,ekran[j].x,ekran[j].y);      end;    readkey;    closegraph;   end; { G�ŕWNA CZ¨�� PROGRAMU }  begin   clrscr;   writeln('Podaj ilo�� miast: ');   readln(n);   ustaw(miasta,n);    for i:=1 to n do      for j:=1 to n do      if (j = i) then miasta[i,j] := 0 else       if ((i <> j) AND (miasta[i,j] <> miasta[j,i]) AND (miasta[i,j] <> 0)) then        begin         writeln('Podaj odleglosc z miasta ',i,' do miasta ',j,': ');         readln(miasta[i,j]);         miasta[j,i] := miasta[i,j];        end;  for i:=1 to n do   begin    for j:=1 to n do     write(miasta[i,j]:4);    writeln;   end;   readkey;   clrscr;   writeln('Sprawdzanie miast...');   sprawdz(miasta,n,gotowiec,polaczenia);   writeln('Koniec');   writeln('Wypisanie:');   wypisz(gotowiec,n);   readln;   rysuj(gotowiec,n);   writeln('Koniec programu');   writeln("Napisał go Noose');   writeln('Wszelkie uwagi kierować na noose@tweak.pl');   readkey;  end.