Алгоритмизации

• Название: Алгоритмизации
• Дата: 27.09.2022
• Размер: 1.15 Mb.
• Имя файла: 12_100229_1_124427 (1).docx
• Тип: Документы; #700459
• страница: 43 из 67

ЗАДАНИЕ 9. Деревья и польская запись

Вариант1.Созданиеиобработкаструктуртипа«дерево»

Разработать проект для обработки дерева поиска, каждый элемент которого содержит целочисленный ключ и строку текста, содержащую, например, ФИО и номер паспорта (ввод исходной информации рекомендуется записать в файл). В программе должны быть реализованы следующие возможности:

• 
  создание дерева;
  
• 
  добавление новой записи;
  
• 
  поиск информации по заданному ключу;
  
• 
  удаление информации с заданным ключом;
  
• 
  вывод информации;
  
• 
  решение индивидуального задания;
  
• 
  освобождение памяти при выходе из программы.
  

1. 
   Поменять местами информацию, содержащую максимальный и минимальный ключи.
   
2. 
   Подсчитать число листьев в дереве.
   
3. 
   Удалить из дерева ветвь с вершиной, имеющей заданный ключ.
   
4. 
   Определить глубину дерева.
   
5. 
   Определить число узлов на каждом уровне дерева.
   
6. 
   Удалить из левой ветви дерева узел с максимальным значением ключа и все связанные с ним узлы.
   
7. 
   Определить количество узлов с четными ключами.
   
8. 
   Определить число листьев на каждом уровне дерева.
   
9. 
   Определить число узлов в дереве, имеющих только одного потомка.
   
10. 
    Определить количество узлов правой ветви дерева.
    
11. 
    Определить количество записей в дереве, начинающихся с введенной с клавиатуры буквы.
    
12. 
    Найти среднее значение всех ключей дерева и найти строку, имеющую ближайший к этому значению ключ.
    
13. 
    Определить количество узлов левой ветви дерева.
    
14. 
    Определить число узлов в дереве, имеющих двух потомков.
    
15. 
    Найти запись с ключом, ближайшим к среднему значению между максимальным и минимальным значениями ключей.
    

Вариант2.Созданиеииспользованиепольскойзаписи

Написать программу формирования обратной польской записи и расчета полученного выражения. Предусмотреть возможности того, что идентификаторы могут состоять более чем из одного символа и могут быть использованы операции % и возведение в степень. Результат работы программы проверить на конкретном примере (табл. 15.1).

Например, если ввести выражение (a + b)*(c– d)/e и значения переменныха= 3, b= 5, c= 6, d= 9, е= 7, должны получиться следующие результаты:

Постфикснаяформаab+cd– *e/

Результатрасчета –3.42857

Таблица 15.1

№	Выражение a	b	c		d	eРез	ультат
1 a	/(b– c)*(d+e)	8.6	2.4	5.1	0.3	7.9	– 26.12
2	(a+b)*(c– d)/e	7.4	3.6	2.8	9.5	0.9	– 81.89
3 a	– (b+c*d)/e	3.1	5.4	0.2	9.6	7.8	2.16
4 a	/b– ((c+d)*e)	1.2	0.7	9.3	6.5	8.4	– 131.006
5 a	*(b– c+d)/e	9.7	8.2	3.6	4.1	0.5	168.78
6	(a+b)*(c– d)/e	0.8	4.1	7.9	6.2	3.5	2.38
7 a	*(b– c)/(d+e)	1.6	4.9	5.7	0.8	2.3	– 0.413
8 a	/(b*(c+d))– e	8.5	0.3	2.4	7.9	1.6	1.151
9	(a+(b/c– d))*e	5.6	7.4	8.9	3.1	0.2	0.666

10	a*(b+c)/(d– e)	0.4	2.3	6.7	5.8	9.1	– 1.091
11	a– (b/c*(d+e))	5.6	3.2	0.9	1.7	4.8	– 17.51
12	(a– b)/(c+d)*e	0.3	6.7	8.4	9.5	1.2	– 0.429
13	a/(b+c– d*e)	7.6	4.8	3.5	9.1	0.2	1.173
14	a*(b– c)/(d+e)	0.5	6.1	8.9	2.4	7.3	– 0.144
15	(a+b*c)/(d– e)	9.1	0.6	2.4	3.7	8.5	– 2.196