Giúp đỡ bài tập về đệ quy

e đang học về phần đệ quy, mọi người xem giúp e bài này vs
Dãy {an} được cho dưới dạng công thức truy hồi

an = 2an-1 + an-2;

a0 = 1, a1 = 2;

Lập chương trình in ra màn hình n phần tử đầu theo 2 cách:

C1: Lập hàm đệ quy a(n) để xác định số hạng thứ n

C2 Dùng mảng 1 chiều để lưu trữ các phần tử của dãy

int recursive(int n) {
     if (n == 0) return 1;
     else if (n == 1) return 2;
     return 2*recursive(n-1) + recursive(n-2);
}

3 Likes
int find(int n) {
	if (n == 0) {
		return 1;
	}
    int[] arr = new int[n + 1];
	arr[0] = 1; arr[1] = 2;
	for (int i = 2; i < arr.length; i++) {
		arr[i] = 2 * arr[i - 1] + arr[i - 2];
	}
	return arr[n];
}
3 Likes

Cách 3, không cần dùng mảng, cũng không cần đệ quy. :slight_smile:

int find(const int n) {
  if (n == 0) return 1;
  if (n == 1) return 2;
  int i = 1, j = 2;
  for (int k = 1; k < n; k++) {
    j = 2 * j + i;
    i = (j - i) / 2;
  }
  return j;
}
3 Likes

Xài thẳng công thức CodeCogsEqn

https://rextester.com/RYA77507

#include <boost/multiprecision/gmp.hpp>
#include <iostream>

template <class T, size_t SqrtIntegerValue>
struct SqrtSum {
    T rp = T(0); // rational part
    T ip = T(0); // irrational part
    SqrtSum(T rp, T ip = T(0)) : rp(rp), ip(ip) {}
    SqrtSum operator+(const SqrtSum& rhs) const
    {
        return {rp + rhs.rp, ip + rhs.ip};
    }
    SqrtSum& operator*=(const SqrtSum& rhs)
    {
        T temp = rp * rhs.rp + ip * rhs.ip * SqrtIntegerValue;
        ip = rp * rhs.ip + ip * rhs.rp;
        rp = temp;
        return *this;
    }
    SqrtSum operator*(SqrtSum rhs) const { return rhs *= *this; }
};

template <class T, size_t V>
auto pow(SqrtSum<T, V> a, size_t p)
{
    SqrtSum<T, V> res = T(1);
    for (; p; p >>= 1, a *= a)
        if (p & 1)
            res *= a;
    return res;
}

int main()
{
    using rational_t = boost::multiprecision::mpq_rational;
    auto fNth = [](auto u, auto v, auto a, auto b) {
        return [=](size_t n) { return (a * pow(u, n) + b * pow(v, n)).rp; };
    };
    
    auto f = [&](size_t n) {
        using S2 = SqrtSum<rational_t, 2>;
        return fNth(S2(1, 1), S2(1, -1), S2({2, 4}, {1, 4}),
                    S2({2, 4}, {-1, 4}))(n);
    };
    for (size_t n = 0; n <= 25; ++n)
        std::cout << n << "\t" << f(n) << "\n";

    auto fibo = [&](size_t n) {
        using S5 = SqrtSum<rational_t, 5>;
        return fNth(S5({1, 2}, {1, 2}), S5({1, 2}, {-1, 2}), S5(0, {1, 5}),
                    S5(0, {-1, 5}))(n);
    };
    for (size_t n = 0; n <= 25; ++n)
        std::cout << n << "\t" << fibo(n) << "\n";
}

:horse::horse::horse:

5 Likes

giải thích rõ cho e về đoạn code này với

Dùng phép thế đại số nào :smiley:

2 Likes

i là ak - 2, j là ak - 1.

ak = 2ak - 1 + ak - 2 = 2j + i.

Gán j = ak.

Để tương đương với j mới thì i phải là ak - 1 và bằng (ak - ak - 2) / 2. (Theo giả thuyết)

Hay i = (j - i) / 2.

Lặp như vậy n - 1 lần thì j sẽ là an. :slight_smile:

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