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人，他站在哪里。Ans : 我试着制作一个程序，你输入 n(候选人的数量) 它将打印一个未被选中的座位的值。

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

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

我的程序适用于输入 2、4、8、16、32、64 等，因为所有这些中的答案都是 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 candidates left，下一个候选人就是答案。所以答案是 2x+1。

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

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