вперед со своей первой идеей. Это, конечно, должно согласовываться со своевременным началом написания программы. Думается, что подлинное искусство - определить этот момент. Умение правильно во всем разобраться приходит только с опытом решения задач и размышления над известными решениями,
2.6. ЗАДАЧИ
1. Рассмотрим задачу нахождения всех анаграмм заданного слова. Как бы вы решали эту задачу, если а) заданы слово и словарь; б) пришлось затрачивать время и использовать память для обработки словаря перед ответом на каждый вопрос?
2. Дана магнитная лента, содержащая 1 050 000 20-битовых чисел. Как вы найдете то из них, которое записано на ленте по крайней мере дважды?
3. Мы рассмотрели два алгоритма циклического сдвига вектора, для которых требуется умелое программирование. Запрограммируйте их. Какое участие принимает наибольший общий делитель чисел I и N в каждой из этих программ?
4. Некоторые читатели обратили внимание на то, что хотя на работу каждого из трех алгоритмов циклического сдвига затрачивается время, пропорциональное N, алгоритм с трюком, вероятно, вдвое быстрее, чем алгоритм реверсирования: в нем запоминается и читается каждый элемент массива только один раз, в то время как в алгоритме реверсирования это делается дважды. Я реализовал обе под программы без трюков и обнаружил, что для малых значений N на выполнение этих программ затрачивается одинаковое процессорное время; при N = 380 000 - по 14 с. Однако при N = 390 000 программа реверсирования выполняется 16 с, тогда как программу с трюком я прервал через 1 час. Объясните, почему результаты реальных измерений противоречат простой теории. (Полезные дополнительные сведения: машина имеет ОЗУ емкостью 2 Мбайт, каждый элемент массива занимает 4 байта, а при работе в течение одного часа I = 256.)
5. Программа циклического сдвига заменяет вектор АВ на вектор ВА; как бы вы преобразовали вектор ABC в вектор СВА? (Это моделирует задачу свопинга (взаимной замены) блоков памяти неодинаковой длины.)
6. Фирма Bell Labs имеет программу "Справочная служба, эксплуатируемая пользователем", которая позволяет предпринимателям находить номера в телефонном справочнике фирмы, используя стандартный телефон с кнопочным набором.
