#c
Вопрос:
Мне был задан этот вопрос для моей лаборатории (и да, я понимаю, что будет отрицательная реакция, потому что это домашнее задание). Я работал над этим вопросом в течение нескольких дней безрезультатно, и мне кажется, что я упускаю что-то совершенно очевидное.
Мой код:
int processSuitors(vector<int>amp; currentSuitors, list<int>amp; rekt)
{
int sizeSuitors = currentSuitors.size();
int eliminated = 2;
while(sizeSuitors != 1)
{
rekt.push_back(currentSuitors[eliminated]);
currentSuitors.erase(currentSuitors.begin() eliminated);
sizeSuitors--;
if(eliminated > sizeSuitors)
{
eliminated -= sizeSuitors;
}
}
return currentSuitors[0];
}
Незамедлительный:
В древней стране у прекрасной принцессы Евы было много поклонников. Она решила провести следующую процедуру, чтобы определить, за какого жениха она выйдет замуж. Во-первых, все претенденты будут выстроены один за другим и им будут присвоены номера. Первым претендентом будет номер 1, вторым-номер 2, и так далее, вплоть до последнего претендента, номер n. Начиная с первого претендента, она затем отсчитала бы трех претендентов по очереди (из-за трех букв в ее имени), и третий претендент был бы исключен из выигрыша ее руки, и он был бы удален из очереди. Затем Ева продолжила бы, подсчитав еще трех претендентов и исключив каждого третьего претендента. Когда она дойдет до конца очереди, она продолжит отсчет с самого начала.
Напишите функцию с именем processSuitors, которая принимает в качестве аргументов вектор STL типа int, содержащий претендентов, и список STL типа int, который соберет всех исключенных претендентов. Функция возвращает значение int, в котором хранится позиция, в которой должен находиться жених, чтобы жениться на принцессе, если есть n женихов. Функция, вызывающая processSuitors, отправит вектор, уже заполненный n претендентами (1, 2, 3… n), и пустой список, который необходимо заполнить номером позиции исключенных претендентов в порядке их исключения.
Ограничения: Вы не можете создавать какие-либо контейнеры (ни массивов, ни векторов и т.д.); вам необходимо использовать вектор и список, которые передаются в качестве параметров. Используйте ТОЛЬКО следующие функции STL:
vector::size
vector::erase
vector::begin
ist::push_back
vector::operator[ ]
Соседние файлы скрыты, так как мы должны полагаться на то, что дано. Любая очистка моего кода также была бы чрезвычайно признательна.
Комментарии:
1.
return currentSuitors[0]— А что, если этот вектор пустой? Доступ к элементу 0 является неопределенным поведением, если это так.2. Где вы увеличиваете
eliminated? Согласно вопросу, индекс должен быть увеличен. Например: номер 3, 5,7…и т.д. Согласно «Ева затем продолжила бы, подсчитав еще трех претендентов и устранив каждого третьего претендента».3. Вы должны написать код и создать свои собственные тестовые примеры, чтобы проверить свою логику с помощью отладчика. Не пяльтесь в бездну и не пытайтесь вытащить жука. Бездна не будет смотреть в ответ так, как ты хочешь.
4. Ваш код устранит претендентов 3, 4, 5, … n, 2 (имейте в виду, что векторная индексация начинается с 0, поэтому претендент 1 является элементом с индексом 0). Код должен исключить претендентов: 3, 6, 9, …, при достижении конца он должен начинаться спереди, таким образом, во втором раунде устраняя 4, 8 и т.д. Попробуйте создать несколько небольших тестовых примеров, решить их вручную, а затем попробуйте переписать решение.
5. Неясно, что произойдет, когда останутся только 1-е 2 претендента, потому что, если мы исключим каждого 3-го претендента, претенденты 1 и 2 не будут удалены. Так кого же из них выберет принцесса? 1-й или 2-й, так как нет 3-го жениха, которого нужно устранить!
Ответ №1:
Что вы думаете об этом решении?
Сохраните другой вектор, который отмечает, был ли удален индекс в вашем currentSuitors векторе. Затем есть вспомогательная функция, которая всегда найдет следующий свободный индекс.
Вместо того, чтобы пытаться уменьшить текущие требования, вы просто продолжаете отмечать элементы в списке принятых.
size_t findNextFreeSlot(const vector<bool>amp; taken, size_t pos)
{
// increment to the next candidate position
pos = (pos 1) % taken.size();
// search for the first free slot
for (size_t i = 0; i < taken.size(); i )
{
if (taken[pos] == false)
{
return next;
}
pos = (pos 1) % taken.size();
}
// assert(false); // we should never get here as long as there's one free slot index in taken
return -1;
}
int processSuitors(vector<int>amp; currentSuitors, list<int>amp; rekt)
{
size_t len = currentSuitors.size();
vector<bool> taken(len); // keep a vector of eliminated indices from current
size_t index = len; // initialize one past the last valid element
size_t eliminated = 0;
if (len == 0)
{
return -1;
}
while (eliminated < (len-1))
{
// advance the index three times to the next "untaken" index
index = findNextFreeSlot(taken, index);
index = findNextFreeSlot(taken, index);
index = findNextFreeSlot(taken, index);
taken[index] = true; // claim this index as taken
rekt.push_back(currentSuitors[index]); // add the value at this index to the eliminated list
eliminated ;
}
index = findNextFreeSlot(taken, index); // find the last free index
return currentSuitors[index];
}