Получить индекс элемента из исходного списка и значение оставшегося элемента
Я пытаюсь решить задачу Иосифа, где помимо значения оставшегося элемента мне нужно вернуть его индекс в исходном списке. Я сам реализовал список, и он работает хорошо, значение получаю правильно, но не могу понять, как получить индекс из исходного массива!
Может ли кто-нибудь объяснить мне это, пожалуйста?
Мой код:
#include "circular_linked_list.h"
enum class direction { clockwise, counterclockwise };
template<typename T>
std::pair<int, T> Josephus_problem(CircularLinkedList<T> list, direction dir, unsigned step) {
if (list.getLength() == 0) {
throw std::invalid_argument("List is empty");
}
int currentIndex = 0;
int size = list.getLength();
int finalIndex = 0;
while (list.getLength() > 1) {
if (dir == direction::counterclockwise) {
finalIndex -= step + 1;//???
currentIndex = (currentIndex - step + 1) % list.getLength();
} else {
finalIndex += step - 1;//???
currentIndex = (currentIndex + step - 1) % list.getLength();
}
list.removeAt(currentIndex);
}
finalIndex = ...;//Don't know what to do here!
return {finalIndex, list[0]};
}
Ответы 1
Примерно это:
Инициализируйте std::list целых чисел без знака (size_t), которые представляют индекс каждого элемента в списке от 0 до N-1.
std::list<size_t> listOfPositions;
size_t N = <how ever many elements are in your original list>
for (size_t i = 0; i < N; i++) {
listOfPositions.push_back(i);
}
Затем просто просматривайте список один за другим. Каждый раз, когда вы нажимаете на элемент STEPth, вы стираете его. Вы можете воспользоваться тем фактом, что list.erase в элементе позиции вернет следующий за ним элемент.
Вот простая логика:
unsigned int index = 1;
auto pos = listOfPositions.begin();
while (listOfPositions.size() > 1) {
if (index == step) {
pos = listOfPositions.erase(pos); // returns the next item in the list
index = 1;
}
else {
pos++;
index++;
}
if (pos == listOfPositions.begin()) {
pos = listOfPositions.end();
}
}
И вы можете воспользоваться обратными итераторами для операций против часовой стрелки. Некоторые небольшие изменения в приведенной выше логике, чтобы она работала при обратных итерациях.
unsigned int index = 1;
auto pos = listOfPositions.rbegin() + N - 1; // point to the first item in the list
while (listOfPositions.size() > 1) {
if (index == step) {
pos = listOfPositions.erase(pos); // return the previous item in the list when using reverse iterators
index = 1;
}
else {
pos++;
index++;
}
if (pos == listOfPositions.rend()) {
pos = listOfPositions.rbegin();
}
}
В обоих случаях «последний оставшийся индекс» таков:
size_t last_remaining = *pos;
Еще одна вещь, о которой я подумал. Вместо альтернативных реализаций циклов по часовой стрелке и против часовой стрелки, просто инициализируйте элементы списка в обратном порядке, при этом 0 по-прежнему будет первым элементом. Вместо 0,1,2,3,4,5,6 инициализируйте его как 0,6,5,4,3,2,1 для вращения против часовой стрелки. Тогда для решения вам не понадобится версия итерационного цикла rbegin/rend.
Создайте список индексов — только целые числа от 0 до
list.getLength()-1. Поиграйте в игру на этом. В конце у вас будет выживший индекс. Найдите сохранившееся значение в исходном списке, используя этот индекс.