พิจารณาว่าเรามีอาร์เรย์วงกลมหนึ่งชุดที่มีจำนวนเต็มตั้งแต่ 1 ถึง n ค้นหาองค์ประกอบสุดท้าย ซึ่งจะยังคงอยู่ในรายการหลังจากลบทุกองค์ประกอบที่สองโดยเริ่มจากองค์ประกอบแรก หากอินพุตเป็น 5 อาร์เรย์จะเป็น [1, 2, 3, 4, 5] เริ่มจาก 1 หลังจากลบแต่ละองค์ประกอบที่สองจะเป็นเช่น -
1 0 3 4 5 1 0 3 0 5 0 0 3 0 5 0 0 3 0 0
ดังนั้นองค์ประกอบที่ยังคงอยู่ในรายการคือ 3
เราจะแก้ปัญหานี้โดยใช้การเรียกซ้ำ สมมุติว่า n เป็นคู่ ตัวเลข 2, 4, 6 จะถูกลบออก จากนั้นเราจะเริ่มต้นจาก 1 อีกครั้ง ดังนั้นตัวเลข n/2 จะถูกลบออก และเราเริ่มต้นราวกับว่ารูปแบบ 1 ในอาร์เรย์ของ n/2 ที่มีเฉพาะเลขคี่ 1, 3, 5, … n/2 เราก็เขียนสูตรได้ดังนี้ −
solve(n)=2*solve(n/2)-1[when n is even] solve(n)=2*solve(n-1/2)+1[when n is odd]
เงื่อนไขพื้นฐานคือแก้(1) =1
ตัวอย่าง
#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;
} ผลลัพธ์
Remaining Element: 3 Remaining Element: 5
