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ć?

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