2

質問 :候補者を採用する会社が、候補者を輪になって座らせます。彼らは 1 人おきに候補を選び、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!)

賢すぎるジョンは、この意地悪な会社の一員になりたくありません。

全部で 560 人いると知ったら、彼はどこに立っているでしょうか。 回答 : n(候補者の数) を入力すると、選択されない 1 議席の値が出力されるプログラムを作成しようとしました。

循環リンクリストと削除を使用しました。

私はコーディングにかなり慣れていないので、ご容赦ください。

私のプログラムは、入力 2、4、8、16、32、64 などに対して動作します。これらすべての ans は 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);

このループはデータを 1 回だけ通過します。最初に に戻ったときに停止するため、最初の削除セットの終わりに到達すると停止しstartます。そのため、常に答え 1 が得られます。これは、ご指摘のとおり、リストの長さが 2 の累乗の場合に正しいです。

むしろ、node次のnode. したがって、do ... whileループの最後の行は次のようになります。

    } while (temp2->ptr != temp2)

明らかに世界は進んでいます。このパズルを初めて聞いたとき、誰が宝物を手に入れたかを決めるために海賊が毒を飲むというものでした!

于 2013-05-13T10:18:10.647 に答える
2

私のプログラムは、これらすべての ans が 1 であるため、入力 2、4、8、16、32、64 などに対して機能します。

これは良い観察です。実際、答えはここからの小さな一歩です。

候補が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 の場合、それを残りのノードの 1 つとしてカウントしないでください。削除済み = 0 の 2 番目のノードが見つかるまで続けて、 1にします。

この時点では、循環リストは必要ありませんし、リストさえも必要ありません。値が 0 または 1 の int の配列を使用できます。残りの数を数え続ける場合は、残りが 1 つになったらすぐに停止できます。そうしないと、配列全体をトラバースする必要があります。残っていないことを確認します。

リストが小さくなることはなく、削除されたエントリが多数表示されるため、これはそれほど高速ではありませんが、はるかに簡単です。

于 2013-05-13T10:20:21.890 に答える
0

2 番目の do while ループ (削除) に小さなエラーがあります。while ステートメントは、ループを 1 回繰り返した後、強制的にループを終了させます。つまり、ループが開始ノードに戻ると終了します。行を変更する必要があります

while(temp2->ptr!=start);

に

while(temp2->ptr!=temp2);

また、最後の do while ループは、そのすぐ上のステートメントのために無限ループに陥っているようです。

temp2 = start;

削除中、要素 1 が削除されるとすぐに削除される開始ポインターを追跡しません。したがって、temp2 はガベージを指します。この行を削除すると、それも修正されるはずです。

于 2013-05-13T11:43:12.327 に答える