Zachłanny algorytm poszukiwania drogi w podanej tablicy - pomoże ktoś w rozwiązaniu?

0

Zaimplementuj zachłanny algorytm poszukiwania drogi w podanej tablicy. Dane podane są w pliku wejściowym dane.txt. W pliku znajduje się liczba N oraz tablica liczb nieujemnych, całkowitych o wymiarach N x N. Program, z użyciem metody zachłannej, znajduje drogę z lewego dolnego rogu tablicy do prawego górnego rogu i jej koszt. Program wypisuje do pliku wynik.txt współrzędne kolejnych pól na drodze w tablicy. Po tablicy możemy poruszać się tylko do góry lub w prawo.

Nie pokazuje błędu a w okienku nic mi nie wyświetla, mógłby ktoś powiedzieć co zmienić żeby mi to działało dobrze?

#include <iostream>
#include<fstream>
#include<string>

using namespace std;

int main()
{
    string tekst;
    ifstream plik("dane.txt");
    if(plik.is_open())
    {
        while(plik.good())
        {
            getline(plik, tekst);
            cout << tekst << endl;
        }
        plik.close();
    }
    int n,m;
    cin >> n >> m;
    int G[n][m+1];
    int P[n+1][m];
    int D[n+1][m+1];
    D[0][0] = 0;
    int i,j;
    for(i=0; i<n ; i++){
        for(j=0; j<m ; j++)
        {
            cout << "Podaj dlugosci drog z punktu" << i <<","<< j <<" w prawo" <<endl;
            cin >> P[i][j];
            cout << "w gore";
            cin >> G[i][j];
        }
        cout << "Podaj dlugosc drogi w gore z punktu" << i <<","<< j << endl;
        cin >> G[i][j];
    }
    for(j=0;j<m;j++)
    {
        cout << "Podaj dlugosc drogi w prawo z punktu" << i <<","<< j << endl;
        cin >> P[i][j];
    }
    i=0;
    for(j=1;j<m+1;j++)
    {
        D[i][j]=D[i][j-1]+P[i][j-1];
    }


    for(i=1;i<n+1;i++){
        D[i][0]=D[i-1][0]+G[i-1][0];
        for(j=1;j<m+1;j++)
        {
            if(D[i][j-w[i]]+c[i]<D[i-1][j])
            {
                D[i][j] = D[i-1][j];
            }
            else
            {
                D[i][j] = D[i][j-w[i]] + c[i];
            }        }
    }

    for(i=n;i>=0;i--){
        for(j=0;j<m+1;j++)
        {
            cout << D[i][j] <<" ";
        }
        cout << endl;
    }
    return 0;
}
0

Skoro tablica jest kwadratowa o boku N, to Siostro przelecenie całej od lewa/dół do prawa/góra wygląda tak:

    for (int row = N - 1, column = 0; column < N; row--, column++)
    {
        cout << "[" << row << "]" << "[" << column << "] = " << table[row][column] << "\n";
    }
0

Plik wejściowy dane.txt

5
2 3 4 2 5
5 2 1 2 2
2 4 2 2 3
1 2 2 4 3
3 2 1 2 3

I nie wiem czy wczytywanie zrobiłam poprawnie

0

Nie zrobiłaś. Zamiast getline(), wczytuj liczba po liczbie, za pomocą plik >> zmienna.
Kolejnym błędem jest używanie VLA. To nie jest poprawne w C++, więc zamiast

cin >> n >> m;
int G[n][m+1];
int P[n+1][m];
int D[n+1][m+1];

Zrób to na wektorach:

cin >> n >> m;
std::vector<int> G(n, std::vector<int>(m + 1));
std::vector<int> P(n + 1, std::vector<int>(m));
std::vector<int> G(n + 1, std::vector<int>(m+1));

EDIT

Nie pokazuje błędu a w okienku nic mi nie wyświetla

Brzmi jakbyś czekała na wynik, podczas gdy program czeka na dane z wejścia (czyt. stoi na cin >> n >> m;), z czego wnioskuję, że kompletnie pomyliłaś do czego są std::cin i std::cout.

To, że przy wczytywaniu z pliku zrobisz coś takiego std::cout << linia nie oznacza, że linia ta zostanie magicznie wpisana do std::cin, więc gdy potem robisz std::cin >> n >> m nie sprawi, że będziesz sobie czytała dane z wcześniej wspomnianej linii, tylko program będzie 'czekał aż coś wpiszesz z klawiatury`.

tl;dr

  1. Nie używaj gołych tablic - użyj std::vector
  2. Stwórz wektory przed wczytywaniem danych i wczytuj od razu do wektorów za pomocą plik >> zmienna, a moe getline()

Samego algorytmu nie analizowałem.
Wektory stwórz przed wczytywaniem do pliku.

0

Problem pierwszy. wszystko znajduje się w jednej funkcji main. Może jesteś na tyle genialna, że potrafisz sprawnie to ogarnąć, ja nie potrafię.
Podziel to na funkcję na co najmniej trzy funkcje: wczytującą dane, szukającą drogi, oraz wypisującą wynik.

Problem drugi. Po co wypisujesz tekst "Podaj dlugosci drog z punktu" skoro i tak czytasz plik tekstowy "dane.txt"?
Wszystkie dane potrzebne do rozwiązania masz w pliku tekstowym, wiec interakcja z użytkownikiem jest zbędna.

Problem trzeci nazwy G P D nic nie mówią, ergo nie trudno zrozumieć jak to ma działać.

Przykład wczytywania danych:

std::vector<std::vector<int>> loadDistances(std::istream &input)
{
    int n;
    if (!(input >> n)) {
        return {};
    }

    std::vector<std::vector<int>> result(n, std::vector<int>(n));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
              input >> row[i][j];
        }
    }
    return result;
}

std::vector<std::vector<int>> loadDistances(const std::string &file)
{
    std::ifstream f { file };
    return loadDistances(f);
}
0

@Nency Black: po pliku danych widzę, że o coś innego chodziło. To algorytm poszukujący drogi będzie zawierał się w krokach:

  1. ustawiasz start na [N - 1][0] => lewy, dolny róg.
  2. sprawdzasz, który z kierunków zawiera miejszą wartość - czy w górę, czyli [N - 1 - 1][0], czy w prawo, czyli [N -1][1]
    2a) może nastąpić przypadek, że po drodze dojdziesz do wiersza 0, albo kolumny N - 1. Od takiego momentu możliwy jest tylko ruch w prawo (dla wiersza 0), albo w górę (dla ostatniej kolumny), musisz to Siostro uwzględnić w algorytmie.
  3. przestawiasz start na znaleziony w punkcie 2 indeks, i powtarzasz krok 2 póki nie dojdzie do [0][N - 1] => prawy, górny róg
0

Zacznijmy od wczytania z pliku


int main()
{
  using namespace std;
   int zmienna;

   fstream plik("dane.txt");
   if(plik.is_open())
   {
       while(plik.good())
       {
           plik >> zmienna;;
           cout << plik << endl;
       }
       plik.close();
   }

Tak jest dobrze żeby było znak po znaku? Jak zrobić żeby wyświetliła się zawartość tego pliku?

0

A jakoś prościej nie da się tego napisać ? W taki sposob nie pisaliśmy na zajęciach

Tak nie używaliśmy takich rzeczy na ćwiczeniach

0

Nency, napierw poprawnie pobierz z pliku wielkość tablicy, a upewnisz się o tym wyświetlając ją cout-em.

0

A w jaki sposób to zrobić ? mógłbyś to na moim przykładzie wytłumaczyc w którym miejscu dokladnie to zrobić?

0

Jak pisałam wyżej
Plik dane.txt wygląda ta czyli to 5 będzie ?
Plik wejściowy dane.txt

5
2 3 4 2 5
5 2 1 2 2
2 4 2 2 3
1 2 2 4 3
3 2 1 2 3

0

    if(plik.is_open())
    {
        int size;
        plik >> size;
        cout << "wczytana wielkosc tablicy: " << size;//wedug danych jakie podałaś powinno pokazać 5
     }

to są dane jakie przytoczyłaś

0
int main()
{
   using namespace std;
    int zmienna;

    fstream plik("dane.txt");
  if(plik.is_open())
    {
        int size;
        plik >> size;
        cout << "wczytana wielkosc tablicy: " << size;
    {
        while(plik.good())
        {
            plik >> zmienna;;
            cout << plik << endl;
        }
        plik.close();
    }

return 0;
}
}

Całość ma tak wyglądać , bo działa ale nic nie wyświetla to, coś jeszcze w tym zmienić ?

0

wstawić 5 zamiast size czy ma size być?

0

Ma być size, toć na tym cała linijka cout << "wczytana wielkosc tablicy: " << size; się opiera.
Ale skoro twierdzisz, że nic się nie pokazuje to może oznaczać, że plik się nie otwiera. Dopisz to:

    if (plik.is_open())
    {
       //tutaj zostaje co masz
    }
    else
    {
       cout << "Blad otwarcia pliku dane.txt!";
    }

i daj znać, czy się komunikat z else'a pokazał

0

wyświetla " Blad otwarcia pliku dane.txt!"
a teraz pokazuje to :
wczytana wielkosc tablicy: 50x6dfe54
0x6dfe54
0x6dfe54
0x6dfe54
0x6dfe54
0x6dfe54
0x6dfe54
0x6dfe54
0x6dfe54
0x6dfe54
0x6dfe54
0x6dfe54
0x6dfe54
0x6dfe54
0x6dfe54
0x6dfe54
0x6dfe54
0x6dfe54
0x6dfe54
0x6dfe54
0x6dfe54
0x6dfe54
0x6dfe54
0x6dfe54
0x6dfe54

0

Jakiego środowiska IDE używasz?

0

code blocks

0

jak zrobiłam np tak:

int main()
{
    string tekst;
    ifstream plik("dane.txt");
    if(plik.is_open())
    {
        while(plik.good())
        {
            getline(plik, tekst);
            cout << tekst << endl;
        }
        plik.close();
    }

    return 0;
}

to wypisało zawartość tego dane.txt bez błedu

potem zrobiłam tak:

using namespace std;

int main()
{
    string tekst;
    ifstream plik("dane.txt");
    if(plik.is_open())
    {
         int size;
        plik >> size;
        cout << "wczytana wielkosc tablicy: " << size;
        {


        while(plik.good())
        {
            getline(plik, tekst);
            cout << tekst << endl;
        }
        plik.close();
    }
    }
    else
    {
       cout << "Blad otwarcia pliku dane.txt!";

    return 0;
  }
    }

i wyświetliło tak :
wczytana wielkosc tablicy: 5
2 3 4 2 5
5 2 1 2 2
2 4 2 2 3
1 2 2 4 3
3 2 1 2 3

0

co ty z tym getline?
Olej go nie jest ci do niczego potrzebny.

0

Czyli jak rozumiem wypisało 5? Jeśli tak, to czeka cię teraz utworzenie dynamicznej, dwuwymiarowej tablicy o odczytanym rozmiarze.

0

Tak, wypisało to:
wczytana wielkosc tablicy: 5
2 3 4 2 5
5 2 1 2 2
2 4 2 2 3
1 2 2 4 3
3 2 1 2 3

Tylko kolega twierdzi, że po co getline a w inny sposób mi dziala źle

0

getline jest potrzebny jeśli nie masz pewności co do długości linii i dlugość linii niesie ci jakąś informację.
jako, że długość linii masz zdefiniowaną w pierwszej linii (każda następna linia zawiera n liczb), getline ci tylko komplikuje kod.
Wystarczy, że przerobisz gotowca, którego ci dałem (te dwa for-y) i tyle.

0

Co zmienić w tablicy ?


#include <iostream>
#include<fstream>
#include<string>

using namespace std;

int main()
{
    string tekst;
    fstream plik("dane.txt");
    if(plik.is_open())
    {
         int size;
        plik >> size;
        cout << "wczytana wielkosc tablicy: " << size;
        {


        while(plik.good())
        {
            getline(plik, tekst);
            cout << tekst << endl;
        }
        plik.close();
    }
}
    else
    {
       cout << "Blad otwarcia pliku dane.txt!";

{
    int n;
int i,j;
    int G[n-1-1][0];
    int P[n-1][1];
    int D[n-1][0];
    int liczba[5][5];
    ifstream plik("dane.txt");
    for(int i = 0; i < 5; i++)
        for(int j = 0; j < 5; j++)
            plik >> liczba[i][j];

    for(int i = 0; i < 5; i++)
    {
        for(int j = 0; j < 5; j++)
            cout << liczba[i][j] << " ";
        cout << "\n";
    }
     i=0;
    for(j=1;j<n+1;j++)
    {
        D[i][j]=D[i][j-1]+P[i][j-1];
    }


    for(i=1;i<n+1;i++){
        D[i][0]=D[i-1][0]+G[i-1][0];
        for(j=1;j<n+1;j++)
        {
            if(D[i-1][j]+G[i-1][j]<D[i][j-1]+P[i][j-1])
            {
                D[i][j] = D[i-1][j] + G[i-1][j];
            }
            else
            {
                D[i][j] = D[i][j-1] + P[i][j-1];
            }
        }
    }

    for(i=n;i>=0;i--){
        for(j=0;j<n+1;j++)
        {
            cout << D[i][j] <<" ";
        }
        cout << endl;
    }

    }
    }
     return 0;
     }

a mi cały czas pokazuje

wczytana wielkosc tablicy: 5
2 3 4 2 5
5 2 1 2 2
2 4 2 2 3
1 2 2 4 3
3 2 1 2 3

Bo wynik mam miec taki :

Przykładowe wyjście (może się różnić, w zależności od implementacji) - plik wynik.txt

Koszt: 22
4 0
3 0
2 0
2 1
1 1
1 2
1 3
0 3
0 4

0

Ten kod nie ma prawa działać.
Pierwszy warunek: jeśli udało się otworzyć plik to poczytaj go sobie i nic nie rób. Jeśli się nie udało, to spróbuj go otworzyć jeszcze raz (nie wiem czemu tym razem miało by się udać) i próbuj wczytać dane ignorując błędy.
Koniec końców przetwarzane są dane śmieci z pamięci.

0

Cały czas pojawia się tylko to z dane.txt

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