Đệ quy trong C++ là 1 phương thức vô cùng quan trọng và là cơ sở của rất rất đa dạng thuật toán. Vì vậy, hiểu được đệ quy sẽ giúp bạn dễ dàng tiếp cận và học hỏi thêm nhiều kiến thức khác về lập trình. Trong bài viết ngày này, Techacademy sẽ chia sẻ với các bạn tất tần tật mọi thứ về đệ quy cùng với các bài tập đệ quy có lời giải chi tiết để giúp bạn hiểu rõ hơn về nó nữa đấy!
I. Đệ Quy Trong C++ Là Gì
Đệ quy trong C++ là quá trình trong đó một phương thức gọi lại chính nó một cách liên tiếp. Một hàm trong C++ gọi lại chính nó được gọi là phương thức đệ quy. Trong một hàm đệ quy sẽ gồm có điều kiện dừng và lời gọi hàm đệ quy, cú pháp cụ thể 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ễ hình dung hơn thì dưới đây sẽ là ví dụ về hàm đệ quy giúp tính giai thừa của một số 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 đích của hàm đệ quy là chia vấn đề thành những vấn đề nhỏ hơn cho đến lúc đạt được điều kiện cơ bản. Lưu ý quan trọng khi dùng đệ quy là bắt buộc phải có điều kiện 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 thể 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 giản về hàm đệ quy trong C++ đó là tính giai thừa của một số nguyên.
Trước khi giải bài toán tính giai thừa của một số nguyên trong 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 một số 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<iostream>
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à kết quả sau khi thực thi chương trình trên như sau:
Như vậy, để giải quyết bài toán giai thừa của một số bằng vòng lặp for trong C++ rất đơn giản phải không các 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 để ý 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 các 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ê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 có thể áp dụng giải thuật đệ quy C++ để giải quyết, bằng cách bên trong thân hàm sẽ gọi đến chính hàm đó.
Ví dụ
#include<iostream>
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à kết quả sau khi thực thi chương trình trên như sau:
Đối với các bạn mới bắt đầ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, các bạn đừng quá lo lắng, mình sẽ giải thích đoạn code cho các 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 vấn đề thành các vấn đề nhỏ hơn cho đến khi đạt được điều kiện cơ bản.
Ví dụ trong chương trình giai thừa ở trên, chúng ta đang giải quyết 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 lặp lại liên tục cho đến khi giá trị n đạt đến điều kiện cơ sở (GiaiThua(1) = 1).
III. Đệ Quy Quay Lui Trong C++
Quay lui là 1 kĩ thuật thiết kế giải thuật dựa trên đệ quy. Ý tưởng của quay lui là tìm lời giải từng bước, mỗi bước chọn một trong số các lựa chọn khả dĩ và đệ quy. Người đầu tiên đề 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 cấu hình. Mỗi cấu hình được xây dựng bằng từng phần tử. Mỗi phần tử lại được chọn bằng cách thử toàn bộ các khả năng.
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 quá 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 trò chơi khá phổ biến và chắc ai cũng biết. Trò chơi như sau: có một hình vuông được chia thành 9×9 ô vuông con. Mỗi ô vuông con có giá trị trong khoảng từ 1 đến 9. Ban đầu hình vuông có một số ô vuông con cho trước (có điền sẵn số) và còn lại là trống. Hãy điền các số từ 1-9 vào các ô con lại sao cho: hàng ngang là các số khác nhau từ 1 đến 9, hàng dọc là các số khác nhau từ 1 đến 9, và mỗi khối 3×3 chính là các số khác nhau từ 1 đến 9. Sau đây là 1 ví dụ về đề bài và lời giải:
Áp dụng quay lui để giải bài toán sudoku. Ý tưởng: Mỗi bước tìm tập các 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ú ý mảng chỉ có kích thước 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ất cả các tổ hợp để tìm được một lời giải. Thế mạnh của phương pháp này là nhiều cài đặt tránh được việc phải thử nhiều trường hợp chưa hoàn chỉnh, nhờ đó giảm thời gian 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 các nhược điể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 các tác vụ như sắp xếp hoặc tính toán các 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 <conio.h>
#include <iostream.h>
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 "<<a<<" va "<<b<<" la "<<UCLN(a,b);
getch();
}
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 <conio.h>
#include <iostream.h>
/*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 "<<n<<" phan tu\n";
for(int i=0; i<n ; i++){
cout<<"a["<<i<<"] = ";
cin>>a[i];
}
cout<<"UCLN cua "<<n<<" phan tu vua nhap la "<<UC(a,n);
getch();
}
+ Đệ Quy Fibonacci Trong C++
Chắc các 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 các bạn cách tính số fibonacci bằng phương pháp 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 <stdio.h>
#include <conio.h>
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 <iostream>
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 giả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 các 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ẽ yêu cầu tính hai số fibonacci thứ 4 và thứ 3. Nó lại tiếp 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 chúng ta chạy nhanh hơn thì 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à 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 <stdio.h>
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 <iostream>
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 tham khảo code này.
Lời giải cho chương trình in ra 1000 số Fibo đầu tiên.
#include <bits/stdc++.h>
using namespace std;
const int base = 1000000000;
const int base_digits = 9;
struct bigint
{
vector<int> 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<bigint, bigint> 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<int> convert_base(const vector<int> &a, int old_digits, int new_digits)
{
vector<long long> 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<int> 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<long long> 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<int> a6 = convert_base(this->a, base_digits, 6);
vector<int> 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 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ố 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ụ chúng ta nhập số 1234 thì sẽ thu về số 4321 chẳng hạn.
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ăn bản vô cùng hay giúp chúng ta rèn luyện lập trình bằng ngôn ngữ C.
Tìm số đảo ngược trong C
Cách tìm số đảo ngược trong C rất đơn giản, 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ì chúng ta sẽ viết ngược như thế nào?
Giả sử số đã cho là n = 1234. Chúng ta có thể biểu diễn số này dưới dạng tổng các lũy thừa của 10 như sau:
n = 1x104 + 2x103 + 3x102 + 4x101
Để biểu diễn số này theo cách ngược lại, 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, chúng ta sẽ chia lần lượt số đã cho cho các luỹ 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 để thực hiện 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 có thể gọi hàm này và sử dụng trong chương trình nhập vào một số 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 <stdio.h>
/*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à kết 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 bắt đầu học hoặc đã bỏ lỡ qua bài toán thú vị này thì cũng đừng lo, vì trong bài viết này mình sẽ giới thiệu cho tất cả các 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ự để biểu đạt một giá trị số, bằng tổng số các lũy thừa của 2. Hai ký tự đó thường là 0 và 1, chúng thường được dùng để biể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 tính toán đơn giản, dễ dàng thực hiện về mặt vật lý, chẳng hạn như trên các mạch điện tử, hệ nhị phân trở thành một phần kiến tạo căn bản trong các máy tính đương thời.
Ví dụ 0, 1, 0000, 0001, 010101, 00011100 là các 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é.
Bài toán cụ thể như sau:
Nhập vào một số nguyên dương N (1 ≤ N ≤ 20) hãy đưa ra tất cả các chuỗi nhị phân độ dài N, một chuỗi ghi trên một dòng, các 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à thú vị đúng không nào, đã có ai có ý tưởng 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 đã 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 các chuỗi nhị phân độ dài N lần lượt là biểu diễn nhị phân của các 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 chúng ta rất đơn giản đó là chỉ cần chuyển đổi các số tự nhiên từ 0 đến 2N-1 sang chuỗi nhị phân là được (chú ý nhớ chèn các ký tự ‘0’ vào các chuỗi nhị phân để độ dài của chuỗi nhị phân đủ N).
Để chuyển một số tự nhiên sang chuỗi nhị phân ta 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 kết quả 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 <iostream>
#include <math.h>
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 có thể dùng phương pháp đệ quy, hiểu đơn giản là 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.
phương pháp này để các bạn luyện tập đệ quy rất tốt, nhưng mình không khuyến khích các bạn dùng đệ quy trong khi nó có thể làm theo cách khác nha.
Source code:
#include <iostream>
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 các 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ư các chuỗi nhị phân độ dài 2 có các 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 có thể sinh ra các chuỗi nhị phân độ dài N.
Source code:
#include <iostream>
#include <math.h>
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 phương pháp 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’ cuối cùng của S.
– Thay thì bit thứ index từ ‘0’ thành ‘1’.
– Biến đổi tất cả 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’ cuối cùng là bit thứ 3, ta biến đổi 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 <iostream>
#include <math.h>
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 chia sẻ thuật toán và cách tính n giai thừa trong C/C+ sử dụng hai phương pháp đệ quy và khử đệ quy. Một bài toán hay dành cho các 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 kinh điển 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 có thể tóm tắt lại như sau: Tính n giai thừa và in kết quả ra màn hình, n nhập vào từ bàn phím.
Trước khi giải quyết bài toán, chúng ta cần hiểu định nghĩa về n! (n là một số nguyên dương): n giai thừa là tích của n số nguyên dương đầu tiên.
Công thức tổng quát: n! = n*(n-1)!
Trường hợp đặc biệt: 0! = 1
Tính giai thừa sử dụng vòng lặp
Cách tính đầu tiên này sẽ đơn giản hơn cách sử dụng đệ quy. Và nó được gọi là cách khử đệ quy bởi vì 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 giải quyết:
- 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 trước tiên bạn nên tìm hiểu 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 vì thế, 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 các số bắt đầu 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 giá cả 2 cách: Cách sử dụng đệ quy để tính giai thừa có vẻ chuyên nghiệp hơn. Tuy nhiên cách sử dụng vòng lặp có tốc độ nhanh không kém đệ quy, thậm trí là nhanh hơn.
Trong cách bài toán thực tế, nếu để lựa chọn thì các lập trình viên sẽ sử dụng cách 1 để hạn chế ít nhất việc sử dụng đệ quy.
Chú ý: Ở đây kiểu dữ liệu của hàm mình để là kiểu int, chính vì thế chỉ có thể chạy khi n <= 19 (nếu quá thì sẽ vượt kích thước của kiểu int dẫn đến sai kết 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<bits/stdc++.h>
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 "<<n<<"!: "<<factorial(n); // De quy
// cout<<"Ket qua "<<n<<"!: "<<giaithualap(n); // Khu de quy
}The post Đệ Quy Trong C++ first appeared on Techacademy.
source https://techacademy.edu.vn/de-quy-trong-c/
Nhận xét
Đăng nhận xét