Песни о Паскале - [83]
• Массивы, как любые переменные, «живут» в оперативной памяти. Переместив данные из файлов в массивы, мы многократно ускорим их обработку.
• Для индексации массивов допустимы любые порядковые типы данных. Выбор подходящего типа для индекса упрощает и украшает программу.
• При чтении чисел из текстового файла в «боевых» программах необходимо учитывать возможное наличие в файле пустых строк. Такие строки могут привести к чтению оператором Read несуществующего пустого числа (см. процедуру ReadFromFile в программе «P_40_2»).
А) Напишите программу для подсчета различных цифр в файле полицейской базы данных (считать надо именно цифры, а не числа!).
Б) Объявите массив из сотни целых чисел, заполните его случайными числами в диапазоне от 0 до 255 и распечатайте этот массив.
В) Найдите в массиве (задание Б) все элементы, хранящие число 7 (если таковые найдутся). Напечатайте индексы элементов, которые содержат это число.
Г) Заполните массив (задание Б) случайными числами в диапазоне от 0 до 255 так, чтобы ни одно из них не повторялось. Воспользуйтесь вспомогательным множеством чисел, где будут запоминаться сгенерированные ранее числа.
Д) Найдите в массиве (задание Г) наименьшее и наибольшее числа, напечатайте их, а также соответствующие им индексы элементов массива.
Е) Вращение массива вправо. Объявите массив из 10 чисел и заполните его случайным образом. Напишите процедуру, перемещающую 1-й элемент на 2-е место, 2-й – на 3-е место и т.д. Последний элемент должен занять 1-е место.
Ж) Вращение массива влево. Напишите процедуру для перемещения 2-го элемента на 1-е место, 3-го – на 2-е место и т.д. При этом первый элемент должен стать последним.
И) Напишите функцию для подсчета количества номеров в полицейской БД при условии, что одна строка может содержать несколько номеров, а некоторые строки (в т.ч. в конце файла) могут быть пустыми.
Глава 41
По порядку, становись!
В 39-й главе, где состоялось наше знакомство с массивами, мы намерились отсортировать футбольные команды в порядке набранных ими очков. Следуя к этой цели, перенесемся ненадолго в прошлое, – лет на триста назад.
Тогда в морях разбойничали «джентльмены», которых мы зовем пиратами. Одной из таких бригад повелевал некто Райт. Пиратские команды не отличались дисциплиной, но Райт добился порядка на корабле, избегая жестокостей. Отважный в бою, Райт давал пример и в мирных обстоятельствах, деля добычу если не поровну, то хотя бы по справедливости. Вожак брал равную со всеми долю, потому команда чтила его и подчинялась беспрекословно.
Однажды джентльменам удачи достался сундук с золотыми слитками. Пересчитав их, пираты выяснили, что каждому из них полагается ровно по два. Казалось бы, о чем тут думать? – садись и дели. Однако слитки существенно отличались формой и размерами. Пираты не могли распилить или переплавить их, сделав одинаковыми. Как быть? – с таким вопросом Райт обратился к экипажу.
После недолгих споров разбойники уже готовы были бросить жребий (на случайную дележку никто не обижался). Но тут голос подал бывший аптекарь, а ныне корабельный лекарь по кличке Нашатырь.
– Я предлагаю, – молвил Нашатырь, – разложить слитки в порядке их веса. Затем кто-то из нас возьмет самый легкий и самый тяжелый из них. Другой – самый легкий и самый тяжелый из оставшихся, и так далее.
Свою мысль он сопроводил рисунком с шестью слитками разного веса и размера (рис. 89).
– Отлично, – согласился Райт, – но как взвесить слитки? У нас нет ни гирь, ни весов.
– Зачем мне гири? Для сравнения слитков годится вот это, – и лекарь достал из своего сундука самодельные чашечные весы.
– Ну что ж, – сказал Райт, – ты придумал, тебе и делить.
И под пристальными взглядами всей команды лекарь принялся за дело.
Вначале ряд слитков он выложил, как попало. Затем стал по очереди сравнивать соседние куски. Если первый из них был тяжелее второго, аптекарь менял их местами. Так он сравнил первый и второй слитки, второй и третий, третий и четвертый и так далее до последнего слитка. В конце концов, самый тяжелый слиток оказался на последнем месте. Затем он повторил все это ещё раз, – и тогда второй по величине слиток оказался на предпоследнем месте. Проделав это N-1 раз, где N – количество слитков, лекарь выложил слитки в нужном порядке: первым лежал самый легкий, а последним – самый тяжелый.
«А теперь бросайте жребий, – подытожил Нашатырь, скромно отходя в сторону, – пусть он определит порядок взятия долей». Пираты остались довольны.
Вернемся в наше время. О пиратской истории программист сказал бы так: разложив куски золота в нужном порядке, лекарь отсортировал массив слитков. Его метод известен как «пузырьковая сортировка» – Bubble Sort. Откуда взялось это название? Проследите за пузырьками в стакане газировки: по мере всплытия они объединяются с другими и становятся крупнее.
Воспользуемся методом лекаря-аптекаря для сортировки массива из 10 целых чисел – это будут наши золотые слитки. А для испытания алгоритма напишем программу «P_41_1», которая вначале заполнит массив случайным образом и распечатает его. Затем отсортирует этот массив и снова распечатает. Работу по сортировке выделим в отдельную процедуру по имени BubbleSort, – она ещё пригодится нам в последующих проектах.
