2

问题：一家公司招聘候选人，让他们围成一圈。他们选择每隔一个候选人，然后他离开圈子（因此圈子越来越小），直到只剩下 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;
}
4

4 回答 4

2

问题在于核心循环：

do {
    temp2->ptr=temp3->ptr;
    temp3->ptr=NULL;
    delete temp3;
    temp2=temp2->ptr;
    temp3=temp2->ptr;
    } while (temp2->ptr!=start);

这个循环只遍历数据一次：它在到达第一组删除的末尾时停止，因为它在第一次返回时停止start。这就是为什么你总是得到答案 1，正如你所指出的，当列表长度是 2 的幂时，答案是正确的。

相反，它应该循环直到只剩下一个node，它将指向自己作为下一个node。所以do ... while循环的最后一行应该是：

    } while (temp2->ptr != temp2)

显然，世界已经在前进：我第一次听到这个谜题是关于海盗喝毒药来确定谁得到了宝藏！

于 2013-05-13T10:18:10.647 回答
2

我的程序适用于输入 2、4、8、16、32、64 等，因为所有这些都是 1。

这是一个很好的观察。实际上，答案只是从这里迈出的一小步。

你有n候选人，你每次选择 1 个。如果n是x + 2^k（具有最大可能的 k），则在x步骤之后您还有2^k候选者，并且该行中的下一个候选者就是答案。所以答案是2x+1。

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

注意：这个练习可以在具体数学：计算机科学基础中找到。我强烈推荐它。

于 2013-05-13T10:09:18.957 回答
0

为了大大简化您的解决方案，请实施“软删除”。在您的节点结构上放置一个名为“int deleted”的标志并将其初始化为0。每次要删除节点时，只需设置deleted = 1。您问题中的指针逻辑有问题，这消除了大部分.

在寻找下一个要删除的节点时，如果该节点已删除== 1，则不要将其视为剩余节点之一，继续直到找到第二个已删除= 0的节点，然后设置它为 1。

在这一点上，你甚至不需要一个循环列表，甚至是一个列表。您可以只使用值为 0 或 1 的整数数组。如果您计算仍然存在的数量，那么您可以在只剩下一个时立即停止，否则您将不得不遍历整个数组以确保没有剩余。

这不是那么快，因为您的列表永远不会变小，并且您正在查看很多已删除的条目，但它要简单得多。

于 2013-05-13T10:20:21.890 回答
0

第二个do while循环（删除）有一个小错误。while 语句在循环遍历一次后强制终止循环，即一旦返回到起始节点，它就退出。你需要换行

while(temp2->ptr!=start);

至

while(temp2->ptr!=temp2);

由于上面的语句，最后一个 do while 循环似乎陷入了无限循环：

temp2 = start;

在删除过程中，您不会跟踪元素 1 被删除后立即被删除的起始指针。因此 temp2 指向垃圾。删除这条线也应该解决这个问题。

于 2013-05-13T11:43:12.327 回答