Forum PCLab.pl: Zachłanne szukanie drogi w tablicy - Forum PCLab.pl

Skocz do zawartości

Otwarty

Ikona Ostatnio dodane tematy

Ikona Najnowsze pliki

Strona 1 z 1
  • Nie możesz rozpocząć nowego tematu
  • Nie możesz odpowiadać w tym temacie

Zachłanne szukanie drogi w tablicy Oceń temat: -----

#1 Użytkownik jest niedostępny   Roundstic 

  • Dyskutant
  • PipPip
  • Grupa: Forumowicze
  • Postów: 24
  • Dołączył: Wed, 13 Lis 19

Napisany 03 Grudzień 2019 - 20:46

Zaimplementuj zachłanny algorytm poszukiwania drogi w podanej tablicy. Użytkownik podaje liczbę N, i tablicę liczb 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 współrzędne kolejnych pól na drodze w tablicy. Po tablicy możemy poruszać się tylko do góry lub w prawo.

Przykład

Wejście

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
Przykładowe wyjście (może się różnić, w zależności od implementacji)

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

Sam napisałem jedynie, początek i nie wiem co dalej myślałem nad utworzeniem nowej tablicy

#include <iostream>

using namespace std;


int main()
{
    int n;
    int T[100][100];
    
    cout<<"Podaj liczbe: ";
    cin>>n;
    
    cout<<"Podaj tablice liczb: "<<endl;
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<n; j++)
        {
            cin>>T[i][j];
        }
    }

    int A[100][100];


#2 Użytkownik jest niedostępny   Bono[UG] 

  • Wiecznie niewyspany...
  • PipPipPipPipPip
  • Grupa: Forumowicze
  • Postów: 20408
  • Dołączył: Pt, 27 Wrz 02

Napisany 03 Grudzień 2019 - 20:58

Przede wszystkim czy wiesz jak ma wyglądać algorytm? Czy potrafisz znaleźć drogę mając wyrysowaną tabelę i chodząc palcem po niej?
Czy po poprzednich zadaniach z algorytmów zachłannych rozumiesz na czym polega idea takiej grupy algorytmów, czym jest ta zachłanność?

Z tego co na razie masz, to do czego ma służyć ta nowa tablica? W jakim celu ją tworzysz? Co dzięki niej osiągniesz?

#3 Użytkownik jest niedostępny   Roundstic 

  • Dyskutant
  • PipPip
  • Grupa: Forumowicze
  • Postów: 24
  • Dołączył: Wed, 13 Lis 19

Napisany 03 Grudzień 2019 - 21:27

Algorytm powinien wybierać najbardziej optymalną wartość, jednak czasami nie najbardziej opłacalną.
Droga w tablicy powinna wyglądać tak, że pierw idzie od dołu do samej góry i prawego rogu, a potem kolejne komórki powinien wybierać, albo z boku, albo z dołu w zależności od najmniejszej wartości.
Nową tablicę chciałem utworzyć na drogę

#4 Użytkownik jest niedostępny   januzi 

  • ^ patryjota, katolig, bochater
  • Ikona
  • Grupa: Moderatorzy
  • Postów: 35721
  • Dołączył: Nd, 08 Cze 03

Napisany 03 Grudzień 2019 - 23:00

Nie ma potrzeby tworzenia drugiej tablicy, wszystko możesz pokazać "na żywca".

#5 Użytkownik jest niedostępny   Bono[UG] 

  • Wiecznie niewyspany...
  • PipPipPipPipPip
  • Grupa: Forumowicze
  • Postów: 20408
  • Dołączył: Pt, 27 Wrz 02

Napisany 04 Grudzień 2019 - 09:20

Zobacz postRoundstic, o 03 Grudzień 2019 - 21:27, napisał(a):

Algorytm powinien wybierać najbardziej optymalną wartość, jednak czasami nie najbardziej opłacalną.
Droga w tablicy powinna wyglądać tak, że pierw idzie od dołu do samej góry i prawego rogu, a potem kolejne komórki powinien wybierać, albo z boku, albo z dołu w zależności od najmniejszej wartości.
Nową tablicę chciałem utworzyć na drogę

Algorytmy zachłanne najprościej opisać: bierz najlepsze rozwiązanie w danym momencie i idź dalej.
Tak, wybiera się optymalną wartość ale tylko w danym kroku. Ogólny wynik może być daleki od najlepszego.


Coś chyba nie do końca zrozumiałeś zadanie lub zbyt skrótowo to teraz opisujesz.
Startujesz z lewego dołu, masz dojść do prawej góry.
Możesz iść w górę lub w prawo.
Trudnością tutaj może być orientacja góra - dół, lewo - prawo względem indeksów tablicy.


Ok, chcesz zapisać przebytą drogę w tablicy. Po co ci zatem o takich samych rozmiarach, co plansza?
Zapis drogi to kolejne pary liczb, współrzędne położenia. Czyli tablica jeden z wymiarów powinna mieć 2, np. tab[10][2] pozwoli na zapamiętanie 10 kroków.
Gdybyś poruszał się po tablicy trójwymiarowej, to przykładowa tablica byłaby: tab[10][3]. tab[10][10] z kolei umożliwia zapamiętanie 10 kroków w 10 wymiarowej przestrzeni.

Deklarując tablicę 100x100 marnujesz pełno pamięci lub dokładasz sobie roboty z wyszukaniem w niej jaką drogę przeszedłeś.

#6 Użytkownik jest niedostępny   maxpower 

  • ..........
  • PipPipPipPipPip
  • Grupa: Forumowicze
  • Postów: 1852
  • Dołączył: Nd, 23 Sie 09

Napisany 04 Grudzień 2019 - 10:14

A*?
Dodaj obrazek

Ten post był edytowany przez maxpower dnia: 04 Grudzień 2019 - 10:21


#7 Użytkownik jest niedostępny   Kitu 

  • Dyskutant
  • PipPip
  • Grupa: Forumowicze
  • Postów: 66
  • Dołączył: Nd, 24 Sty 16

Napisany 04 Grudzień 2019 - 11:06

Zobacz postmaxpower, o 04 Grudzień 2019 - 10:14, napisał(a):

A*?



To jeszcze nie ten poziom - z tego, co zdążyliśmy się zorientować, Roundstic dopiero zaczyna swoją przygodę w programowaniem (w ogóle wygląda to na pierwszy semestr studiów) - nie dawaliby mu zadania z A* bez wcześniejszego wspomnienia o nim. Przy tym poziomie w zupełności wystaczy porównanie kosztu przejścia w górę i w prawo (o ile sa możliwe) oraz wybranie mniejszego kosztu jako kolejny krok. To nic ponad zadanie na zrozumienie indeksów w tablicy dwuwymiarowej ;)

Strona 1 z 1
  • Nie możesz rozpocząć nowego tematu
  • Nie możesz odpowiadać w tym temacie

1 Użytkowników czyta ten temat
0 użytkowników, 1 gości, 0 anonimowych