Многие задачи, решаемые на ЭВМ, в конечном счете, сводятся к формированию таблиц значений функций, которые в дальнейшем используются для накопления результатов, построения графиков и анализа результатов. Таблица должна содержать аргумент и одну или несколько функций. Для хранения таблицы можно использовать несколько одномерных массивов (каждый для отдельной функции), либо один двумерный массив, в котором аргумент и функции хранятся в столбцах массива. Использование двумерного массива является более предпочтительным, так как все данные хранятся в одном месте.
В качестве исходных данных можно задавать: начальное значение аргумента (XH), конечное значение аргумента (XK) и шаг изменения аргумента (DX), либо начальное значение и шаг аргумента (XH, DX) и количество рассчитываемых точек (N).
Особенности, которые надо учитывать в алгоритме:
1. Использовать циклический процесс.
2. Накапливать и выводить надо аргумент и функции.
3. Надо предусматривать средства контроля данных, если возможно аварийное завершение программы (знаменатель может быть равен нулю, аргумент логарифма или корня меньше нуля и т.п.). При этом надо формировать признаки завершения вычислительного процесса и вывод соответствующих сообщений.
Пример. Алгоритм вычисления таблицы значений функции
В данном случае таблица должна содержать два столбца; первый столбец для аргумента Х и второй - для функции У. В качестве исходных данных для организации вычислительного процесса зададим ХН, ДХ и N. Кроме того, входными данными являются параметры функции A и B. Результаты будем накапливать в массиве FY(100,2), то есть таблица может содержать не более 100 строк (количество строк в таблице определяется характером решаемой задачи и определяется программистом).
Функция содержит знаменатель, поэтому в алгоритме необходимо предусмотреть проверку знаменателя на равенство нулю. Так как нулевой может быть всего одна точка, то после вывода сообщения (например, такого: точка разрыва – знаменатель равен нулю") можно продолжить вычислительный процесс.
Схема алгоритма решения этой задачи приведена на рис.3.11.1. В алгоритме, кроме указанных выше переменных, используются следующие переменные: К – счетчик циклов (параметр цикла); Х – текущее значение аргумента; Z – значение знаменателя.
Во втором блоке на рис.3.11.1указан размер массива. После ввода исходных данных задаются начальные значения Х и К и далее организован циклический процесс вычисления функции У (цикл с предусловием). В каждом цикле сначала вычисляется значение знаменателя (Z) и осуществляется проверка Z на равенство нулю.
Рис.3.11.1
3.12. Нечисловые алгоритмы.
До сих пор мы рассматривали алгоритмы, в которых основными являются математические операции. Существует класс алгоритмов, в котором основными являются не математические вычисления, а операции сравнения и пересылки. Такие алгоритмы принято называть нечисловыми. Сюда относятся задачи связанные с:
- обработкой символьных данных;
- сортировкой данных;
- поиском данных.
3.12.1. Обработка символьных данных.
В ЭВМ можно хранить и обрабатывать не только числа, но и символы. Обычно для хранения символа используется ячейка память из восьми двоичных разрядов, в которой хранится код символа. Существуют различные системы кодирования символов, но всегда последовательности символов упорядочены и каждому символу соответствует определенный номер. Поэтому символы можно сравнивать и говорить о том, что один символ больше или меньше другого.
Существует много задач связанных с обработкой символьных данных: задачи связанные с построением редакторов; формирование сообщений программы; организация диалогового режима работы программы. При решении задач связанных с обработкой символьных данных можно использовать следующие типы данных (они имеются в языках программирования):
- символьные и строковые константы;
- символьные и строковые переменные;
- символьные и строковые массивы.
Пример 1.
Пусть последовательность символов (цифры и буквы латинского алфавита) хранится в массиве MS. Надо определить, сколько букв в этой последовательности.
Алгоритм. Так как символы пронумерованы последовательно в цикле будем сравнивать каждый элемент массива с символом 'A' (должно выполняться условие MS(K) >= 'A') и символом 'Z' (MS(K) <= 'Z'). Если эти два условия выполняются одновременно, то в данном элементе массива хранится буква и счетчик букв (обозначим его KS) надо увеличить на единицу.
Рис.3.11.2.
Схема алгоритма решения этой задачи приведена на рис.3.11.2. В алгоритме используются: K – счетчик элементов массива; N – количество обрабатываемых элементов массива. Заметим, что символ "И" в блоке сравнения элементов массива – это логическая операция И.
Пример 2. Алгоритм исключения символа.
Пусть имеем строку символов в массиве MS. Надо составить алгоритм исключения из этой строки всех символов, заданных переменной SK, обрабатывать N элементов массива MS.
Идея алгоритма:
- в цикле определяем номер элемента массива MS, который совпадает с заданным символом SK;
- сдвигаем все символы, расположенные справа, на одну позицию влево
- заносим пробел на последнюю позицию.
Уточнение алгоритма: После каждого сдвига символов влево правую границу можно уменьшить на единицу.
Рис.3.11.3.
Фрагмент схемы алгоритма исключения символов приведен на рис.3.11.3. В схеме алгоритма обозначено: N – количество символов в массиве MS; NE – динамическая длина массива; K, L – счетчики (параметры циклов); KS – количество исключенных символов.
3.12.2. Сортировка данных.
Существует большой класс задач, в которых надо упорядочивать данные (числа, последовательности символов) в определенном порядке – по возрастанию или по убыванию. Особенностью таких задач является то, что массив данных может быть большим – десятки и сотни тысяч данных, поэтому сортировать надо в самом массиве. Методы, использующие пересылку данных в другой массив, интереса не представляют.
Мерой эффективности алгоритмов сортировки являются количество сравнений (С) и количество пересылок данных (М). Простые методы требуют порядка С2 операций сравнения, а эффективные – порядка С log(C) операций. К настоящему времени придумано много различных алгоритмов сортировки. Все они делятся на три класса:
- сортировка выбором;
- сортировка включением;
- сортировка обменом.