Алгоритм сортировки методом обмена (методом пузырька)
Лекция 9. Структурное программирование сверху вниз.
Нисходящая и восходящая технологии алгоритмизации. Структурное программирование. Базовые алгоритмические структуры. Разработка алгоритмов методом структурного программирования сверху вниз.
СТРУКТУРНОЕ ПРОГРАММИРОВАНИЕ СВЕРХУ ВНИЗ
Основные этапы решения задач на ЭВМ
1. Проектирование программы (17%).
1.1. Постановка задачи.
1.2. Выбор или разработка метода решения.
1.3. Алгоритмизация – проектирование структуры данных и алгоритма программы.
Программа = Данные + Алгоритм
2. Программирование (8%).
3. Отладка программы (25%).
4. Сопровождение программы при эксплуатации (50%).
Борьба с ошибками - главная проблема программирования.
Разработка алгоритма
Алгоритмизация – это представление метода решения задачи в виде четкого алгоритма.
Методы алгоритмизации:
· структурное программирование;
· разработка сверху вниз.
Структурное программирование основано на применении так называемых структурных алгоритмов, построенных из стандартных базовых структур.
Базовые алгоритмические структуры:
· последовательность,
· ветвление,
· циклы.
Базовые алгоритмические структуры и операторы языка C для их реализации представлены на рис. 1.
Рис.1. Базовые структуры и операторы языка C для их реализации
 |
Каждая базовая структура имеет один вход и один выход и может рассматриваться как один блок. Каждый блок - прямоугольник этих структур также может иметь внутри любую из допустимых структур.
|
|
|
Если по правилам языка должен быть один оператор, но требуется написать последовательность операторов, то эта последовательность операторов заключается в фигурные скобки и превращается в один, но составной оператор.
Главная идея структурного программирования – стандартизация. Алгоритм становится понятнее, но может быть более громоздким. Если для решения задачи существует алгоритм, то существует и структурный алгоритм. Таким образом, метод структурного программирования не ограничивает множество решаемых задач.
Разработка сверху вниз и снизу вверх
Любая сложная система состоит из более мелких частей, таким же образом можно представить любой алгоритм или программу. На первом этапе, проектируемый алгоритм, представляется в виде одного блока. Затем определяется структура этого блока, исходный алгоритм разбивается на части и т.д. На рис.2. представлены нисходящая (сверху вниз) и восходящая (снизу вверх) технологии алгоритмизации.
 |
Рис. 2. Нисходящая и восходящая технологии алгоритмизации
Структурное программирование обычно сочетают с проектированием алгоритма сверху вниз.
|
|
|
Задача. Составить программу решения уравнения
cos x = x (6.1)
На этом примере рассмотрим основные этапы разработки программы методом структурного программирования сверху вниз.
1. Постановка задачи.
Уравнение (6.1) не имеет аналитического решения (в виде общей формулы для x). Поэтому требуется находить приближенное значение x с погрешностью, не превышающей заданную величину e.
Обозначив F(x) = cos x - x, из (6.1) получим уравнение
F(x) = 0 (6.2)
Если F(x) непрерывна на отрезке [a; b] и в его концах имеет разные знаки: F(a)*F(b) < 0, то она имеет на этом отрезке хотя бы один корень (в общем случае - любое нечетное количество корней). Для уравнения (6.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.
/* Программа 17. Решение уравнения 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; /* Концы и середина текущего отрезка */
cout<<"\nВведите границы исходного отрезка и погрешность";
cin>>a>>b>>e;
if (F(a) * F(b) > 0)
cout<<"\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;
}
cout<< "\nКорень = "<< s;
}
}
Результаты работы программы:
Введите границы исходного отрезка и погрешность
0 1 1E-6
Корень = 0.739085
Задача. Сортировка числовой последовательности.
Дано целое n и вещественные x1, x2, ..., xn. Составить программу печати заданных вещественных чисел в порядке возрастания (не убывания).
Тест. Вход: Введите количество чисел 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];
Одним из простейших методов сортировки является метод обмена (пузырька).
Алгоритм сортировки методом обмена (методом пузырька)
При просмотре массива упорядочиваются пары соседних элементов: элементы, расположенные не по возрастанию, меняются местами. После просмотра максимальный элемент окажется в конце массива, и второй раз просматриваются уже n - 1 элементов, затем n - 2 и т. д., последний раз просматриваются два элемента.
12 6 14 3 10 // рассматривается n элементов
6 12 14 3 10
6 12 3 14 10
6 12 3 10 14
6 12 3 10 // рассматривается n-1 элементов
6 3 12 10
6 3 10 12
6 3 10 // рассматривается n-2 элементов
3 6 10
3 6 // рассматривается n-3 элементов
/* 2. Сортировка массива x по возрастанию методом обмена */
int k; /* Максимальный индекс просмотра */
. . .
for (k=n-1; k>0; k--)
/* Просмотр элементов x[0], ... , x[k] */
for (i=0; i<k; i++)
/* Сортировка x[i] и x[i+1] */
if (x[i] > x[i+1]) /* Порядок нарушен */
Обмен: x[i] <--> x[i+1];
Реализация алгоритма сортировки методом обмена приведена в программе 18.
/* Программа 18. Печать входных чисел по возрастанию */
#include <stdio.h>
#define NMAX 100 /* Макс-е количество входных чисел */
void main (void)
{ float x[NMAX]; /* Обрабатываемые числа */
int n; /* Количество чисел */
int i; /* Индекс текущего числа */
int k; /* Максимальный индекс просмотра */
float r; /* Для обмена */
/* 1. Ввод массива x */
cout>> "\nВведите количество чисел”;
cin>>n;
cout<< "Введите числа\n";
for (i=0; i<n; ++i)
cin>>x[i];
/* 2. Сортировка массива x по возрастанию методом обмена */
for (k=n-1; k>0; k--)
for (i=0; i<k; i++)
if (x[i] > x[i+1])
{r=x[i]; x[i]=x[i+1]; x[i+1]=r;}
/* 3. Вывод массива x */
cout<<"\n Упорядоченные числа”;
for (i=0; i<n; ++i)
cout<<”\n=” x[i];
}
Контрольные вопросы и упражнения .
1. Назовите основные этапы решения задачи на ЭВМ и основные методы алгоритмизации.
2. Объясните достоинства метода структурного программирования.
3. Нарисуйте схемы базовых алгоритмических структур и запишите операторы языка С, их реализующие.
4. Нарисуйте схему заданного фрагмента, используя базовые алгоритмические структуры. Выделите базовые алгоритмические структуры на схеме (например, штриховой линией) и подпишите их названия.
float x, max;
int k, i, nom;
cin>>k;
if (k < 1) cout"\nВходная последовательность пуста\n";
else
{ cin>>max; nom=0;
for (i = 1; i<k; i++)
{ cin>>x;
if (x > max) { max = x; nom= i; }
}
cout<<"\nМаксимум= “<<max<<” номер =”<<nom;
}
5. Перепишите заданный фрагмент, заменив оператор цикла do while, оператором цикла while.
int n, s=0;
cin>>n;
do
{ s+= 5;
n--;
} while ( n>0 );
6. Дано целое N ³ 0 и массив из N вещественных чисел. Разработайте методом структурного программирования сверху вниз и напишите программу для сортировки массива по не убыванию (чтобы каждый элемент был не меньше предыдущего элемента) следующим способом.
Сортировка вставкой. Каждый элемент, начиная со второго, вставлять в нужное место среди предыдущих элементов, увеличивая, таким образом, на единицу длину уже упорядоченной последовательности, пока она не охватит весь массив.
7. Дано целое N ³ 0 и массив из N целых чисел. Напишите программу для сортировки массива по убыванию следующим способом.
Сортировка подсчетом индекса. Для каждого элемента подсчитать количество меньших или равных ему элементов, которое и определит его индекс в упорядоченном массиве.
8. Дано целое N ³ 0 и массив из N целых чисел. Напишите программу для сортировки массива по возрастанию следующим способом.
Сортировка подсчетом количества значений. Подсчитать в массиве количество экземпляров каждого возможного значения (все значения могут быть целыми числами в диапазоне от A до B). Заполнить массив заново в требуемом порядке нужными значениями в подсчитанных количествах.
Дата добавления: 2018-09-23; просмотров: 748; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!