1. Определите следующие понятия:

а) К^Б-принцип к) БГП б) универсальность л) подыгрывающая программа в) сложность м) псевдокод г) независимость н) БПР д) клудж о) мобильная программа е) правильная программа п) приспособляемость ж) проектирование сверху вниз р) недолговечность з) разбиение на модули с) побочный эффект и) структурное программирование т) перестройка

2. Каковы обязанности а) главного программиста, б) помощника главного программиста ив) библиотекаря?

3. Какие свойства вашего языка программирования затрудняют/облегчают структурное программирование?

4. Почему труднее программировать большие программы?

5. Приведите примеры простого и сложного программирования.

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

7. Перечислите стандартные приемы для вашего языка программирования, которыми следует воспользоваться.

8. В чем заключаются некоторые преимущества модульного программирования? Каковы вго недостатки?

9. Приведите несколько примеров универсальных и неуниверсальных приемов программирования.

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

11. Найдите книгу, содержащую вычислительные алгоритмы или программы, представляющие интерес для вашей работы.

12. Многие выступают против использования операторов EQUIVALENCE в ФОРТРАНе, REDEFINES в КОБОЛе или DEFINED в ПЛ/1. Эти операторы позволяют присвоить несколько имен одной ячейке памяти. В каких случаях вы считаете оправданным их применение? Ошибки ' какого типа могут возникнуть при модификации программы вследствие использования этих операторов? Приведите аргументы в пользу и против применения указанных операторов.

13. Большинство языков программирования разрешает применять глобальные переменные при помощи операторов COMMON в ФОРТРАНе, LINKAGE SECTION в КОБОЛе и EXTERNAL в ПЛ/1. Возникновению каких ошибок способствует использование глобальных переменных? Когда их следует использовать и когда нет? Приведите аргументы в подтверждение обеих точек зрения.

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

15. Многие задачи не следует решать на вычислительной машине, так как получается незначительный выигрыш от ее применения. Проклассифицируйте перечисленные задачи с точки зрения целесообразности решения их на машине, давая один из трех ответов: "Да", "Нет" и "Сомнительно".

а) Платежная ведомость 250 человек.

б) Платежная ведомость 12 человек.

в) Платежная ведомость 3 человек.

г) Программа грамматического разбора предложений на английском языке.

1 д) Просуммируйте 100 первых целых чисел арифметической прогрессии.

е) Просуммируйте числа 2, 4, 8, 16, 32, 2^*20 геометри-. ческой прогрессии.

ж) Программа нахождения трех последовательных пятниц, которые попадают на 13-е число.

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

матной доске таким образом, чтобы каждая шашка занимала точно две клетки и все клетки были заняты.

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

к) Составьте таблицу из 1000 случайных чисел. Воспользуйтесь главой "Что такое машинная задача?" из книги Ф. Грюенбергера1*.

ПРОГРАММЫ

16. Целое число можно представить как сумму его частей, называемых разбиениями. Так, число 4 можно представить как 4; 3+1; 2+1 + 1; 2+2; 1 + 1 + 1 + 1. Р(п)>— количество разбиений, Р(4)=5. Напишите программу, которая читает число п и печатает разбиения числа п и количество Р(п).

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

18. Напишите программу, которая печатает текст какой-нибудь песни.

19. Получите первые 1000 простых чисел, используя алгоритм, приведенный на рис. 2.1. Затем улучшите программу, как предложено в разд. 2.4, и определите различие во времени выполнения.

20. Решето Эратосфена. Составьте программу задачи получения простых чисел, используя следующий метод. Создайте последовательность положительных целых чисел от 1 до N. Начните с числа 2 и вычеркните все числа, кратные 2. Следующее за 2 не вычеркнутое число является очередным простым числом, т. е. 3. Теперь начните с 3. Вычеркните все числа, кратные 3. Следующее не вычеркнутое число 5 является очередным простым числом. Вычеркните все числа, кратные 5, и т. д. Все оставшиеся числа и будут простыми.

21. Составьте детальный план нижеследующей программы и затем используйте его для написания самой программы. Программа предназначена для чтения целых чисел и выбора второго по величине значения. Последнее число является нулем. Затем обобщите задачу, то есть выберите N•e по величине значение, где N считывается каждый раз.

22. Банковский вклад. Разработайте план решения следующей задачи и затем напишите программу. Ежемесячно начисляется 6% вклада. Если вклады сделаны до десятого числа, то начисляются проценты за весь месяц. Для того чтобы вкладчики не изымали часто вклады, приняты следующие меры: с вкладчика с минимальным балансом менее 1000 долл., делающего более пяти изъятий в месяц, удерживают 50 центов с каждого изъятия после

*> Gruenberger F., Computing: A Second Course, Canfield Press, San Francisco, 1971.

пяти изъятий. Процент начисляется ежемесячно по минимальному месячному балансу.

23. Создайте нижеследующие подпрограммы, работающие со строкой символов:

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

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

1567842-*- 1,567,842

Напишите программу обратного действия. Составьте аналогичные программы для вещественных чисел.

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

ПРОЕКТЫ

24.. Коммивояжер. Напишите детальный план решения следующей задачи. Коммивояжер обслуживает 16 городов. Так как он сам покупает бензин, то предпочитает ездить самым коротким путем. Каждую пятницу он получает список городов, которые должен посетить на следующей неделе. Он может объезжать их в любом порядке и не всегда посещать все города.

25. Лабиринт Минотавра. Напишите детальный план решения следующей задачи. План должен быть понятен любому, кто захочет использовать его для написания программы. Определите все модули и интерфейсы. Введите массив 21X21, состоящий из нулей (не путь) и единиц (путь). Напишите программу, которая читает вышеуказанный массив и находит выход из лабиринта. Минотавр начинает двигаться из центра массива. Если он находится в некотором квадрате, то может переместиться в любой из четырех смежных квадратов, если последний содержит единицу. Нуль блокирует путь. После того как вы нашли путь из массива, напечатайте массив, отмечая путь крестиком. Покажите только правильный путь, т. е. не печатайте возврат.

26. Напишите программу печати точной копии самой себя. Операторы ввода не допускаются.

27. Напишите программу печати 100-символьной последовательности цифр 0, 1 и 2, в которой нет двух смежных идентичных подпоследовательностей. Решение этой задачи есть в книге [8].

28. Гипотеза Симона о факториале. Только четыре факториала могут быть определены как произведение трех последовательных Целых чисел. Вот два из них:

41=2*3*4=24 51=4*5*6=120

Можете вы найти еще два факториала? Не смогли бы вы найти количество таких факториалов и доказать неправильность предположения, что их только четыре?

29. Напишите программу нахождения всех способов разрезания шахматной доски с числом клеток пу^п на две равные части (не считая вращений и отражений). Если п нечетно, то центр находится слева. (Указание: попытайтесь вначале составить программу для доски 4X4. Затем добавьте ограничение, что две раз* резанные части должны быть одинаковой формы. При использовании этого ограничения существует 15 различных путей разрезания доски 5X5.)

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

31. Декабрьский выпуск журнала ACM Computing Surveys за 1974 г. посвящен структурному программированию. Просмотрите его.

32. Сложность программ трудно оценить. Один метод измерения сложности заключается в подсчете количества непоследовательных частей в программе. Представляется ли вам это хорошим критерием? Оцените некоторые программы, используя это правило. Сложность программ обсуждается в работе [2]. Этот вопрос также излагается в книге Милса по структурному программированию. Ознакомьтесь с этими книгами и подумайте, можете ли вы разработать некоторые принципы для измерения сложности машинных программ.

33. Просмотрите несколько известных статей, касающихся оператора GO ТО. Начните со статьи Д. Кнута1*.

34. Создайте предварительный проект программы начисления зарплаты. Посмотрите реальные ведомости расчета зарплаты и определите, какие производятся удержания. Затем перечислите все изменения, которые нужно внести в программу начисления зарплаты. Если это задание выполняли другие, соберите все сведения об изменениях и переделайте программу начисления зарплаты таким образом, чтобы она могла легко приспособиться к внесению новых изменений. Это упражнение можно также проверить на многих других программах.

35. Теорема о структурировании утверждает, что любая правильная программа эквивалентна программе, которая содержит в качестве логических структур только

"> Knuth D. E., Structured Programming with GOTO Statements, ACM Com* pitting Surveys (December 1974).

а) последовательность двух или более операторов, б) условный переход к одному из двух операторов и возврат (IF THEN ELSE);

в) повторение операторов, пока условие истинно (DO WHILE).

Приведите несколько примеров для того, чтобы убедиться в справедливости этой теоремы. Насколько целесообразно было бы привести все программы к вышеуказанной форме? Просмотрите соответствующую литературу1*.

36. Сделайте колоду перфокарт или перфоленту, содержащую программу, которая выполняется одинаково независимо от того, с какого конца она загружена в машину. В более сложном варианте программа перфорирует свою копию.

37. Попытайтесь разработать некоторые правила разделения программ на модули2).

38. Каждая система программирования, поставляемая фирмой, содержит обычно стандартные языки (ANSI COBOL или ANSI FORTRAN) и некоторые их расширения. Эти расширения отражают торговую политику фирмы, заключающуюся в том, что вы не можете использовать другой компилятор и ваши программы перестают быть мобильными. Если вы хотите этого избежать и иметь мобильные программы, вы должны по возможности не пользоваться расширениями языка, что часто бывает трудно, так как расширения предоставляют хорошие возможности. Определите расширения и стандартные конструкции, имеющиеся в одном из ваших компиляторов. Затем разработайте программу, которая читает исходную программу и печатает ее, отмечая все нестандартные свойства языка.

39. Напишите статью о будущем программирования (но не машин). Областями вашего исследования являются будущее использования языков КОБОЛ, ФОРТРАН, ПЛ/1 и БЕЙСИК, роль структурного программирования, доказательства правильности-программ, автоматическое программирование и т. д. Некоторые сведения вы можете почерпнуть из работы Э. Дейкстры3>.

40. Напишите статью об истории программирования. Для изучения этой темы хорошо ознакомиться с работой Дж. Сэммета4).

1> Например, Bohm С, Jacopïnî G., Flow Diagrams, Turing Machines, and1 Languages with Only Two Formation Rules, Communications of the ACM (May 1966) и Mills H. D., Mathematical Foundations for Structured Programming, IBM Report No. FSC 72-6012, 1972.

2> По этому вопросу см. Parnas D. L., Communications of the ACM (May 1972) (December 1972).

3> Dijkstra E. W., The Humble Programmer, Communications of the ACM (October 1972).

4) Sammet J. E., Programming Languages, Prentice-Hall, Englewood Cliffs,, 8—899