Từ 1 tới 9 trên tổng số 9 kết quả

Đề tài: Sử dụng Stack để khử đệ quy fibonaci?

  1. #1
    Ngày gia nhập
    06 2011
    Bài viết
    5

    Mặc định Sử dụng Stack để khử đệ quy fibonaci?

    Cho dãy số được định nghĩa như sau.
    f(n) = 1 nếu n=0 hay n=1.
    f(n) = f(n-1) + f(n-2) nếu n>1.

    Hãy viết hàm không đệ quy để tính giá trị của f(n), với n được nhập từ bàn phím. Sừ dụng Stack để khử đệ quy.

  2. #2
    Ngày gia nhập
    01 2011
    Nơi ở
    -Mountain-
    Bài viết
    768

    Trích dẫn Nguyên bản được gửi bởi phanxuanbanglhu Xem bài viết
    Cho dãy số được định nghĩa như sau.
    f(n) = 1 nếu n=0 hay n=1.
    f(n) = f(n-1) + f(n-2) nếu n>1.

    Hãy viết hàm không đệ quy để tính giá trị của f(n), với n được nhập từ bàn phím. Sừ dụng Stack để khử đệ quy.
    f (0) = 1, f (1) = 1;
    ---> push (0), push (1) vào stack
    if (i = 0 hoặc i = 1) thì f (..) = 1;
    else
    for (int i = 2; i < n; i ++)
    ---> lấy a1, a2 ra khỏi stack cộng lại ra a3
    --->push (a2), push(a3) vào stack

    -------> kết quả cần tìm
    Hướng dẫn C++: https://www.youtube.com/watch?v=BwLodoQdoY4&list=PL1c9Uxlo-mplJDRGdONNupgo5OCBTyGGn

  3. #3
    Ngày gia nhập
    12 2009
    Nơi ở
    The country of happiness
    Bài viết
    182

    C++ Code:
    1.  
    2. #include<iostream>
    3. #include<cstdio>
    4. #include<sstream>
    5. #include<string>
    6. #include<cstring>
    7. #include<map>
    8. #include<set>
    9. #include<queue>
    10. #include<stack>
    11. #include<vector>
    12. #include<algorithm>
    13. #include<cmath>
    14. #include<cstdlib>
    15. #include<bitset>
    16. using namespace std;
    17.  
    18. typedef long long ll;
    19. #define INF 2023456789
    20. #define EPS 1e-11
    21. #define FOR(i,a,b) for(int i = a; i < b; ++i)
    22. #define REP(i,a,b) for(int i = a; i <= b; ++i)
    23. #define FORD(i,a,b) for(int i = a; i >= b; --i)
    24.  
    25.  
    26. int gcd(int x, int y) {
    27.     return y == 0 ? x : gcd(y, x % y);
    28. }
    29.  
    30. int n;
    31. stack<int> st;
    32.  
    33. void read() {
    34.     cin >> n;
    35. }
    36.  
    37. void init() {
    38.     st.push(1);
    39.     st.push(1);
    40. }
    41.  
    42. void solve() {
    43.     int fi_0, fi_1, fi_2;
    44.     REP(i,2,n){
    45.  
    46.         fi_0 = st.top();
    47.         st.pop();
    48.  
    49.         fi_1 = st.top();
    50.         st.pop();
    51.  
    52.         fi_2 = fi_0 + fi_1;
    53.  
    54.         st.push(fi_0);
    55.         st.push(fi_2);
    56.  
    57.         //cout << fi_2 << endl;
    58.     }
    59.  
    60.     cout << st.top();
    61. }
    62.  
    63. int main() {
    64.  
    65. #ifndef ONLINE_JUDGE
    66.     freopen("in.txt", "r", stdin);
    67.     // freopen("out.txt", "w", stdout);
    68. #endif
    69.  
    70.     read();
    71.     init();
    72.     solve();
    73.  
    74. }

    File "in.txt" :
    Code:
     5
    Out :
    Code:
     8
    Trích dẫn Nguyên bản được gửi bởi Wazi Armstrong Xem bài viết
    Ôi skill của mình đã đạt đến hàng tuyệt đỉnh
    Không chỉ ăn, tắm, đi lại có thể code
    Mà giờ đã mình có thể code cả khi ngủ. Code tạm vào buffer của não, lúc nào dậy chỉ việc viết ra một cách trôi chảy không lưỡng lự.
    PS: Nếu ngủ dài rảnh rảnh có thể debug luôn, dậy chỉ việc build ?
    Trích dẫn Nguyên bản được gửi bởi vietanh8286 Xem bài viết
    Lập trình viên giỏi là lập trình viên có vợ

  4. #4
    Ngày gia nhập
    08 2009
    Bài viết
    6

    Mặc định Chỉ cần stack size = 2

    Rõ ràng là F(i+2) = F(i+1) + F(i) mà không cần biết giá trị của F(0) ... F(i-1) nên việc sử dụng stack với các thao tác pop, push là hơi phức tạp so với yêu cầu của bài này.
    Thực chất ta chỉ cần lưu giá trị của F(i), F(i+1) rồi tính ra F(i+2), sau đó lấy giá trị F(i+2) đè lên F(i) để "stack" lưu lại F(i+1), F(i+2) và cứ thế tính tiếp F(i+3)...

    Và vì stack chỉ có 2 ô nên ta phải lưu như sau:
    f(0) f(1) -> tính ra f(2), đè lên f(0) ~ f[0]
    f(2) f(1) -> tính ra f(3), đè lên f(1) ~ f[1]
    f(2) f(3) -> tính ra f(4), đè lên f(2) ~ f[0]
    ...
    f(i-2) f(i-1) -> tính ra f(i), đè lên f(i-2) ~ f[i % 2]

    long f[2];
    f[0] = f[1] = 1;

    if (n < 2) {
    cout << f[n];
    } else {
    for (unsigned short i = 2; i<n; ++i) {
    f[i%2] = f[0] + f[1];
    }
    cout << f[n%2];
    }

  5. #5
    Ngày gia nhập
    01 2011
    Nơi ở
    -Mountain-
    Bài viết
    768

    Trích dẫn Nguyên bản được gửi bởi chipchipknight Xem bài viết
    Rõ ràng là F(i+2) = F(i+1) + F(i) mà không cần biết giá trị của F(0) ... F(i-1) nên việc sử dụng stack với các thao tác pop, push là hơi phức tạp so với yêu cầu của bài này.
    Thực chất ta chỉ cần lưu giá trị của F(i), F(i+1) rồi tính ra F(i+2), sau đó lấy giá trị F(i+2) đè lên F(i) để "stack" lưu lại F(i+1), F(i+2) và cứ thế tính tiếp F(i+3)...

    Và vì stack chỉ có 2 ô nên ta phải lưu như sau:
    f(0) f(1) -> tính ra f(2), đè lên f(0) ~ f[0]
    f(2) f(1) -> tính ra f(3), đè lên f(1) ~ f[1]
    f(2) f(3) -> tính ra f(4), đè lên f(2) ~ f[0]
    ...
    f(i-2) f(i-1) -> tính ra f(i), đè lên f(i-2) ~ f[i % 2]

    long f[2];
    f[0] = f[1] = 1;

    if (n < 2) {
    cout << f[n];
    } else {
    for (unsigned short i = 2; i<n; ++i) {
    f[i%2] = f[0] + f[1];
    }
    cout << f[n%2];
    }
    Stack là yêu cầu của đề bài nên ta phải làm theo chứ không phải tự ý mà đề bài có vậy
    Còn nếu làm như bạn thì phức tạp thêm vấn đề ?
    Mà bạn đã test thử bài của mình chưa
    hình như f (3) = f (4) = ................. = 2
    Hướng dẫn C++: https://www.youtube.com/watch?v=BwLodoQdoY4&list=PL1c9Uxlo-mplJDRGdONNupgo5OCBTyGGn

  6. #6
    Ngày gia nhập
    08 2009
    Bài viết
    6

    Mặc định Dùng cấu trúc dữ liệu stack chứ không ai bắt dùng std::stack cả

    Code:
    #include <stdio.h>
    #include <conio.h>
    
    int main () {
    	short n;
    	scanf ("%d", &n);
    	//----------------------------
    	long f[2];
    	f[0] = f[1] = 1;
    	
    	if (n < 2) {
    	
    	    printf ("%ld", f[n]);
    	
    	} else {
    	
    	    for (unsigned short i = 2; i<=n; ++i) {
    	
    	        f[i%2] = f[0] + f[1];
    	
    	    }
    	    printf ("%ld", f[n%2]);
    	
    	}
    	//----------------------------	
    	getch();
    	return 0;
    }
    Mình code rồi chạy thử đúng rồi này!
    Cái việc f[i%2] chính là tìm vị trí top trong cái "stack" tự tạo của mình mà!

  7. #7
    Ngày gia nhập
    01 2011
    Nơi ở
    -Mountain-
    Bài viết
    768

    Mình code rồi chạy thử đúng rồi này!
    Cái việc f[i%2] chính là tìm vị trí top trong cái "stack" tự tạo của mình mà!
    Uh sorry nay không đọc kỹ
    Hướng dẫn C++: https://www.youtube.com/watch?v=BwLodoQdoY4&list=PL1c9Uxlo-mplJDRGdONNupgo5OCBTyGGn

  8. #8
    Ngày gia nhập
    05 2011
    Bài viết
    299

    @tiendaotd: hix, bài của bạn xài nhiều thư viện quá @@
    Programming tutorials and source code examples

    Trong nhà không vợ không con
    Uống bia gặm thịt sao ngon thế này
    Nhậu nhẹt không bị la rầy
    Một tuần ta cứ bảy ngày " nâng ly "....

  9. #9
    Ngày gia nhập
    12 2009
    Nơi ở
    The country of happiness
    Bài viết
    182

    Trích dẫn Nguyên bản được gửi bởi rossoneri Xem bài viết
    @tiendaotd: hix, bài của bạn xài nhiều thư viện quá @@
    bạn xóa hết đi, để lại iostream, cstdio và stack thôi.
    Trích dẫn Nguyên bản được gửi bởi Wazi Armstrong Xem bài viết
    Ôi skill của mình đã đạt đến hàng tuyệt đỉnh
    Không chỉ ăn, tắm, đi lại có thể code
    Mà giờ đã mình có thể code cả khi ngủ. Code tạm vào buffer của não, lúc nào dậy chỉ việc viết ra một cách trôi chảy không lưỡng lự.
    PS: Nếu ngủ dài rảnh rảnh có thể debug luôn, dậy chỉ việc build ?
    Trích dẫn Nguyên bản được gửi bởi vietanh8286 Xem bài viết
    Lập trình viên giỏi là lập trình viên có vợ

Các đề tài tương tự

  1. Bài tập C++ copy noi dung tu stack S sang stack D
    Gửi bởi thaodn_chuprong trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 12
    Bài viết cuối: 18-10-2012, 11:45 PM
  2. Cấu trúc dữ liệu Chuyển các phần tử từ stack này sang stack kia như thế nào?
    Gửi bởi rukawa1184 trong diễn đàn Thắc mắc CTDL & Giải thuật
    Trả lời: 9
    Bài viết cuối: 06-12-2011, 06:52 PM
  3. Stack, ngăn xếp - Thiết lập và ứng dụng stack trong C
    Gửi bởi PoPoPoPo trong diễn đàn Thủ thuật, Tutorials CTDL & Giải thuật
    Trả lời: 8
    Bài viết cuối: 15-11-2010, 11:24 PM
  4. Stack trên C | Lỗi khó hiểu trong Stack
    Gửi bởi tom3cang trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 1
    Bài viết cuối: 22-05-2009, 11:09 PM
  5. Code về stack | Chuyển hệ số 10 sang 2 dùng stack
    Gửi bởi ahappyboy89 trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 13
    Bài viết cuối: 17-04-2009, 09:48 AM

Quyền hạn của bạn

  • Bạn không thể gửi đề tài mới
  • Bạn không thể gửi bài trả lời
  • Bạn không thể gửi các đính kèm
  • Bạn không thể chỉnh sửa bài viết của bạn