Решение задачи Задача Иосифа Флавия с Acmp

Без пояснения   Просмотров: 2379

Существует легенда, что Иосиф Флавий - известный историк первого века - выжил и стал известным благодаря математической одаренности. В ходе иудейской войны он в составе отряда из 41 иудейского воина был загнан римлянами в пещеру. Предпочитая самоубийство плену, воины решили выстроиться в круг и последовательно убивать каждого третьего из живых до тех пор, пока не останется ни одного человека. Однако Иосиф наряду с одним из своих единомышленников счел подобный конец бессмысленным - он быстро вычислил спасительные места в порочном круге, на которые поставил себя и своего товарища. И лишь поэтому мы знаем его историю…

В нашем варианте мы начнем с того, что выстроим в круг N человек, пронумерованных числами от 1 до N, и будем исключать каждого k-ого до тех пор, пока не уцелеет только один человек.

Например, если N=10, K=3, то сначала умрет 3-й, потом 6-й, затем 9-й, затем 2-й, затем 7-й, потом 1-й, потом 8-й, за ним - 5-й, и потом 10-й. Таким образом, уцелеет 4-й.

Требуется написать программу, которая по заданным N и K будет определять номер уцелевшего человека.

Код 

#include <bits/stdc++.h>
 
using namespace std;
 
int main()
{
    int n,k;
    cin >> n >> k;
    vector<vector<int> > a;
    vector<int> t;
    for(int i = 0; i < k; ++i)
        t.push_back(1);
    a.push_back(t);
    for(int i = 1; i < n; ++i){
        t.clear();
        for(int j = 0; j < k; ++j)
            t.push_back((a[i - 1][j] + j) % (i + 1) + 1);
        a.push_back(t);
    }
    cout << a[n - 1][k - 1];
    return 0;
}

         

Администратор Photo Автор: Администратор



Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться



info@mycod.net   Карта сайта   Правообладателям
Заявка на расчет
×

или напишите нам прямо сейчас:

Написать в MAX
Написать в Telegram
Написать в WhatsApp