Структуры данных и алгоритмы (1021739), страница 11
Текст из файла (страница 11)
Зарезервированные слова Pascal выделяются полужирным начертанием,типы данных пишутся обычным начертанием, а имена процедур, функций и переменных — курсивом. Мы различаем строчные и прописные буквы.Упражнения1.1.В состязаниях футбольной лиги участвуют шесть команд: Соколы, Львы, Орлы, Бобры, Тигры и Скунсы. Соколы уже сыграли с Львами и Орлами. Львытакже сыграли с Бобрами и Скунсами.
Тигры сыграли с Орлами и Скунсами.Каждая команда играет одну игру в неделю. Найдите расписание матчей, чтобы все команды сыграли по одному разу друг с другом в течение минимального количества недель. Совет. Создайте граф, где вершины будут соответство1Чтобы по возможности не плодить в листингах смесь "английского с нижегородским", мыбудем применять русский язык только в псевдопрограммах, оставляя названия типов данныхна английском языке и давая их перевод или в тексте, или иногда непосредственно в листингах. — Прим. ред.40ГЛАВА 1. ПОСТРОЕНИЕ И АНАЛИЗ АЛГОРИТМОВвать парам команд, которые еще не играли между собой. Что должны обозначать ребра в таком графе, если при правильной раскраске графа каждый цветсоответствует матчам, сыгранным в течение определенной недели?*1.2.
Рассмотрим руку робота с закрепленным одним концом. Рука состоит из двух"колен", каждое из которых может поворачивать руку на 90 градусов вверх ивниз в вертикальной плоскости. Какую математическую модель следует применить для описания перемещения оконечности руки? Разработайте алгоритм дляперемещения оконечности руки из одного возможного положения в другое.*1.3. Предположим, что необходимо перемножить четыре матрицы действительныхчисел Мi х М2 х М3 х М4, где Afj имеет размер 10 х 20, размер М2 составляет20 х 50, М3 — 50 х 1 и М4 — 1 х.100.
Предположим, что для перемножениедвух матриц размером р х q и q х г требуется pqr скалярных операций, это условие выполняется в обычных алгоритмах перемножения матриц. Найдите оптимальный порядок перемножения матриц, который минимизирует общеечисло скалярных операций. Как найти этот оптимальный порядок в случаепроизвольного числа матриц?**1.4.
Предположим, что мы хотим разделить множество значений квадратных корней целых чисел от 1 до 100 на два подмножества так, чтобы суммы чиселобоих подмножества были по возможности максимально близки. Если мы имеем всего две минуты машинного времени для решения этой задачи, то какиевычисления необходимо выполнить?1.5. Опишите "жадный" алгоритм для игры в шахматы.
Каковы, по вашему мнению, его достоинства и недостатки?1.6. В разделе 1.2 мы рассмотрели абстрактный тип данных SET (Множество) соператорами MAKENULL, UNION и SIZE. Для определенности положим, чтовсе множества являются подмножествами множества {О, 1, ..., 31}, а АТД SETинтерпретируется как тип данных языка Pascal set of 0..31. Напишите процедуры на языке Pascal для выполнения этих операторов, используя даннуюреализацию АТД SET.1.7. Наибольшим общим делителем двух целых чисел р и q называется наибольшее целое число d, которое делит р та q нацело.
Мы хотим создать программудля вычисления наибольшего общего делителя двух целых чисел р и q, используя следующий алгоритм. Обозначим через г остаток от деления р на q.Если г равно 0, то q является наибольшим общим делителем. В противномслучае положим р равным q, затем — q равным г и повторим процесс нахождения остатка от деления р на q.а) покажите, что этот алгоритм правильно находит наибольший общий делитель;6} запишите алгоритм в виде программы на псевдоязыке;в) преобразуйте программу на псевдоязыке в программу на языке Pascal.1.8. Мы хотим создать программу форматирования текста, которая выравнивала бытекст по ширине строк. Программа должна иметь' буфер слов и буфер строки.Первоначально оба буфера пусты.
Очередное слово считывается в буфер слов. Если в буфере строки достаточно места, то слово переносится в буфер строки. Впротивном случае добавляются пробелы между словами до полного заполнениябуфера строки, затем после печати строки этот буфер освобождается.а) запишите алгоритм в виде программы на псевдоязыке;б) преобразуйте программу на псевдоязыке в программу на языке Pascal.1.9. Рассмотрим множество из п городов и таблицу расстояний между ними.
Напишите программу на псевдоязыке для нахождения кратчайшего пути, который предусматривает посещение каждого города только один раз и возвращается в тот город, откуда начался путь. На сегодняшний день единственным методом точного решения этой задачи является только метод полного перебораУПРАЖНЕНИЯ411.10.всех возможных вариантов. Попытайтесь построить эффективный алгоритмдля решения этой задачи, используя эвристический подход.Рассмотрим следующие функции от л:/,<я) = л2;2£(л) = л + 1000л;если л нечетно,, если л четно;(л, если л<100,л4( )=\ 3[п , если л>100.Укажите для каждой пары функций, когда Д(л) имеет порядок О(Д(п)) и когда/,(л) есть 0(/Хп)).1.11.
Рассмотрим следующие функции от п:2л для четных л > О,3! л для нечетных л S 1;л для 0 < л < 100,3л для л > 100;Укажите для каждой пары функций, когда gt(n) имеет порядок О(#Дп)) и когдай(л) есть й(^у<л)).1.12. Найдите, используя О-символику, время выполнения в наихудшем случае следующих процедур как функции от л:a) procedure matmpy ( л: integer) ;vmri, j, k: integer;beginfor i : = 1 to п do14for j : = 1 to л do beginC [ i , j ] : = 0;for k:= 1 to л doend•ndC5) procegure mysteiry ( л: integer ) ;vari, j, £: integer;beginfor i : = 1 to- n - i dofor j:= i + 1 to л dofor £:= 1 to j do{группа операторов с временем выполнения 0(1) }endв) procegure veryodd ( л: integer ) ;vari/ j/ x, y.
integer;begin42ГЛАВА 1. ПОСТРОЕНИЕ И АНАЛИЗ АЛГОРИТМОВfor i:= 1 to л doif нечетное(i) then beginfor j:= 1 to л dox: = x + 1 ;for j':= 1 to i doy:= у + 1endend*r)procegure recursive ( n: integer ) : integer;beginif n <= 1 thenreturn(1)elsereturn(recursive(л - 1) + recursive(n - 1))end1.13. Докажите, что следующие утверждения истинны:а) 17 имеет порядок О(1);б) п(п - 1)/2 имеет порядок О(л2);в) max(n3, Юл2) имеет порядок О(п3);г) £i* есть О(л*+1) и Й(л*+1) для целых k;1=1д) если р(х) — полином степени k с положительным старшим коэффициентом,то р(х) есть О(п*) и й(л*).*1.14. Предположим, что Ti(n) есть £1(/(л)) и Т2(п) — fi(g(n)). Какие из следующих• утверждений истинны?а) Тг(п) + Т2(п) есть П(тах(Ял), g(n)));б) Ti(n)r2(n) есть n(f(n)g(n)).*1.15.
Некоторые авторы определяют нижний порядок роста ti следующим образом:f(n) есть £l(g(n)), если существуют такие неотрицательные константы п0 и с,что для всех л > п0 выполняется неравенство /(га) £ cg(n).а) В рамках этого определения будет ли истинным следующее утверждение:f(n) есть й(£(га)) тогда и только тогда, когда g(n) имеет порядок O(f(ri))lб) Будет ли утверждение а) истинным для определения П из раздела 1.4?в) Выполните упражнение 1.14 для данного определения П.1.16. Расположите следующие функции в порядке степени роста: а) п, б) vra ,в) logra, г) log logn, д) Iog2n, e) n/logn, ж) Vn log2 л , з) (1/3)",и) (3/2)", к) 17.1.17. Предположим, что параметр л приведенной ниже процедуры является положительной целой степенью числа 2, т.е.
л = 2, 4, 8, 16, ... . Найдите формулудля вычисления значения переменной count в зависимости от значения л.procegure mystery ( n: integer ) ;varx, count: integer;begincount:= 0;x:= 2;while x < n do beginx:= 2 * x;count:= count + 1/УПРАЖНЕНИЯ43end;endwriteln(count)1.18. Рассмотрим функцию max(i, n), которая возвращает наибольший из элементов,стоящих в позициях от i до i + п - 1 в целочисленном массиве А. Также предположим, что п является степенью числа 2.procegure max ( i, n: integer ) : integer;varml, m2: integer;beginif n = 1 thenreturn(A[i])else bedinml: = max (i, n div 2) ;m2:= xnaxd+л div 2, n div 2 ) ;if ml < m2 thenreturn (m2)elsereturn(ml)endendа) Пусть Т(п) обозначает время выполнения в наихудшем случае программыmax в зависимости от второго аргумента га.
Таким образом, п — число элементов, среди которых ищется наибольший. Запишите рекуррентное соотношение для Т(п), в котором должны присутствовать T(j) для одного илинескольких значений у, меньших п, и одна или несколько констант, представляющих время выполнения отдельных операторов программы max.б) Запишите в терминах О-болыное и П верхнюю и нижнюю границы для Т(п)в максимально простом виде.Библиографические замечанияКонцепция абстрактных типов данных берет свое начало от типа class в языкеSIMULA 67 [12]. С тех пор разработано много языков программирования, поддерживающих абстрактные типы данных, среди которых язык AJphard [100], С с классами[105], CLU [69], MESA [42] и Russell [23]. Концепция АТД активно обсуждалась вработах [43] и [122].[63] — первая большая работа, посвященная систематическому изучению временивыполнения программ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
