Witam, mógłby ktoś jakoś w skrócie opisać jak mógłbym obronić tę pracę u prowadzącego zajęcia. Żebym był w stanie odpowiedzieć mu na pytania: czemu tak? dlaczego nie inaczej ? itp. Będę bardzo wdzięczny :)
#include <cstdlib>
#include <iostream>
#include <stdlib.h>
#include <time.h>
#include <stdio.h>
using namespace std;
int** zbuduj_macierz_uporzadkowana(int m, int n);
int** zbuduj_macierz_losowa(int m, int n);
void pokaz_macierz(int** macierz, int m, int n, bool naglowek);
void szukaj_najdluszej_sciezki_po_elementach_maksymalnych(int** macierz, int m, int n, int j, int k, int index);
// funkcje pomocnicze
string intToStr(int n);
int strToInt(char *s);
int strToInt(string s);
string tylko_cyfry(string txt);
int main(int argc, char *argv[])
{
string buffer = "";
int m = 1;
int n = 1;
int i=0;
int j=0;
bool macierz_losowa = true;
// zainicjowanie generator liczb losowych (potrzebny do macierzy losowej)
srand( (unsigned)time(NULL) );
while (buffer != "QUIT" && buffer!="quit" && buffer!="q" && buffer!="Q")
{
// Czyszczenie ekranu
system("cls");
// komunikat poczatkowy
cout << "------------------------------------------------------------------------------" << endl;
cout << "q - wyjscie z programu" << endl << endl;
// Podanie rozmiary macierzy
cout << "Macierz ma miec rozmiar M x N" << endl;
cout << "Podaj liczbe M > 0: ";
getline(cin,buffer);
if (buffer == "QUIT" || buffer=="quit" || buffer=="q" || buffer=="Q") break;
m = strToInt(tylko_cyfry(buffer));
if (m<1) m=1;
cout << "M = " << m << endl;
cout << "Podaj liczbe N > 0: ";
getline(cin,buffer);
if (buffer == "QUIT" || buffer=="quit" || buffer=="q" || buffer=="Q") break;
n = strToInt(tylko_cyfry(buffer));
if (n<1) n = 1;
cout << "N = " << n << endl;
// Wybranie czy ma byc macierz losowa, czy uporzakowana
cout << "Czy macierz ma byc losowa (T/n): ";
getline(cin,buffer);
if (buffer == "QUIT" || buffer=="quit" || buffer=="q" || buffer=="Q") break;
macierz_losowa = true;
if (buffer=="N" || buffer=="n") macierz_losowa = false;
// Prezentacja macierzy na ekranie
cout << "Macierz " << (macierz_losowa ? "losowa":"uporzadkowana") << " o rozmiarze: " << m << " x " << n << endl;
cout << "Liczba elementow w macierzy: " << (m*n) << endl;
int** macierz = (macierz_losowa ? zbuduj_macierz_losowa(m,n):zbuduj_macierz_uporzadkowana(m,n));
pokaz_macierz(macierz,m,n, true);
// Wybieranie elementu macierzy, od ktorego ma być robiona sciezka
if (m>1 && n>1) cout << "Wybierz element I x J" << endl;
else if (m>1) cout << "Wybierz element I" << endl;
else if (n>1) cout << "Wybierz element J" << endl;
if (m>1) {
cout << "Podaj I zakres [0," << (m-1) << "]: ";
getline(cin,buffer);
if (buffer == "QUIT" || buffer=="quit" || buffer=="q" || buffer=="Q") break;
i = strToInt(tylko_cyfry(buffer));
if (i<0) i = 0;
if (i>=m) i = m - 1;
cout << "I = " << i << endl;
}
else i=0;
if (n>1) {
cout << "Podaj J zakres [0," << (n-1) << "]: ";
getline(cin,buffer);
if (buffer == "QUIT" || buffer=="quit" || buffer=="q" || buffer=="Q") break;
j = strToInt(tylko_cyfry(buffer));
if (j<0) j = 0;
if (j>=n) j = n - 1;
cout << "J = " << j << endl;
}
else j=0;
// Wypisanie na ekranie elementu wybranego (starowego) dla wyliczenia sciezki
cout << "Element wybrany I x J [" << i << " x " << j << "], wartosc: " << macierz[i][j] << endl;
cout << endl;
// Prezentacja sciezki po elementach maksymalnych
cout << "Najdluzsza sciezka po elementach maksymalnych" << endl;
cout << "rozpoczecie od elementu [" << i << " x " << j << "] o wartosci: " << macierz[i][j] << endl << endl;
szukaj_najdluszej_sciezki_po_elementach_maksymalnych(macierz, m, n, i, j, 0);
cout << endl << endl;
// Komunikat końcowy
cout << "q - wyjscie z programu" << endl;
cout << "inny klawisz - nowa macierz" << endl;
getline(cin,buffer);
}
return EXIT_SUCCESS;
}
// funckja budujaca macierz 2d, w ktorej liczby sa uporzadkowane
int** zbuduj_macierz_uporzadkowana(int m, int n) {
int** macierz; // wskaznik do macierzy, inaczej tablica 2d o nieokreslonym rozmiarze, czyli int macierz[][]
macierz = new int*[m]; // inicjalizuje macierz pierwszego wymiaru na ilość elementów m (liczba wierszy)
int i, j, k;
// wypelnienie macierzy wartosciami od 1 do (m*n) - ważne: wartosc 0 jest uzywana do oznacznia pola jako juz odwiedzonego, dlatego wartosci pol w macierzy musza byc >0
k=0;
for (i=0;i<m;i++) {
macierz[i] = new int[n]; // inicializacja kolumn w macierzy dla wiersza "i"
for (j=0;j<n;j++) {
macierz[i][j] = (++k); // przypisanie kolejnej wartosci w macierzy dla wiersza "i" i kolumny "j" (od wartosci 1)
}
}
return macierz;
}
// zwraca macierz losowa
int** zbuduj_macierz_losowa(int m, int n) {
int** macierz = zbuduj_macierz_uporzadkowana(m,n); // buduje macierz uporzadkowana
int i,j,ii, jj, k, kk, p, r;
k=0;
// kazdy element macierzy jest losowo wyminiany w innym elementem
for (i=0;i<m;i++) {
for (j=0;j<n;j++) {
r = (rand()%20)+5; // losowa liczba wymian
for (p=0;p<r;p++) {
ii = rand()%m; // pozycja "i" do wymiany (wartosc losowa)
jj = rand()%n; // pozycja "j" do wymiany (wartosc losowa)
// wymiana wartosci elemntu [i][j] na element [ii][jj].
k = macierz[i][j];
kk = macierz[ii][jj];
macierz[ii][jj] = k;
macierz[i][j] = kk;
}
}
}
return macierz;
}
// szuka najdluszej sciezki wsrod elementow zaczynajac od elementu o parametrach "j" i "k"
void szukaj_najdluszej_sciezki_po_elementach_maksymalnych(int** macierz, int m, int n, int j, int k, int index) {
// zmienna "index" potrzebna do wyliczenia ilosci elementow w sciezce
int new_j=-1; // nowa pozycja "I" kolejnego elemntu wyszukanego
int new_k=-1; // nowa pozycja "J" kolejnego elementu wyszukanego
int max_element = 0; // wartosc maksymalna elementu "dookoła" (4 elementy obok pola, 2 w pionie, 2 w poziomie) elementu podanego "j x k"
int wartosc = macierz[j][k]; // wartosc biezacego elementu do wyswietlenia
int i =0;
int elem=0;
cout << (index>0 ? ",":"") << wartosc; // wypisanie na ekranie elementu
macierz[j][k]=0; // ustalenie wyszukanego elementu na 0 (ważne: potrzebne do zapisu że to pole było już odwiedzane)
int* elementy_dookola = new int[4]; // tablica elemnetów "dookola" bieżącego elementu (element wyżej + element niżej + element na lewo + element na prawo)
i=0;
// gorny element
elementy_dookola[i++] = (j>0 ? macierz[j-1][k]:0);
// dolny element
elementy_dookola[i++] = (j<(m-1) ? macierz[j+1][k]:0);
// lewy element
elementy_dookola[i++] = (k>0 ? macierz[j][k-1]:0);
// prawy element
elementy_dookola[i++] = (k<(n-1) ? macierz[j][k+1]:0);
i=0;
// sprawdzenie gorny element
elem = elementy_dookola[i++];
if (elem>max_element) {
// jesli element ma wartosc wieksza niz max (na pocztaku 0) przypisuje nowy element do wyszukania do zmienych new_j i new_k;
max_element = elem;
new_j = j-1;
new_k = k;
}
// sprawdzenie dolny element
elem = elementy_dookola[i++];
if (elem>max_element) {
// jesli element ma wartosc wieksza niz max (na pocztaku 0) przypisuje nowy element do wyszukania do zmienych new_j i new_k;
max_element = elem;
new_j = j+1;
new_k = k;
}
// sprawdzenie lewy element
elem = elementy_dookola[i++];
if (elem>max_element) {
// jesli element ma wartosc wieksza niz max (na pocztaku 0) przypisuje nowy element do wyszukania do zmienych new_j i new_k;
max_element = elem;
new_j = j;
new_k = k-1;
}
// sprawdzenie prawy element
elem = elementy_dookola[i++];
if (elem>max_element) {
// jesli element ma wartosc wieksza niz max (na pocztaku 0) przypisuje nowy element do wyszukania do zmienych new_j i new_k;
max_element = elem;
new_j = j;
new_k = k+1;
}
if (new_j<0 || new_k<0) {
// jesli nie ma nowego elementu maksymalnego "dookoła" to wypisz liczbe elementow sciezki i zakończ funckje
cout << endl << endl << "Liczba elementow sciezki: " << (index+1) ;
return;
}
// jeśli jest nowy element maksymalny "dookoła" to wyszukaj znów ściężkę dla tego nowego elementu (uwzględnia już przechodone pola, dzięki zapisaniu w nich wartości 0)
// jest to wywołanie rekurencyjne (wywołanie funkcji wewnatrz niej samej, z zmienionymi parametrami).
szukaj_najdluszej_sciezki_po_elementach_maksymalnych(macierz, m, n, new_j, new_k, ++index);
}
// funckja prezentujaca macierz na ekranie, wraz z naglowkiem (w zaleznosci od prametru naglowek)
void pokaz_macierz(int** macierz, int m, int n, bool naglowek)
{
int i, j;
int max = m*n;
string frm = "%s%5d";
string frm2 = "%s%5s";
string frm3 = "%5s|";
string frm4 = "-----+";
string frm5 = "%5d|";
string frm6 = "-----";
string frm7 = "%5s|";
string frm8 = "%5s";
if (naglowek) {
// naglowek
cout << endl;
// linia gorna naglowka
printf(frm4.c_str());
for (j=0;j<n;j++) {
printf(frm2.c_str(), (j>0 ? "+":""),frm6.c_str());
}
cout << endl;
// numery kolumn
printf(frm3.c_str(),"");
for (j=0;j<n;j++) {
if (j>0) printf(frm.c_str(), "|", j);
else printf(frm8.c_str(),"J=0");
}
cout << endl;
}
// linia dolna naglowka
if (naglowek) printf(frm4.c_str());
for (j=0;j<n;j++) {
printf(frm2.c_str(), (j>0 ? "+":""),frm6.c_str());
}
cout << endl;
// wyswietalnie wartosci macierzy
for (i=0;i<m;i++) {
if (naglowek) { if (i>0) printf(frm5.c_str(),i); else printf(frm7.c_str(),"I=0"); }; // w przyadku kiedy jest naglowek wypisz także numery wierszy
for (j=0;j<n;j++) {
printf(frm.c_str(), (j>0 ? " ":""), macierz[i][j]); // wypisywanie kolejnych wartosci
}
cout << endl;
}
cout << endl;
}
// funckja zmieniaca wartosc typu int na string
string intToStr(int n)
{
string tmp;
if(n < 0) {
tmp = "-";
n = -n;
}
if(n > 9)
tmp += intToStr(n / 10);
tmp += n % 10 + 48;
return tmp;
}
// funckja zmianiaca string-a (w formacie char*) na wartosc typu int
int strToInt(char *s)
{
int tmp = 0, m = 0;
if(*s == '-') {
m = 1;
*s++;
}
while(*s)
tmp = 10 * tmp + *s++ - 48;
return m ? -tmp : tmp;
}
// funckja zmianiaca string na wartosc typu int
int strToInt(string s)
{
if (s.length()<=0) return 0;
bool m=false;
int tmp=0;
int i=0;
if(s[0]=='-')
{
i++;
m = true;
}
while(i<s.size())
{
tmp = 10*tmp+s[i]-48;
i++;
}
return m ? -tmp : tmp;
}
// funckja zostawiajaca tylko cyfry z ciągu znakow
string tylko_cyfry(string txt) {
int len = txt.length();
if (len<=0) return "";
string str = ("");
for (int i=0;i<len;i++) {
char c = txt[i];
if (c>='0' && c<='9') str = str + c;
}
return str;
}
