Задача на С++ олимпиадная

163
30 декабря 2019, 08:20

Вокруг ведущего стоит N человек, которые пронумерованы по часовой стрелку числами от 1 до N. Ведущий, начиная с первого отсчитывает M человек и тот, на котором остановится счет, выходит из круга. Счет возобновляется со следующего человека, и так до тех пор, пока не останется один. Определить номер последнего человека.

Подскажите, в каком направлении идти?

Answer 1

Ну, для нескольких десятков можно просто смоделировать :) - с помощью простейшего массива, например...
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;
}

Миллионные числа сработают быстро, миллиарды будут тормозить...

А вообще - ищите "Задачу Иосифа Флавия".

READ ALSO
Как вывести определенную часть файла?

Как вывести определенную часть файла?

Пишу несложную базу данных (использую простоtxt файлы) на c++ Вот так выглядят данные в файле

205
QWebEnginePage findText всегда false

QWebEnginePage findText всегда false

Не могу разобраться почему у меня не работает findText в QWebEnginePage, я точно знаю что текст на странице есть, а он пишет false:

146
Не проходит 10 тест на acmp (задача 65) [закрыт]

Не проходит 10 тест на acmp (задача 65) [закрыт]

Хотите улучшить этот вопрос? Update the question so it's on-topic for Stack Overflow на русском

150
Задать цвет текста кнопки программно

Задать цвет текста кнопки программно

Написал калькулятор, в котором для обработки нажатий используется интерфейс OnClickListenerВнешний вид калькулятора прописал в xml файле, а в файле...

131