Форум программистов, компьютерный форум CyberForum.ru

Задача Иосифа - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 43, средняя оценка - 4.67
Вилен
172 / 0 / 0
Регистрация: 09.10.2007
Сообщений: 5
26.11.2007, 21:16     Задача Иосифа #1
Что-то жесткая задача...
По кругу располагаются n=20 человек. Ведущий считает по кругу, начиная с первого, и выводит («казнит») m-го человека. Круг смыкается, счет возобновляется со следующего после «казненного»; так продолжается, пока «в живых» останется только один человек. Найти номер оставшегося «в живых» человека, а также найти такое m>1, при котором «в живых» останется первый.
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
26.11.2007, 21:16     Задача Иосифа
Посмотрите здесь:

C++ Написать алгоритм Иосифа Флавия, используя очередь
задача Иосифа Флавия / с помо щью циклического списка C++
C++ Задача Иосифа Флавия. Удалить каждый второй элемент из списка и в конце вывести на экран последний оставшийся элемент
C++ Задача Иосифа Флавия

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
nikita
1 / 1 / 0
Регистрация: 13.11.2007
Сообщений: 31
28.11.2007, 15:53     Задача Иосифа #2
Казнить предлагаю рекурсивно. Что касается касакется m>1 найти методом простого перебора.
guestonearth
3 / 3 / 2
Регистрация: 18.03.2010
Сообщений: 12
18.03.2010, 17:11     Задача Иосифа #3
Сообщение было отмечено автором темы, экспертом или модератором как ответ
вычисление за О(n):

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<stdio.h>
 
using namespace std;
 
int winchair(int n, int k) {
 
     int res = 0;
     for (int i=1; i<=n; ++i)
         res = (res + k) % i;
     return ++res;
 }
 
int main(){
    int n,k;
    while (1){ 
 
        scanf("%d %d",&n,&k);
        if (n==0 && k==0) break;
        if (n==1) printf("1\n");
        else printf("%d %d %d\n",n,k,winchair(n,k));
    }
    return 0;
}
где n - количество солдат(или стульев :-D ) а к - какого нужно убивать
Yandex
Объявления
18.03.2010, 17:11     Задача Иосифа
Ответ Создать тему
Опции темы

Текущее время: 21:31. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru