Đệ Quy Trong C++ – Techacademy

Đệ quy trong C + + là 1 phương pháp vô cùng quan trọng và là cơ sở của rất rất phong phú thuật toán. Vì vậy, hiểu được đệ quy sẽ giúp bạn thuận tiện tiếp cận và học hỏi thêm nhiều kỹ năng và kiến thức khác về lập trình. Trong bài viết ngày này, Techacademy sẽ san sẻ với những bạn tất tần tật mọi thứ về đệ quy cùng với những bài tập đệ quy có giải thuật cụ thể để giúp bạn hiểu rõ hơn về nó nữa đấy !

I. Đệ Quy Trong C + + Là Gì

Đệ quy trong C + + là quy trình trong đó một phương pháp gọi lại chính nó một cách liên tục. Một hàm trong C + + gọi lại chính nó được gọi là phương pháp đệ quy. Trong một hàm đệ quy sẽ gồm có điều kiện kèm theo dừng và lời gọi hàm đệ quy, cú pháp đơn cử như sau :

Kiểu_trả_về   Tên_hàm (Các_tham_số)
{ 
    Điều_kiện_dừng;

    return Tên_hàm (Các_tham_số_mới) ;
    // hoặc một biểu thức có chứa lời gọi hàm.
}

Để giúp bạn dễ tưởng tượng hơn thì dưới đây sẽ là ví dụ về hàm đệ quy giúp tính giai thừa của 1 số ít tự nhiên :

long long Giaithua(int n)
{
    if (n==0 || n==1)
       return 1;
    else
       return Giaithua(n-1) * n;
}

Giải thích thuật toán: Ở đây, điều kiện dừng chính là n=0 hoặc là n=1 thì sẽ trả về giá trị là 1 ( Do 0!=1!=1). Ngược lại, nếu n>1, hàm sẽ trả về n*Giaithua(n-1). Chẳng hạn ta cho n nhận giá trị là 3, chương trình sẽ thực thi như sau:

GiaiThua(3) 
GiaiThua(2) 
GiaiThua(1) 
return 1 
return 2*1 = 2 
return 3*2 = 6

Vậy mục tiêu của hàm đệ quy là chia yếu tố thành những yếu tố nhỏ hơn cho đến lúc đạt được điều kiện kèm theo cơ bản. Lưu ý quan trọng khi dùng đệ quy là bắt buộc phải có điều kiện kèm theo dừng, nếu không có thì sẽ làm hàm gọi hàm liên tục không có điểm dừng và dẫn đến chương trình không hề kết thúc được .

II. Cách Sử Dụng Đệ Quy Trong C + +

Trong C + +, một hàm gọi chính nó ta gọi đó là hàm đệ quy, nghĩa là trong thân hàm sẽ gọi đến chính tên hàm hiện tại và truyền đúng những tham số mà hàm đã khai báo .
Cú pháp : Cú pháp của hàm đệ quy trong C + + như sau :

HamDeQuy(){    
      HamDeQuy();  //goi lai chinh no
}

Ví dụ : Chúng ta cùng xem một ví dụ đơn thuần về hàm đệ quy trong C + + đó là tính giai thừa của một số ít nguyên .
Trước khi giải bài toán tính giai thừa của 1 số ít nguyên trong C + + tất cả chúng ta cùng nhớ lại công thức tính giai thừa trong toán học trước đã nhé .
Theo định nghĩa giai thừa ta có :

• 0! = 1
• n! = 1 * 2 * 3 * … * n

Vậy là ta đã có công thức tính giai thừa của 1 số ít nguyên rồi. Nếu n = 0 thì giai thừa bằng 1. Nếu n > 0 thì giai thừa sẽ là tích từ 1 đến n. Và không có giai thừa của số âm .

Giải bằng vòng lặp For

Trước khi đi vào giải bài toán trên bằng hàm đệ quy, mình sẽ giải bằng vòng lặp for trong C + + trước nhé .
Ví dụ

#include  
using namespace std;
int main()   
{    
    int n;
    while(true) {
        int giaithua = 1;
        cout << "Nhap so n: ";
        cin >> n;
         
        //Nhap n nho hon 0 de thoat khoi vong lap
        if(n < 0) {
            cout << "  So am khong co giai thua" << endl;
            break;
        }
 
        if ( n > 0) {
            for(int i = 1; i <=n; i++) {
                giaithua = giaithua * i;
            }
        }
        cout << "  Giai thua cua " << n << " la: " << giaithua << endl;
 
    }
    return 0;  
}

Và hiệu quả sau khi thực thi chương trình trên như sau :

Như vậy, để xử lý bài toán giai thừa của một số ít bằng vòng lặp for trong C + + rất đơn thuần phải không những bạn ? Bây giờ mình sẽ giải bài toán giai thừa trên bằng hàm đệ quy trong C + + .

Giải bằng đệ quy C++

Các bạn chú ý kỹ thì thấy thuật toán tính giai thừa sẽ như sau : Giả sử cần tính 5 !, lúc này quy luật của nó sẽ là .

• 5! = 4! * 5
• 4! = 3! * 4
• 3! = 2! * 3
• 2! = 1! * 2
• 1! = 1

Thay những vế vào ta sẽ được quy luật : 5 ! = 1 * 2 * 3 * 4 * 5 .
Giả sử ta có hàm tính gian thừa của một số ít tên là GT, lúc này thay vào công thức trên ta được như sau :

• GT(5) = GT(4) * 5
• GT(4) = GT(3) * 4
• GT(3) = GT(2) * 3
• GT(2) = GT(1) * 2
• GT(1) = 1

Vậy, ta hoàn toàn có thể vận dụng giải thuật đệ quy C + + để xử lý, bằng cách bên trong thân hàm sẽ gọi đến chính hàm đó .
Ví dụ

#include  
using namespace std;
int GiaiThua(int n) {
    // Trường hợp người dùng nhập
    if (n == 1)
        return 1;
    else
        return (n * GiaiThua(n - 1));
}
 
int main()   
{    
    int n;
    while(true) {
        cout << "Nhap so n: ";
        cin >> n;
        //Nhap n nho hon 0 de thoat khoi vong lap
        if(n < 0) {
            cout << "  So am khong co giai thua" << endl;
            break;
        }
        cout << "  Giai thua cua " << n << " la: " << GiaiThua(n) << endl;
    }
    return 0;  
}

Và hiệu quả sau khi thực thi chương trình trên như sau :

Đối với những bạn mới khởi đầu học lập trình thì cách giải bài toán giai thừa trên bằng vòng lặp for sẽ dễ hiểu hơn rất nhiều so với việc giải bằng hàm đệ quy. Tuy nhiên, những bạn đừng quá lo ngại, mình sẽ lý giải đoạn code cho những bạn bạn dễ hiểu .
Giả sử mình nhập n = 5 thì chương trình trên sẽ chạy như sau :

GiaiThua(5) 
   GiaiThua(4) 
      GiaiThua(3) 
         GiaiThua(2) 
            GiaiThua(1) 
               return 1 
            return 2*1 = 2 
         return 3*2 = 6 
      return 4*6 = 24 
   return 5*24 = 120

Mục đích của hàm đệ quy là chia yếu tố thành những yếu tố nhỏ hơn cho đến khi đạt được điều kiện kèm theo cơ bản .
Ví dụ trong chương trình giai thừa ở trên, tất cả chúng ta đang xử lý hàm giai thừa GiaiThua ( n ) bằng cách gọi hàm giai thừa nhỏ hơn GiaiThua ( n-1 ), điều này được tái diễn liên tục cho đến khi giá trị n đạt đến điều kiện kèm theo cơ sở ( GiaiThua ( 1 ) = 1 ) .

III. Đệ Quy Quay Lui Trong C + +

Quay lui là 1 kĩ thuật phong cách thiết kế giải thuật dựa trên đệ quy. Ý tưởng của quay lui là tìm giải thuật từng bước, mỗi bước chọn một trong số những lựa chọn khả dĩ và đệ quy. Người tiên phong đề ra thuật ngữ này ( backtrack ) là nhà toán học người Mỹ D. H. Lehmer vào những năm 1950 .

Tư tưởng

Dùng để giải bài toán liệt kê những thông số kỹ thuật. Mỗi thông số kỹ thuật được kiến thiết xây dựng bằng từng thành phần. Mỗi thành phần lại được chọn bằng cách thử hàng loạt những năng lực .
Các bước trong việc liệt kê cấu hình dạng X [ 1 … n ] :

• Xét tất cả các giá trị X[1] có thể nhận, thử X[1] nhận những giá trị đó. Với mỗi giá trị của X[1] ta sẽ:
• Xét đa số giá trị X[2] có thể nhận, lại thử X[2] cho các giá trị đó. Với mỗi giá trị X[2] lại xét khả năng giá trị của X[3]…tiếp tục như vậy cho đến bước:
• …
• …
• Xét tất cả giá trị X[n] có thể nhận, thử cho X[n] nhận lần lượt giá trị đó.
• Thông báo cấu hình tìm được.

Bản chất của quay lui là một quy trình tìm kiếm theo chiều sâu ( Depth-First Search ) .

Mô hình thuật toán

• Mã giả cho thuật toán quay lui.

Backtracking(k) {
   for([Mỗi phương án chọn i(thuộc tập D)]) {
      if ([Chấp nhận i]) {
         [Chọn i cho X[k]];
         if ([Thành công]) {
            [Đưa ra kết quả];
         } else {
            Backtracking(k+1);
            [Bỏ chọn i cho X[k]];
         }
      }
   }
}

Ví dụ : Trò chơi Sudoku

Sudoku là một game show khá thông dụng và chắc ai cũng biết. Trò chơi như sau : có một hình vuông vắn được chia thành 9 × 9 ô vuông con. Mỗi ô vuông con có giá trị trong khoảng chừng từ 1 đến 9. Ban đầu hình vuông vắn có 1 số ít ô vuông con cho trước ( có điền sẵn số ) và còn lại là trống. Hãy điền những số từ 1-9 vào những ô con lại sao cho : hàng ngang là những số khác nhau từ 1 đến 9, hàng dọc là những số khác nhau từ 1 đến 9, và mỗi khối 3 × 3 chính là những số khác nhau từ 1 đến 9. Sau đây là 1 ví dụ về đề bài và giải thuật :

Áp dụng quay lui để giải bài toán sudoku. Ý tưởng : Mỗi bước tìm tập những giá trị khả dĩ để điền vào ô trống, và sau đó đệ quy để điền ô tiếp theo. Giả mã của thuật toán ( ở đây chú ý quan tâm mảng chỉ có size 9 × 9 × 9 )

void solveSudoku(int S[][9], int x, int y){
    if(y == 9){
        if(x == 8){
            printSolution(S);
            exit(0);
        } else {
            solveSudoku(S, x+1,0);
        }
    } else if(S[x][y] == 0){
        for (int k = 1; k <=9; k++){
            if(checkValid(S,x,y,k)){
                S[x][y] = k;
                solveSudoku(S, x, y+1);
                S[x][y] = 0;
            }
        }
    } else {
        solveSudoku(S,x,y+1);
    }
}

boolean checkValid(int S[][9], int x, int y, int k){
    for(int i = 0; i <9 ; i++){
        if(S[x][i] == k) return false;
    }
    for(int i = 0; i <9 ; i++){
        if(S[i][y] == k) return false;
    }
    int a = x/3, b = y/3;
    for(int i = 3*a; i < 3*a+3; i++){
        for(int j = 3*b; j < 3*b+3; j++){
            if(S[i][j] == k) return false;
        }
    }
    return true;
}

Nhận xét

Ưu điểm : Việc quay lui là thử tổng thể những tổng hợp để tìm được một lời giải. Thế mạnh của giải pháp này là nhiều thiết lập tránh được việc phải thử nhiều trường hợp chưa hoàn hảo, nhờ đó giảm thời hạn chạy .
Nhược điểm : Trong trường hợp xấu nhất độ phức tạp của quay lui vẫn là cấp số mũ. Vì nó mắc phải những điểm yếu kém sau :

• Rơi vào tình trạng “thrashing”: qúa trình tìm kiếm cứ gặp phải bế tắc với cùng một nguyên nhân.
• Thực hiện các công việc dư thừa: Mỗi lần chúng ta quay lui, chúng ta cần phải đánh giá lại lời giải trong khi đôi lúc điều đó không cần thiết.
• Không sớm phát hiện được các khả năng bị bế tắc trong tương lai. Quay lui chuẩn, không có cơ chế nhìn về tương lai để nhận biết đc nhánh tìm kiếm sẽ đi vào bế tắc.

IV. Bài Tập Đệ Quy Quay Lui Trong C + +

+ Tìm Ước Chung Lớn Nhất Và Bội Chung Nhỏ Nhất Bằng Đệ Quy

Hàm đệ quy là những hàm gọi lại chính nó. Nó hữu dụng trong những tác vụ như sắp xếp hoặc đo lường và thống kê những số giai thừa … Hàm đệ quy tương ứng với khái niệm quy nạp trong toán học .

Bài tập 1. Thuật toán Euclide tìm ước chung lớn nhất

Viết chương trình tìm ước chung lớn nhất của 2 số nguyên dương a, b bằng thuật toán. Euclide được định nghĩa đệ quy như sau :
[Cài đặt:]

#include 
#include 
int UCLN(int a, int b) {
if(a==b)
return a;
else if(a>b)
return UCLN(a-b,b);
else
return UCLN(a,b-a);
}
void main() {
clrscr();
int a,b;
cout<<"Nhap a = ";
cin>>a;
cout<<"Nhap b = ";
cin>>b;
cout<<"Uoc chung lon nhat cua "<
[ Cài đặt : ]
Bài tập 2. Tìm ước chung lớn nhất của n số nguyên
Viết chương trình tìm ước chung lớn nhất của n số nguyên dương 0 1, …, n  a a được định nghĩa đệ quy như sau :
[Cài đặt:]
#include 
#include 
/*Ham tra ve uoc chung lon nhat cua a va b*/
int UCLN(int a, int b) {
if(a==b)
return a;
else if(a>b)
return UCLN(a-b,b);
else
return UCLN(a,b-a);
}
/*Ham tra ve uoc chung lon nhat cua n phan tu duoc luu tru trong mang 1 chieu a*/
int UC(int a[], int n) {
if(n==1)
return a[0];
else
return UCLN(a[n-1],UC(a,n-1));
}
void main() {
clrscr();
int *a,n;
cout<<"Nhap n = ";
cin>>n;
a = new int[n];
cout<<"Nhap vao "<
+ Đệ Quy Fibonacci Trong C + +
[ Cài đặt : ]Chắc những bạn cũng đã biết dãy Fibonacci là gì rồi. Đó là dãy số mà số tiếp theo là tổng của hai số liền trước, ví dụ : 1, 1, 2, 3, 5, 8, 13, …. Bài viết này sẽ hướng dẫn cho những bạn cách tính số fibonacci bằng chiêu thức dùng đệ quy và không dùng đệ quy .
Dùng đệ quy để tính số fibonacci
Công thức truy hồi của dãy fibonacci có dạng : f ( n ) = f ( n-1 ) + f ( n-2 ) .
Với f ( 1 ) = 1 ; f ( 2 ) = 1 ;
Cách tính số Fibonacci trong C
 
#include 
#include 
int Fibonacci(int n)
{
    if (n == 1 || n == 2)
        return 1;
    return Fibonacci(n - 1) + Fibonacci(n - 2);
}
int main()
{
    int n;
    printf("nhap n: ");
    scanf("%d", &n);
    printf("So Fibonacci thu %d la: %d", n, Fibonacci(n));
    return 0;
}

 
nhap n: 6
So Fibonacci thu 6 la: 8

Cách tính số Fibonacci trong C + +
 
#include 
using namespace std;
int Fibonacci(int n)
{
    if (n == 1 || n == 2)
        return 1;
    return Fibonacci(n - 1) + Fibonacci(n - 2);
}
int main()
{
    int n;
    cout << "nhap n: ";
    cin >> n;
    cout << "So Fibonacci thu " << n << " la: " << Fibonacci(n);
    return 0;
}

 
nhap n: 6
So Fibonacci thu 6 la: 8

Khi đã có hệ thức truy hồi thì việc viết hàm đệ quy rất đơn thuần phải không nào ? Nhưng liệu bạn có thử nhập n lớn ( cỡ 30 – 40 ) không ạ. Nếu thử rồi thì chắc những bạn cũng thấy nó chậm hơn rất nhiều. Nguyên nhân là khi tính số fibonacci thứ 5 chương trình sẽ nhu yếu tính hai số fibonacci thứ 4 và thứ 3. Nó lại liên tục như vậy đến khi tính được số fibonacci thứ 2 hoặc thứ 1 mới dừng lại .



Vậy nếu muốn chương trình của tất cả chúng ta chạy nhanh hơn thì tất cả chúng ta phải khử đệ quy. Cùng làm nhé !
Cách tính số Fibonacci không dùng đệ quy
Ý tưởng cách này là tất cả chúng ta sẽ dùng một vòng lặp để tính số Fibonacci .

Nếu n = 1 hoặc n = 2 thì chúng ta return 1
Sau đó tạo một biến i có giá trị bằng 3
Trong vòng while chúng ta tính a = a1 + a2
Sau đó gán a1 = a2 và a2 = a cứ chạy đến khi nào i = n thì dừng

 
#include 
int Fibonacci(int n)
{
    int a1 = 1, a2 = 1;
    if (n == 1 || n == 2)
        return 1;
    int i = 3, a;
    while (i <= n)
    {
        a = a1 + a2;
        a1 = a2;
        a2 = a;
        i++;
    }
    return a;
}
int main()
{
    int n;
    printf("nhap n: ");
    scanf("%d", &n);
    printf("So Fibonacci thu %d la: %d", n, Fibonacci(n));
    return 1;
}

 
nhap n: 40
So Fibonacci thu 40 la: 102334155

Cách tính số Fibonacci trong C + +
 
#include 
using namespace std;
int Fibonacci(int n)
{
    int a1 = 1, a2 = 1;
    if (n == 1 || n == 2)
        return 1;
    int i = 3, a;
    while (i <= n)
    {
        a = a1 + a2;
        a1 = a2;
        a2 = a;
        i++;
    }
    return a;
}
int main()
{
    int n;
    cout << "nhap n: ";
    cin >> n;
    cout << "So Fibonacci thu " << n << " la: " << Fibonacci(n);
    return 1;
}

nhap n: 40
So Fibonacci thu 40 la: 102334155

Tìm 1000 số Fibonacci đầu tiên
Với code trên bạn tìm đến số Fibo thứ 50 là bị tràn số rồi. Code với số nguyên lớn dưới đây sẽ giúp bạn tính được số Fibo thứ 1000 hoặc hơn thế nữa. Có thể bạn sẽ cần đọc bài viết dưới đây trước khi tìm hiểu thêm code này .

Lời giải cho chương trình in ra 1000 số Fibo tiên phong .
 
#include 
using namespace std;
 
const int base = 1000000000;
const int base_digits = 9;
struct bigint
{
    vector a;
    int sign;
 
    bigint() : sign(1)
    {
    }
 
    bigint(long long v)
    {
        *this = v;
    }
 
    bigint(const string &s)
    {
        read(s);
    }
 
    void operator=(const bigint &v)
    {
        sign = v.sign;
        a = v.a;
    }
 
    void operator=(long long v)
    {
        sign = 1;
        if (v < 0)
            sign = -1, v = -v;
        for (; v > 0; v = v / base)
            a.push_back(v % base);
    }
 
    bigint operator+(const bigint &v) const
    {
        if (sign == v.sign)
        {
            bigint res = v;
 
            for (int i = 0, carry = 0; i < (int)max(a.size(), v.a.size()) || carry; ++i)
            {
                if (i == (int)res.a.size())
                    res.a.push_back(0);
                res.a[i] += carry + (i < (int)a.size() ? a[i] : 0);
                carry = res.a[i] >= base;
                if (carry)
                    res.a[i] -= base;
            }
            return res;
        }
        return *this - (-v);
    }
 
    bigint operator-(const bigint &v) const
    {
        if (sign == v.sign)
        {
            if (abs() >= v.abs())
            {
                bigint res = *this;
                for (int i = 0, carry = 0; i < (int)v.a.size() || carry; ++i)
                {
                    res.a[i] -= carry + (i < (int)v.a.size() ? v.a[i] : 0);
                    carry = res.a[i] < 0;
                    if (carry)
                        res.a[i] += base;
                }
                res.trim();
                return res;
            }
            return -(v - *this);
        }
        return *this + (-v);
    }
 
    void operator*=(int v)
    {
        if (v < 0)
            sign = -sign, v = -v;
        for (int i = 0, carry = 0; i < (int)a.size() || carry; ++i)
        {
            if (i == (int)a.size())
                a.push_back(0);
            long long cur = a[i] * (long long)v + carry;
            carry = (int)(cur / base);
            a[i] = (int)(cur % base);
            //asm("divl %%ecx" : "=a"(carry), "=d"(a[i]) : "A"(cur), "c"(base));
        }
        trim();
    }
 
    bigint operator*(int v) const
    {
        bigint res = *this;
        res *= v;
        return res;
    }
 
    friend pair divmod(const bigint &a1, const bigint &b1)
    {
        int norm = base / (b1.a.back() + 1);
        bigint a = a1.abs() * norm;
        bigint b = b1.abs() * norm;
        bigint q, r;
        q.a.resize(a.a.size());
 
        for (int i = a.a.size() - 1; i >= 0; i--)
        {
            r *= base;
            r += a.a[i];
            int s1 = r.a.size() <= b.a.size() ? 0 : r.a[b.a.size()];
            int s2 = r.a.size() <= b.a.size() - 1 ? 0 : r.a[b.a.size() - 1];
            int d = ((long long)base * s1 + s2) / b.a.back();
            r -= b * d;
            while (r < 0)
                r += b, --d;
            q.a[i] = d;
        }
 
        q.sign = a1.sign * b1.sign;
        r.sign = a1.sign;
        q.trim();
        r.trim();
        return make_pair(q, r / norm);
    }
 
    bigint operator/(const bigint &v) const
    {
        return divmod(*this, v).first;
    }
 
    bigint operator%(const bigint &v) const
    {
        return divmod(*this, v).second;
    }
 
    void operator/=(int v)
    {
        if (v < 0)
            sign = -sign, v = -v;
        for (int i = (int)a.size() - 1, rem = 0; i >= 0; --i)
        {
            long long cur = a[i] + rem * (long long)base;
            a[i] = (int)(cur / v);
            rem = (int)(cur % v);
        }
        trim();
    }
 
    bigint operator/(int v) const
    {
        bigint res = *this;
        res /= v;
        return res;
    }
 
    int operator%(int v) const
    {
        if (v < 0)
            v = -v;
        int m = 0;
        for (int i = a.size() - 1; i >= 0; --i)
            m = (a[i] + m * (long long)base) % v;
        return m * sign;
    }
 
    void operator+=(const bigint &v)
    {
        *this = *this + v;
    }
    void operator-=(const bigint &v)
    {
        *this = *this - v;
    }
    void operator*=(const bigint &v)
    {
        *this = *this * v;
    }
    void operator/=(const bigint &v)
    {
        *this = *this / v;
    }
 
    bool operator<(const bigint &v) const
    {
        if (sign != v.sign)
            return sign < v.sign;
        if (a.size() != v.a.size())
            return a.size() * sign < v.a.size() * v.sign;
        for (int i = a.size() - 1; i >= 0; i--)
            if (a[i] != v.a[i])
                return a[i] * sign < v.a[i] * sign;
        return false;
    }
 
    bool operator>(const bigint &v) const
    {
        return v < *this;
    }
    bool operator<=(const bigint &v) const
    {
        return !(v < *this);
    }
    bool operator>=(const bigint &v) const
    {
        return !(*this < v);
    }
    bool operator==(const bigint &v) const
    {
        return !(*this < v) && !(v < *this);
    }
    bool operator!=(const bigint &v) const
    {
        return *this < v || v < *this;
    }
 
    void trim()
    {
        while (!a.empty() && !a.back())
            a.pop_back();
        if (a.empty())
            sign = 1;
    }
 
    bool isZero() const
    {
        return a.empty() || (a.size() == 1 && !a[0]);
    }
 
    bigint operator-() const
    {
        bigint res = *this;
        res.sign = -sign;
        return res;
    }
 
    bigint abs() const
    {
        bigint res = *this;
        res.sign *= res.sign;
        return res;
    }
 
    long long longValue() const
    {
        long long res = 0;
        for (int i = a.size() - 1; i >= 0; i--)
            res = res * base + a[i];
        return res * sign;
    }
 
    friend bigint gcd(const bigint &a, const bigint &b)
    {
        return b.isZero() ? a : gcd(b, a % b);
    }
    friend bigint lcm(const bigint &a, const bigint &b)
    {
        return a / gcd(a, b) * b;
    }
 
    void read(const string &s)
    {
        sign = 1;
        a.clear();
        int pos = 0;
        while (pos < (int)s.size() && (s[pos] == '-' || s[pos] == '+'))
        {
            if (s[pos] == '-')
                sign = -sign;
            ++pos;
        }
        for (int i = s.size() - 1; i >= pos; i -= base_digits)
        {
            int x = 0;
            for (int j = max(pos, i - base_digits + 1); j <= i; j++)
                x = x * 10 + s[j] - '0';
            a.push_back(x);
        }
        trim();
    }
 
    friend istream &operator>>(istream &stream, bigint &v)
    {
        string s;
        stream >> s;
        v.read(s);
        return stream;
    }
 
    friend ostream &operator<<(ostream &stream, const bigint &v)
    {
        if (v.sign == -1)
            stream << '-';
        stream << (v.a.empty() ? 0 : v.a.back());
        for (int i = (int)v.a.size() - 2; i >= 0; --i)
            stream << setw(base_digits) << setfill('0') << v.a[i];
        return stream;
    }
 
    static vector convert_base(const vector &a, int old_digits, int new_digits)
    {
        vector p(max(old_digits, new_digits) + 1);
        p[0] = 1;
        for (int i = 1; i < (int)p.size(); i++)
            p[i] = p[i - 1] * 10;
        vector res;
        long long cur = 0;
        int cur_digits = 0;
        for (int i = 0; i < (int)a.size(); i++)
        {
            cur += a[i] * p[cur_digits];
            cur_digits += old_digits;
            while (cur_digits >= new_digits)
            {
                res.push_back(int(cur % p[new_digits]));
                cur /= p[new_digits];
                cur_digits -= new_digits;
            }
        }
        res.push_back((int)cur);
        while (!res.empty() && !res.back())
            res.pop_back();
        return res;
    }
 
    typedef vector vll;
 
    static vll karatsubaMultiply(const vll &a, const vll &b)
    {
        int n = a.size();
        vll res(n + n);
        if (n <= 32)
        {
            for (int i = 0; i < n; i++)
                for (int j = 0; j < n; j++)
                    res[i + j] += a[i] * b[j];
            return res;
        }
 
        int k = n >> 1;
        vll a1(a.begin(), a.begin() + k);
        vll a2(a.begin() + k, a.end());
        vll b1(b.begin(), b.begin() + k);
        vll b2(b.begin() + k, b.end());
 
        vll a1b1 = karatsubaMultiply(a1, b1);
        vll a2b2 = karatsubaMultiply(a2, b2);
 
        for (int i = 0; i < k; i++)
            a2[i] += a1[i];
        for (int i = 0; i < k; i++)
            b2[i] += b1[i];
 
        vll r = karatsubaMultiply(a2, b2);
        for (int i = 0; i < (int)a1b1.size(); i++)
            r[i] -= a1b1[i];
        for (int i = 0; i < (int)a2b2.size(); i++)
            r[i] -= a2b2[i];
 
        for (int i = 0; i < (int)r.size(); i++)
            res[i + k] += r[i];
        for (int i = 0; i < (int)a1b1.size(); i++)
            res[i] += a1b1[i];
        for (int i = 0; i < (int)a2b2.size(); i++)
            res[i + n] += a2b2[i];
        return res;
    }
 
    bigint operator*(const bigint &v) const
    {
        vector a6 = convert_base(this->a, base_digits, 6);
        vector b6 = convert_base(v.a, base_digits, 6);
        vll a(a6.begin(), a6.end());
        vll b(b6.begin(), b6.end());
        while (a.size() < b.size())
            a.push_back(0);
        while (b.size() < a.size())
            b.push_back(0);
        while (a.size() & (a.size() - 1))
            a.push_back(0), b.push_back(0);
        vll c = karatsubaMultiply(a, b);
        bigint res;
        res.sign = sign * v.sign;
        for (int i = 0, carry = 0; i < (int)c.size(); i++)
        {
            long long cur = c[i] + carry;
            res.a.push_back((int)(cur % 1000000));
            carry = (int)(cur / 1000000);
        }
        res.a = convert_base(res.a, 6, base_digits);
        res.trim();
        return res;
    }
};
 
int main()
{
    bigint first, second, temp;
    first = 1;
    second = 1;
    int i = 3;
    cout << 1 << " " << first << "\n";
    cout << 2 << " " << second << "\n";
    while (i < 1000)
    {
        i++;
        temp = first + second;
        cout << i << " " << temp << "\n";
        first = second;
        second = temp;
    }
}

Dưới đây là giá trị của số Fibo thứ 1000 :
 
26863810024485359386146727202142923967616609318986952340123175997617981700247881689338369654483356564191827856161443356312976673642210350324634850410377680367334151172899169723197082763985615764450078474174626

+ In Đảo Ngược Một Số Nguyên Dương N
Hướng dẫn cách tìm số đảo ngược trong C. Bạn sẽ học được cách tạo hàm tìm số đảo ngược trong C sau bài học kinh nghiệm này .
Bài toán tìm số đảo ngược trong C
Tìm số đảo ngược trong C là bài toán nhập vào một số ít nguyên dương n từ bàn phím. In ra số đảo ngược của số n vừa nhập .

Ví dụ tất cả chúng ta nhập số 1234 thì sẽ thu về số 4321 ví dụ điển hình .

Mặc dù không không có ý nghĩa về mặt ứng dụng nhưng đây là một bài toán cơ bản vô cùng hay giúp tất cả chúng ta rèn luyện lập trình bằng ngôn từ C .
Tìm số đảo ngược trong C
Cách tìm số đảo ngược trong C rất đơn thuần, tất cả chúng ta viết lại từng hàng trong số theo thứ tự ngược lại là xong .

Vậy thì tất cả chúng ta sẽ viết ngược như thế nào ?

Giả sử số đã cho là n = 1234. Chúng ta hoàn toàn có thể trình diễn số này dưới dạng tổng những lũy thừa của 10 như sau :
n = 1x104 + 2x103 + 3x102 + 4x101
Để màn biểu diễn số này theo cách ngược lại, tất cả chúng ta sẽ giữ nguyên phần lũy thừa của 10 và viết ngược lại từng chữ số trong tổng như sau :
n = 4x104 + 3x103 + 2x102 + 1x101
Để tìm ra được từng chữ số trong hàng thập phân như trên, tất cả chúng ta sẽ chia lần lượt số đã cho cho những lũy thừa của 10 để tìm phần dư là xong .

Chúng ta sẽ sử dụng vòng lặp while và viết hàm để triển khai giải quyết và xử lý đảo ngược số ở trên như sau :
/*Hàm tìm số đảo ngược trong C*/
int reverse_num(int n){ 
  int reverse = 0; 
  while (n > 0) {
    reverse = reverse * 10 + n % 10;
    n /= 10;
  }
  return reverse;
}
Chúng ta hoàn toàn có thể gọi hàm này và sử dụng trong chương trình nhập vào 1 số ít nguyên dương n từ bàn phím. In ra số đảo ngược của số n vừa nhập trong C như sau :
#include 

/*Hàm tìm số đảo ngược trong C*/
int reverse_num(int n){ 
  int reverse = 0; 
  while (n > 0) {
    reverse = reverse * 10 + n % 10;
    n /= 10;
  }
  return reverse;
}

int main(void){
    int n;
 
    printf(">> nhap mot so nguyen duong: ");
    scanf("%d",&n);

    int result = reverse_num(n);
    printf("So dao nguoc: %d\n",result );

    return 0;
}
Màn hình nhập liệu và hiệu quả tìm số đảo ngược trong C sẽ như sau :
>> nhap mot so nguyen duong: 1234
So dao nguoc: 4321

>> nhap mot so nguyen duong: 23456789
So dao nguoc: 98765432

+ In Ra Dạng Nhị Phân Của Số Nguyên Dương N
Chắc hẳn ai học về giải thuật cũng đã từng nghe qua và làm về bài toán đưa ra chuỗi nhị phân độ dài N rồi, nếu bạn mới mở màn học hoặc đã bỏ lỡ qua bài toán mê hoặc này thì cũng đừng lo, vì trong bài viết này mình sẽ ra mắt cho toàn bộ những bạn về bài toán này nhé .
Chuỗi nhị phân là gì?
Khái niệm về chuỗi nhị phân

Hệ nhị phân ( hay hệ đếm cơ số hai hoặc mã nhị phân ) là một hệ đếm dùng hai ký tự để miêu tả một giá trị số, bằng tổng số những lũy thừa của 2. Hai ký tự đó thường là 0 và 1, chúng thường được dùng để miêu tả hai giá trị hiệu điện thế tương ứng ( có hiệu điện thế, hoặc hiệu điện thế cao là 1 và không có, hoặc thấp là 0 ). Do có ưu điểm thống kê giám sát đơn thuần, thuận tiện triển khai về mặt vật lý, ví dụ điển hình như trên những mạch điện tử, hệ nhị phân trở thành một phần thiết kế cơ bản trong những máy tính đương thời .

Ví dụ 0, 1, 0000, 0001, 010101, 00011100 là những chuỗi nhị phân

Bài toán đưa ra chuỗi nhị phân độ dài N
Chắc hẳn ai học về giải thuật cũng đã từng nghe qua và làm về bài toán đưa ra chuỗi nhị phân độ dài N rồi, nếu bạn mới bắt đầu học hoặc đã bỏ lỡ qua bài toán thú vị này thì cũng đừng lo, vì ngay bây giờ mình sẽ giới thiệu về nó nhé.

Xem thêm: Đa hình trong Lập trình hướng đối tượng | How Kteam 

Bài toán đơn cử như sau :

Nhập vào một số ít nguyên dương N ( 1 ≤ N ≤ 20 ) hãy đưa ra tổng thể những chuỗi nhị phân độ dài N, một chuỗi ghi trên một dòng, những chuỗi được sắp xếp từ bé đến lớn theo thứ tự từ điển ,

Ví dụ 1 :



Input
Output


1
0

1



Ví dụ 2 :



Input
Output


2
00

01

10

11



Ví dụ 3 :



Input
Output


3
000

001

010

011

100

101

110

111



Bài toán khá là mê hoặc đúng không nào, đã có ai có sáng tạo độc đáo làm bài này chưa ? hãy thử làm nó nhé, nếu bạn đã làm xong hoặc chưa biết làm thì cũng xem thử mình đã giải quyết và xử lý bài toán này bằng cách nào nhé .
Một số thuật toán đưa ra chuỗi nhị phân độ dài N
Biến đổi số thành chuỗi nhị phân

Thực chất những chuỗi nhị phân độ dài N lần lượt là màn biểu diễn nhị phân của những số thập phân từ 0 đến 2N-1 .

Ví dụ 0 = 0 ( 2 ), 1 = 1 ( 2 ), 2 = 10 ( 2 ), 7 = 111 ( 2 ) .

Việc cần làm của tất cả chúng ta rất đơn thuần đó là chỉ cần quy đổi những số tự nhiên từ 0 đến 2N-1 sang chuỗi nhị phân là được ( quan tâm nhớ chèn những ký tự ‘ 0 ’ vào những chuỗi nhị phân để độ dài của chuỗi nhị phân đủ N ) .

Để chuyển 1 số ít tự nhiên sang chuỗi nhị phân ta hoàn toàn có thể làm như sau :


string decToBin(int n){
    string ans = "";
    while (n > 0) {
        ans = char (n % 2 + '0') + ans;
        n /= 2;
    }
    while (ans.length() < N)
        ans = "0" + ans;
    return ans;
}
Ta sẽ chia N cho 2 cho đến khi tác dụng bằng 0, mỗi lần chia như vậy ta lưu lại số dư của N cho 2, chuỗi nhị phân của N chính là chuỗ số dư được đọc ngược .

Source code :
#include 
#include 
 
using namespace std;
 
int N;
 
string decToBin(int n){
    string ans = "";
    while (n > 0) {
        ans = char (n % 2 + '0') + ans;
        n /= 2;
    }
    while (ans.length() < N)
        ans = "0" + ans;
    return ans;
}
 
int main(){
    cin >> N;
    int N_2 = pow(2, N);
    for (int i = 0; i < N_2; i++)
        cout << decToBin(i) << endl;
}
Đệ quy quay lui

Với bài này ta hoàn toàn có thể dùng chiêu thức đệ quy, hiểu đơn thuần là tất cả chúng ta cần dùng N vòng for lồng nhau, mỗi vòng for biến chạy sẽ chạy từ 0 đến 1 .

giải pháp này để những bạn rèn luyện đệ quy rất tốt, nhưng mình không khuyến khích những bạn dùng đệ quy trong khi nó hoàn toàn có thể làm theo cách khác nha .

Source code :
#include 
 
using namespace std;
 
int N;
 
int x[100];
 
void in(int x[]){
    for (int i = 1; i <= N; i++)
        cout << x[i];
    cout << endl;
}
 
void deQuy(int i){
    for (int j = 0; j <= 1; j++){
        x[i] = j;
        if (i == N)
            in(x);
        else
            deQuy(i + 1);
        
    }
}
 
int main(){
    cin >> N;
    deQuy(1);
}
Phương pháp sinh

Ta thấy rằng nếu lấy lần lượt những chuỗi nhị phân độ dài N – 1, sau đó thêm ký tự 0 hoặc 1 vào cuối chuỗi đó, ta sẽ được 2 chuỗi nhị phân độ dài N .

Ví dụ như những chuỗi nhị phân độ dài 2 có những chuỗi là “ 00 ”, “ 01 ”, “ 10 ”, “ 11 ” .

Với chuỗi “ 00 ” khi ta thêm vào cuối nó ký tự ‘ 0 ’ hoặc ‘ 1 ’ ta có chuỗi “ 000 ” và “ 001 ” .

Tương tự với chuỗi “ 01 ” ta sẽ có chuỗi “ 010 ” và “ 011 ” .

Tương tự với chuỗi “ 10 ” ta sẽ có chuỗi “ 100 ” và “ 101 ” .

Tương tự với chuỗi “ 11 ” ta sẽ có chuỗi “ 110 ” và “ 111 ” .

Như vậy chỉ cần 2 ký tự “ 0 ” và “ 1 ” ta hoàn toàn có thể sinh ra những chuỗi nhị phân độ dài N .

Source code :
#include 
#include 
 
using namespace std;
 
int N;
 
string a[100009];
 
int main(){
    cin >> N;
    int n = 2;
    a[0] = "0";
    a[1] = "1";
    int k = 0;
    while (a[k].length() < N){
        a[n++] = a[k] + "0";
        a[n++] = a[k] + "1";
        k++;
    }
    for (int i = k; i < n; i++)
        cout << a[i] << endl;
}
Tìm chuỗi nhị phân tiếp theo

Với chiêu thức này ta sẽ tìm chuỗi nhị phân tiếp theo khi biết được chuỗi nhị phân trước đó, ví dụ tiếp theo của chuỗi “ 101 ” là “ 110 ”, tiếp theo của “ 111 ” là “ 1000 ”, vậy là sao làm được như vậy .

Cách làm sẽ là với chuỗi nhị phân S, để tìm chuỗi nhị phân tiếp theo của S ta sẽ làm như sau .

– Tìm vị trí index là vị trí của bit khác ‘ 0 ’ sau cuối của S .

– Thay thì bit thứ index từ ‘ 0 ’ thành ‘ 1 ’ .

– Biến đổi toàn bộ bit ‘ 1 ’ thành ‘ 0 ’ từ vì trí index + 1 đến hết chuỗi .

Ví dụ :

Với chuỗi S = “ 10011 ”, thì ta có bit bằng ‘ 0 ’ ở đầu cuối là bit thứ 3, ta biến hóa bit 3 thành 1 và bit 4, bit 5 thành 0, ta sẽ được chuỗi nhị phân tiếp theo của S là “ 10100 ” .

Source code :
#include 
#include 
 
using namespace std;
 
int N;
 
string next(string s){
    for (int i = s.length() - 1; i >= 0; i--)
        if (s[i] == '0'){
            s[i] = '1';
            return s;
        } else
            s[i] = '0';
    return "";
}
 
int main(){
    cin >> N;
    string s = "";
    for (int i = 0; i < N; i++)
        s = "0" + s;
    for (int i = 0; i < pow(2, N); i++){
        cout << s << endl;
        s = next(s);
    }
}
+ Tính N Giai Thừa Trong C / C + + Bằng Đệ Quy Và Khử Đệ Quy
Bài viết san sẻ thuật toán và cách tính n giai thừa trong C / C + sử dụng hai chiêu thức đệ quy và khử đệ quy. Một bài toán hay dành cho những bạn học lập trình .
Giới thiệu bài toán
Giai thừa là một bài toán tầm cỡ trong lập trình, nó là một bài toán mà mình tin là bất kỳ bạn nào mới học đều phải trải qua. Bài toán này sẽ giúp bạn hiểu được thuật toán đệ quy hoặc sử dụng thành thạo vòng lặp .

Đề bài đại loại hoàn toàn có thể tóm tắt lại như sau : Tính n giai thừa và in tác dụng ra màn hình hiển thị, n nhập vào từ bàn phím .

Trước khi xử lý bài toán, tất cả chúng ta cần hiểu định nghĩa về n ! ( n là một số ít nguyên dương ) : n giai thừa là tích của n số nguyên dương tiên phong .

Công thức tổng quát : n ! = n * ( n-1 ) !

Trường hợp đặc biệt quan trọng : 0 ! = 1


Tính giai thừa sử dụng vòng lặp
Cách tính tiên phong này sẽ đơn thuần hơn cách sử dụng đệ quy. Và nó được gọi là cách khử đệ quy chính do nó tránh được việc phải dùng đến đệ quy. Tùy từng trường hợp mà đệ quy và khử đệ quy có ưu điểm khác nhau .

Tư tưởng xử lý :

Khai báo một biến để lưu giá trị và gán nó bằng 1: giai_thua = 1

Sử dụng vòng lặp chạy i từ 1 đến n sau đó gán : giai_thua = giai_thua * i

Code C / C + + :
// giai thua su dung vong lap
int giaithualap(int n){
    int giai_thua = 1;
    for (int i = 1; i <= n; i++)
        giai_thua = giai_thua * i;
    return giai_thua;
}
Tính giai thừa sử dụng đệ quy

Để hiểu rõ hơn thuật toán này thứ nhất bạn nên tìm hiểu và khám phá thuật toán đệ quy .

Ở bài này, ta có công thức tổng quát n giai thừa là : n ! = n * ( n-1 ) !

Chính do đó, ta cũng sử dụng lệnh truy hồi dựa trên công thức này .

Điều kiện dừng ở đây là khi n = 1 ( vì ta tính tích những số mở màn từ 1 )

Code C / C + + :
// tinh giai thua su dung de quy
int factorial(int n){
    if(n==1)
        return 1;
    return(n*factorial(n-1));
}
Đánh Ngân sách chi tiêu 2 cách : Cách sử dụng đệ quy để tính giai thừa có vẻ như chuyên nghiệp hơn. Tuy nhiên cách sử dụng vòng lặp có vận tốc nhanh không kém đệ quy, thậm trí là nhanh hơn .

Trong cách bài toán thực tiễn, nếu để lựa chọn thì những lập trình viên sẽ sử dụng cách 1 để hạn chế tối thiểu việc sử dụng đệ quy .

Chú ý : Ở đây kiểu tài liệu của hàm mình để là kiểu int, chính cho nên vì thế chỉ hoàn toàn có thể chạy khi n < = 19 ( nếu quá thì sẽ vượt size của kiểu int dẫn đến sai hiệu quả ). Nếu bạn muốn chạy được số lớn hơn thì nên để kiểu double ( max n 170 ) .
Code full bài toán nhập N và tính đệ quy :


/*  Bai toan tinh N giai thua trong C++
    By: https://duongdinh24.com/
    github: https://github.com/duongdinh24/
*/
#include
using namespace std;
// n! su dung de quy
int factorial(int n){
    if(n==1)
        return 1;
    return(n*factorial(n-1));
}
// nn! Khu de quy su dung vong lap
int giaithualap(int n){
    int giai_thua = 1;
    for (int i = 1; i <= n; i++)
        giai_thua = giai_thua * i;
    return giai_thua;
}
int main(){
    int n;
    cout<<"Nhap n: "; cin>>n;
    cout<<"Ket qua "<
Click to rate this post !
[Total: 
0
Xem thêm: Tại sao cần vẽ lưu đồ giải thuật (Flow Chart ) khi lập trình
  Average: 0]

Source: https://final-blade.com
Category : Kiến thức Internet