Khử đệ quy bằng Stack java bị lỗi

#1

Em làm một đoạn code khử đệ quy Fibonaci bằng Stack và bị lỗi, mọi người xem giúp em với ạ. Em cảm ơn.

public static int Fibona(int n) {
	Stack < Integer > X =  new Stack< Integer >();
	int sum = 0 ;
	X.push(n);
	while(!X.isEmpty()) {
		if(X.pop()>2) {
			X.push(n-2);
			X.push(n-1);   // Lỗi ở dòng này (Dòng này không có lỗi đỏ ạ.).
			}
		else
			sum++;
		}
	return sum;
}
#2

Không rành java nhưng làm thế này thử xem


public static int Fibona(int n) {
	Stack < Integer > X =  new Stack< Integer >();
	int sum = 0 ;
        int lay_ra=0;// of me
	X.push(n);
	while(!s.isEmpty()) {
		if(X.pop()>2) {
                        lay_ra=X.pop();//of me
                        sum+=lay_ra;//of me
			X.push(n-2);
			X.push(n-1);   // Lỗi ở dòng này (Dòng này không có lỗi đỏ ạ.).
		}
		//else
			//sum++;
		//}
        }//end while
	return sum;
}

Phản hồi nếu thành công nhá, xem như phước chủ may thầy!!! :joy:

1 Like
#3

không chạy được rồi ạ .

#4

có bị loop (lặp vô tận) không bạn?
Bạn phải xem chừng khi push, nó push số âm không?
Chớ cái đoạn khử đệ qui đó là kinh điển rồi đấy!!!

Giải thuật của bạn hình như không chính xác
phải
X.push(lay_ra-2)…:joy:


public static int Fibona(int n) {
	Stack < Integer > X =  new Stack< Integer >();
	int sum = 0 ;
        int lay_ra=0;// of me
	X.push(n);
	while(!s.isEmpty()) {
                lay_ra=X.pop();
		//if(X.pop()>2) {
                if(lay_ra >2) { 
                        //lay_ra=X.pop();//of me
                        sum+=lay_ra;//of me
			X.push(lay_ra-2);
			X.push(lay_ra-1);   // Lỗi ở dòng này (Dòng này không có lỗi đỏ ạ.).
		}
		//else
			//sum++;
		//}
        }//end while
	return sum;
}
#5

Bài này làm cái gì đây bạn

#6

Bắt buộc phải là Stack hay chỉ cần khử được đệ quy là được?

Nếu chỉ cần khử đệ quy thì:

Javascript 
fib = function(n){ // Đệ quy
  if(n<=1) return 1;
  return fib(n-1)+fib(n-2);
}
fib2 = function(n){ // Khử đệ quy
  var a = 0;
  var b = 1;
  var s = 0;
  for(var i = 1; i <= n; i++){
    s = a+b;
    a = b;
    b = s;
  }
  return s;
}

console.log(fib(5),fib2(5));
document.write("fib1: "+fib(5)+"<br/>fib2: "+fib2(5));
#7

Làm như vầy thì được rồi ạ, nhưng kết quả thì bị sai ạ.

#8

Tính tổng các số fibonaci nhỏ hơn n.

#9

Làm phải bằng Stack ạ

#10

Bài này dùng stack có vẻ không cần thiết lắm

1 Like
#11

Đúng vậy, thậm chí có thể dùng hai công thức nhân đôi O(logn) phép tính :smiley: chẳng qua là để làm bài khử đệ quy nhị phân thôi.

Để ý rằng hướng làm của thớt không hẳn là mô phỏng 100% (kết quả cũng đưa lên stack), mà là dùng chính ct truy hồi T(0) = 0, T(1) = 1 (thớt chưa làm đc), T(n) = T(n-1) + T(n-2).

1 Like
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?