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

Đề tài: Không dùm đệ qui,không dùm mảng tạm

  1. #1
    Ngày gia nhập
    12 2007
    Bài viết
    2

    Mặc định Không dùm đệ qui,không dùm mảng tạm

    Với mỗi n>=1, số Yn được tính như sau:
    Y1 = 3, Y2 = 4, Y3 = 5
    Yn = 3Yn-1 + 4Yn-2 + 5Yn-3 nếu n>=4.
    Viết hàm tính Yn không dùm đệ qui mà cũng không dùng mảng để lưu các giá trị tạm.
    ----------
    Viết bằng đệ qui thì em viết được còn không dùm đệ qui thì em không biết phải viết ra sao, anh chị có lòng tốt giúp em với... thank rất nhiều

  2. #2
    Ngày gia nhập
    11 2010
    Bài viết
    589

    Lại dạng bài cũ:
    C++ Code:
    1. #include <iostream>
    2. template<int N>
    3.    struct Y {
    4.           enum {value = 3*Y<N-1>::value+4*Y<N-2>::value + 5*Y<N-3>::value};
    5.     };
    6.  
    7. template <>
    8.     struct Y<3> {
    9.            enum {value = 5};
    10.     };
    11.  
    12. template <>
    13.     struct Y<2> {
    14.            enum {value = 4};
    15.     };
    16.  
    17. template <>
    18.     struct Y<1> {
    19.            enum {value = 3};
    20.     };
    21.  
    22. int main() {
    23.     std::cout << Y<10>::value << std::endl;
    24.     return 0;
    25. }

    Tìm trên forum với từ khoá template metaprogramming sẽ thấy nhiều cái liên quan;


    Code trên là cách nhanh nhất khi N đã biết lúc compile-time, còn nếu N chưa biết thì vẫn phải dùng 3 biến tạm để tính Y4,Y5 ... YN.
    C++ Code:
    1. unsigned Y(unsigned n) {
    2.     if(n==0) return -1; // ko hop le
    3.     else if(n==1) return 3;
    4.     else if(n==2) return 4;
    5.     else if(n==3) return 5;
    6.  
    7.     unsigned a = 3, b = 4, c=5; // bien tam de luu gia tri day y
    8.     unsigned max_loop = (n/3)*3; // so nhat chia het cho 3, vi ta se tinh tung bo 3 so lan luot
    9.     foo(int i = 4; i <= max_loop;i+=3) {
    10.         a = 3*c+4*b+5*a; // a bay gio la y_3k+1
    11.         b = 3*a+4*c+5*b;
    12.         c = 3*b+4*a+5*c;
    13.     }
    14.     switch(n-max_loop) {
    15.     case 0:    return c; break;
    16.     case 1:    
    17.          a = 3*c+4*b+5*a;
    18.          return a;
    19.          break;
    20.     case 2:    
    21.          a = 3*c+4*b+5*a;
    22.          b = 3*a+4*c+5*b;
    23.          return b;
    24.          break;
    25.      }
    26.      return 0;
    27. }
    Đã được chỉnh sửa lần cuối bởi boss14420 : 10-12-2011 lúc 08:25 AM.

  3. #3
    Ngày gia nhập
    04 2010
    Bài viết
    1,534

    Làm theo phương pháp trực tiếp, không phân tích tối ưu hóa công thức:

    C Code:
    1. // (tôi tự đóng các dấu ngoặc, vì chủ đề không cho rõ vị trí các dấu ngoặc)
    2. // code tính Y(1) = 3, Y(2) = 4, Y(3) = 5
    3. // Yn = 3Y(n-1) + 4Y(n-2) + 5Y(n-3) nếu n>=4.
    4.  
    5. int Y = 0;
    6. if (n == 1) Y = 3;
    7. else if (n == 2) Y = 4;
    8. else if (n == 3) Y = 5;
    9. else
    10. {
    11.   for (int i=4, Yb1 = 5, Yb2 = 4, Yb3 = 3; i <= n; i++, Yb3 = Yb2, Yb2 = Yb1, Yb1 = Y)
    12.     Y = 3*Yb1 + 4*Yb2 + 5*Yb3;
    13. }

  4. #4
    Ngày gia nhập
    10 2011
    Bài viết
    552

    Thêm 1 cách nữa:
    Làm theo cách giải hệ thức truy hồi, tìm công thức của nó rồi return 1 phát xong thôi
    Um Mani Padme Hum...!!

  5. #5
    Ngày gia nhập
    12 2007
    Bài viết
    2

    thank anh chị nhiều, em sẽ ngâm cứu, nếu không hiểu mong anh chị giúp đỡ thêm.

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

  1. Lập trình C++ coi dùm minh bài code sai ở chỗ nào và sữa dùm mình với
    Gửi bởi hchuy94 trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 4
    Bài viết cuối: 02-09-2013, 10:16 AM
  2. Lập trình C tìm lỗi dùm em với
    Gửi bởi dammelaptrinh trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 2
    Bài viết cuối: 20-12-2011, 12:23 AM
  3. Nhớ mấy anh đánh giá dùm CV của em
    Gửi bởi tomahutbui trong diễn đàn Thắc mắc chung
    Trả lời: 6
    Bài viết cuối: 10-06-2011, 06:01 PM
  4. Mình mới vừa học lập trình ,xin fix lỗi dùm mình và cho mình hỏi 1 vải điều .
    Gửi bởi ANHCHANG60GIAY trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 9
    Bài viết cuối: 30-04-2010, 11:40 AM
  5. xem dùm bài đệ quy t=x^n??
    Gửi bởi #include# trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 6
    Bài viết cuối: 10-04-2008, 11:41 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