Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.96/55: Рейтинг темы: голосов - 55, средняя оценка - 4.96
 Аватар для Fixer_84
1505 / 969 / 812
Регистрация: 30.04.2016
Сообщений: 3,337

Задача Иосифа Флавия

28.05.2017, 21:02. Показов 10482. Ответов 7
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Здравствуйте! Пытаясь ответить на вопрос одного из пользователей данного форума, решил в лоб следующую задачу:

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

Определите номер человека, который останется в кругу последним.

Входные данные:
Программа получает на вход числа N и K, не превосходящие 100

Выходные данные:
Программа должна вывести одно число от 1 до N, являющееся ответом на поставленную задачу.

Пояснение к примеру:
В этом примере люди выбывают в таком порядке: 2, 5, 1, 3, остался номер 4.

Входные данные
5 7
Выходные данные
4

Мой код:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <iostream>
#include <vector>
 
using namespace std;
 
int main()
{
    int N, K, p, t, L;
    cin >> N >> K;
    vector<int>A(N);
    for (int i = 0; i < N; i++)
    {
        A[i] = i + 1;
    }
    if (N == 2)
    {
        if (K % 2 == 0)
            cout << A[0] << endl;
        else
            cout << A[1] << endl;
    }
    else
    {
        L = 0;
        while (A.size() != 1)
        {
            p = 0;
            while (p < K + 1 - L)
            {
                t = A[A.size() - 1];
                for (int i = A.size() - 1; i >= 0; i--)
                {
                    A[i] = A[i-1];
                }
                A[0] = t;
                p++;
            }
            A.pop_back();
            L++;
        }
        if (K % 2 == 0)
            cout << A[0] << endl;
        else
            cout << A[1] << endl;
    }
    system("pause");
    return 0;
}
Код, вроде бы, работает, но я не могу пройти множество тестов на сайте Дистанционная подготовка. Где может быть ошибка? Прошу предоставить входные данные для которых мой код не работает.
0
IT_Exp
Эксперт
34794 / 4073 / 2104
Регистрация: 17.06.2006
Сообщений: 32,602
Блог
28.05.2017, 21:02
Ответы с готовыми решениями:

Задача Иосифа Флавия
Здравствуйте. Помогите пожалуйста реализовать такую задачу через списки: По кругу становятся несколько человек, пронумерованых от 1 до...

Задача иосифа флавия
N человек играют в следующую игру: стоя в кругу они начинают считалку. Счёт идёт до числа M. Игрок, на которого падает счёт M, выбывает,...

Задача Иосифа Флавия
Всем привет. Помогите пожалуйста с этой задачей. Никак допедрить не могу. вот код: #include&lt;iostream&gt; ...

7
4 / 4 / 2
Регистрация: 24.05.2013
Сообщений: 300
28.05.2017, 21:50
Fixer_84, N = 5, K = 7
C++
1
_DEBUG_ERROR("vector subscript out of range");

Не по теме:

это было не сложно

0
 Аватар для Fixer_84
1505 / 969 / 812
Регистрация: 30.04.2016
Сообщений: 3,337
28.05.2017, 22:18  [ТС]
Evgen8, спасибо за ваш ответ! У вас, вероятно, другой компилятор. У меня в DevC++ для этих входных данных выдает 4.
0
354 / 135 / 28
Регистрация: 16.12.2012
Сообщений: 607
Записей в блоге: 1
29.05.2017, 21:07
99 100
Ответ 22
Где ошибка не скажу, потому что мне лень разбираться - я бы писал не так
0
 Аватар для Fixer_84
1505 / 969 / 812
Регистрация: 30.04.2016
Сообщений: 3,337
29.05.2017, 21:11  [ТС]
Ромаха, хорошо. Я попробую переделать. Кажется, правда, можно проще. Да и правда что-то не так. У меня для тех же данных выводит 28. Буду разбираться.
0
192 / 166 / 82
Регистрация: 01.07.2016
Сообщений: 943
29.05.2017, 21:23
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <iostream>
#include <vector>
#include <iterator>
using namespace std;
 
int main()
{
    setlocale(LC_ALL, "rus");
    int n, m;
    cin >> n >> m;
 
    vector<int> MyVector(n);
    vector<int>::iterator it;
 
    int itmp(0);
    for(auto& x : MyVector)
        x = ++itmp;
 
    copy(MyVector.begin(), MyVector.end(), ostream_iterator<int>(cout, " "));
    cout << endl;
 
    it = MyVector.begin();
    int index = -1, tmp = 0, i;
    while(MyVector.size() != 1)
    {
        while(tmp < m)
        {
            for(i = index + 1; i < MyVector.size(); ++i)
            {
                tmp++;
                index = i;
                break;
            }
 
            if(i == MyVector.size())
            {
                for(int j = 0; j < 1; ++j)
                {
                    index = -1;
                    break;
                }
            }
        }
 
    tmp = 0;
 
    cout << "Шаг " << n - MyVector.size() + 1 << ": ";
    copy(MyVector.begin(),
        MyVector.end(),
        ostream_iterator<int>(cout, " ")
        );
    cout << " Удаляем: " << MyVector[index];
 
    MyVector.erase(it + index);
    index--;
 
    cout << endl;
    }
 
    cout << "Ответ: " << MyVector.front();
}
0
354 / 135 / 28
Регистрация: 16.12.2012
Сообщений: 607
Записей в блоге: 1
29.05.2017, 23:53
Зачем удалять?
Какая разница? Лишний же гемор.
Уменьшить сложность? Тогда другой алгоритм.
Чтобы проходила? Да итак пройдет. Будет же не больше 100^3

Просто ставить 0 в удаленных.
Тогда просто
Code
1
2
3
4
5
for(int i = 0; i < k;) {
    i += (v[j] == 1);
    j = (j+1)%n;
}
v[j] = 0;
0
192 / 166 / 82
Регистрация: 01.07.2016
Сообщений: 943
31.05.2017, 16:07
Цитата Сообщение от Ромаха Посмотреть сообщение
Просто ставить 0 в удаленных
Изначально я так и решил задачу. Просто захотелось решить задачу с использованием vector.

Добавлено через 15 секунд
Цитата Сообщение от Ромаха Посмотреть сообщение
Просто ставить 0 в удаленных
Изначально я так и решил задачу. Просто захотелось решить задачу с использованием vector.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
BasicMan
Эксперт
29316 / 5623 / 2384
Регистрация: 17.02.2009
Сообщений: 30,364
Блог
31.05.2017, 16:07
Помогаю со студенческими работами здесь

Задача Иосифа Флавия, решение циклическим списком
http://andrei-sapeshko.blogspot.ru/2013/04/blog-post.html тут есть пример, но он немного непонятный. struct node { int item; ...

Алгоритм нахождения главного элемента из списка (задача Иосифа Флавия)
Выписал алгоритм,называется ф-ция Иосифа. Смысл такой,что N=9 M=5 . Допустим есть 9 человек в кругу, и после каждого 5 удаления смыкают...

Задача Иосифа Флавия. Удалить каждый второй элемент из списка и в конце вывести на экран последний оставшийся элемент
Создать циклический список, в котором находятся элементы от 1 до N. Нужно написать программу, которая удаляет каждый второй элемент из...

Написать алгоритм Иосифа Флавия, используя очередь
Сущ-т легенда что Иосиф Флавий выжил и стал известным благодоря математической одаренности. В ходе Иудейской войны он в составе отряда из...

Задача Иосифа
Что-то жесткая задача... По кругу располагаются n=20 человек. Ведущий считает по кругу, начиная с первого, и выводит («казнит») m-го...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
8
Ответ Создать тему
Новые блоги и статьи
Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка.
Programma_Boinc 23.12.2025
Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка. Рецензия / Мнение Это мой обзор планшета X220 с точки зрения школьника. Недавно я решила попытаться уменьшить свой. . .
PhpStorm 2025.3: WSL Terminal всегда стартует в ~
and_y87 14.12.2025
PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .
Как объединить две одинаковые БД Access с разными данными
VikBal 11.12.2025
Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.
Новый ноутбук
volvo 07.12.2025
Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro
Музыка, написанная Искусственным Интеллектом
volvo 04.12.2025
Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .
От async/await к виртуальным потокам в Python
IndentationError 23.11.2025
Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов
Argus19 22.11.2025
Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .
Сколько Государство потратило денег на меня, обеспечивая инсулином.
Programma_Boinc 20.11.2025
Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .
Ломающие изменения в C#.NStar Alpha
Etyuhibosecyu 20.11.2025
Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .
Мысли в слух
kumehtar 18.11.2025
Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2025, CyberForum.ru