Witam wszystkich serdecznie!

Mam problem z przekształceniem algorytmu w zapisie matematycznym do postaci kodu w C++. Problem przedstawia się następująco:

Należy wyznaczyć wartość wyrażenia (stosując technikę programowania dynamicznego):

dla i = 4, j = 4

Moje dotychczasowe postępy:

int main(int argc, char *argv[])
{
    int i,j, tab[4][4] = {
                           (1,7,1,8),
                           (3,6,1,1),
                           (3,7,1,2),
                           (3,2,2,4)
    },
    tab2[4][4] = {};
    
    cout<<"i: ";
    cin>>i;    
    cout<<"j: ";
    cin>>j;
    
    if(i == 0 && j > 0) 
    {tab2[i][j] = 1;}
    if(i > 0 && j == 0) 
    {tab2[i][j] = 0;}
    if(i > 0 && j > 0)
    {
         for(int n = 1; n < i; n++)
         {
                 for(int k = 1; k < j; k++)
                 {                                                 
                         tab2[n][k] = (tab[n-1][k]+tab[n][k-1])/2;     
                 }        
         }
    }
    system("PAUSE");
    return EXIT_SUCCESS;
}

Nie wiem jak to dalej ugryźć i czy w ogóle idę w dobrym kierunku. Jakieś sugestie, pomysły? Z góry dzięki za każdą wskazówkę.

1. nie ten dział
2. pierwsze dwa przypadki źle zrobiłeś. Tam nie powinny być if-y ale odpowiednia pętla for.
3. po co ci dane wejściowe? zadanie nic nie mówi o danych wejściowych!
4. po co ci dodatkowa tablica?

MarekR22 napisał(a)

nie ten dział

1. pierwsze dwa przypadki źle zrobiłeś. Tam nie powinny być if-y ale odpowiednia pętla for.
2. po co ci dane wejściowe? zadanie nic nie mówi o danych wejściowych!
3. po co ci dodatkowa tablica?

Pętla for w dwóch pierwszych przypadkach? Ale po co? Skoro i = 0 i j > 0 (pierwszy przypadek), to wystarczy prosty warunek i instrukcja, która zwróci/zapisze odpowiednią wartość. Podobnie w drugim przypadku. Odnośnie danych wejściowych to faktycznie, zadanie nic o nich nie mówi, ale żeby wykonać tą operację widoczną w trzecim przypadku - trzeba mieć jakieś podłoże w postaci przykładowej macierzy (tablicy) wypełnionej jakimiś danymi. Przynajmniej ja to tak interpretuje. Jeżeli chodzi o tablice pomocniczą, to w programowaniu dynamicznym wyniki obliczeń są właśnie zapamiętywane w takiej tablicy. Jak wspominałem wcześniej, nie wiem czy idę w dobrym kierunku dlatego prosiłbym o nakierowanie mnie, bądź podanie jakiegoś konkretnego przykładu.

Jeżeli chodzi o dział, to wydawało mi się, że ten jest jak najbardziej prawidłowy, bowiem jest to zadanie właśnie z przedmiotu algorytmy i struktury danych.

Człowieku, czy ty nie widzisz, że masz zwykłą rekurencyjną definicję?
W kroku pierwszym ustalasz wartości, które znasz, czyli pierwszy wiersz i pierwszą kolumnę, więc potrzebujesz tam pojedyncze pętle for by wypełnić ten fragment macierzy.
Reszta kodu najwyraźniej przez przypadek jest prawidłowa (wszystkie if-y są zbędne).

PS. Nie licz na to, że dam ci gotowe rozwiązanie.

MarekR22 napisał(a)

Człowieku, czy ty nie widzisz, że masz zwykłą rekurencyjną definicję?
W kroku pierwszym ustalasz wartości, które znasz, czyli pierwszy wiersz i pierwszą kolumnę, więc potrzebujesz tam pojedyncze pętle for by wypełnić ten fragment macierzy.
Reszta kodu najwyraźniej przez przypadek jest prawidłowa (wszystkie if-y są zbędne).

PS. Nie licz na to, że dam ci gotowe rozwiązanie.

Może dla Ciebie to jest tak wszystko proste, że aż banalne, ale ja ewidentnie mam z tym mały problem. Trochę zrozumienia, człowieku. Po to są fora (między innymi właśnie takie jak to), by sobie wzajemnie pomagać. Wcale nie oczekuję gotowego rozwiązania, sam (ewentualnie z niewielką pomocą) chcę do tego dojść.

Najwidoczniej odebrałeś moją prośbę o pomoc jako chęć otrzymania gotowego rozwiązania, a wcale o takie nie prosiłem. Czyżbym gdzieś wspomniał, że takie wymagam? Siedzę na tym zagadnieniem chwilę, wrzucam swoje dotychczasowe postępy i próbuję w te czy we w te, by to doprowadzić do końca, ale najzwyczajniej w świecie mi nie wychodzi, mam pewny zastój. Gdyby nie to, że czas mnie nagli - nie pisałbym tutaj.

Wynika z tego, że moim problemem nie jest napisanie algorytmu, ale zrozumienie i odczytanie zapisu matematycznego (jakiś sprawdzony link na ten temat by się przydał).

W każdym razie dzięki za pomoc i spróbuję się dostosować do Twoich wskazówek. Powtórzę jeszcze raz, więcej zrozumienia. Zawsze możesz nie odpowiadać, jeżeli temat aż tak bardzo Cię irytuje :)

Zakładam że jesteś bardziej programistą niż matematykiem, więc kod powinien być dla ciebie bez problemu zrozumiały. Podaną funkcję możesz zapisać w C w taki sposób:

int M(int i, int j)
{
	if (i == 0 && j > 0) { return 1; }
	if (i > 0 && j == 0) { return 0; }
	if (i > 0 && j > 0) { return (M(i - 1, j) + M(i, j - 1)) / 2; }
	// blow up the universe
}

(biorę przykład z twojej tablicy którą zadeklarowałeś jako int, ale rozważyłbym na twoim miejscu użycie tutaj floatów)

Wtedy M(4, 4) jest rozwiązaniem twojego zadania.

Oczywiście taka rekurencyjna definicja jest dobra matematycznie, ale w praktyce jest bardzo wolna dla wyższych wartości i oraz j. Żeby to rozwiązanie sensownie działało, możesz użyć, jak masz w poleceniu, programowania dynamicznego.

Jeśli nie wiesz jak to zrobić albo Ci nie będzie wychodzić to pytaj, ale wrzuć wtedy przy okazji kod który stworzysz próbując.

Tezcatlipoca napisał(a)

Zakładam że jesteś bardziej programistą niż matematykiem, więc kod powinien być dla ciebie bez problemu zrozumiały. Podaną funkcję możesz zapisać w C w taki sposób:

int M(int i, int j)
{
	if (i == 0 && j > 0) { return 1; }
	if (i > 0 && j == 0) { return 0; }
	if (i > 0 && j > 0) { return (M(i - 1, j) + M(i, j - 1)) / 2; }
	// blow up the universe
}

(biorę przykład z twojej tablicy którą zadeklarowałeś jako int, ale rozważyłbym na twoim miejscu użycie tutaj floatów)

Wtedy M(4, 4) jest rozwiązaniem twojego zadania.

Oczywiście taka rekurencyjna definicja jest dobra matematycznie, ale w praktyce jest bardzo wolna dla wyższych wartości i oraz j. Żeby to rozwiązanie sensownie działało, możesz użyć, jak masz w poleceniu, programowania dynamicznego.

Jeśli nie wiesz jak to zrobić albo Ci nie będzie wychodzić to pytaj, ale wrzuć wtedy przy okazji kod który stworzysz próbując.

@Tezcatlipoca: Tą funkcję z rekurencją, którą mi podrzuciłeś mam już opracowaną. Kolejnym etapem miało być przekształcenie tego kodu stosując programowanie dynamiczne. Efekty moich dotychczasowych poczynań znajdziesz w pierwszym poście. Poczytam jeszcze o tej metodzie, bo przyznam, że bardzo się nie zagłębiałem w temat i spróbuje jeszcze coś wymodzić. Aha i co konkretnie się dzieje w trzecim przypadku - dodajemy przekątne, a później dzielimy ich wartość przez 2? No i o co według Ciebie chodzi w tym zadaniu? Powoli zaczynam się gubić. Dzięki za odzew.

@MarekR22: zgadza się, poziom nauczania matematyki (i nie tylko) jest teraz na żenującym poziomie, sam jestem tego przykładem. Dodam jeszcze, że miałem takiego pecha, że akurat mój rocznik był pierwszym rocznikiem, który podchodził do nowej matury. Jako, że nikt wcześniej nie przykładał większej uwagi do matmy (mowa bardziej o nauczycielach), tak w ciągu półtora roku chcieli nadrobić całe cztery lata materiału, a wyszło jak wyszło. Ci bardziej zaradni pracowali w domu, na własną rękę i jakoś sobie dali radę, inni zaś (w tym ja) sobie odpuścili i teraz są tego skutki.

Musisz odwrócić podejście i zamiast liczyć 'od końca' liczysz 'od początku' - czyli od najprostszych rozwiązań które później łączysz otrzymując bardziej skomplikowane wyniki które później łączysz, itd aż do wyniku końcowego. Taka ewolucja :>.

Wyobraź sobie że masz tablicę w której przechowujesz wartości funkcji M dla wszystkich i w <0;iMax) oraz j w <0; jMax). Wyglądałaby mniej więcej tak:

? 1 1 1 1 1
0 \ \ \ \ \
0 \ \ \ \ \
0 \ \ \ \ \
0 \ \ \ \ \

Oznaczmy przez X szukaną wartość:

? 1 1 1 1 1
0 \ \ \ \ \
0 \ \ \ \ \
0 \ \ \ \ \
0 \ \ \ \ X

Nie możemy jej od razu niestety obliczyć... Możemy jednak zaznaczyć jeszcze kilka pól w poszukiwaniu natchnienia:

? 1 1 1 1 1
0 A B \ \ \
0 C D \ \ \
0 \ \ \ \ \
0 \ \ \ \ X

Zauważ że pola A możesz bez problemu od razu obliczyć, bo 'powyżej' i 'na lewo' masz stałe. Wtedy staje się cud - pole B i C też możesz wyliczyć od razu bo masz już wszystkie potrzebne dane. I kolejny cud następuje - nagle możesz obliczyć D (oraz dwa inne, nieoznaczone pola). I tak dalej, aż do pola X które jest twoim celem. Proste :>.

Kod pokazujący co mam na myśli (może gdzieś być błąd składniowy albo off-by-one, nie testowałem go ale powinno być ok):

float M(int iMax, int jMax)
{
	// naiwne podejście, alokowanie tablicy i wypełnianie jej od zera za każdym razem. W praktyce lepiej prawdopodobnie by ją było gdzieś przechowywać.
        // użyłem floatów bo z intami ta funkcja nie ma sensu
	float **array = alloc_2d_array(iMax + 1, jMax + 1);
	
	for(int i = 1; i <= iMax; i++)
	{
		// pola spełniające warunek i > 0 i j == 0
		array[i][0] = 1;
	}
	
	for(int j = 1; j <= jMax; j++)
	{
		// pola spełniające warunek i == 0 i j > 0
		array[0][j] = 0;
	}
	
	for(int i = 1; i <= iMax; i++)
	{
		for(int j = 1; j <= jMax; j++)
		{
			// reszta pól.
			// invariant: za każdym razem podczas obliczania pola (i, j), pola (i-1, j) i (i, j-1) są już obliczone
			array[i][j] = (array[i-1][j] + array[i, j-1]) / 2;
		}
	}
	
	// zwracamy obliczony wynik;
	return array[iMax][jMax];
}

@Tezcatlipoca: Można powiedzieć, że mniej więcej zrozumiałem co miałeś na myśli. W sumie to odwaliłeś resztę roboty za mnie.

Dzięki panowie za pomoc, lecą plusiki czy co tu macie :)