เกมกำจัดใน C ++

สมมติว่าเรามีรายการของจำนวนเต็มที่เรียงลำดับตั้งแต่ 1 ถึง n ที่เริ่มจากซ้ายไปสิ้นสุดที่ด้านขวาเราต้องลบตัวเลขแรกและหมายเลขอื่น ๆ ออกทั้งหมดจนกว่าจะถึงจุดสิ้นสุดของรายการ เราจะทำซ้ำขั้นตอนก่อนหน้านี้อีกครั้ง แต่คราวนี้จากขวาไปซ้าย ลบตัวเลขที่ถูกต้องที่สุดและตัวเลขอื่นๆ ทั้งหมดออกจากตัวเลขที่เหลือ เราจะทำซ้ำขั้นตอนอีกครั้งโดยสลับจากซ้ายไปขวาและจากขวาไปซ้ายจนเหลือเลขตัวเดียว เราต้องหาตัวเลขสุดท้ายที่ยังขึ้นต้นด้วยรายการความยาว n

ดังนั้นหากอินพุตเป็น n =9 ขั้นตอนจะเป็นดังนี้ −

• 1 ,2,3 ,4,5 ,6,7 ,8,9

• 2,4 ,6,8

• 2 ,6

• 6

ดังนั้นคำตอบจะเป็น 6.

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• ซ้าย :=1 หัว :=1 ขั้นตอน :=1 rem :=n

• ในขณะที่ rem> 1

  • ถ้า left ไม่ใช่ศูนย์หรือ rem เป็นเลขคี่ ดังนั้น head :=head + step

  • ขั้นตอน :=ขั้นตอนที่ * 2

  • ซ้าย :=ผกผันของซ้าย

  • rem :=rem / 2

• กลับหัว

ตัวอย่าง (C++)

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int lastRemaining(int n) {
      int head = 1;
      int step = 1;
      int rem = n;
      int left = 1;
      while(rem > 1){
         if(left || rem % 2 == 1){
            head += step;
         }
         step *= 2;
         left = !left;
         rem /= 2;
      }
      return head;
   }
};
main(){
   Solution ob;
   cout << (ob.lastRemaining(9));
}

อินพุต

9

ผลลัพธ์

6