Skocz do zawartości
Roundstic

Zachłanne szukanie drogi w tablicy

Rekomendowane odpowiedzi

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];

Udostępnij tę odpowiedź


Odnośnik do odpowiedzi
Udostępnij na innych stronach

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?

Udostępnij tę odpowiedź


Odnośnik do odpowiedzi
Udostępnij na innych stronach

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ę

Udostępnij tę odpowiedź


Odnośnik do odpowiedzi
Udostępnij na innych stronach

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

Udostępnij tę odpowiedź


Odnośnik do odpowiedzi
Udostępnij na innych stronach

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ś.

Udostępnij tę odpowiedź


Odnośnik do odpowiedzi
Udostępnij na innych stronach

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 ;)

Udostępnij tę odpowiedź


Odnośnik do odpowiedzi
Udostępnij na innych stronach

Jeśli chcesz dodać odpowiedź, zaloguj się lub zarejestruj nowe konto

Jedynie zarejestrowani użytkownicy mogą komentować zawartość tej strony.

Zarejestruj nowe konto

Załóż nowe konto. To bardzo proste!

Zarejestruj się

Zaloguj się

Posiadasz już konto? Zaloguj się poniżej.

Zaloguj się

  • Ostatnio przeglądający   0 użytkowników

    Brak zarejestrowanych użytkowników przeglądających tę stronę.

  • Tematy

  • Odpowiedzi

    • FuryGPU - pojedynczy użytkownik opracował od podstaw własną kartę graficzną. Zaskakująco dobrze radzi sobie z grą Quake Ja mam wielki szacunek dla takich napaleńców, co ja umiem sam zrobić, ratuję stare komputery/laptopy/tablety/smartfony ze śmietnika i przywracam je do życia. Te które się nadają oczywiście  
    • Obie konstrukcje mają swoje zady i walety. Najlepiej przeanalizuj jakie masz potrzeby, popatrz testy i wybierz konstrukcje Ci odpowiadającą. Tutaj istotny jest indywidualizm. Podpowiem, że karta zielonych będzie lepsza do tytułów z RT.
    • Akurat panowie gram głównie na słuchawkach albo na głośnych głośnikach więc i tak nie słyszę chłodzenia więc raczej i tak jesli chodzi o chłodzenia to zostanę przy czymś za 200-300 zł max
    • U nas było powszechne oburzenie kiedy notorycznego oszusta z OLX skazano na 20 lat więzienia... takie kary powinny być za oszustwa/przestępstwa finansowe(w zależności od skali od kilku lat do nawet do dożywocia, jak w USA w przypadku piramid finansowych). Można się tylko domyślać ile tragedii życiowych spowodował taki bandzior(w białych rękawiczkach). Taki Marcin P. i jego małżonka nigdy nie powinni opuścić zakładu karnego.
    • No i to jest smutne, bo rozłożenie na lata pozwala myśleć, że pewnie pojawi się jakaś technologia, tanie magazyny ttd, Bo przy obecnych ja tego "net zero" nie bardzo widzę. Te jebnie, a jedyna dobra rzecz w tym, że pewnie nie dożyję najgorszego. Np. peerelowskie budownictwo (choć to z lat 90 nie lepsze). Wiadomo, można dokładać styropianu na ściany i lepsze okna, ale z wentylacją grawitacyjną czy układem pewnych rzeczy nie przeskoczysz bez wyburzenia i zbudowania na nowo. A tak mieszkają miliony ludzi. I nawet jak im pomontujesz pompy ciepła i sieć elektryczna tu uciągnie, to one będą ciągnąć gigawaty i z czegoś trzeba te gigawaty wygenerować, najwięcej w chłodnie i długie zimowe noce.
  • Aktywni użytkownicy

×
×
  • Dodaj nową pozycję...