zachłanny algorytm, wczytujacy dane z pliku txt

0

Witam wszystkich, znowu mam problem z algorytmem. Mam do napisania zachłanny algorytm, który musi znaleźć drogę w tablicy (która znajduje się w pliku txt w pliku również znajduje się liczba N), jej przykład:

5
2 3 4 2 5
5 2 1 2 2
2 5 2 2 3
1 3 1 4 3
2 2 1 2 3
a wymiary to NxN

muszę zaczynać z dolnego lewego punktu, i mogę poruszać się tylko do góry i w prawo
i na końcu zapisuje do pliku txt dane współrzędne kolejnych pól po których się poruszał
Nie mam kompletnie pojęcia jak się za to zabrać.
Czy mogę liczyć na jakieś podpowiedzi z Waszej strony?

0

Najlepiej zacznij od początku, czyli:

  1. napisz funkcję, która wczytuje tą macierz
    std::vector<std::vector<int>> readData(std::istream& input)
    {
    ....
    }
  2. Napisz funkcję, która zachłannie wyznaczy drogę przez tą macierz.
  3. Napisz funkcję wypisującą wynik.

Nie napisałeś co ma być optymalizowane.

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.

To jest treść polecenia, i szczerze nie mam pojęcia co ma być optymalizowane

plik wejściowy:
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
plik wyjściowy:

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

0

Tutaj masz gotową funkcją liczącą koszt drogi przy pomocy zachłannego algorytmu.

int calculateGreedyRoadCost( const vector<vector<int>>& data )
{
    if( data.empty() ) return -1;

    size_t posx {data.size()-1};
    size_t posy {0};
    int cost {data[posx][posy]};

    do
    {
        if( posx!=0 && posy!=data.size()-1 )
        {
            data[posx-1][posy]<data[posx][posy+1]?--posx:++posy;
        }
        else if( posy==data.size()-1 ) --posx;
        else if( posx==0 ) ++posy;
        cost += data[posx][posy];
    }
    while( posx!=0 || posy!=data.size()-1 );

    return cost;
}
0

Na tę chwilę mam takie coś:

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

using namespace std;

bool dane(string nazwa )
{
    fstream plik;
    plik.open( nazwa.c_str() );
    if( !plik.good() )
         return false;

    string wartosc;
    while( getline( plik, wartosc ) )
         cout << wartosc << endl;

    plik.close();
    return true;
}

int main()
{
    fstream plik( "dane.txt", ios::in );
    string n;
    getline( plik, n);

    if( !dane( "dane.txt" ) )
         cout << "Nie jestem w stanie otworzyc pliku" << endl;

    return 0;
}
0
MarekR22 napisał(a):
  1. napisz funkcję, która wczytuje tą macierz
    std::vector<std::vector<int>> readData(std::istream& input)
    {
    ....
    }

lecisz po prostu plik >> x;, getline nie jest ci potrzebny, bo na początku masz rozmiar macierzy

std::vector<std::vector<int>> readData(std::istream& input)
{
    size_t size;
    input >> size;
    std::vector<std::vector<int>> m(size, std::vector<int>(size));

    ....

    return m;
}
0

Jednak to chyba zła droga
może w ten sposób:

#include <iostream>
#include <fstream>

using namespace std;
int main()
{
 fstream plik;
plik.open("dane.txt",ios::in);
int n;
plik>>n;
cout<<n<<endl;
int tab[100][100];

for (int j=0;j<n;j++){
    for (int k=0;k<n;k++){
plik >> tab[j][k];
cout << tab[j][k];}
cout << endl;

    }
    return 0;
}

Jak dalej mogę znaleźć drogę metodą zachłanną ?

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