Przypisanie elementow tablicy jako wspolrzedne oraz obliczenie odleglosci miedzy miastami.

Odpowiedz Nowy wątek
2011-08-10 16:19
0

Witam.

Pisze do Was z prosba o pomoc w rozwiazaniu problemu polegajacego na przypisaniu okreslonych indeksow tablicy jako wspolrzedne x i y, ktore wczesniej odczytalem z pliku. Nastepnie musze obliczyc odleglosc miedzy punktami(miastami). Posiadam takze macierz sasiedztwa, aby wiedziec ktore miasto ma sasiada.

Na poczatku przedstawie pliki i kody zrodlowe, a wtedy moj problem bedzie lepiej zobrazowany.

Plik wspolrzedne.txt - odpowiednio wsp. x oraz y. Liczba wierszy = liczba miast.

12
58
27
41
35 

Program odczytujacy z pliku wspolrzedne.txt liczby i zapisujacy je do tablicy.

 
#include <iostream>
#include <fstream>
 
using namespace std;
string wiersze; // zmienna globalna z iloscia wierszy dostepna dla poszczegolnych funkcji.
 
typedef  struct {
    int x,y;
} TPoint;
 
int zlicz(const string &wspolrzedne) // zlicza ilosc wierszy = ilosc miast.
{
  char wiersz[50];
  // string wiersz;
   int liczba_wierszy = 0;
        ifstream plik("wspolrzedne.txt");
        if (plik.fail())
         {
                cout << "Pliku nie mozna otworzyc" << endl;
        }
        while  (! plik.eof())
        {
          plik.getline(wiersz,sizeof(wiersz)); //metoda getline czytajaca z otwartego pliku cały wiersz
                                                          //i ładujaca go do tablicy znakowej o nazwie wiersz.
          liczba_wierszy++;
        }
    cout << "Liczba wierszy w tekscie: " << liczba_wierszy << endl;
    wiersze = liczba_wierszy;
    plik.close();
}
 
int main (void)
{
    zlicz("wspolrzedne.txt");
 
    /* Odczyt wspolrzednych z pliku*/
    ifstream plik("wspolrzedne.txt");
    if (!plik.is_open())
    throw-1;
    char tablica[100];
    for (int i=0; i<100; i++)
     {
        plik >> tablica[i];
     }
    for (int i=0; tablica[i]!=NULL; i++)
     {
       cout << tablica[i] << tablica[i+1] << endl;
       i++;
     }
return 0;
}

Oczywiscie ilosc wierszy(miast) ma byc elastyczna. Czyli moze sie zmieniac.
Dlatego nie da sie na sztywno przypisac konkretnych indeksow tablicy do wspolrzednych konkretnego miasta.

Plik macierz_sasiedztwa.txt

01010
10011
00011
11101
01110 

Program odczytujacy macierz z pliku i zapisujacy ja do tablicy dwuwymiarowej.

#include <iostream>
#include <fstream>
#include <string>
 
using namespace std;
const int VMAX=32;
typedef bool Matrix[VMAX+1][VMAX+1];
int licznik=0;
int wiersze =0;
 
int zlicz(const string &macierz_sasiedztwa)
{
  char wiersz[30];
  // string wiersz;
   int liczba_wierszy = 0;
        ifstream plik("macierz_sasiedztwa.txt");
        if (plik.fail()) {
                cout << "Pliku nie mozna otworzyc" << endl;
        }
        while  (! plik.eof())  {
      plik.getline(wiersz,sizeof(wiersz)); //metoda getline czytajaca z otwartego pliku cały wiersz
                                                          //i ładujaca go do tablicy znakowej o nazwie wiersz
//         plik.getline(sizeof(wiersz));
          liczba_wierszy++;
   }
 
   cout << "Liczba wierszy w tekscie: " << liczba_wierszy << endl;
   wiersze = liczba_wierszy;
        plik.close();
}
 
bool readMatrix(const string &macierz_sasiedztwa, Matrix &matrix)
{
  string line,wiersz;
  ifstream fp("macierz_sasiedztwa.txt");
   if (!fp)
   {
       cout<<"Nie moge otworzyc' pliku "<<macierz_sasiedztwa<<" do odczytu!"<<endl;
       return false;
   }
 
    for (int i=0;i <wiersze  ;i++)
    {
      if (!getline(fp,line) || line.length() < wiersze )
       {
         cout<<"B?a;d podczas odczytu pliku (plik za krótki?)"<<endl;
         return false;
       }
      for (int j=0;j < wiersze ;j++)
 
      matrix[i][j] = line[j]-'0';
   }
 
    return true;
}
 
void printMatrix(const Matrix &matrix)
{
    ifstream fp("macierz_sasiedztwa.txt");
   for (int i=0; i < wiersze ; i++)
   {
      for (int j=0; j < wiersze; j++)
         cout<<matrix[i][j]<<' ';
      cout<<endl;
   }
   cout<<matrix[3][4]<<' '<< endl;
   cout<<wiersze<<' '<< endl;
}
 
int main()
{
 
   Matrix MS;
   zlicz("macierz_sasiedztwa.txt");
   if (readMatrix("macierz_sasiedztwa.txt",MS))
      printMatrix(MS);
 
  }
 

Odleglosc miedzy punktami wyliczamy oczywiscie:

Odlegosc = sqr(szer^2 + wys^2)
    gdzie:
         szer = |x2 - x1|
         wys = |y2 -y1|

Teraz konkretne pytania do Was.

  1. Jak przypisac indeksy tablicy do wspolrzednych x i y konkretnego miasta?
  2. Jak zaimplementowac obliczenie szer oraz wys na podstawie x1,x2,y1,y2 ?
  3. Jak napisac warunek aby przypisywac tylko miasta ktore maja ze soba polaczenia(na podstawie macierzy sasiedztwa zapisanej w tablicy dwuwymiarowej matrix[i][j])?

Pomyslalem tez ze wspolrzedne mozna zapisac zamiast tablicy jednowymiarowej do dwuwymiarowej(tab[x][y]). Niestety nie mam pojecia jak to zrealizowac.

Wszystkie te rzeczy sa mi potrzebne do projektu TSP przy uzyciu algorytmu mrowkowego.
Mam nadzieje, ze napisalem zrozumiale i licze na Wasza pomoc.

Pozdrawiam.

Pozostało 580 znaków

2011-08-10 17:00
0

Przed chwila wpadlem na pomysl co do pkt.pierwszego.
Jest dosyc prosty i ciekawi mnie czy zadziala.

for( int i=0; i < liczba_miast; i++)
 {
    tab[i] = x.miasto[i];
    tab[i+1] = y.miasto[i];
    i++; // aby przeskoczylo do nastepnego wiersza.
 }

Teraz tylko nie wiem jak stworzyc strukture miast i wspolrzednych i jak sie potem do nich odwolac.

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0