Вокруг ведущего стоит N человек, которые пронумерованы по часовой стрелку числами от 1 до N. Ведущий, начиная с первого отсчитывает M человек и тот, на котором остановится счет, выходит из круга. Счет возобновляется со следующего человека, и так до тех пор, пока не останется один. Определить номер последнего человека.
Подскажите, в каком направлении идти?
Ну, для нескольких десятков можно просто смоделировать :) - с помощью простейшего массива, например...
O(N2) вполне достаточно для таких чисел.
Для более серьезных N можно воспользоваться рекурсивным O(N) решением
int J(int n, int m)
{
if (n == 1) return 1;
return (J(n-1,m)+m-1)%n+1;
}
int main()
{
int n, m;
cin >> n >> m;
cout << J(n,m) << endl;
}
Понятно, что его легко превратить в итеративное:
int J(int n, int m)
{
int j = 1;
for(int k = 1; k < n; ++k)
{
j = (j+m-1)%(k+1)+1;
}
return j;
}
Миллионные числа сработают быстро, миллиарды будут тормозить...
А вообще - ищите "Задачу Иосифа Флавия".
Виртуальный выделенный сервер (VDS) становится отличным выбором
Пишу несложную базу данных (использую простоtxt файлы) на c++ Вот так выглядят данные в файле
Не могу разобраться почему у меня не работает findText в QWebEnginePage, я точно знаю что текст на странице есть, а он пишет false:
Хотите улучшить этот вопрос? Update the question so it's on-topic for Stack Overflow на русском
Написал калькулятор, в котором для обработки нажатий используется интерфейс OnClickListenerВнешний вид калькулятора прописал в xml файле, а в файле...