Иванова Г.С., Ничушкина Т.Н. - Разработка алгоритмов простейших программ (1075619), страница 3
Текст из файла (страница 3)
f(a)f(b)<0). Излагаемые здесь методы состоят в приемах, при помощи которых находится новый интервал [a1, b1],такой чтоa a1 < x0 < b1 b,где x0 корень уравнения.2.5.1 Метод половинного деленияЭтот метод является одним из самых простых. Приближение к корнюуравнения здесь осуществляется с помощью деления отрезка [a, b] пополам. В результате мы получаем новую точку c (см. рисунок 2.8).2.5y0abc’xcРисунок 2.8 – Метод половинного деленияДалее проверяется, является ли точка c корнем уравнения f(x)=0.
В случаеположительного ответа задача решена, в случае отрицательного мы сравниваем17знак функции в точке c со знаками функций в концах отрезка и, в дальнейшем,будем рассматривать тот отрезок ([a, c] или [c, b]), где функция принимает разныезнаки. Новый отрезок снова делится пополам, и все действия повторяются вновь.Таким образом, длина рабочего отрезка будет постоянно уменьшаться, а искомыйкорень уравнения будет оставаться внутри этого отрезка. Вычисления прекращаются тогда, когда будет достигнута заданная точность вычислений (т.е. |f(с)|< ).2.5.2 Метод хордМетод хорд аналогичен методу половинного деления, но дает более быстрое приближение к корню уравнения.
Здесь новая точка выбирается по несколькодругому закону. Точки с координатами (a, f(a)) и (b, f(b)) соединяются отрезком(хордой) и точка c выбирается как точка пересечения полученной хорды с осьюOX(см. рисунок 2.9.)y0abxcРисунок 2.9 – Метод хордКоординату точки c находят по формуле:c a f (a )baf (b ) f ( a )илиc b f (b )baf (b ) f ( a )Нахождение длины кривойПусть на отрезке [a,b] уравнением y=f(x) задана непрерывная кривая.
Нужнонайти длину, заданной кривой. Задачу можно решить, если разбить отрезок [a,b]на несколько частей, см. рисунок 2.10.2.6abРисунок 2.10 – Метод хорд нахождения длины кривойЕсли теперь провести прямые, параллельные оси OY, то кривая будет разбита на такое же количество более мелких кривых. Соединив точки разбиения кривой прямым линиями, получим ломаную, длину которой определить не представляет большого труда, поскольку каждая вершина имеет координаты (xi, f(x)). Очевидно, что чем больше звеньев у ломанной, тем ближе ее длина к длине кривой.18Поэтому алгоритм вычисления можно построить следующим образом: нужно увеличивать количество точек разбиения и вычислять длину ломанной до тех пор,пока не будет достигнута требуемая точность.193 МассивыМассив – это упорядоченная совокупность однотипных данных, с каждым изкоторых связан упорядоченный набор целых чисел, называемых индексами.
Индексы определяют положение элемента в массиве.Работа с массивом сводится к действиям над его элементами. Для обращения к конкретному элементу массива необходимо указать имя массива и значениеиндекса (индексов) элемента. Все задачи по работе с массивами можно разбить наследующие классы:1. Последовательная обработка элементов массива.2. Выборочная обработка элементов массива.3.
Изменение порядка следования элементов без изменения размеров исходного массива.4. Переформирование массива с изменением его размеров.5. Одновременная обработка нескольких массивов или подмассивов.6. Поиск в массиве единственного элемента, отвечающего некоторому условию.Выделение шести перечисленных классов обусловлено тем, что каждому изних соответствуют приемы программирования. В реальной жизни задачи в чистомвиде встречаются довольно редко.
Однако любая сложная задача может быть разбита методом пошаговой детализации на более простые задачи, относящиеся куказанным выше классам. Следует также учитывать, что существует спецификареализации решений всех классов задач, зависящая от количества индексов массивов.3.1Приемы обработки одномерных массивовОдномерными называют массивы, для доступа к элементам которых необходимо задавать один индекс.
Рассмотрим наиболее распространенные приемыпрограммирования обработки одномерных массивов.3.1.1Последовательная обработка элементов массиваПримерами подобного класса задач служат: нахождение суммы элементов,произведения элементов, среднего арифметического, среднего геометрического,подсчет количества элементов, отвечающих определенному условию или обладающих некоторыми признаками, а также их суммы, произведения и т.д. Кроме того, к этой группе могут быть отнесены задачи ввода и вывода массивов. Особенностью задач класса является то, что количество обрабатываемых элементов массива известно.
Это позволяет использовать счетные циклы, параметр которыхобеспечивает доступ к элементам. Однако, возможно применение и других менееэффективных в рассматриваемом случае типов циклов.Рассмотрим некоторые типовые алгоритмы задач первого типа.Пример 3.1. Пусть необходимо ввести или вывести массив. Для этого нужнопоследовательно перебрать все элементы массива. Если количество вводимыхэлементов известно заранее, то для этой операции удобно использовать счетныециклы. При неизвестном количестве элементов лучше использовать циклы с предили пост условиями.
При выводе количество элементов может быть известно заранее или задаваться пользователем. Схема алгоритма, при помощи которогоосуществляется ввод количества элементов n и ввод-вывод одномерного массиваA(n) представлен на рисунке 3.1, а.20НачалоВводni:=1,nВводA[i]НачалоВводn, А(n)i:=1,nВыводA[i]ВыводА(n)КонецКонецaбРисунок 3.1 – Ввод-вывод одномерного массиваПоскольку ввод-вывод массивов всегда осуществляется одинаково, каждыйраз расписывать эти операции нет необходимости. На схеме алгоритма операцииввода-вывода массива обычно не раскрывают (см.
рисунок 3.1, б).Пример 3.2. Сравнительно часто встречается задача нахождения наибольшего или наименьшего элемента массива (например, при построении графикафункции).Вспомогательной переменной Аmax присваивается значение первого элемента массива, затем последовательно все элементы массива сравниваются с переменной Аmax, если значение Аmax оказывается больше, чем очередной элемент,то Аmax присваивается новое значение (см. рисунок 3.2).НачалоВводn, А(n)Amax:=A[1]i:=2,nA[i]>AmaxнетдаAmax:=A[i]ВыводАmaxКонецРисунок 3.2 – Схема алгоритма нахождения максимального элемента массива21Пример 3.3.
Пусть необходимо найти среднее арифметическое значение положительных элементов целочисленного массива, кратных трем. Для решенияэтой задачи сначала необходимо двум вспомогательным переменным Sum и Kol,которые будут использоваться для накопления суммы требуемых элементов и ихколичества, присвоить нулевые значения (см. рисунок 3.3).НачалоВводn, А(n)Kol:=0Sum:=0i:=1,nA[i] mod 3=0нетдаKol:=Kol+1Sum:=Sum+A[i]ВыводSum/KolКонецРисунок 3.3 – Схема алгоритма нахождения среднего арифметического элементов, кратных 3После этого осуществляется перебор всех элементов и, если очередной удовлетворяет условию, его значение добавляется к содержимому переменной Sum, азначение переменной Kol увеличивается на единицу.
После просмотра массивасреднее арифметическое определяется делением накопленной суммы на количество найденных элементов.Пример 3.4. Пусть необходимо заменить все отрицательные элементы массива на нулевые.Несложно увидеть, что схема очень похожа на предыдущую, поскольку, какв предыдущем алгоритме, осуществляется последовательная проверка всех элементов массива.Схема алгоритма решения задачи показана на рисунке 3.4.22НачалоВводn, А(n)i:=1,nA[i] < 0нетдаA[i]:=0ВыводA(n)КонецРисунок 3.4 – Схема алгоритма замены отрицательных элементов массива нулямиВыборочная обработка элементов массиваК задачам данного типа относятся задачи по формулировке сходные с задачами первого класса, но обработка ведется не надо всеми элементами массива, атолько теми, которые имеют вполне определенное значение индексов.
Поэтому,особенностью этого класса задач является наличие определенного закона изменения индексов рассматриваемых элементов. С целью уменьшения времени работыпрограммы и увеличения ее эффективности, программисту следует найти этот закон и обеспечить его исполнение. В зависимости от закона изменения индексовмогут использоваться все виды циклов, а также их сочетание.Пример 3.5. Определить максимальный элемент, среди элементов целочисленного массива, стоящих на четных местах.При решении этой задачи начинать надо со второго элемента и увеличиватьномер на два после каждой проверки. Количество анализируемых элементов приэтом уменьшается вдвое.
Схема алгоритма решения задачи представлена на рисунке 3.5.3.1.223НачалоВводn, А(n)k:=2max:=A[2]i:=1,n div2-1даA[k] > maxнетk:=k+2max:=A[k]ВыводmaxКонецРисунок 3.5 – Схема алгоритма поиска максимального элемента, записанного на четном местеПример 3.6. Заменить каждый третий элемент массива значением 0 – еслион четен и остатком от деления элемента на пять, если он нечетен.В этом случае нас интересует каждый третий элемент, поэтому количествопросматриваемых элементов уменьшается втрое, а значение k в цикле увеличивается на три (см.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
