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

@Lyanai · Регистрация: 20.02.2022

Студворк — интернет-сервис помощи студентам

всем привет, я студент, у которого в программе есть информатика. нам задали вот такую задачу на с++.
Вывести в порядке выбытия номера последних трех из N участников, считающихся начиная с первого "по кругу" считалкой из M слов, с выбытием каждого участника, на котором текст считалки заканчивается
в интернете есть достаточно легкий способ с помощью рекурсии найти последнего выжившего, однако из-за необходимости найти 3х последних, я решила писать в лоб. вот что у меня получилось:

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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <iostream>
using namespace std;
 
int Last_Iosif(int n, int m){
  bool *persons = new bool[n];
  for (int i = 0; i < n; i++){
    persons[i] = true;
  } //create a bool massive, all people are alive(true)
  int counter = 0; // as a on whom is the count now
  int num = -1;
  for (int i = 0; i < n; i++){
    while (counter < m){
      num = (num + 1) % n;
      
      if(persons[num] == true){ 
        counter++;//because we need to count only alive persons
      }
    }
    counter = 0;
    persons[num] = false; // man number num died
  }
  delete [] persons; //get free a memory 
  return num + 1 ; // the last man, who lives 
}
int Pre_Last_Iosif(int n, int m){
  bool *persons = new bool[n];
  for (int i = 0; i < n; i++){
    persons[i] = true;
  }
  int counter = 0;
  int num = -1;
  for (int i = 0; i < n-1; i++){ //we do only n-1 steps now
    while (counter < m){
      num = (num + 1) % n;
      
      if(persons[num] == true){ 
        counter++;
      }
    }
    counter = 0;
    persons[num] = false; 
  }
  delete [] persons;  
  return num + 1 ; 
}
int Pre_Pre_Last_Iosif(int n, int m){
  bool *persons = new bool[n];
  for (int i = 0; i < n; i++){
    persons[i] = true;
  }
  int counter = 0;
  int num = -1;
  for (int i = 0; i < n-2; i++){ //we do only nn-2 steps now
    while (counter < m){
      num = (num + 1) % n;
      
      if(persons[num] == true){ 
        counter++;
      }
    }
    counter = 0;
    persons[num] = false;
  }
  delete [] persons; 
  return num + 1 ;
}
 
int main(){
  int n, m;
  cout << "Please say a number of participants: ";
  cin >> n;
  cout <<'\n'<<"Say a number of words: ";
  cin >> m;
  cout << "\n" <<"Latest retired are numbers: " << Pre_Pre_Last_Iosif(n,m)<<' '<<Pre_Last_Iosif(n,m)<<' '<< Last_Iosif(n, m) << endl;
  return 0;
}

программа работает правильно, однако из-за трёх практически одинаковых функций мне сказали улучшить её до одной функции. я попыталась добавить в функцию ещё один цикл, который бы делал шаги и вернуть массив из 3х чисел. но cpu переполняется. я подозреваю, что где-то проблема с циклом для k, но не могу понять, в чем конкретно проблема. также возможно, что я неправильно переоформила три функции в одну и неправильно вывожу массив. прошу мне помочь, указав причину переполняющейся cpu и возможно вы знаете, как правильно решить задачу на 3 числа через одну функцию.

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
#include <iostream>
using namespace std;
 
int *Iosif(int n, int m){
  int  *latest = new int[3];
  bool *persons = new bool[n];
  for (int i = 0; i < n; i++){
    persons[i] = true;
  }
  int counter = 0;
  int num = -1;
  for (int k=0; k < 3; k++){
  for (int i = 0; i < n -k ; i++){
    while (counter < m) {
      num = (num + 1) % n;
      if(persons[num] == true) counter++;
    }
    counter = 0;
    persons[num] = false;
    }
    latest[k] = ++num;
    }
  delete [] persons;
  
  return latest;
  delete [] latest;
}
 
int main(){
  int n, m;
  cout << "Enter a number of persons >> ";
  cin >> n;
  cout <<"\nEnter an ordinal number >> ";
  cin >> m;
  int* pointer = Iosif(n, m);
  cout << "\n" << pointer[2]<< ' '<< pointer[1]<< ' '<< pointer[0] << endl;
  delete [] pointer;
  return 0;
}

прошу мне помочь, указав причину переполняющейся cpu и возможно вы знаете, как правильно решить задачу на 3 числа через одну функцию.

@igorrr37 · 20.02.2022, 14:45

через std::forward_list

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
#include <iostream>
#include <forward_list>
#include <numeric>
 
 
int main()
{
    int n = 4, m = 2;
    std::forward_list<int> lst(n); // односвязный список
    std::iota(lst.begin(), lst.end(), 1);
    int ler{};
    for (auto ib = lst.before_begin(); !lst.empty(); )
    {
        for (int sc = 0; sc < m - 1; ++sc)
        {
            ++ib;
            if (ib == lst.end())
            {
                ib = lst.begin();
            }
        }
        auto ibc = ib;
        ++ibc;
        if (ibc == lst.end())
        {
            ibc = lst.begin();
            ib = lst.before_begin();
        }
        ler = *ibc;
        if (--n <= 2)
        {
            std::cout << ler << std::endl;
        }
        lst.erase_after(ib);
    }
}
// 1234

Новые блоги и статьи Все статьи Все блоги /
Подстановка значения реквизита справочника в табличную часть документа Maks 10.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: при выборе сотрудника (справочник Сотрудники) в ТЧ документа. . .	Очистка реквизитов документа при копировании Maks 09.04.2026 Алгоритм из решения ниже применим как для типовых, так и для нетиповых документов на самых различных конфигурациях. Задача: при копировании документа очищать определенные реквизиты и табличную. . .	модель ЗдравоСохранения 8. Подготовка к разному выполнению заданий anaschu 08.04.2026 https:/ / github. com/ shumilovas/ med2. git main ветка * содержимое блока дэлэй из старой модели теперь внутри зайца новой модели 8ATzM_2aurI	Блокировка документа от изменений, если он открыт у другого пользователя Maks 08.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа, разработанного в конфигурации КА2. Задача: запретить редактирование документа, если он открыт у другого пользователя. / / . . .
Система безопасности+живучести для сервера-слоя интернета (сети). Двойная привязка. Hrethgir 08.04.2026 Далее были размышления о системе безопасности. Сообщения с наклонным текстом - мои. А как нам будет можно проверить, что ссылка наша, а не подделана хулиганами, которая выбросит на другую ветку и. . .	Модель ЗдрввоСохранения 7: больше работников, больше ресурсов. anaschu 08.04.2026 работников и заданий может быть сколько угодно, но настроено всё так, что используется пока что только 20% kYBz3eJf3jQ	Дальние перспективы сервера - слоя сети с космологическим дизайном интефейса карты и логики. Hrethgir 07.04.2026 Дальнейшее ближайшее планирование вывело к размышлениям над дальними перспективами. И вот тут может быть даже будут нужны оценки специалистов, так как в дальних перспективах всё может очень сильно. . .	Горе от ума kumehtar 07.04.2026 Эта мне ментальная установка, что вот прямо сейчас, мол, мне для полного счастья не хватает (нужное вписать), и когда я этого достигну - тогда и полный кайф. Одна из самых сильных ловушек на пути. . . .