Глава 5

Элемент 12 выделен курсивом, чтобы показать, что он переставлен с 37.

2) Начиная с левого конца массива, но со следующего после элемента 12, сравниваем каждый элемент с 37 до тех пор, пока не будет найден элемент, больший, чем 37; тогда переставляем 37 и этот элемент. Первый элемент, больший, чем 37, - число 89, так что переставляем местами 89 и 37. Получаем новый массив:

12 2 6 4 37 8 10 68 45

3) Начиная справа, но с первого элемента перед 89, сравниваем каждый элемент с 37 до тех пор, пока не будет найден элемент, меньший, чем 37; тогда переставляем 37 и этот элемент. Первый элемент, меньший, чем 37, - число 10, так что переставляем местами 10 и 37. Получаем новый массив:

12 2 6 4 8 37 89 68 45

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

Когда выполнена декомпозиция массива, появляются два несортированных массива. Подмассив со значениями, меньшими, чем 37, содержит числа 12, 2, 6, 4, 10 и 8. Подмассив со значениями, большими, чем 37, содержит числа 89, 68 и 45. Сортировка продолжается и оба подмассива подвергаются декомпозиции тем же способом, что и исходный массив.

Основываясь на приведенных рассуждениях, напишите рекурсивную функцию quicksort для сортировки одномерного массива целых. Функция должна принимать в качестве аргументов массив целых, начальный массив и окончательный массив. Функция partition должна вызываться функцией quicksort для выполнения шага декомпозиции.

5.25. (Блуждание по лабиринту) Приведенная ниже сетка из значков # и точек (.) является двумерным массивом, представляющим лабиринт.

############

# # #

#.#.#### #

###.#. . . #....###

# # # # #

######.###

#......# . .

####.#.# #..#.#.# ##.#.#.#

# # # # # #

############

В приведенном двумерном массиве # представляют собой стены лабиринта, а точки представляют собой возможные пути по лабиринту.

Движение возможно только по тем позициям в массиве, которые содержат точки.

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

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

5.26. {Случайная генерация лабиринта) Напишите функцию mazeGenera-tor, которая получает в качестве аргумента двумерный массив символов 12 на 12 и создает лабиринт случайным образом. Функция должна также выдавать начальную и конечную позиции в лабиринте. Поработайте с вашей функцией mazeTraverse из упражнения 5.25, используя несколько случайно сгенерированных лабиринтов.

5.27. {Лабиринты любого размера) Обобщите функции mazeTraverse и mazeGenerator из упражнений 5.25 и 5.26 так, чтобы можно было работать с лабиринтами любой ширины и высоты.

5.28. {Массивы указателей на функцию) Перепишите программу на рис. 4.23 так, чтобы использовать интерфейс, управляемый меню. Программа должна предлагать пользователю меню из четырех позиций, как показано ниже (эти строки должны отображаться на экране):

Выберите:

0 Напечатать массив оценок

1 Найти низшую оценку

2 Найти высшую оценку

3 Напечатать среднее значение по всем тестам для каждого студента

4 Завершить программу

Одним из ограничений на применение массивов указателей на функции является то, что все указатели должны иметь один и тот же тип. Указатели должны быть на функции, имеющие одинаковый возвращаемый тип и тип принимаемых аргументов. По этой причине функции на рис. 4.23 должны быть модифицированы так, чтобы они возвращали одинаковый тип и принимали одинаковые по типу параметры. Модифицируйте функции minimum и maximum, чтобы они печатали минимальное и максимальное значение и ничего не возвращали. Для позиции 3 модифицируйте функцию average на рис. 4.23, чтобы выводить среднее значение для каждого студента (а не указанного студента). Функция average ничего не должна воз-

вращать и должна получать те же самые параметры, что и функции printArray, miiumum и maximum. Храните указатели на четыре функции в массиве processGrades и используйте выбор, сделанный пользователем, в качестве индексов массива для вызова каждой функции.

5.29. (Модификации программы моделирования Простотрона) В упражнении 5.19 вы написали моделирующую программу компьютера, который выполняет программы, написанные на Языке Машины Простотрон (ЯМП). В данном упражнении мы предлагаем несколько модификаций и усовершенствований программы моделирования Простотрона. Мы предлагаем построить компилятор, который преобразует программы, написанные на языке высокого уровня (варианте языка Бейсик) в программы на языке ЯМП. Некоторые из следующих модификаций и усовершенствований могут потребоваться для выполнения программ, создаваемых компилятором.

a) Расширьте память модели Простотрона до 1000 ячеек, чтобы Простотрон был в состоянии обрабатывать большие программы.

b) Предоставьте возможность модели Простотрона выполнять возведение в степень. Это потребует новых команд ЯМП.

c) Предоставьте возможность модели Простотрона выполнять вычисления экспонент. Это потребует новых команд ЯМП.

d) Модифицируйте моделирующую программу так, чтобы она могла использовать для представления команд ЯМП вместо целых значений шестнадцатиричные.

e) Модифицируйте моделируюшую программу так, чтобы позволить ей выводить символ перевода строки. Это потребует новых команд ЯМП.

f) Модифицируйте моделирующую программу так, чтобы она могла работать со значениями с плавающей запятой в дополнение к работе с целыми значениями.

g) Модифицируйте имитатор так, чтобы он мог обрабатывать ввод строки. Подсказка: каждое слово Простотрона можно разделить на две части, каждая из которых содержит двухразрядное целое. Каждое двухразрядное целое представляет десятичный эквивалент АЗСП символа. Добавьте команду машинного языка, которая будет вводить строку и хранить ее, начиная с указанной ячейки памяти Простотрона. Первая половина слова в этой ячейке будет равна числу символов в строке (т.е. длине строки). Каждое последующее полуслово содержит один АЗСП символ, выражаемый двумя десятичными цифрами. Команда машинного языка преобразует каждый символ в его эквивалент АЗСП и присваивает его полуслову.

h) Модифицируйте моделирующую программу так, чтобы она могла обрабатывать вывод строки, хранимой в формате пункта g). Подсказка: добавьте команду машинного языка, которая будет печатать строку, начиная с указанной ячейки памяти Простотрона. Первая половина слова в этой ячейке - число символов в строке (т.е. длина строки). Каждое последующее полуслово содержит один символ АЗСП, выражаемый двумя десятичными цифрами. Команда машинного языка проверяет длину и печатает строку, переводя каждое двухразрядное число в эквивалентный ему символ.