โปรแกรม C++ หาสมาชิกสุดท้ายหลังลบทุกตัวที่สองในอาร์เรย์ n จำนวนเต็ม

พิจารณาว่าเรามีอาร์เรย์วงกลมที่มีจำนวนเต็มจาก 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

เราจะแก้ปัญหานี้ด้วยการเรียกซ้ำ (recursion) สมมติ n เป็นคู่ ตัวเลข 2, 4, 6 จะถูกลบ แล้วเราจะเริ่มจาก 1 อีกครั้ง ดังนั้น n/2 ตัวเลขถูกลบ และเราเริ่มเหมือนจาก 1 ในอาร์เรย์ n/2 ที่มีเฉพาะเลขคี่ 1, 3, 5... n/2 ดังนั้นเราสามารถเขียนสูตรได้ว่า −

solve(n) = 2*solve(n/2) - 1 [เมื่อ n เป็นคู่]
solve(n) = 2*solve((n-1)/2) + 1 [เมื่อ n เป็นคี่]

เงื่อนไขฐานคือ solve(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