Задача-считалка

Считалка. Даны натуральные числа m и n. Предполагается, что n человек встают в круг и получают номера, считая против часовой стрелки, 1, 2, 3,... n. Затем, начиная с первого, также против часовой стрелки отсчитывается m-й человек (поскольку люди стоят по кругу, то за n-м человеком стоит первый). Этот человек выходит из круга, после чего, начиная со следующего, снова отсчитывается m-й человек и так до тех пор пока из всего круга не останется один человек. Определить его номер. Задание №3(Двунаправленные списки) (см. "Сборник задач для начинающего программиста").

Алгоритм:

-Создаём структуру "Titem",которая будет хранить порядковый номер человека из введённого числа участников "считалки" и указатель на следующего и предыдущего человека(элемент списка).

-Описываем функцию "add_item" добавляющую в список порядковые номера участников.

-Запускаем функцию "add_item".

-Выводим на экран исходный список.

-Из списка с порядковыми номерами участников удаляем m-ый по счёту столько раз, пока не останется один участник (после удаления участника считать начинаем со следующего после удалённого).

-Выводим его номер на экран.

#include<stdio.h>
#include<conio.h>  //библиотека с функцией GETCH
 
struct Titem{      //Создаём структуру "Titem"
  int n;
  Titem *next,*prev;
} *first,*s,*p;
 
int n,m;
 
void add_item(int v){     //Описываем функцию "add_item" добавляющую в список порядковые номера участников
  Titem *p;
 
  if (s==NULL && first==NULL){
    s=new Titem;
    s->n = v;
    s->next = NULL;
    s->prev = NULL;
    first=s;
  }
 
  else{
 
    p = new Titem;
    p->n = v;
    p->next=NULL;
    p->prev=s;
    s->next=p;
    s=p;
 
  }
return;
}
 
int main (){
 
  int i;
 
  printf("\nвведите число n ");
  scanf("%d", &n);
 
  printf("\nвведите число m ");
  scanf("%d", &m);
 
  for (i=0; i<n; i++)    //Запускаем функцию "add_item"
    add_item(i+1);
  s->next=first;         //Замыкаем список
  first->prev=s;
 
  p=first;
  for(i=0; i<n; i++){
    printf("%d ",p->n);  //Выводим на экран исходный список
    p=p->next;
  }
  printf("\n");
 
 
  s=first;
  while(n>1){               //Из списка с порядковыми номерами участников удаляем m-ый
                            //по счёту столько   раз, пока не останется один участник
                            //(после удаления    участника считать начинаем со следующего после удалённого)
    p=s;
    for(i=1; i<m; i++)
      p=p->next;
    p->next->prev=p->prev;   //Перед удалением m-ого элемента списка выстраивается свзь между предыдущим 
    p->prev->next=p->next;   //и следующим элементами списка
    s=p->next;
    delete p;
    n--;
  }
 
 
  printf("%d ",s->n);         //Выводим на экран номер оставшегося участника
 
  getch();
  return 0;
}

Ключевые слова: 
Двунаправленные списки
ВложениеРазмер
Prog2.rar9.75 кб