logo elektroda
logo elektroda
X
logo elektroda
REKLAMA
REKLAMA
Adblock/uBlockOrigin/AdGuard mogą powodować znikanie niektórych postów z powodu nowej reguły.

Program w C -> z wykorzystaniem algorytmu warshall'a

greenGhost 04 Gru 2005 17:00 2568 5
REKLAMA
  • #1 2053091
    greenGhost
    Poziom 14  
    Posty: 79
    Pomógł: 2
    Witam! Mam niezly problem z napisaniem tego programu i moze jest mi ktos w stanie pomoc, gdyz jestem bardzo raczkujacy jesli chodzi o C, a do napisania mam taki oto program:

    "Sieć komputerowa odporna na zakłócenia. Wszystkie komputery są połączone, choć nie zawsze bezpośrednio. Połączenie krytyczne to takie, którego uszkodzenie powoduje podzielenie sieci na rozłączne części. Napisz program wczytujący plik, w którym każdy wiersz zawiera nazwy dwóch komputerów połączonych bezpośrednio. Program powinien znajdować wszystkie krytyczne połączenia i wypisywać pary nazw komputerów, między którymi połączenie jest krytyczne."

    Z tego co sie dowiadywalem wczesniej nalezaloby skorzystac z algorytmu warshall'a, ale jakos znalezione na Google info niewiele mi mowia :cry:

    Ktos jest w ogole w stanie napiac cos takiego, albo chociaz podpowiedziec jak to powinno wygladac i z czego skorzystac do napisania tego programu?

    Z gory wielkie dzieki!
  • REKLAMA
  • #2 2056755
    stepowicz
    Poziom 17  
    Posty: 160
    Pomógł: 18
    Jeśli chodzi o algorytm Roy-Warshalla to jego prostą implementacje skladajaca sie tylko z trzech petli iteracyjnych i drobnych operacji znajdziesz w ksiązce "Algorytmy struktury danych i techniki programowania" Piotr Wróblewski strona: 252.
    Zostanie ci tylko do przygotowania macierz wejsciowa i wyjsciowa.

    Przykladowe podobne zadania znajdziesz w skryptach z OI.
    http://www.oi.edu.pl/
  • REKLAMA
  • #3 2057492
    greenGhost
    Poziom 14  
    Posty: 79
    Pomógł: 2
    A mialbys moze gdzies pod reka (na dysku) wyciag z tej ksiazeczki?
    Bo mnie niestety troche pili z tym problemem, a zanim te ksiazeczke dorwe w swoje lapy, to chwila minie :cry:

    I jeszcze pytanie: Jak przygotowac te macierz wejsciowa i wyjsciowa?
    Bo jestem totalnie zielony w programowaniu i nie kumam jak to w ogole zrobic...

    EDIT:

    Plik wejsciowy wyglada nastepujaco:

    1-2
    2-4
    5-3
    1-6
    2-5
    5-6

    Wiec teraz problem sie sprowadza do tego jak wczytac dane z pliku, przepisac je do tablicy dwu wymiarowej.

    Moglbys to wytlumaczyc jak dla debila? :|
  • REKLAMA
  • REKLAMA
  • #5 2062667
    greenGhost
    Poziom 14  
    Posty: 79
    Pomógł: 2
    Dzieki za gotowca. Mogloby w nim byc troche wiecej komentarzy, bo niewiele z niego rozumiem :| A byloby dobrze gdybym rozumial, bo chcialbym sie tego nauczyc... Moglby mi ktos wyjasnic chociaz te czesc z matrycami z kodu tego programu?
  • #6 2072910
    greenGhost
    Poziom 14  
    Posty: 79
    Pomógł: 2
    Oka, to poprawnie dzialajacy program powinien wygladac tak:

    
    #include <stdio.h>
    #include <stdlib.h>
    
    #define M 20
    
    int G[M][M], V[M], max=0;
    
    
    
    
    int warshall(int g[M][M])
    {
    int x,y,z,pom=0, H[M][M];
    
    for (x=0; x<M; x++)
      for (y=0; y<M; y++)
        H[x][y] = g[x][y];
                  
                       for (x=1; x<=max; x++)
                        for (y=1; y<=max; y++)
                        {
                            for (z=1; z<=max; z++)
                              if (H[y][z] == 0)
                               {
                                   if((H[y][z]=H[y][x] * H[x][z]) == 1)
                                   {
                                       pom= 0;     
                                   }
                                   else{
                                       pom=1;
                                   }
                                }                           
                        }
                   
    return pom;                         
    }
    
    void zwiedzaj(int g[M][M], int v[M], int i)
    {
       int k;
       v[i]=1; // zaznaczamy wiercholek jako "zbadany"
       
        for ( k = 1; k <= max; k++ )
            if ( g[i][k] != 0 && i != k)
            { 
            /* istnieje przejscie */
                if ( v[k] == 0 ){
                   g[i][k]=0;g[k][i]=0;
                   if (warshall(g) == 1)
                       printf("polaczenie krytyczne %d %d\n", i, k);
                   g[i][k]=1;g[k][i]=1; 
      
                }
            }   
    }
    
    
    void szukaj(int g[M][M], int v[M])
    {
     int i;
     for (i=0; i<max; i++){
         v[i]=0;
        zwiedzaj(g,v,i);
     }    
    }  
    
    
    
    
    int main()
    {   
        int a,b;
        FILE *fp;
    
       /* sprawdzenie czy plik istnieje i czy mozna go otworzyc do czytania */
     
       if ( (fp=fopen("polaczenia.txt","r")) == NULL )
            printf("Nie mozna otworzyc pliku\n");
       else
           {
       /* czytanie danych z pliku do momentu napotkania konca pliku */
    
           while (fscanf(fp,"%d %d", &a, &b) > 0)
              {                        
                  printf("%d %d\n", a,b);
                  G[a][b]=1;
                  G[b][a]=1;
                  if ( a > max)
                     max=a;
                  if ( b > max)
                     max=b;
                  a=b=0;	      
              }
           }
    
    szukaj(G,V);
    
    return 0;
    }
    
    


    Moze sie jeszcze komus przyda ta ciezka praca :)

    Dzieki za pomoc!
REKLAMA