кольцо | C++ для приматов

Задача: Задача Иосифа. По кругу располагается [latex]n[/latex] человек. Ведущий считает по кругу и выводит («казнит») [latex]m[/latex]-го человека*. Круг смыкается, счет возобновляется со следующего после «казнённого»; так продолжается, пока «в живых» не остаётся только 1 человек. Найти номер этого человека, [а так-же для заданного [latex]n[/latex] найти такое [latex]m>1[/latex] , при котором в живых остаётся первый]**.

* — m не может превышать n по условию.

** — вторая часть задачи.

Тесты:

Ввод	Вывод	Комментарий
2 1	2 [2]	Работает
3 3	2 [не существует]	Работает
271 42	121 [69]	Работает
271 69	1 [69]	Работает

Объяснение переменных:

bool existing - булева переменная для фиксирования существования второй части задачи. vector <int> a — вектор, по задаче представляет собой нумерацию людей.

unsigned int n, m — переменные, где n и m соответсвуют условию задачи.

int JeosifFunc(a, n, m) — функция, которая выполняет основной алгоритм задачи.

Код: Проверить на ideone.

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

//функция ниже нам понадобится дважды.
int JeosifFunc(vector <int> a, unsigned int n, unsigned int m){
	for (unsigned int i=a.size(); i>1; i--){ //задаем цикл, который выполняется n-1 раз
		if (m>a.size()){        
				m=a.size()%m-1; //m не больше n => (люди в круге, используем операцию %)
		}                       
		a.erase (a.begin()+m-1);//=> последовательно стираем 
		for (unsigned int i=0; i<m-1; i++){
			a.push_back (a[i]); // для удобства первые элементы до m продублируем вконец вектора
		}
		a.erase (a.begin(), a.begin()+m-1);//стираем всё до m.
	}
	return a[0]; //ответ будет храниться в a[0].
}

int main() {
	bool existing = false;
	vector <int> a;
	unsigned int n, m;
	cin >> n >> m; // 
	for (unsigned int i=1; i<=n; i++){ // заполняем вектор числами от 1 до n
		a.push_back (i);
	}
	cout << JeosifFunc(a, n, m) << " ["; // первая часть задания на этом закончена.
	//подставим всевозможные m в виде k и зафиксируем k при JeosifFunc(a, n, k) = 1
	for (unsigned int k = 2; (k <= n)&&(existing == false); k++){// m>1 => k = 2
		if( JeosifFunc(a, n, k) == 1){ // если обнаруживается такое k, что выживает первый номер,
			existing = true;//выключаем цикл
			cout << k<< "]";// выводим k
		}
	}
	if (existing == false){ // если такого k не нашлось.
		cout << "не существует]";
	}
	return 0;
}

#include <iostream>

#include <vector>

using namespace std;

//функция ниже нам понадобится дважды.

int JeosifFunc(vector <int> a, unsigned int n, unsigned int m){

for (unsigned int i=a.size(); i>1; i--){ //задаем цикл, который выполняется n-1 раз

if (m>a.size()){

m=a.size()%m-1; //m не больше n => (люди в круге, используем операцию %)

}

a.erase (a.begin()+m-1);//=> последовательно стираем

for (unsigned int i=0; i<m-1; i++){

a.push_back (a[i]); // для удобства первые элементы до m продублируем вконец вектора

}

a.erase (a.begin(), a.begin()+m-1);//стираем всё до m.

}

return a[0]; //ответ будет храниться в a[0].

}

int main() {

bool existing = false;

vector <int> a;

unsigned int n, m;

cin >> n >> m; //

for (unsigned int i=1; i<=n; i++){ // заполняем вектор числами от 1 до n

a.push_back (i);

}

cout << JeosifFunc(a, n, m) << " ["; // первая часть задания на этом закончена.

//подставим всевозможные m в виде k и зафиксируем k при JeosifFunc(a, n, k) = 1

for (unsigned int k = 2; (k <= n)&&(existing == false); k++){// m>1 => k = 2

if( JeosifFunc(a, n, k) == 1){ // если обнаруживается такое k, что выживает первый номер,

existing = true;//выключаем цикл

cout << k<< "]";// выводим k

}

if (existing == false){ // если такого k не нашлось.

cout << "не существует]";

}

return 0;

}

Алгоритм выполнения описан в комментариях в коде.

Особенности:

В коде очень легко запутаться, т.к. нумерация «слотов» вектора начинается с нуля, следовательно везде по коду мы должны это учитывать. Это здорово мешает в понимании кода.
Алгоритм выполнения первой задачи заключен в функцию. Без этого хода нельзя было бы выполнить вторую часть задания методом, представленным выше.
( if( JeosifFunc(a, n, k) == 1 )