Ошибка в алгоритме Флавия

[Еким]

Привет всем! Задача Флавия.

Задача основана на легенде, что отряд Иосифа Флавия, защищавший город Йодфат, не пожелал сдаваться в плен блокировавшим пещеру превосходящими силам римлян. Воины, в составе сорока человек, стали по кругу и договорились, что каждые два воина будут убивать третьего, пока не погибнут все. При этом двое воинов, оставшихся последними в живых, должны были убить друг друга. Иосиф Флавий, командовавший этим отрядом, якобы быстро рассчитал, где нужно встать ему и его товарищу, чтобы остаться последними, но не для того, чтобы убить друг друга, а чтобы сдать крепость римлянам

Делаю так:

int flav3 (int n, int k) {
	
	vector<int> wars[n];

	// Инициализация массива
    for (int i=0; i<=n; ++i) {
        
        wars->push_back (i);    
    }
    
    int uk=k;                    // Удаляемый элемент
    while (n>1) {
        
        
        // Найдем позицию удаляемого элемента
        uk=uk+k;
        
        // Вышли за границу массива?
        if (uk > n-1){
            
            // Вычтем массив
            uk=uk-n;
        }
       
        // Оставшиеся элементы
        n=n-1;
        
        // Удаляем элемент
        wars->erase(wars->begin() + uk);
    }
    
    // Результат
    return wars->front();
}

Но результат отличается от правильного

[p51x]

Сообщение от Еким

vector<int> wars[n];

Массив векторов?

Сообщение от Еким

for (int i=0; i<=n; ++i) {

n+1 элемент?

Сообщение от Еким

int uk=k; // Удаляемый элемент

Т.е. первого подходящего пропускаем?

Сообщение от Еким

while (n>1) {

Два же должны остаться.

[Еким]

Спасибо за замечания!

Два же должны остаться.

Задача в общем виде, и преподаватель сказал, что всегда должен оставаться 1 У меня есть рабочий пример с Википедии, там тоже один остается...

[Еким]

Я исправил

int flav3 (int n, int k) {
	
	vector<int> wars;

	// Инициализация массива
    for (int i=0; i<n+1; ++i) {
        
        wars.push_back (i);    
    }
    
    int uk=0;                    // Удаляемый элемент
    while (n>1) {
        
        
        // Найдем позицию удаляемого элемента
        uk=uk+k;
        
        // Вышли за границу массива?
        if (uk > n-1){
            
            // Вычтем массив
            uk=uk-n;
        }
       
        // Оставшиеся элементы
        n=n-1;
        
        // Удаляем элемент
        wars.erase(wars.begin() + uk);
        uk=uk-1;
    }
    
    // Результат
    return wars.front();
}

Добавил в конце вычитание указателя на 1. Я плохо представляю процесс, но думаю я когда удаляю элемент в векторе должен и уменьшать указатель на 1 - массив же уменьшился. Или нет?. Контрольный пример для n=5. k=2 (ответ 3) теперь проходит. Но остальные примеры нет.

[Еким]

Вот я дурак! Оказывается не проходит. Я не правильно инициализировал вектор!
Вставил вывод вектора на экран.

int flav3 (int n, int k) {
	
	vector<int> wars;

	// Инициализация массива
    for (int i=0; i<n+1; ++i) {
        
        wars.push_back (i+1);    
    }
    
    int uk=0;                    // Удаляемый элемент
    while (n>1) {
        
        
        // Найдем позицию удаляемого элемента
        uk=uk+k;
        
        // Вышли за границу массива?
        if (uk > n-1){
            
            // Вычтем массив
            uk=uk-n;
        }
       
        // Оставшиеся элементы
        n=n-1;
        
        // Удаляем элемент
        wars.erase(wars.begin() + uk);
        
        for (int i=0; i<=wars.size(); ++i) {
            
            cout<<wars[i]<<" ";
        }
        
        cout<<"\n";
    }
    
    // Результат
    return wars.front();
}

В общем алгоритм работает не правильно.

[p51x]

int flav3 (int n, int k) {
	std::vector<int> wars;
	// Инициализация массива
    for (int i=0; i<n; ++i) {
        wars.push_back(i);
    }
    
    int uk = 0;
    while (wars.size()>1) {
    	uk=(uk+k-1)%wars.size();
        wars.erase(wars.begin() + uk);
        for (auto& e : wars) {
            std::cout << e << ' ';
        }
        std::cout << '\n';
    }
    
    // Результат
    return wars.front();
}

пробуйте

[Еким]

Да, это работает!
Что значит

for (auto& e : wars)

?
Вот я знал, что где-то нужно двигать указатель удаляемого элемента:

uk=(uk+k-1)%wars.size();

Только я никак не мог понять где его нужно двигать для расчета.

[p51x]

https://en.cppreference.com/w/cpp/language/range-for

[Еким]

Нас такому не учили .
Но https://www.onlinegdb.com проглатывает.
Спасибо большое! Тему можно считать исчерпанной!