c++ - 最后一个站着的人，使用了循环链表

Question

问题:一家公司在招聘候选人时，让他们坐成一圈。 他们每隔一个选择一个候选人，然后他离开圆圈(因此圆圈不断变小)，直到只剩下 1 个人。 所以，如果有 5 个人，就会像这样:-

1 2 3 4 5
1 3 4 5    (2 is selected)
1 3 5      (4 is selected)
3 5        (1 is selected)
3          (3 is left, does'nt get the job!)

Jhon 是一个过于聪明的人，他不想成为这家恶意公司的一部分。

如果他知道总共有 560 人，他站在哪里？ 答:我尝试制作一个程序，您可以在其中输入 n(候选人数量) 它会打印将取消选择的一个席位的值。

我使用了循环链表和删除。

请耐心等待，因为我对编码还很陌生。

我的程序适用于输入 2、4、8、16、32、64 等，因为所有这些中的 an 都是 1。 但任何其他输入都不起作用。

#include <iostream>

using namespace std;

struct node
{
    node* ptr;
    int data;
}start;


int main()
{
    node *start=NULL;
    int n;
    cout<<"Enter the number of students : ";
    cin>>n;

   node *temp=new node;
   temp->data=1;
   temp->ptr=NULL;
   start=temp;
   for(int x=2;x<=n;x++)
   {
       node* temp1=new node;
       temp1->data=x;
       temp->ptr=temp1;
       temp1->ptr=start;
       temp=temp1;

   }
   node* temp2=start;
   do
   {
       cout<<temp2->data<<" ";
       temp2=temp2->ptr;
   }while(temp2!=start);
   cout<<endl;


   //delete bigins here

   temp2=start;
   node* temp3=temp2->ptr;

   do
   {
        temp2->ptr=temp3->ptr;
        temp3->ptr=NULL;
        delete temp3;
        temp2=temp2->ptr;
        temp3=temp2->ptr;


   }while(temp2->ptr!=start);

    temp2=start;
   do
   {
       cout<<temp2->data<<" ";
       temp2=temp2->ptr;
   }while(temp2!=temp3);
   cout<<endl;
}

Answer 1

My program works for inputs 2, 4, 8, 16, 32, 64 and so on as ans in all these is 1.

这是一个很好的观察。事实上，答案离这里仅一步之遥。

您有 n 名候选人，您每次选择 1 名。如果n是x + 2^k(具有最大可能的k)，在x步之后你有2^k code> 留下的候选者和该行中的下一个候选者就是答案。所以答案是2x+1。

1 2 3 4 5 6 7
  ^   ^   ^ |
   removed  |
       answer

注意:此练习可以在Concrete Mathematics: Foundation for Computer Science中找到。我强烈推荐它。