Приложение 2. Примеры реализации алгоритмов
Пример 1. Дано 10 чисел. Определить, какие из них больше своих соседей.
#include <stdio.h>
#include <cstdlib>
int main()
{
int arr[10]; // Массив arr из 10 целочисленных элементов
int i; // Счетчик для циклов
for (i = 0; i < 10; i++) // Вводим элементы массива
{
printf("Введите %d элемент массива : ", i);
scanf("%d",&arr[i]);
}
for (i = 1; i <= 8; i++) // Перебираем все элементы массива от 1 до 8
{
/* Сравниваем элемент с предыдущим и слудующим. Если элемент больше, то выводим его на экран */
if(arr[i] > arr[i-1] && arr[i] > arr[i+1])
printf("\nЭлемент %d больше своих сосдей : %d\n",i,arr[i]);
}
system("pause");
}
Результат выполнения программы
Введите 0 элемент массива : 1
Введите 1 элемент массива : 3
Введите 2 элемент массива : 4
Введите 3 элемент массива : 5
Введите 4 элемент массива : 2
Введите 5 элемент массива : 8
Введите 6 элемент массива : 6
Введите 7 элемент массива : 10
Введите 8 элемент массива : 5
Введите 9 элемент массива : 1
Элемент 3 больше своих сосдей : 5
Элемент 5 больше своих сосдей : 8
Элемент 7 больше своих сосдей : 10
Пример 2. Напечатать заданный непустой текст, удалив из него все цифры.
#include <stdio.h>
#include <cstdlib>
#include <string.h>
int main()
{
int i;
char z; // Текущий вводимый символ
printf (“\nНапишите предложение с точкой в конце:\n”);
/* Пока не встретилась точка считываем символы. Если встретилась цифра, заканчиваем итерацию цикла, иначе выводим символ */
for (i = 0, z = 'a'; z != '.'; i++) {
scanf ("%c", &z);
if (z == '0' || z == '1' || z == '2' || z == '3' || z == '4') continue;
if (z == '5' || z == '6' || z == '7' || z == '8' || z == '9') continue;
printf (“Полученный текст : “);
printf ("%c\n", z);
}
system ("pause");
}
Результат выполнения программы
Напишите предложение с точкой в конце:
З2д3е6с8ь0 н76е9т 2н5и о8д0н7ой 3ц6и6фры4
Полученный текст : Здесь нет ни одной цифры
Пример 3. Определить, находится ли точка внутри шара?
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
typedef struct
{
float x;
float y;
float z;
float R;
} shar;
typedef struct
{
float x;
float y;
float z;
} tochka;
int main()
{
shar S;
tochka T;
printf ("\n Введите координаты шара: x,y,z,R ");
scanf ("%f %f %f %f",&S.x,&S.y,&S.z,&S.R);
printf ("\n Введите координаты точки:x,y,z ");
scanf ("%f %f %f", &T.x,&T.y,&T.z);
if ((T.x-S.x)*(T.x-S.x)+(T.y-S.y)*(T.y-S.y)+(T.z-S.z)*(T.z-S.z)<=S.R*S.R)
printf ("\n Точка находится в шаре!");
else
printf ("\n Точка не находится в шаре!");
getch();
}
Результат выполнения программы
Введите координаты шара: x,y,z,R 0 0 0 2
Введите координаты точки:x,y,z 1 1 1
Точка находится в шаре!
Пример 4. Вычисление периода дроби.
#include <stdio.h>
#include <stdlib.h>
#include <iostream.h>
#include <math.h>
// объявление переменных
int m,n;
int* ostatki;
int* period;
unsigned int len;
// проверка остатков
int IsInOstatki(int ost, int len)
{
//len-1 чтоб не проверять остаток, ввденый на текущем шаге
for (int i = 0; i < len - 1; i++)
{
if (ostatki[i] == ost) return i;
}
return 0;
}
int main()
{
cout << "Введите числитель дроби : \r";
cin >> m;
cout << "\r\nВведите знаменатель дроби : \r";
cin >> n;
ostatki = new int[n+1];
period = new int[n+1];
int d = m, q = n;
int r, pos;
len = 1;
do
{
r = d % q;
ostatki[len] = r;
d /= q;
period[len] = d;
d = 10 * r;
len++;
}
while ((pos = IsInOstatki (r, len/*сколько остатков помещено в массив остатков*/)) == 0);
// вывод результатов
cout << "дробь= \r\n";
cout << period[1] << ",";
for (r = 2; r < len; r++)
{
cout << period[r];
}
cout << "\r\n период = ";
for(r = pos + 1; r < len; r++)
cout << period[r];
cout << "\r\n";
// освобождение ресурсов
delete[] ostatki;
delete[] period;
system ("pause");
}
Результат выполнения программы
Введите числитель дроби :
Введите знаменатель дроби :
дробь
0,923076
период = 923076
Пример 5. Вычисление интервала в днях между двумя датами текущего года.
Год високосный, если он делится на четыре без остатка, но если он делится на 100 без остатка, это не високосный год. Однако если он делится без остатка на 400, это високосный год. Таким образом, 2000 г. является особым високосным годом, который бывает лишь раз в 400 лет.
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <conio.h>
int main()
{
int Temp;
int DaysInMonth[2][12]= //количество дней в месяцах 0-обычном, 1 - високосном
{{31,28,31,30,31,30,31,31,30,31,30,31},
{31,29,31,30,31,30,31,31,30,31,30,31}
};
//вводим исходные данные
int CurrentYear, Diff, Day1, Day2, Month1, Month2, i, Visokos;
printf("\nВведите год : ");
scanf("%d",&CurrentYear);
printf("Введенный год %d. \n",CurrentYear);
//проверяем нависокосный год
if(CurrentYear%400==0 || (CurrentYear%4==0 && CurrentYear%100!=0))
{
printf("\nВисокосный год!\n\n"); Visokos=1;
}
else
{
printf("\nNE Visokosny god!\n\n"); Visokos=0;
}
do
{
printf("Введите день 1 (1-31):");
scanf("%d",&Day1);
printf("Введите месяц 1 (1-12) :");
scanf("%d",&Month1);
}
while ((Month1<1||Month1>12)||(Day1<1||Day1>DaysInMonth[Visokos][Month1-1]));
do
{
printf("Введите день 2 (1-31) : ");
scanf("%d",&Day2);
printf("Введите месяц 2 (1-12) : ");
scanf("%d",&Month2);
}
while ((Month2<1||Month2>12)||(Day2<1||Day2>DaysInMonth[Visokos][Month2-1]));
if(Month1>Month2)
{ //вторая дата должна быть старше первой
Temp=Month1;Month1=Month2;Month2=Temp; //меняем даты местами
Temp=Day1;Day1=Day2;Day2=Temp;
}
Diff=0; //итоговая разность в днях
if (Month1==Month2) Diff=abs(Day1-Day2); //если один и тот же месяц то просто вычитаем дни
else
{
for (i=Month1;i<Month2-1;i++) //пройти по всем ПОЛНОСТЬЮ прошедшим месяцам
Diff += DaysInMonth[Visokos][i]; // и сложить дни
Diff+=(DaysInMonth[Visokos][Month1-1]-Day1);//добавить отстатки дней от первого месяца
Diff+=Day2; //и еще добавить дни второго месяца
}
//вывести результат
printf ("Между %d.%d.%d и %d.%d.%d",Day1,Month1,CurrentYear,Day2,Month2, CurrentYear);
printf ("\nРазница = %d дней\n",Diff);
getch();
}
Результат выполнения программы
Введите год : 2008
Введенный год 2008.
Високосный год!
Введите день 1 (1-31):3
Введите месяц 1 (1-12) :10
Введите день 2 (1-31) : 12
Введите месяц 2 (1-12) : 10
Между 3.10.2008 и 12.10.2008
Разница = 9 дней
Пример 6. Алгоритм построения треугольника Паскаля
Треугольник Паскаля - арифметический треугольник, образованный биномиальными коэффициентами. Назван в честь Блеза Паскаля.
Если очертить треугольник Паскаля, то получится равнобедренный треугольник. В этом треугольнике на вершине и по бокам стоят единицы. Каждое число равно сумме двух расположенных над ним чисел. Продолжать треугольник можно бесконечно. Строки треугольника симметричны относительно вертикальной оси.
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <conio.h>
#define M 13
int main()
{
int n;
int a[M][M];
int i, j, k;
do
{
printf ("Введите n < 12 : ");
scanf("%d", &n);
}
while (n >= 12);
puts ("Таблица 1");
for (i = 0; i <= n; i++)
{
for (j = 0; j <= i; j++)
{
if ((i == j) || (j == 0)) a[i][j] = 1;
else a[i][j] = a[i-1][j-1] + a[i-1][j];
printf ("%4d", a[i][j]);
}
printf ("\n");
}
Puts ("Таблица 2");
for (i = 0; i <= n; i++)
{
for (j = 0;j <= i; j++)
{
if (j == 0)
for (k = 0; k < (n-i); k++) printf (" ");
printf ("%6d", a[i][j]);
}
printf ("\n");
}
getch ();
}
Результат выполнения программы
Введите n < 12 : 7
Таблица 1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
Таблица 2
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
Пример 7. Сравнение способов сортировки: способ «пузырька», сортировка выбором и метод простых вставок.
#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#include <conio.h>
#include <math.h>
inline void Change(int a[], int first, int second)
// меняем местами элементы буфера first на second
// a[] - заданный массив
// first и second - номера элементов массива a, которые надо поменять местами!
{
if (first == second) // Если одинаковые номера элементов, то не нужно менять их местами
return;
int i;
i = a[second];
a[second] = a[first];
a[first] = i;
}
int FindMax(int a[], int max)
// Поиск максимального числа в массиве от a[0] до a[max]
// a[] - заданный массив
// max - размер массива a
{
int imax = 0;
for (int i = 0; i <= max; i++)
{
if (a[imax] < a[i]) imax = i;
}
return imax;
}
void SelectSort(int b[], int max)
// Сортировка выбором
// b[] - заданный массив
// max - размер массива b
{
int i1;
for (int i = max - 1; i > 0; i--)
{
i1 = FindMax(b, i); // Находим самое максимальное число в промежутке от a[0] до a[i]
Change(b, i, i1); // ставим максимальное число в конец (а именно на место эллемента под номером i)
}
}
void BubbleSort(int c[], int max)
// Сортировка "пузырьком"
// c[] - заданный массив
// max - размер массива c
{
for (int i1 = 0; i1 < max; i1++)
{
for (int i = max-2; i >= i1; i--)
{
if (c[i+1] > c[i]) continue;
Change(c, i, i+1); // Двигаем минимальное число вверх, тем самым сортируя числа
}
}
}
void InsertSort(int d[], int max)
// Сортировка методом простых вставок
// d[] - заданный массив
// max - размер массива c
{
int temp, j;
for (int i = 1; i < max; i++) // цикл проходов, i - номер прохода
{
temp = d[i];
j = i - 1; // поиск места элемента в готовой последовательности
while (j >= 0 && d[j] > temp)
{
d[j+1] = d[j]; // сдвигаем элемент направо, пока не дошли
--j;
}
// место найдено, вставить элемент
d[j+1] = temp;
}
}
int main()
{
int MAX;
printf("Введите количество элементов : ");
scanf("%i", &MAX);
// Объявляем буферы
int *a = new int[MAX];
int *b = new int[MAX];
int *c = new int[MAX];
int *d = new int[MAX];
srand((unsigned)time(0));
for (int i = 0; i < MAX; i++)
{
a[i] = rand(); // заполняем случайными числами
b[i] = a[i]; // делаем копию
c[i] = a[i]; // делаем копию
d[i] = a[i]; // делаем копию
}
clock_t begin, end;
begin = clock();
BubbleSort(b, MAX); // Сортируем массив с методом "пузырька"
end = clock();
float f0 = (float)(end-begin); // Измеряем время, занятое сортировкой методом "пузырька"
printf ("\nСортировка массива из %i элементов методом "пузырька" заняла \t%.0f msec.\r\n", MAX, f0);
begin = clock();
SelectSort(c, MAX); // Сортируем массив b методом выбора
end = clock();
float f1 = (float)(end-begin); // Измеряем время, занятое сортировкой методом выбора
printf ("Сортировка массива из %i элементов методом выбора заняла \t%.0f msec.\r\n", MAX, f1);
begin = clock();
InsertSort(d, MAX); // Сортируем массив b методом вставок
end = clock();
float f2 = (float)(end-begin); // Измеряем время, занятое сортировкой методом вставок
printf ("Сортировка массива из %i элементов методом вставок заняла \t%.0f msec.\r\n", MAX, f2);
// Просмотр отсортированных данных?
printf("\r\n\r\n\r\nВы хотите просмотреть отсортированные данные? (y/n)");
short Key = 0;
while (Key = _getch()) // Ожидание нажатия на кнопку
{
if (Key == 'n' || Key == 'N' || Key == 27) // если нажата кнопк N или Esc, то
return 0; // выход
else if (Key == 'y' || Key == 'Y') // если y, то
break; // то продолжаем
}
printf("\r\n\r\n\r\n\r\n");
printf(" N.\tБез сортировки\tN.\tМетод «пузырька»\tN.\tМетод выбора\tN.\tМетод вставки\r\n");
printf("\r\n");
for (int i = 0; i < MAX; i++)
printf("%3i.\t%5i\t%3i.\t%5i\t%3i.\t%5i\t%3i.\t%5i\r\n",
i+1, a[i], i+1, b[i], i+1, c[i], i+1, d[i]); // Печать содержимого массивов
printf("\r\nНажмите любую кнопку для продолжения\r\n");
Key = 0;
while (!Key) Key = _getch(); // Ожидание нажатия на кнопку
}
Результат выполнения программы
Введите количество элементов : 10000
Сортировка массива из 10000 элементов методом "пузырька" заняла 1139 msec.
Сортировка массива из 10000 элементов методом выбора заняла 175 msec.
Сортировка массива из 10000 элементов методом вставок заняла 113 msec.
Вы хотите просмотреть отсортированные данные? (y/n)
N. Без сортировки N. Метод «пузырька» N. Метод выбора N. Метод вставки
1. 30410 1. 1072 1. 1072 1. 1072
2. 7475 2. 1219 2. 1219 2. 1219
3. 13312 3. 1405 3. 1405 3. 1405
4. 30386 4. 1911 4. 1911 4. 1911
5. 27070 5. 3080 5. 3080 5. 3080
6. 11743 6. 6686 6. 6686 6. 6686
7. 23967 7. 6981 7. 6981 7. 6981
8. 7718 8. 7229 8. 7229 8. 7229
9. 24750 9. 7457 9. 7457 9. 7457
10. 29293 10. 7475 10. 7475 10. 7475
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Пример 8. Процедуры для организации и работы с односвязными списками.
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <conio.h>
#include <iostream>
#include <windows.h>
using namespace std;
class Node
{
public:
int number;
Node* next;
};
int main()
{
Node* head = NULL;
Node* lastPtr = NULL;
short action = -1;
while (1)
{
printf("1. Добавить Элемент\n");
printf("2. Просмотр Списка\n");
printf("3. Поиск Элемента\n");
printf("4. Удалить Элемент\n");
printf("5. Удалить Элемент По Выбору\n");
printf("0. Выход\n\n");
printf("Ваш Выбор: ");
cin>>action;
if (action == 0)
{
system("CLS");
break;
}
if (action == 1)
{
system("CLS");
Node* ptr = new Node;
int numb = -1;
printf("Введите Число: ");
cin>>numb;
ptr->number = numb;
ptr->next = NULL;
if (head == 0)
{
head = ptr;
lastPtr = ptr;
system("CLS");
continue;
}
lastPtr->next = ptr;
lastPtr = ptr;
system("CLS");
continue;
}
if (action == 2)
{
Node* ptr = NULL;
system("CLS");
if (head == NULL)
{
printf("\t!!! СПИСОК ПУСТ !!!\n\n");
system("PAUSE");
system("CLS");
continue;
}
printf("* * * * * СПИСОК * * * * *\n\n");
ptr = head;
while (1)
{
cout<<ptr->number<<" ";
if (ptr->next == 0)
break;
ptr = ptr->next;
}
cout<<"\n\n";
system("PAUSE");
system("CLS");
continue;
}
if (action == 3)
{
Node* ptr = NULL;
int key = -1;
system("CLS");
if (head == NULL)
{
printf("\t!!! СПИСОК ПУСТ !!!\n\n");
system("PAUSE");
system("CLS");
continue;
}
printf("Введите Элемент Для Поиска: ");
cin>>key;
ptr = head;
while (1)
{
if (key == ptr->number)
{
printf("\n\t!!! ЭЛЕМЕНТ НАЙДЕН !!!\n");
break;
}
if (ptr->next == NULL)
{
printf("\n\t!!! ЭЛЕМЕНТ НЕ НАЙДЕН !!!\n");
break;
}
ptr = ptr->next;
}
system("PAUSE");
system("CLS");
continue;
}
if (action == 4)
{
system("CLS");
Node* ptrDelete = NULL;
if (head == NULL)
{
printf("\t!!! СПИСОК ПУСТ !!!\n\n");
system("PAUSE");
system("CLS");
continue;
}
if (head->next == NULL)
{
head = NULL;
delete head;
continue;
}
ptrDelete = head;
head = ptrDelete->next;
delete ptrDelete;
continue;
}
if (action == 5)
{
system("CLS");
Node* ptrPrev = NULL;
Node* ptrDelete = NULL;
int key = -1;
if (head == NULL)
{
printf("\t!!! СПИСОК ПУСТ !!!\n\n");
system("PAUSE");
system("CLS");
continue;
}
printf("Введите Элемент Для Удаления: ");
cin>>key;
ptrDelete = head;
if (ptrDelete->number == key)
{
head = ptrDelete->next;
delete ptrDelete;
system("CLS");
continue;
}
while (1)
{
if (key == ptrDelete->number)
{
ptrPrev->next = ptrDelete->next;
delete ptrDelete;
break;
}
if (ptrDelete->next == 0)
{
printf("\n\t!!! ЭЛЕМЕНТ НЕ НАЙДЕН !!!\n");
system("PAUSE");
break;
}
ptrPrev = ptrDelete;
ptrDelete = ptrDelete->next;
}
system("CLS");
continue;
}
if (action > 5)
{
system("CLS");
printf("\t!!! НЕВЕРНЫЙ ВЫБОР. ПОВТОРИТЕ ВВОД !!!\n\n");
system("PAUSE");
system("CLS");
continue;
}
}
}
Результат выполнения программы (меню программы)
1. Добавить Элемент
2. Просмотр Списка
3. Поиск Элемента
4. Удалить Элемент
5. Удалить Элемент По Выбору
0. Выход
Ваш Выбор:
Пример 9. Процедуры для организации и работы с двусвязными списками.
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <conio.h>
#include <iostream>
#include <windows.h>
using namespace std;
class Node
{
public:
int number;
Node* next;
Node* last;
};
void main()
{
short action = -1;
Node* head = NULL;
Node* tail = NULL;
Node* ptrLast = NULL;
while (1)
{
puts("1. Добавить Элемент\n");
puts("2. Просмотр Списка слева направо\n");
puts("3. Просмотр Списка направа слево\n");
puts("4. Удалить головной элемент\n");
puts("5. Удалить последний элемент\n");
puts("6. Поиск элемента\n");
puts("0. Выход\n\n");
puts("Ваш выбор: ");
cin>>action;
if (action == 0)
{
system("CLS");
break;
}
if (action == 1)
{
system("CLS");
int numb = -1;
puts("Введите число: ");
cin>>numb;
Node* ptr = new Node;
ptr->number = numb;
ptr->next = NULL;
tail = ptr;
if (head == NULL)
{
head = ptr;
ptrLast = ptr;
ptr->last = NULL;
system("CLS");
continue;
}
ptr->last = ptrLast;
ptrLast->next = ptr;
ptrLast = ptr;
system("CLS");
continue;
}
if (action == 2)
{
system("CLS");
Node* ptr = NULL;
if (head == NULL)
{
puts("\t!!! Список пуст !!!\n\n");
system("PAUSE");
system("CLS");
continue;
}
puts("* * * * * Список: слева направо * * * * *\n\n");
ptr = head;
while (1)
{
cout<<ptr->number<<" ";
if (ptr->next == 0)
break;
ptr = ptr->next;
}
cout<<"\n\n";
system("PAUSE");
system("CLS");
continue;
}
if (action == 3)
{
system("CLS");
Node* ptr = NULL;
if (head == NULL)
{
puts("\t!!! Список пуст !!!\n\n");
system("PAUSE");
system("CLS");
continue;
}
puts("* * * * * Список: справа налево * * * * *\n\n");
ptr = tail;
while (1)
{
cout<<ptr->number<<" ";
if (ptr->last == 0)
break;
ptr = ptr->last;
}
cout<<"\n\n";
system("PAUSE");
system("CLS");
continue;
}
if (action == 4)
{
system("CLS");
Node* ptrDelete = NULL;
if (head == NULL)
{
puts("\t!!! Список пуст !!!\n\n");
system("PAUSE");
system("CLS");
continue;
}
if (head->next == NULL)
{
head = NULL;
tail = NULL;
delete head;
continue;
}
ptrDelete = head;
head = ptrDelete->next;
head->last = NULL;
delete ptrDelete;
continue;
}
if (action == 5)
{
system("CLS");
Node* ptrDelete = NULL;
if (tail == NULL)
{
puts("\t!!! Список пуст !!!\n\n");
system("PAUSE");
system("CLS");
continue;
}
if (tail->last == NULL)
{
head = NULL;
tail = NULL;
delete tail;
continue;
}
ptrDelete = tail;
tail = ptrDelete->last;
tail->next = NULL;
ptrLast = tail;
delete ptrDelete;
continue;
}
if (action == 6)
{
system("CLS");
Node* ptr = NULL;
int key = -1;
if (head == NULL)
{
puts("\t!!! Список пуст !!!\n\n");
system("PAUSE");
system("CLS");
continue;
}
puts("Введите искомый элемент: ");
cin>>key;
ptr = head;
while (1)
{
if (key == ptr->number)
{
puts("\n\t!!! Элемент найден !!!\n");
break;
}
if (ptr->next == NULL)
{
puts("\n\t!!! Элемент не найден !!!\n");
break;
}
ptr = ptr->next;
}
system("PAUSE");
system("CLS");
continue;
}
if (action > 6)
{
system("CLS");
puts("\t!!! Неверный выбор. Повторите ввод !!!\n\n");
system("PAUSE");
system("CLS");
continue;
}
}
}
Результат выполнения программы (меню программы)
1. Добавить Элемент
2. Просмотр Списка слева направо
3. Просмотр Списка направа слево
4. Удалить головной элемент
5. Удалить последний элемент
6. Поиск элемента
0. Выход
Ваш выбор:
Пример 10. Процедуры для организации очередей и работы с ними.
class Node
{
public:
int number;
Node* last;
Node* next;
};
int main()
{
Node* head = NULL;
Node* tail = NULL;
Node* ptrLast = NULL;
short action = -1;
while(1)
{
printf("1. Добавить Элемент\n");
printf("2. Просмотр Очереди\n");
printf("3. Удалить Элемент\n");
printf("4. Поиск Элемента\n");
printf("0. Выход\n\n");
printf("Ваш Выбор: ");
cin>>action;
if (action == 0)
{
system("CLS");
break;
}
if (action == 1)
{
system("CLS");
int numb = -1;
printf("Введите Число: ");
cin>>numb;
Node* ptr = new Node;
ptr->number = numb;
ptr->next = NULL;
tail = ptr;
if (head == NULL)
{
head = ptr;
ptrLast = ptr;
ptr->last = NULL;
system("CLS");
continue;
}
ptr->last = ptrLast;
ptrLast->next = ptr;
ptrLast = ptr;
system("CLS");
continue;
}
if (action == 2)
{
system("CLS");
Node* ptr = NULL;
if (head == NULL)
{
printf("\t!!! ОЧЕРЕДЬ ПУСТА !!!\n\n");
system("PAUSE");
system("CLS");
continue;
}
printf("* * * * * ОЧЕРЕДЬ * * * * *\n\n");
ptr = tail;
while (1)
{
cout<<ptr->number<<" ";
if (ptr->last == 0)
break;
ptr = ptr->last;
}
cout<<"\n\n";
system("PAUSE");
system("CLS");
continue;
}
if (action == 3)
{
system("CLS");
Node* ptrDelete = NULL;
if (head == NULL)
{
printf("\t!!! ОЧЕРЕДЬ ПУСТА !!!\n\n");
system("PAUSE");
system("CLS");
continue;
}
if (head->next == NULL)
{
head = NULL;
tail = NULL;
delete tail;
continue;
}
ptrDelete = head;
head = ptrDelete->next;
head->last = NULL;
delete ptrDelete;
continue;
}
if (action == 4)
{
system("CLS");
Node* ptr = NULL;
int key = -1;
if (head == NULL)
{
printf("\t!!! СПИСОК ПУСТ !!!\n\n");
system("PAUSE");
system("CLS");
continue;
}
printf("Введите Элемент Для Поиска: ");
cin>>key;
ptr = head;
while (1)
{
if (key == ptr->number)
{
printf("\n\t!!! ЭЛЕМЕНТ НАЙДЕН !!!\n");
break;
}
if (ptr->next == NULL)
{
printf("\n\t!!! ЭЛЕМЕНТ НЕ НАЙДЕН !!!\n");
break;
}
ptr = ptr->next;
}
system("PAUSE");
system("CLS");
continue;
}
if (action > 4)
{
system("CLS");
printf("\t!!! НЕВЕРНЫЙ ВЫБОР. ПОВТОРИТЕ ВВОД !!!\n\n");
system("PAUSE");
system("CLS");
continue;
}
}
}
Результат выполнения программы (меню программы)
1. Добавить Элемент
2. Просмотр Очереди
3. Удалить Элемент
4. Поиск Элемента
0. Выход
Ваш выбор:
Пример 11. Процедуры для организации и работы со стеками.
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <conio.h>
#include <iostream>
#include <windows.h>
using namespace std;
class Node
{
public:
int number;
Node* last;
};
int main()
{
Node* ptrLast = NULL;
Node* top = NULL;
short action = -1;
while (1)
{
printf("1. Затолкнуть В Стек\n");
printf("2. Вытолкнуть Из Стека\n");
printf("3. Вершина Стека\n");
printf("4. Содержимое Стека\n");
printf("0. Выход\n\n");
printf("Ваш Выбор: ");
cin>>action;
if (action == 0)
{
system("CLS");
break;
}
if (action == 1)
{
system("CLS");
int numb = -1;
printf("Введите Число: ");
cin>>numb;
Node* ptr = new Node;
ptr->number = numb;
if (top == NULL)
{
ptr->last = NULL;
top = ptr;
ptrLast = ptr;
system("CLS");
continue;
}
top = ptr;
ptr->last = ptrLast;
ptrLast = ptr;
system("CLS");
continue;
}
if (action == 2)
{
system("CLS");
Node* ptrDelete = NULL;
if (top == NULL)
{
printf("\t!!! СТЕК ПУСТ !!!\n\n");
system("PAUSE");
system("CLS");
continue;
}
ptrDelete = top;
if (ptrDelete->last == NULL)
{
top = NULL;
delete ptrDelete;
system("CLS");
continue;
}
top = ptrDelete->last;
ptrLast = top;
delete ptrDelete;
continue;
}
if (action == 3)
{
system("CLS");
if (top == NULL)
{
printf("\t!!! СТЕК ПУСТ !!!\n\n");
system("PAUSE");
system("CLS");
continue;
}
printf("Вершина Стека: ");
cout<<top->number<<"\n\n";
system("PAUSE");
system("CLS");
continue;
}
if (action == 4)
{
system("CLS");
Node* ptr = NULL;
if (top == NULL)
{
printf("\t!!! СТЕК ПУСТ !!!\n\n");
system("PAUSE");
system("CLS");
continue;
}
printf("* * * * * СОДЕРЖИМОЕ СТЕКА * * * * *\n\n");
ptr = top;
while (1)
{
cout<<ptr->number<<endl;
if (ptr->last == NULL)
{
system("PAUSE");
system("CLS");
break;
}
ptr = ptr->last;
}
}
if (action > 4)
{
system("CLS");
printf("\t!!! НЕВЕРНЫЙ ВЫБОР. ПОВТОРИТЕ ВВОД !!!\n\n");
system("PAUSE");
system("CLS");
continue;
}
}
}
Результат выполнения программы (меню программы)
1. Затолкнуть В Стек
2. Вытолкнуть Из Стека
3. Вершина Стека
4. Содержимое Стека
0. Выход
Ваш выбор:
Пример 12. Алгоритм решения задачи «Ханойская башня».
Ханойская башня является одной из популярных головоломок XIX века. Даны три стержня, на один из которых нанизаны восемь колец, причем кольца отличаются размером и лежат меньшее на большем. Задача состоит в том, чтобы перенести пирамиду из восьми колец за наименьшее число ходов. За один раз разрешается переносить только одно кольцо, причём нельзя класть большее кольцо на меньшее.
Эту известную игру придумал французский математик Эдуард Люка, в 1883 году её продавали как забавную игрушку. Первоначально она называлась «Профессор Клаус (Claus) из Коллеж Ли-Су-Стьян (Li-Sou-Stian)», но вскоре обнаружилось, что таинственный профессор из несуществующего колледжа - не более чем анаграмма фамилии изобретателя игры - профессора Люка (Lucas) из коллежа Сен-Луи (Saint Louis).