Khám Phá 10 Bài Tập Đệ Quy Kinh Điển Trong Lập Trình C++
Những bài tập áp dụng đệ quy trong lập trình C++ thực sự là KINH ĐIỂN, mà bất kỳ sinh viên công nghệ thông tin nào cũng đã từng tiếp xúc với nó. Đệ quy có thể không phải là giải pháp tối ưu nhất cho mọi bài toán, nhưng đối với những bạn mới bắt đầu, nó thật sự dễ đọc và dễ hiểu.
1. Tháp Hà Nội
cpp
#include <iostream>
using namespace std;
void towerOfHanoi(int n, char source, char destination, char auxiliary)
{
if (n == 1)
{
cout << "Chuyển đĩa 1 từ cột " << source << " sang cột " << destination << endl;
return;
}
towerOfHanoi(n - 1, source, auxiliary, destination);
cout << "Chuyển đĩa " << n << " từ cột " << source << " sang cột " << destination << endl;
towerOfHanoi(n - 1, auxiliary, destination, source);
}
int main()
{
int n;
cout << "Nhập số đĩa: ";
cin >> n;
towerOfHanoi(n, 'A', 'C', 'B');
return 0;
}2. Bài Toán Xếp N Quân Hậu
cpp
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
bool columns[13], mainDiagonals[26], antiDiagonals[26];
vector<int> queenRows, queenColumns;
int numberOfSolutions = 0;
void printSolution(int n)
{
for (int i = 0; i < n; i++)
{
cout << "(" << queenRows[i] << ", " << queenColumns[i] << ")";
if (i < n - 1) cout << ", ";
}
cout << endl;
}
void solveNQueens(int n, int currentRow)
{
for (int currentColumn = 1; currentColumn <= n; currentColumn++)
{
int currentMainDiagonal = currentRow + currentColumn;
int currentAntiDiagonal = currentRow - currentColumn + 13;
if (columns[currentColumn] || mainDiagonals[currentMainDiagonal] || antiDiagonals[currentAntiDiagonal]) continue;
queenRows.push_back(currentRow);
queenColumns.push_back(currentColumn);
columns[currentColumn] = true;
mainDiagonals[currentMainDiagonal] = true;
antiDiagonals[currentAntiDiagonal] = true;
if (queenRows.size() == n)
{
numberOfSolutions++;
printSolution(n);
}
else
{
solveNQueens(n, currentRow + 1);
}
queenRows.pop_back();
queenColumns.pop_back();
columns[currentColumn] = false;
mainDiagonals[currentMainDiagonal] = false;
antiDiagonals[currentAntiDiagonal] = false;
}
}
int main()
{
int n;
cout << "Nhập số lượng quân hậu muốn xếp: ";
cin >> n;
memset(columns, 0, sizeof(columns));
memset(mainDiagonals, 0, sizeof(mainDiagonals));
memset(antiDiagonals, 0, sizeof(antiDiagonals));
int currentRow = 1;
solveNQueens(n, currentRow);
cout << "Tổng số cách xếp là: " << numberOfSolutions << endl;
return 0;
}3. Tìm Kiếm Nhị Phân
cpp
#include <iostream>
using namespace std;
#define NOT_FOUND -1
int binarySearch(int arr[], int left, int right, int target)
{
if (right >= left)
{
int mid = left + (right - left) / 2;
if (arr[mid] == target)
return mid;
if (arr[mid] > target)
return binarySearch(arr, left, mid - 1, target);
return binarySearch(arr, mid + 1, right, target);
}
return NOT_FOUND;
}
int main()
{
int n;
cout << "Nhập số phần tử của mảng: ";
cin >> n;
int arr[n];
cout << "Nhập các phần tử của mảng (đã sắp xếp): " << endl;
for (int i = 0; i < n; i++)
{
cin >> arr[i];
}
int target;
cout << "Nhập số cần tìm: ";
cin >> target;
int result = binarySearch(arr, 0, n - 1, target);
if (result != NOT_FOUND)
cout << "Số " << target << " được tìm thấy ở vị trí thứ " << result << endl;
else
cout << "Không tìm thấy số " << target << " trong mảng." << endl;
return 0;
}4. Tính Ước Chung Lớn Nhất (GCD)
cpp
#include <iostream>
using namespace std;
int gcd(int a, int b)
{
if (b == 0)
return a;
return gcd(b, a % b);
}
int main()
{
int a, b;
cout << "Nhập hai số nguyên dương: ";
cin >> a >> b;
cout << "Ước chung lớn nhất của " << a << " và " << b << " là: " << gcd(a, b) << endl;
return 0;
}5. Tính Tổng Các Chữ Số Của Một Số Nguyên
cpp
#include <iostream>
using namespace std;
int sumOfDigits(int number)
{
if (number == 0)
return 0;
return (number % 10) + sumOfDigits(number / 10);
}
int main()
{
int n;
cout << "Nhập số nguyên dương n: ";
cin >> n;
cout << "Tổng các chữ số của " << n << " là: " << sumOfDigits(n) << endl;
return 0;
}6. Chuyển Số Nguyên Sang Dạng Nhị Phân
cpp
#include <iostream>
using namespace std;
void decimalToBinary(int n)
{
if (n != 0)
{
decimalToBinary(n / 2);
cout << (n % 2);
}
}
int main()
{
int n;
cout << "Nhập số nguyên không âm n: ";
cin >> n;
cout << "Số nhị phân tương ứng là: ";
if (n == 0)
cout << "0";
else
decimalToBinary(n);
cout << endl;
return 0;
}7. Chuyển Số Nguyên Sang Dạng Hexadecimal
cpp
#include <iostream>
using namespace std;
void decimalToHex(int n)
{
string hexCharacters = "0123456789ABCDEF";
if (n != 0)
{
decimalToHex(n / 16);
int remainder = n % 16;
cout << hexCharacters[remainder];
}
}
int main()
{
int n;
cout << "Nhập số nguyên không âm n: ";
cin >> n;
cout << "Số hex tương ứng là: ";
if (n == 0)
cout << "0";
else
decimalToHex(n);
cout << endl;
return 0;
}8. Tính Số Fibonacci Thứ N
cpp
#include <iostream>
using namespace std;
int fibonacci(int n)
{
if (n <= 1)
return n;
return fibonacci(n - 1) + fibonacci(n - 2);
}
int main()
{
int n;
cout << "Nhập số nguyên dương n: ";
cin >> n;
cout << "Số Fibonacci thứ " << n << " là: " << fibonacci(n) << endl;
return 0;
}9. Tính Giai Thừa
cpp
#include <iostream>
using namespace std;
int factorial(int n)
{
if (n == 0 || n == 1)
return 1;
return n * factorial(n - 1);
}
int main()
{
int n;
cout << "Nhập số nguyên dương n: ";
cin >> n;
cout << "Giai thừa của " << n << " là: " << factorial(n) << endl;
return 0;
}Kết Luận
Hy vọng những kiến thức về bài tập đệ quy trong C++ này sẽ hữu ích cho bạn trong việc học lập trình. Hãy theo dõi series video Lên Trình Thuật Toán - Lập Trình Thi Đấu của mình trên Youtube để khám phá thêm nhiều kiến thức bổ ích nhé. Chúc bạn học tốt và hẹn gặp lại.
source: viblo
