Padėkit su c++ uzdavinu

Sveiki, susiduriau su idomia uzduotimi, kurios niekaip neiseina ispresti, stai salyga. Is anksto aciu.

Nurodyta skaiciu seka: a1=1, a2=-2, an = an-1 + an-2. kai n>2. Parasykite programa k-tajam sekos nariui apskaiciuoti.

Kontroliniai duomenys :

n / rezultatas

4 / -3

10 / -47

Na, su c++ nemoku, bet cia paprasta rekursija

function f(int n) {
 if (n==1) return 1;
 if (n==2) return -2;
 return f(n-1)+f(n-2);
}

f(4);

Aš taip padariau, lygtais gaunasi :)

C++

#include<iostream>
using namespace std;
int main() {
int n,ma[100];
cin >> n;
for (int i = 0; i < n; i++) {
	if (i == 0) {
		ma[i] = 1;
	}
	if (i == 1) {
		ma[i] = -2;
	}
	else if(i > 1) {
		ma[i] = ma[i-1] + ma[i-2];

	}
}
	cout << ma[n-1] << endl;
return 0;
}

Aš taip padariau, lygtais gaunasi :)

C++

#include<iostream>
using namespace std;
int main() {
int n,ma[100];
cin >> n;
for (int i = 0; i < n; i++) {
	if (i == 0) {
		ma[i] = 1;
	}
	if (i == 1) {
		ma[i] = -2;
	}
	else if(i > 1) {
		ma[i] = ma[i-1] + ma[i-2];

	}
}
	cout << ma[n-1] << endl;
return 0;
}

Sis variantas lyg ir veikia, taciau tokio tipo uzdavinius reiktu iprasti spresti rekursijos pagalba, nes tai daug stipresnis irankis.

Na, su c++ nemoku, bet cia paprasta rekursija

function f(int n) {
 if (n==1) return 1;
 if (n==2) return -2;
 return f(n-1)+f(n-2);
}

f(4);

Algoritmo logika gera, taciau O(n)=1,6^n, reiktu idet rezultatu saugojima, kad padaryt O(n)=n:

$mem = array();
function f($n) {
  global $mem;
  if ($n==1) return 1;
  if ($n==2) return -2;
  return $mem[$n] = (isset($mem[$n-1])?$mem[$n-1]:f($n-1)) + (isset($mem[$n-2])?$mem[$n-2]:f($n-2));
}

Sis variantas lyg ir veikia, taciau tokio tipo uzdavinius reiktu iprasti spresti rekursijos pagalba, nes tai daug stipresnis irankis.

Ypač tinka steko sprogdinimui, kadangi cpp neturi TCO.

Klasikinis pavyzdys parodantis koks neefektyvus gali būti paprastas rekursyvus algoritmas. Sprendimas be masyvų:

int fibClone(int n){
 if (n == 1) return 1;
 if (n == 2) return -2;
 int t1 = 1, t2 = -2, temp;
 for (int i = 2; i < n; i++){
   temp = t2;
   t2 = t2 + t1;
   t1 = temp;
 }
 return t2;
}

Klasikinis pavyzdys parodantis koks neefektyvus gali būti paprastas rekursyvus algoritmas. Sprendimas be masyvų:

int fibClone(int n){
 if (n == 1) return 1;
 if (n == 2) return -2;
 int t1 = 1, t2 = -2, temp;
 for (int i = 2; i < n; i++){
   temp = t2;
   t2 = t2 + t1;
   t1 = temp;
 }
 return t2;
}

Cia ne rekursija

Cia ne rekursija

Negali būti

Negali būti

Kad vyktu rekursija, funkcija turi kreiptis pati i save, tol kol isskaidys problema iki vietos, kai nebeimano jos skaidyt (pvz,: n==1 arba n==2).

Tavo duotam variante, tu tiesiog iskvieti funkcija, kurioje vygdai cikla - tai ne rekursija.

Ir taip, rekursija vyks O=nlogn, tik tada, kai ji tures divide-and-conquer problema (pvz. sort-merge).

Kai problema bus linijine (pvz. skaciaus kelimas laipsniu: a(n) = n * a(n-1);), O=n.

Taciau kai atsiranda daugiau patikros variantu (kaip OP uzduotyje), rekursija veikia ilgiau nei ciklas (turint 2 sakas, veiks mazdaug O=1.6^n), taciau ta galima isspresti naudojant Memoizer (http://javathink.blogspot.dk/2008/09/what-is-memoizer-and-why-should-you.html), ir siuo atveju galima pasiekti O=n.

OP problemos atveju, ciklas yra galimas sprendimas, taciau, kaip programuotojui, pirmas sprendimo budas (jei imanoma) turetu buti rekursija, nes tai daug stipresnis irankis, nei paprasti ciklai.

Klasikinis pavyzdys parodantis koks neefektyvus gali būti paprastas rekursyvus algoritmas. Sprendimas be masyvų:

int fibClone(int n){
 if (n == 1) return 1;
 if (n == 2) return -2;
 int t1 = 1, t2 = -2, temp;
 for (int i = 2; i < n; i++){
   temp = t2;
   t2 = t2 + t1;
   t1 = temp;
 }
 return t2;
}

Tai kad cia pats paprasciausias metodas su ciklu viduje, i rekurcija panasu tik escape kriterijai, viskas kitkas tiesiog loop.

Turbūt teks paaiškinti savo žinutę, nes jei jau du žmonės ją klaidingai suprato, tai jau turbūt mano kaltė :D . Pirmu sakiniu norėjau pasakyti, kad šis uždavinys dažnai yra pateikiamas kaip pavyzdys kai kalbama apie tai kokia neefektyvi gali būti rekursija. O po to eina paprasčiausias uždavinio sprendimas nenaudojant rekursijos.

OP problemos atveju, ciklas yra galimas sprendimas, taciau, kaip programuotojui, pirmas sprendimo budas (jei imanoma) turetu buti rekursija, nes tai daug stipresnis irankis, nei paprasti ciklai.

Jei įmanoma, geriau pasirinkti paprastus ciklus vietoj rekursijos. Netgi kompiliatoriai tam tikrais atvejais rekursiją išlygina iki ciklo.

Nebent reikia labai daug parametrų keisti ar tam tikru atveju rekursiškas sprendimas lengviau suvokiamas, nei su ciklu.

Jei įmanoma, geriau pasirinkti paprastus ciklus vietoj rekursijos. Netgi kompiliatoriai tam tikrais atvejais rekursiją išlygina iki ciklo.

 

Nebent reikia labai daug parametrų keisti ar tam tikru atveju rekursiškas sprendimas lengviau suvokiamas, nei su ciklu.

Tiesa, ka pasirinksi priklauso nuo problemos. Didziajai daliai programuotoju su rekursijomis beveik niekad netenka susidurti, nes ju darbe kilusios problemos yra didziaja dali tiek paprastos, kad jas isspresti su ciklais lengva. Taciau, jeigu tenka susidurti su duomenu analizavimo/ivertinimo, network/graph ar siaip sudetingesnemis problemomis - be rekurcijos daznai neissiversi, nebent nori rasyt koda, kuris ne tik bus letas ir sunkiai suvokiamas, bet ir nelankstus.

Neziurint i visa tai, turi moket su rekurcijomis dirbti, nes rimtesniuose darbuose, kur buna vertinamos tavo zinios, beveik visad praso rekurcija padaryt.

Tiesa, ka pasirinksi priklauso nuo problemos. Didziajai daliai programuotoju su rekursijomis beveik niekad netenka susidurti, nes ju darbe kilusios problemos yra didziaja dali tiek paprastos, kad jas isspresti su ciklais lengva. Taciau, jeigu tenka susidurti su duomenu analizavimo/ivertinimo, network/graph ar siaip sudetingesnemis problemomis - be rekurcijos daznai neissiversi, nebent nori rasyt koda, kuris ne tik bus letas ir sunkiai suvokiamas, bet ir nelankstus.

 

Neziurint i visa tai, turi moket su rekurcijomis dirbti, nes rimtesniuose darbuose, kur buna vertinamos tavo zinios, beveik visad praso rekurcija padaryt.

Na taip, memory-efficiency yra dzin.

Jeigu kalba neturi TCO, tai nekažką ta rekursija. O ir rekursija, naudojanti TCO, neretai būna sunkiai skaitoma.