• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

Algorytm znajdowania liczby dla funkcji (programowanie dynamiczne) - początkujący

VPS Starter Arubacloud
0 głosów
606 wizyt
pytanie zadane 14 listopada 2018 w C i C++ przez Adrian10B Nowicjusz (120 p.)
Cześć, potrzebuję nakierowania na rozwiązanie tego problemu. Mam kilka zadań do zrobienia do szkoły, z jednym już sobie poradziłem, ale tkwię nad tymi poniżej i nie mogę ruszyć z miejsca. Nie chcę gotowych rozwiązań bo nie w tym rzecz. Brakuje mi czasu i nie mogę nawet poszukać pomocy naukowej więc myślę, że prościej będzie tutaj. Jeśli macie jakieś ciekawe linki lub może sami jesteście w stanie podpowiedzieć jak ugryźć to zadanie to będę wdzięczny.

Funkcja f(i, j) określona jest wzorami:
f(0, 0) = 1
f(i, 0) = 0, f(i, i) = 1 dla i = 1, 2, ...
f(i, j) = i * f(i - 1, j) + j * f(i - 1, j - 1) dla i > 1 oraz 1 =< j =< (i - 1)
Podaj algorytm znajdowania dla danego n oraz k (0 =< k =< n) liczby f(n, k) wykorzystujący metodę programowania dynamicznego.

Myślałem, żeby zrobić to w pętli while, określić w niej warunki podane wyżej i następnie obliczać funkcję dla wczytanego z klawiatury f(n,k), ale jako że dopiero zaczynam przygodę z programowaniem to nie wiem czy to w ogóle dobry pomysł i czy da się to w ten sposób wykonać. Potrzebuję natchnienia, pomysłu, a dalej już polecę sam :) (Uczę się pseudokodów, ale praktykuję trochę w C++ )

1 odpowiedź

0 głosów
odpowiedź 14 listopada 2018 przez Maciej Złotorowicz Gaduła (4,230 p.)

problem jest natury rekurencyjnej. zalecam poważnie zaznajomić się z tematem i go zrozumieć ponieważ jest to bardzo ważne zagadnienie. W teorii wygląda to tak:
 

f(x){
if(x == 0){
return 1;
}else{
return f(x-1);
}
}

Oczywiście nie jest to rozwiązanie twojego problemu ale metoda na jego rozwiązanie.
I takie zagnieżdżanie funkcji jest możliwe.
https://www.youtube.com/watch?v=jNi_X5bvmQ0
https://pl.wikipedia.org/wiki/Rekurencja
jeżeli potrzebujesz więcej pomocy to pisz. 

komentarz 14 listopada 2018 przez Adrian10B Nowicjusz (120 p.)

Dzięki za zaangażowanie :) Generalnie to wpadłem na ten pomysł ale z uwagi na to, że jestem żółtodziobem to jestem niemal pewien, że robię masę błędów w implementacji. Poniżej zamieszczam co udało mi się wyskrobać. Bijcie jeśli trzeba, ważne żebym się tego nauczył i zrozumiał. Niestety nikt inny mi nie pomoże.

 

#include <iostream>

using namespace std;

int f(int i,int j)
{
    if (i>0,j=0)
    {
        f(0,0)==1;
        f(i,j)==0;
        f(i,i)==1;
       // int tab[i][j];
    }

    else if (i>1 && (i-1)>=j>=1)
    {
        f(i,j) == i*f(i-1,j) + j*f(i-1,j-1);
    }

}

Czy napisałem to poprawnie? Jeśli nie to gdzie jest błąd i drugie pytanie, jak wyrzucić to na ekran dla danego n i k w funkcji main jak już rozwiążę problem? bo tam mam błąd z wywołaniem funkcji f(). Na razie nazewnictwo nie ma znaczenia chcę tylko rozwiązać problem algorytmu i później to już tylko kosmetyka. Teach me master.

komentarz 14 listopada 2018 przez Maciej Złotorowicz Gaduła (4,230 p.)

jest tu kilkanaście błędów. przede wszystkim mylisz operatory porównanie (==) to nie to samo co przypisanie (=)  f(0,0)== 1; f(i,j)==0; f(i,i)==1; zwróci ci wartość logiczną a nie przypisze, dodatkowo (i>0,j=0) nic nie znaczy nie da sie zrobić takiego warunku musisz użyć jakiegoś operatora (and && lub or ||). na twoim miejscu to po wałkował bym jeszcze składnie C++ bo ostro kuleje. nawet z głupich poradników na internecie. Za wyjście wejście ja zwykle służy cin>>  i cout <<

int f(int i, int j) {
    if (i == 0 && j == 0) {
        return 1;
    }
    if (i == j) {
        return 1;
    }
    if (j == 0) {
        return 0;
    }
    if (i > 1) {
        return i * f(i - 1, j) + j * f(i - 1, j - 1);
    }
}

Tak może wyglądać implementacja funkcji. Sprawdź w internecie jeszcze raz co to funkcja i rekurencja. 

komentarz 14 listopada 2018 przez niezalogowany
W odpowiedz brakuje wzmianki, że funkcją rekurencyjną trzeba będzie zamienić na tablicę.
komentarz 15 listopada 2018 przez Adrian10B Nowicjusz (120 p.)

Cześć,

zanim odpisaliście na moje bzdury to złapałem się za głowę widząc co napisałem. Faktycznie źle się zabrałem do tego. Usunąłem wszystko i napisałem od początku. Przyjąłem taką koncepcję, że dopóki nie wiem jak to zrobić, to napiszę do tego rekurencję, żeby sprawdzać wyniki i wrzucę ją w osobną funkcję. Udało mi się napisać coś takiego (mam wrażenie, że napisałem to dobrze, ale sprawdźcie proszę):

#include <iostream>

using namespace std;
int tab [n][k];

int f(int n,int k)
{
	if (n==k) 
		return 1;
	
	if (n>0 $$ k==0) 
		return 0;
	
	if (n>0 $$ 1<=k $$ k<=n-1)
		return n*f(n-1,k)+k*f(n-1, k-1);
	
}

int main()
{
	if (n==k) return 1;
	if (n>0 $$ k==0) return 0;

I mam kilka dodatkowych pytań. Jak wrzucić to wszystko w tablicę, pętlami for? I czy tablica powinna być globalna czy wrzucić ją do funkcji?

Na ten moment mam rekurencję i wpisałem warunki podstawowe w funkcji main żeby od razu dla tych wartości zwracało 1 i 0 tak jak jest przyjęte w założeniach.

Przyznam, że ciężko mi idzie ogarnięcie tego zadania.

komentarz 15 listopada 2018 przez Adrian10B Nowicjusz (120 p.)
Zamiast && wpisałem $$, ale to nie jest przedmiotem mojej zagwozdki :)
komentarz 15 listopada 2018 przez Maciej Złotorowicz Gaduła (4,230 p.)

@Adrian10B, O jakiej tablicy mówisz? czy chcesz aby wszystkie możliwe kombinacje wyników znalazły się w tablicy? jeżeli tak to wystarczy to zrobić 2 for'ami i w środku dać przypisanie:
tab[i][j] = f(i,j);
Swoją drogą to nie musisz pisać warunków w pętli aby przyspieszyć działanie - wywoływanie funkcji jest tak szybkie że spadek wydajności jest zaniedbywany.

komentarz 16 listopada 2018 przez Adrian10B Nowicjusz (120 p.)
Chodzi mi o to, że rekurencja, którą napisałem ma tylko sprawdzać wyniki, a rozwiązanie zadania ma być przy użyciu techniki dynamicznego programowania. Rekurencja nie jest dynamiczna ale pozwala szybko rozwiązać problem. Ja mam problem z tą drugą częścią. Nie wiem czy teraz zrobić pętlę, zainicjować dwuwymiarową tablicę iterowaną petlą for i wkładać do niej wyniki, a potem wywołać wynik dla danego f(n,k) wskaźnikiem z tablicy? Czy to dobre rozwiązanie?

Podobne pytania

+1 głos
1 odpowiedź 417 wizyt
+1 głos
2 odpowiedzi 3,716 wizyt
pytanie zadane 5 czerwca 2017 w C i C++ przez Koper Początkujący (310 p.)
0 głosów
2 odpowiedzi 887 wizyt

92,453 zapytań

141,262 odpowiedzi

319,087 komentarzy

61,854 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Akademia Sekuraka

Akademia Sekuraka 2024 zapewnia dostęp do minimum 15 szkoleń online z bezpieczeństwa IT oraz dostęp także do materiałów z edycji Sekurak Academy z roku 2023!

Przy zakupie możecie skorzystać z kodu: pasja-akademia - użyjcie go w koszyku, a uzyskacie rabat -30% na bilety w wersji "Standard"! Więcej informacji na temat akademii 2024 znajdziecie tutaj. Dziękujemy ekipie Sekuraka za taką fajną zniżkę dla wszystkich Pasjonatów!

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...