Структурное программирование сверху вниз

Задача 7.1. Составить программу решения уравнения

cos x = x (7.1)

На этом примере рассмотрим основные этапы разработки программы методом структурного программирования сверху вниз.

1. Постановка задачи.

Уравнение (7.1) не имеет аналитического решения (в виде общей формулы для x). Поэтому требуется находить приближенное значение x с погрешностью, не превышающей заданную величину e.

Обозначив F(x) = cos x - x, из (6.1) получим уравнение

F(x) = 0 (7.2)

Если F(x) непрерывна на отрезке [a; b] и в его концах имеет разные знаки: F(a)*F(b) < 0, то она имеет на этом отрезке хотя бы один корень (в общем случае - любое нечетное количество корней). Для уравнения (7.1) можно взять a=0, b=p/2 или b=1, т. к. cos 0 - 0 = 1 > 0, а cos 1 - 1 < 0.

2. Выбор метода решения задачи

Корень можно уточнить с любой заданной погрешностью, например, следующим методом деления пополам.

Находится середина исходного отрезка, и в качестве нового отрезка выбирается та его половина, где находится корень (на ее концах функция F(x) имеет разные знаки).

Описанное разбиение отрезка пополам повторяется, пока не будет достигнута требуемая точность. Это обязательно произойдет, поскольку при каждом разбиении длина содержащего корень отрезка уменьшается в два раза. Рано или поздно она станет меньше любого заранее заданного числа.

Если корней несколько, будет найден один из них.

3. Алгоритмизация

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

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

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

Разработаем алгоритм нисходящим методом на псевдокоде (на каждом следующем шаге детализируем алгоритм). Псевдокод – это сочетание языка С и естественного языка.

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

1) УКРУПНЕННЫЙ алгоритм

Ввод a, b, e

if (F(a)*F(b)>0) /* Корень может отсутствовать */

Вывод сообщения об ошибке;

else УТОЧНЕНИЕ корня делением пополам;

2) УТОЧНЕНИЕ корня делением пополам

l=a; p=b;

s=(l+p)/2;

while (p-l>2*e) /* Погрешность >e */

РАЗБИЕНИЕ отрезка пополам;

Вывод корня s;

3) РАЗБИЕНИЕ отрезка пополам

if (F(l)*F(s)<0) /* В левой части меняется знак */

p = s; /* Выбор левой половины */

else l = s; /* Выбор правой половины */

s=(l+p)/2;

Записанные на псевдокоде алгоритмы легко преобразовать в программу на языке C.

/* Программа 7.1. Решение уравнения F(x)=0 на [a; b] c погрешностью e */

/* методом деления пополам (где F(x) = cos x - x ) */

#include <stdio.h>

#include <math.h>

/* Функция F(x) = cos x - x (левая часть уравнения) */

float F (float x)

{

return cos(x)-x;

}

void main (void)

{ float a, b; /* Концы исходного отрезка */

float e; /* Допустимая погрешность */

float l, p, s; /* Концы и середина текущего отрезка */

printf("\nВведите границы исходного отрезка и погрешность\n");

scanf("%f %f %f", &a, &b, &e);

if (F(a) * F(b) > 0)

printf("\nОшибка: на концах отрезка функция одного знака");

else /* Уточнение корня делением пополам */

{ l = a; p = b;

s = (l + p) / 2;

while (p - l > 2 * e)

{ /* Разбиение отрезка пополам */

if (F(l)*F(s) <= 0) /* В левой части меняется знак */

p = s; /* Выбор левой половины */

else

l = s; /* Выбор правой половины */

s = (l + p) / 2;

}

printf ("\nКорень = %f", s);

}

}

Результаты работы программы:

Введите границы исходного отрезка и погрешность

0 1 1E-6

Корень = 0.739085

Задача 7.2. Сортировка числовой последовательности.

Дано целое n и вещественные x₁, x₂, ..., x_n. Составить программу печати заданных вещественных чисел в порядке возрастания (не убывания).

Тест. Вход: Введите количество чисел 5

Введите числа 12 6 14 3 10

Выход: Упорядоченные числа: 3.0 6.0 10.0 12.0 14.0

Разработаем алгоритм программы нисходящим методом на псевдокоде.

Для хранения данных нужен массив. Исходные данные вводятся в массив, там сортируются по возрастанию, а затем выводятся.

Алгоритм на псевдокоде имеет вид:

int n; /* Количество входных чисел */

float x[N]; /* Массив для хранения чисел */

1. Ввод массива x;

2. Сортировка массива x по возрастанию;

3. Вывод сортированного по возрастанию массива x;

Детализируем шаги алгоритма. Это можно делать в любом порядке. Начнем, например, с ввода и вывода.

/* 1. Ввод массива x */

int i;

. . .

Ввод n;

for (i=0; i<n; i++)

Ввод x[i];

/* 3. Вывод массива x */

Вывод заголовка "Упорядоченные числа:";

for (i=0; i<n; i++)

Вывод x[i];

Одним из простейших методов сортировки является метод обмена (пузырька).