Решение проблемы Иосифа с помощью вектора

Question

Решение проблемы Иосифа с помощью вектора

РЕДАКТИРОВАТЬ: Я, кажется, разобрался с ошибками, по крайней мере, и обновил код. Тем не менее, математика все еще не работает. Есть идеи?

Короче говоря, я пытаюсь написать программу на C ++, которая будет запрашивать у пользователя количество людей в начальном круге, а затем сообщать им, в каком положении они должны стоять, чтобы выжить, если К (количество людей, подсчитанных до казни) = 3.

У меня есть то, что я считаю правильной идеей, но я получаю сообщения об ошибках «Отладка не подтверждена» и «Выражение: итератор стирания вектора вне диапазона», если я ввожу К как что-либо кроме 1, 2 или 5.

// ConsoleApplication2.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"#include <iostream>
#include <vector>
using namespace std;

int _tmain(int argc, _TCHAR* argv[])
{
int n;//size of the circle
vector <int> circle; //the circle itself

//ask for how many people are in the circle
cin >> n;

//fill the circle with 1,2,3...n
for (int idx = 0; idx < n; idx++)
{
circle.push_back (idx+1);
}//cout << "The size of the circle is " << circle.size() << ".\nThe highest number is " << circle[n-1] << "."; //test to make sure numbers are being assigned properly to each vector elementfor (int count = 0, idx = 0; circle.size() > 1; idx++,count++)
{
//if the position (idx) is greater than the size of the circle, go back to the beginning of the circle and start counting again
if (idx >= circle.size())
{
idx = 0;
}

//every time the counter reaches three, that person is executed
if (count == 3)
{
circle.erase (circle.begin()+(idx));
count = 0;
}
}

cout << "The place to stand to win the hand is position #" << circle.front() << ".\n";

return 0;
}

0

c++josephus vector

Решение

Другие решения

@Pradhan уже дал вам решение вашей первоначальной ошибки (idx >= circle.size() вместо idx >= circle.size(),

Почему результат все еще не верен:
Когда вы стираете элемент, вы должны скорректировать свой индекс, чтобы компенсировать его (вычтите 1). В противном случае индекс соответствует следующему элементу в векторе, поэтому фактически вы всегда выполняете каждого четвертого человека, а не каждого третьего.

Вот моя версия кода:

#include <iostream>
#include <vector>
#include <numeric>

using namespace std;

int main(){
int n;
cin >> n;

//fill the circle with 1,2,3...n
vector <int> circle(n);
std::iota(std::begin(circle), std::end(circle),1);

int idx = -1;
while (circle.size() > 1) {
//advance by threee
idx = (idx + 3) % circle.size();

//execute Person
circle.erase(circle.begin() + (idx));

//readjust to compensate for missing element
--idx;
}
cout << "The place to stand to win the hand is position #" << circle.front() << ".\n";
}

конечно, вы можете переписать цикл

    int idx = 0;
while (circle.size() > 1) {
//advance by three
idx = (idx + 2) % circle.size();

//execute Person
circle.erase(circle.begin() + (idx));
}

0

Источник

Accepted Answer

Вы проверяете только if (idx > circle.size()) а затем идти вперед и позвонить circle.erase (circle.begin()+(idx));, Этот звонок не является безопасным, когда idx == circle.size(),

3