Problem Flawiusza

Question

Próbuję rozwiązać problem Flawiusza wektorem. Eliminujemy w nim co drugą osobę.

https://pl.wikipedia.org/wiki/Problem_J%C3%B3zefa_Flawiusza

Nie mam pojęcia dlaczego mój program (co widać dzięki wypisywaniu w pętli for po każdej eliminacji) wykonuje tylko jeden obieg pętli while.

#include<iostream>
#include<vector>
using namespace std;

int flawiusz(int n)
{
	vector<int> kolo;
	for (int i = 0; i < n; i++) kolo.push_back(i);

	auto it = kolo.begin();
	int i = 0;

	while (kolo.size() > 1)
	{
		if (it + 1 == kolo.end())
		{
			kolo.erase(it + 1);
			it=kolo.begin();
		}
		else
		{
			it++;
			kolo.erase(it);
		}
		for (int i = 0; i < kolo.size(); i++)cout << kolo[i] << " ";
	}
	return kolo.front();
}

int main()
{
	cout << "Podaj ilosc osob: ";
	int n;
	cin >> n;
	cout << "Zostal numer: " << flawiusz(n);
}

 

Answer 1

Wiesz, że std::vector::erase unieważnia iteratory?

if (it + 1 == kolo.end())
{
    kolo.erase(it + 1);

Skoro it wskazuje na koniec, to po co to erase (czego zresztą nie możesz robić)?

Comments

#include<iostream>
#include<vector>
using namespace std;

int flawiusz(int n)
{
	vector<int> kolo;
	for (int i = 0; i < n; i++) kolo.push_back(i);

	auto it = kolo.begin();

	while (kolo.size() > 1)
	{
		if (it + 1 == kolo.end()-1)
		{
			it = kolo.erase(it+1);
			it=kolo.begin();
		}
		else
		{
			it = kolo.erase(it+1);
		}
		for (int i = 0; i < kolo.size(); i++)cout << kolo[i] << " ";
		cout << endl;
		cout << "koncze na" << *it;
	}
	return kolo.front();
}

int main()
{
	cout << "Podaj ilosc osob: ";
	int n;
	cin >> n;
	cout << "Zostal numer: " << flawiusz(n);
}

Czy dobrze rozumiem błąd?

Później ogarnąłem, że end() wskazuje na miejsce za ostatnim elementem pojemnika, więc odjąłem 1. Wciąż jednak nie wiem co tutaj nie działa.

---

@j23, Już chyba zrozumiałem na czym polegał błąd. Nie wiedziałem, że zawsze muszę przy używaniu erase jednocześnie ustawiać iterator na danej pozycji. Drugim błędem było traktowanie end() jako wskaźnika do ostatniego elementu, a nie do miejsca za ostatnim elementem.

Teraz program działa tak, jak powinien. Dziękuję za pomoc.

#include<iostream>
#include<vector>
using namespace std;

int flawiusz(int n)
{
	vector<int> kolo;
	for (int i = 0; i < n; i++) kolo.push_back(i);

	auto it = kolo.begin();

	while (kolo.size() > 1)
	{
		if (it == kolo.end() - 1)//jesli znajdujemy sie na ostatnim miejscu
		{
			it = kolo.erase(kolo.begin());
		}
		else if (it + 1 == kolo.end()-1)//jesli znajdujemy sie na przedostatnim miejscu
		{
			kolo.erase(it+1);
			it=kolo.begin();
		}
		else//jesli znajdujemy sie na conajmniej 3 miejscu od konca
		{
			it = kolo.erase(it+1);
		}
		for (int i = 0; i < kolo.size(); i++)cout << kolo[i] << " ";
		cout << endl;
		cout << "koncze na " << *it << endl;
	}
	return kolo.front();
}

int main()
{
	cout << "Podaj ilosc osob: ";
	int n;
	cin >> n;
	cout << "Zostal numer: " << flawiusz(n);
}