Информационни технологии & Интернет

Задание: Около кръгла маса са наредени n на брой човека, номерирани последователно с числата от 1 до n. След това започвайки от номер 1, всеки трети напуска масата, докато накрая остане само един човек. След всяко напускане се сменя посоката на броене. Да се определи номерът на този, който остава последен.

Описание на решението:
мотивировка за избора на конкретно представяне на данните. Използване на СА алгоритми.
Данните са представени чрез двусвързан кръгов списък, тъй като елементите му – n брой човека са наредени около кръгла маса.
Двусвързаният кръгов списък представлява кръгова структура от свързани еднотипни компоненти. Компонентите на двусвързания списък са динамични променливи с три полета:
две указателни полета pre и next – указващи предходната и следващата компоненти в двусвързан списък и информационно поле st, което е ключ, т.е. поле с уникална стойност за всяка компонента;
Списъкът e подреден в нарастващ ред на стойностите на ключа;

Графично изобразяване на избраната структура на данните:

pre st=n next

Наложените върху входните данни ограничени;
Елементите на кръговия двусвързан списък са естествените числа от 1 до n.
да бъде избран ключ за търсене;
Ключът за търсене е третия елемент от списъка, който напуска масата, докато накрая остане само един човек т.е. един елемент от списъка. След всяко напускане се сменя посоката на обхождане.
Задачата не е решена чрез използване на ключ за търсене.
описание на алгоритъма на решението.
Първо се създава двусвързан кръгов списък с дължина n. След това той се обхожда в една посока.  Намира се третия му елемент, който се изтрива. Като се смени посоката, търсенето на третия елемент продължава. Организира се цикъл, докато остане само един елемент от списъка. Накрая се извежда номера му.

III. Описание на използваните процедури и функции:

В програмата са използвани следните функции:
§    List_People(int x,List_People *p );
Използваните параметри са: x – номера на елемента на двусвързания кръгов списък (целочислена променлива), List_People *p– указател към обект от тип двусвързан кръгов списък.
Чрез тази функция се прави описание на конструктора с име List_People *p. Тя се извиква винаги при създаване на обект от този клас.

§    create(int m,List_People*q1);
Използваните параметри са: m – дължина на двусвързан кръгов списък (целочислена променлива), List_People *q1– указател към обект от тип двусвързан кръгов списък.
Тази функция декларира указател към тип List_People, помни първия му елемент(*q1). С помощта на цикъл, започвайки от     указател към тип List_People, създава нов указател към обект от тип List_People и извиква конструктор с параметри i и q – указател към i-тия елемент. Осъществява достъп на следващия елемент на обекта от тип List_People и му присвоява стойност p – указател към следващия елемент. Тъй като списъкът е кръгов първият му елемент получава адреса на последния, а последния получава адреса на първия.

§    del(List_People *p);
Използваният параметър е List_People *p – указател към обект от тип двусвързан кръгов списък.
Действието на функцията е да изтрие намерения трети елемент от списъка, да изведе номера на изтрития му елемент и да замени следващия с предходния и предходния със следващия елемент.

§    tarsi13(int m List_People*p);
Използваните параметри са: m – дължина на двусвързан кръгов списък, List_People*p – указател към обект от тип двусвързан кръгов списък, pos – определя посоката на обхождане на списъка, i,j,k – броячи към оператор за цикъл for. Променливите n, pos, i,j и k са целочислени.
Тази функция организира цикъл, чрез който обхожда списъка, намира третия му елемент, изтрива го като извиква функция del за обект към указател p, сменя посоката на обхождане и повтаря действията докато остане само един елемент от списъка. Накрая извежда неговия номер.
Глобалните променливи, участващи в задачата са: n-брой елементи на кръгов двусвързан списък, a-обект от тип List_People  и uk-указател от тип List_People.

IV. Тестови   примери, доказващи верността на посочените процедури или функции:

Пример1:

Vavedete broq na elementite v spisaka: 12
3-number of deleted element from round list
1-number of deleted element from round list
4-number of deleted element from round list
12-number of deleted element from round list
5-number of deleted element from round list
11-number of deleted element from round list
6-number of deleted element from round list
10-number of deleted element from round list
7-number of deleted element from round list
9-number of deleted element from round list
8-number of deleted element from round list
Posledniq element ot spisaka e 2.

Пример2:

Vavedete broq na elementite v spisaka: 21
3-number of deleted element from round list
1-number of deleted element from round list
4-number of deleted element from round list
21-number of deleted element from round list
5-number of deleted element from round list
20-number of deleted element from round list
6-number of deleted element from round list
19-number of deleted element from round list
7-number of deleted element from round list
18-number of deleted element from round list
8-number of deleted element from round list
17-number of deleted element from round list
9-number of deleted element from round list
16-number of deleted element from round list
10-number of deleted element from round list
15-number of deleted element from round list
11-number of deleted element from round list
14-number of deleted element from round list
12-number of deleted element from round list
13-number of deleted element from round list
Posledniq element ot spisaka e 2.

Пример3:

Vavedete broq na elementite v spisaka: 5
3-number of deleted element from round list
1-number of deleted element from round list
4-number of deleted element from round list
5-number of deleted element from round list
Posledniq element ot spisaka e 2.

Листинг с целия код (с коментари):

#include <iostream.h>

struct List_People {
int st;
List_People *next;
List_People *pre;
public:
List_People(int,List_People *);
void create(int,List_People *);
void tarsi13(int,List_People *);
void del(List_People *);

};
//constructor descripion
List_People::List_People(int x,List_People *p )
{st=x;
pre=p;};

//Set list function
void List_People::create(int m,List_People *q1)
{
List_People *q;
q=q1;
for(int i=2;i<=m;i++){
List_People *p;
p=new List_People(i,q);

q->next=p;
//    cout<<q->pre<<”=”<<q->next<<”z”;
q=p;
}
q1->pre=q;
q->next=q1;
};

//Deletion list people function
void List_People::del(List_People*p)
{
List_People *ne,*pr;
ne=p->next;
pr=p->pre;
cout<<p->st<<”-number of deleted element from round list”<<endl;
ne->pre=pr;
pr->next=ne;

};

//Function for search from list
void List_People::tarsi13(int m, List_People*p)
{
int pos=1;
for(int k=1;k<m;k++){

if(pos==1)
{pos=0; for(int i=1;i<3;i++){p=p->next;};}
else {pos=1; for(int j=1;j<3;j++){p=p->pre;};}
p->del(p); };

p=p->next;
cout<<”Posledniq element ot spisaka e “<<p->st<<”\n” ;
};

//Main program
int main()
{
int n;
cout <<”Vavedete broq na elementite v spisaka: “;
cin>>n;

List_People a(1,NULL); //obekt s ime a i stojnost pre=NULL-prazen ukazatel
List_People *uk=&a; //na ukazatel ot tip List_People se prisvoqva stojnost adresa na obekta
a.create(n,uk);   //sazdavame spisaka
a.tarsi13(n,uk);  //izpalnqvame zada4ata

return 0;

}

Сходни статии:

1. Алгоритми АЛГОРИТМИ – ОСНОВНИ ПОНЯТИЯ Думата ’алгоритъм’ идва от името на арабския математик al-Khwarezmi, който през VIII в. описва откриването на десетичната бройна система и представя редица важни концепции в книгата...
2. Програмиране и използване на компютри. Програмиране на С++ Условие на задачата: Дадени са четири таблици,в които са записани цели шест цифрени положителни числа. Таблиците имат M реда и N колони(3 ≤ M≤10 и 3≤ N≤5).Напишете програма, с която...
3. Пример за обектно – ориентирана реализация на свързан списък В примера се използва шаблон на класа List за обработка на списък от данни от цял тип и списък от данни с плаваща точка. Програма driver дава възможност да се...
4. По-важни алгоритми Програма за преобразуване на еднобайтово число в допълнителен код Инструкцията NEG преобразува в допълнителен код, като инвертира всички 8 бита на числото и добавя единица. За знак използва флага N...
5. Криптографски алгоритми Известните базови криптографски алгоритми се класифицират по различни класификационни признаци. Като класификационен признак на първото ниво на класификацията е използвано свойството симетричност на алгоритмите. По този признак базовите криптографски алгоритми...