1. Что является наиболее важным при написании эффективных программ?

2. Какой тип программ следует оптимизировать? Какой тип программ оптимизировать не надо?

3. Почему оптимизирующий компилятор необходим даже в том случае, когда программист выполнил оптимизацию?

4. Что означают понятия: оверлейность программ, свертка, уменьшение силы операции, исключение повторяющихся выражений, исключение циклов, исключение инвариантных выражений, развертка цикла, критическая область, локализованность?

5. В каком случае использовать цикл менее эффективно, чем программировать последовательно?

6. Как следует располагать вложенные циклы, чтобы сократить число инициирований и проверок цикла?

7. Какие области программы наиболее выгодны для оптимизации?

8. Расположите нижеуказанные операции по скорости их выполнения—от самой быстрой к самой медленной:

а) деление, г) извлечение корня, б) сложение, д) возведение в степень, в) умножение, е) вычитание.

9. Запрограммируйте следующие выражения наиболее эффективным способом:

а) В= —

б) С = Р**0.5

в) Y = 5*4+3*2—2х+2

г) T=COS(THETA) — COS(THETA)**2.0

д) PUT=COST/2*4*K е) T = P/2+(6—R)/4—T/2

ж) Y = 6+T**5.0

з) T=2* PI/4

и) IF(A<B) OR (C>D) THEN X = 4 ELSE Y = 0;

ЗАДАНИЯ

10. Имеется ли оптимизирующий компилятор, пригодный для вашего языка программирования? Если да, то какие типы оптимизации он выполняет?

И. Какие режимы компилятора используются на вашей машине Для ускорения компилирования во время отладки?

12. Какие режимы компилятора используются на вашей машине для ускорения выполнения программы?

13. Имеется ли в вашем компиляторе версия, минимизирующая использование объема памяти в объектной программе за счет снижения скорости выполнения? Можно ли повысить скорость выполнения за счет памяти?

14. Выберите два различных оператора в вашем языке программирования и разработайте тесты, выявляющие, какой оператор выполняется быстрее.

15. Получите листинг ассемблера одной из ваших программ, записанных на языке высокого уровня. Проверьте по листингу ассемблера, какие операторы программы создают самые эффективные коды.

16. Опишите эффективный алгоритм нахождения всех множителей числа. Например, множителями числа 12 являются 1, 2, 3, 4, 6 и 12. Если вы не уверены, что это наиболее эффективный алгоритм, напишите для него программу.

17. Игра в шахматы. Напишите алгоритм расположения максимального количества коней на шахматной доске таким образом, чтобы ни один конь не мог угрожать другому.

18. Какие шаги можно предпринять при компилировании с языка программирования, используемого вами, для ускорения выполнения компилируемой программы?

19. Какой тип переменных наиболее эффективен для использования в качестве индексов в вашем языке программирования?

20. Какой тип переменных наиболее эффективен для проведения многочисленных вычислений с нецелочисленными переменными в вашем языке программирования?

21. Как ваш компилятор обрабатывает приведенное ниже выражение?

В=3.0/4.0*В

Выражение 3.0/4.0 вычисляется во время компилирования или во время выполнения? Посмотрев программу на ассемблере, можно получить ответ.

22. Каким образом вы организуете оверлейность программ на языке программирования, который вы используете?

23. Имеются ли способы задания эквивалентности в вашем языке программирования? Как следует описать два массива, чтобы они использовали одни и те же ячейки памяти?

24. Каким образом вы. можете инициировать в вашем языке программирования переменные (массивы) во время компилирования, а не во время выполнения?

25. Сохраняет ли ваш компилятор константы в форме, не требующей преобразований во время выполнения?

26. Какое время выполнения на вашей машине каждой из нижеследующих операций (просмотрите машинные команды):

а) сложения целых чисел, б) сложения вещественных чисел, в) умножения целых чисел,

* г) умножения вещественных чисел, д) деления вещественных чисел.

27. Получите листинг на ассемблере для программы на языке высокого уровня. Какие операторы представляются вам неэффективными?

28. Использует ли ваша машина двойную буферизацию для операций ввода-вывода? Можете ли вы запросить большее или меньшее количество буферов? Если да, то попытайтесь изменить количество буферов и посмотрите, будет ли изменяться время, используемое программой.

29. Найдите, программу, которую нужно оптимизировать, и попытайтесь сделать это, используя методы, обсуждаемые в этой главе.

30. Можете ли вы придумать методы оптимизации вашей программы, которые не обсуждались в этой главе?

ПРОГРАММЫ

31. Напишите программу, которая должна прочесть первые N положительных целых чисел и найти их сумму.

32. Сложные проценты/ Предположим, что сделан вклад 100 долл. на 55 лет с ежеквартальной прибылью 6%. Найдите суммарную прибыль.

33. Предположим, что I, J, К и L — целые положительные числа, меньшие 20. Напишите программу нахождения значений, удовлетворяющих уравнению "

P + J* + K*=L*.

Программа должна быть как удобочитаемой, так и эффективной. Сравните свое решение с решением вашего коллеги.

34. Задачи сортировки являются хорошими тестами для выбора алгоритма и методов эффективности. Считайте N чисел, затем выполните их сортировку в возрастающей последовательности и на-. печатайте номера членов последовательности, полученные в результате сортировки. Если у вас есть функция — генератор случайных чисел, используйте ее для получения 1000 случайных чисел и выполните их сортировку. Сравните вашу программу с какой-либо другой программой сортировки и посмотрите, чья программа быстрее. Информацию об алгоритмах сортировки вы можете почерпнуть из книги Д. Кнута!>.

35. Табличный поиск. Составьте таблицу из 1000 случайных чисел, значения которых расположены между 1 и 10 000. Напишите программу, которая считывает положительные целые числа, меньшие 10 000, и определяет, имеются ли эти числа в таблице. Вы можете составить таблицу и организовать поиск в ней любым способом, который вам нравится.

36. Диагональная матрица2). Все элементы диагональной матрицы равны нулю, кроме тех, которые расположены по главной диаPaJ- кпа!Ь D* Е" The Art of ComPuter Programming, Vol. 3, Addison-Wesley, nn!S л ' 1?73* [Имеется перевод: Кнут Д., Искусство программирования для ЭВМ, т. 3. —М.: Мир, 1978.]

^ля этой матРичной задачи придумайте сначала эффективный способ хранения матрицы.

гонали. Напишите программу, которая перемножает две диагональные матрицы.

37. Симметрическая матрица. Симметрическая матрица идентична матрице, полученной при ее транспонировании, т. е. для любого элемента ац=а$г. Напишите программу чтения и перемножения двух симметрических матриц. Эффективна ли ваша программа?

38. Треугольная матрица. Элементы нижней треугольной матрицы равны нулю выше главной диагонали, т. е. а^=09 если \>и Напишите эффективную программу для сложения двух больших нижних треугольных матриц.

39. Тетраэдная матрица. Тетраэдная матрица является трехмерной треугольной матрицей. После того как вы представите себе, как она выглядит, напишите программу, которая читает ее элементы и эффективно работает с ними.

40. Трехдиагональная матрица. Трехдиагональная матрица содержит нулевые элементы везде, кроме трех главных диагоналей, т, е. наддиагонали, диагонали и поддиагонали:

а^=0, если |*—/|>1.

Напишите эффективную программу сложения двух трехдиагональ-ных матриц.

41. Повторяющиеся элементы. Предположим, у вас есть большая прямоугольная матрица. Некоторые столбцы матрицы идентичны. Разработайте такой способ запоминания матрицы, чтобы одинаковые столбцы запоминались не более одного раза. Пусть имеются две такие матрицы одинакового размера. Сложите эти матрицы. Совсем необязательно, что одни и те же столбцы этих матриц одинаковы.

42. Разреженная матрица. Предположим, что у вас есть две очень большие матрицы (1000X1000 элементов каждая) и что большинство элементов этих матриц (95%) равно нулю. Придумайте способ эффективного хранения матриц. Затем напишите программу сложения и умножения этих матриц.

43. Если предыдущие задачи для вас слишком легкие, попытайтесь выполнить их для разреженной симметрической матрицы или для разреженной треугольной матрицы. Существует ли разреженная симметрическая или. треугольная матрица?

44. Напишите программу, которая находит наименьшее и наибольшее значения в векторе с п элементами. Определите минимальное число сравнений, необходимых для этого вектора.

45. Напишите программу, которая изменяет порядок элементов в векторе на обратный. Определите минимальное число изменений, которые нужно сделать для вектора с п элементами.

46. Позволяет ли система, на которой вы работаете, читать показания датчика времени? Как вы используете эти показания и какое время вы получаете (астрономическое время, время, прошедшее с момента запуска датчика, машинное время). Можете ли вы измерить время выполнения подпрограммы?

47. Числа Армстронга. Число из п цифр является числом Армстронга, если сумма цифр, возведенных в я-ю степень, равна самому числу. Таким числом является, например, число 153:

153=13+53 + 33 Числом Армстронга из четырех цифр является 1634:

1634=14+64+34 + 44

Найдите все числа Армстронга, состоящие из двух, трех " четырех цифр. Напишите эффективную программу нахождения этих чисел.

ПРОЕКТЫ

48. Волчий остров размером 20X20 заселен дикими кроликами, волками и волчицами. Имеется по нескольку представителей каждого вида. Кролики довольно глупы: в каждый момент времени они с одинаковой вероятностью 1/9 передвигаются в один из восьми соседних квадратов (за исключением участков, ограниченных береговой линией) или просто сидят неподвижно. Каждый кролик с вероятностью 0,2 превращается в двух кроликов. Каждая волчица передвигается случайным образом, пока в одном из восьми соседних квадратов не окажется кролик, за которым она охотится. Если волчица и кролик оказываются в одном квадрате, волчица съедает кролика и получает одно "очко". В противном случае она теряет 0,1 "очка". Волки и волчицы с нулевым количеством "очков" умирают. Волк ведет себя подобно волчице до тех пор, пока поблизости не исчезнут все кролики; тогда если волчица находится в одном из восьми близлежащих квадратов, волк гонится за ней. Если волк и волчица окажутся в одном квадрате и там нет кролика, которого нужно съесть, они производят потомство случайного пола. Запрограммируйте предлагаемую экологическую модель, понаблюдайте за изменением популяции в течение некоторого периода времени. (Очень благодарен Биллу Мак-Кимэну за эту задачу.)

49. Вышеописанная модель по существу неустойчива: Волчьему острову суждено стать пустыней. Добавьте изгородь (запретную зону для волков) и понаблюдайте за результатами.

50^ Поиск ключевых слов. У вас есть список названий книг и статей. Ваша программа должна читать ключевые слова и определять, находятся ли соответствующие им названия книг и статей в списке. Названия, содержащие ключевые слова, печатаются. У вас так много названий литературных источников, что вы не можете хранить их одновременно в оперативной памяти. Вам предоставляется возможность организовать поиск и расположить названия любым желаемым способом, но если программа выполняется слишком медленно, проект будет отвергнут, а вас уволят.

51. Поиск телефонного номера. Ваша телефонная компания получает много запросов от клиентов, которые хотят узнать адрес и фамилию владельцев телефонных номеров. Им отвечали на запросы по справочнику, но теперь передали эту работу вам, поскольку вы сказали, что можете выполнять ее эффективнее на машине. Начните с небольшого списка телефонных номеров, но проектируйте систему таким образом, чтобы она могла значительно расширяться. Информация об абонентах может либо добавляться в файл, либо уничтожаться.

52. Напишите программу чтения карт у пяти игроков в покер. То есть сдайте по пять (или по семь) карт каждому на руки, укажите, у какого игрока карты лучше (двойка, каре, флешь и т.д.).

53. Ханойская башня. Ханойская башня состоит из трех осей Л, В и С9 укрепленных на платформе, и п дисков разных размеров. Вначале все диски, упорядоченные по размеру; расположены один над другим на оси Л, причем самый большой диск находится внизу. Ваша программа должна показать, как переместить диски с оси А на ось В по одному с условием, что ни один диск нельзя расположить на меньшем диске. Ось С может использоваться как вспомогательная. Сколько нужно сделать ходов для башни из п дисков?

54. Игра в палочки1). Напишите программу для игры в палочки. Программа должна читать следующие данные: а) общее количество палочек; б) количество палочек в каждом ряду; в) максимальное количество палочек, которые можно переложить за один ход.

Хорошо составленная программа должна выигрывать в явно "опасной" ситуации.

55. На изображенной ниже игральной доске имеются фишки во всех отверстиях, кроме центрального. За один ход вы можете перескочить через одну фишку, и каждый раз такая фишка подлежит удалению с доски. Конечная цель игры — одна фишка в центральном отверстии.' Составьте программу успешного окончания игры, хотя это и достаточно трудно.

См. гл. 14 "Ним и так-тикс" в книге: Гарднер М., Математические голово" ломки и развлечения. — М.: Мир, 1971, с. 132.

56. Кубики сома1). Вы все, вероятно, пытались играть в эту игру2). Это куб, состоящий из 27 маленьких кубиков, которые склеены по граням так, что образуют семь элементов. Сначала вы его разобрали, а собрать опять трудно. Напишите программу соединения элементов куба. Прежде чем пытаться составить программу, попробуйте собрать такой куб. Посчитайте, сколько имеется различных решений.

57. Разноцветные кубикиЪ). У вас имеется четыре кубика, стороны которых окрашены в разные цвета. Составьте из этих кубиков прямоугольную призму, каждая боковая грань которой раскрашена во все четыре цвета. Напишите программу, определяющую расположение разноцветных кубиков.

58. Задача о восьми ферзях4). Имеется шахматная доска 8X8 и восемь ферзей. Найдите такую позицию для каждого ферзя, чтобы ни один из них не угрожал другому, т. е. чтобы каждый ряд, столбец и диагональ содержали не более одной фигуры. Найдите все решения.

59. Для нижеследующих задач запрограммируйте эффективный алгоритм и оцените необходимые усилия, которые нужно приложить для решения задачи. Решение может быть очень трудным или даже невозможным.

а) Найдите два целых числа тип, таких, что т2=2п2.

б) Найдите несколько целых значений для х, уу г, если хг+ +£/3 + ,г3=1. Два решения известны:

в) Найдите все решения уравнения хъ— г/2 = 18, если х и у — целые числа.

г) Имеется ли решение уравнения хп+уп=гп для целых чисел п, х, у, г, если /г>2?

д) Составьте карту таким образом, чтобы, используя для ее раскраски более четырех цветов, не раскрашивать двух смежных участков одинаковым цветом.

е) Напишите программу создания лабиринта, имеющего только один выход.

1) В этой и двух следующих задачах решение может быть получено только при использовании эффективного алгоритма. Просмотрите работу McKeeman W. М., A Formal Model for Space-Filling Puzzles. Machine Intelligence, Vol. 8, D. Michie, T. Elcock (eds.), 1977.

2) См. гл. 21 "Кубики сома" в книге: Гарднер М., Математические головоломки и развлечения. —М.: Мир, 1971, с. 196. — Прим. перев.

• > См. гл. 8 "Несколько нечисловых задач" в книге: Дрейфус М. и Ган-глоф К., Практика программирования на ФОРТРАНЕ. — М.: Мир, 1978, с. 73.— Прим. перев.

Подобные задачи и решение задачи с четырьмя цветами смотрите в журнале Scientific American1).