Cho mảng vòng chứa số 1 đến n. Tìm phần tử cuối cùng còn lại sau khi xóa mỗi phần tử thứ hai bắt đầu từ phần tử đầu. Input 5 → mảng [1,2,3,4,5]. Xóa lần lượt: 1 0 3 4 5 → 1 0 3 0 5 → 0 0 3 0 5 → 0 0 3 0 0. Phần tử còn lại: 3.
Giải bằng đệ quy. Nếu n chẵn: xóa 2,4,6... bắt đầu lại từ 1 với mảng n/2 chỉ chứa số lẻ. Công thức:
solve(n) = 2*solve(n/2) - 1 [n chẵn] solve(n) = 2*solve((n-1)/2) + 1 [n lẻ]
Điều kiện cơ sở: solve(1) = 1.
Ví dụ mã nguồn
#include <iostream>
using namespace std;
int deleteSecondElement(int n) {
if (n == 1)
return 1;
if (n % 2 == 0)
return 2 * deleteSecondElement(n / 2) - 1;
else
return 2 * deleteSecondElement((n - 1) / 2) + 1;
}
int main() {
int n = 5;
cout << "Remaining Element: " << deleteSecondElement(n) << endl;
n = 10;
cout << "Remaining Element: " << deleteSecondElement(n) << endl;
}
Kết quả đầu ra
Remaining Element: 3 Remaining Element: 5