Cho biến nguyên Number làm đầu vào. Xét mảng chứa các phần tử từ 1 đến Number theo thứ tự đã sắp xếp. Thực hiện phép toán trên mảng: ở mỗi bước loại bỏ các phần tử ở vị trí lẻ. Mục tiêu là thực hiện phép toán N lần cho đến khi chỉ còn một phần tử. In phần tử đó.
Lưu ý: Vị trí phần tử bắt đầu từ 1 (chỉ số 0 là vị trí 1).
Các trường hợp kiểm thử
Number=1 → 1
Number=2 → 2
Number=3 → 2
Number=4 → 4
Number=5 → 4
Number=6 → 4
Number=7 → 4
Number=12 → 8
Number=20 → 16
Quan sát: Với số trong khoảng 2^i đến 2^(i+1)-1, kết quả là 2^i.
Ví dụ
Đầu vào - Number = 7
Đầu ra - Phần tử đơn sau phép giảm: 4
Giải thích - Mảng [1 2 3 4 5 6 7]. Lần 1: [2 4 6]. Lần 2: [4].
Đầu vào - Number = 18
Đầu ra - Phần tử đơn sau phép giảm: 16
Giải thích - Mảng [1..18]. Lần 1: [2 4 6 8 10 12 14 16 18]. Lần 2: [2 8 12 16]. Lần 3: [8 16]. Lần 4: [16].
Phương pháp sử dụng trong chương trình dưới đây
Dùng vòng lặp while tính kết quả dựa trên công thức: giá trị khởi tạo 2, lặp while 2*result ≤ Number, nhân đôi result mỗi lần.
Nhập biến Number.
Hàm getsingleElement(long num) in kết quả theo công thức.
Biến result khởi tạo = 2.
While result*2 ≤ num: result *= 2.
Kết thúc while trả về result.
In kết quả trong main.
Ví dụ mã
#include<bits/stdc++.h> using namespace std; long getsingleElement(long num){ long result; result=2; while(result*2 <= num){ result=result*2; } return result; } int main(){ int Number = 20; cout<<"Phần tử đơn sau phép giảm là : "<<getsingleElement(Number) ; return 0; }
Đầu ra
Nếu chạy mã trên sẽ cho kết quả:
Phần tử đơn sau phép giảm là : 16