Последний мужчина, используемый круглый список

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 и т. Д., Как и во всех этих случаях. Но любой другой вход и он не работает.

#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

Моя программа работает для входов 2, 4, 8, 16, 32, 64 и так далее, как ANS во всех них 1.

Это хорошее наблюдение. На самом деле ответ - всего лишь небольшой шаг отсюда.

У вас есть n кандидатов, и вы выбираете 1 каждый раз. Если n - x + 2^k (с максимально возможной k), после x шагов у вас есть 2^k кандидатов слева, а следующий кандидат в строке - ответ. Так что ответ 2x+1.

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

Примечание: Это упражнение можно найти в Concrete Mathematics: Foundation for Computer Science. Я очень рекомендую.

Answer 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) 

Очевидно, что мир изменился: в первый раз, когда я услышал эту головоломку это было про пиратов питьевой яд, чтобы определить, кто получил сокровище!

Answer 3

, чтобы значительно упростить ваше решение, реализовать «мягкое удаление». Поместите флаг в структуру узла с именем «int deleted» и инициализируйте его до 0. Каждый раз, когда вы хотите удалить узел, просто установите delete = 1.У вашей логики указателя в вашем вопросе возникают проблемы, и это избавляет от большей части этого.

Если вы ищете следующую для удаления, если узел удалил == 1, то не считайте его одним из оставшихся, просто продолжайте движение, пока не найдете второй узел с удаленным = 0 и установите его на 1.

Вам даже не нужен круговой список или даже список на данный момент. Вы можете просто использовать массив int с значениями 0 или 1. Если вы держите подсчет количества пока еще, то вы можете остановиться, как только вы доберетесь до одного оставшегося, иначе вам придется пересекать весь массив чтобы убедиться, что их нет.

Это не так быстро, как ваш список никогда не уменьшается, и вы смотрите на много удаленных записей, но это тонна проще.

Answer 4

Существует небольшая ошибка во втором цикле while (удаление). Оператор while принудительно завершает цикл после повторения через него один раз, то есть, как только он достигает начального узла, он завершает работу. Вам нужно изменить строку

while(temp2->ptr!=start); 

к

while(temp2->ptr!=temp2); 

также последний делать во время цикла, кажется, бежит в бесконечный цикл из-за заявления прямо над ним:

temp2 = start; 

В течение удаление, вы не отслеживаете указатель начала, который удаляется, как только элемент 1 будет удален. Таким образом, temp2 указывает на мусор. Удаление этой строки также должно исправить это.