Разработка алгоритмов и программ сверху вниз. Примеры зачетных задач
Особенности и механизмы разработки алгоритмов и программ сверху вниз и снизу вверх. Сортировка числовой последовательности. Характеристика метода последовательного нахождения максимума. Алгоритм функции сортировки массива неизвестного по возрастанию.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | лекция |
| Язык | русский |
| Дата добавления | 09.09.2017 |
| Размер файла | 33,3 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Лекция: Разработка алгоритмов и программ сверху вниз. Примеры зачетных задач
Разработка алгоритмов и программ сверху вниз и снизу вверх
Любая сложная система состоит из более мелких частей, таким же образом можно представить любой алгоритм или программу. На первом этапе проектируемый алгоритм представляется в виде одного блока. Затем определяется структура этого блока, исходный алгоритм разбивается на части и т.д. На рис.1 представлены нисходящая (сверху вниз) и восходящая (снизу вверх) технологии алгоритмизации.
Рис. 1. Нисходящая и восходящая технологии алгоритмизации
Часто отдельные части сложной программы оформляют в виде отдельных подпрограмм. При разработке программы по принципу «сверху вниз» вначале проектируется алгоритм главной программы (функции main), на втором этапе - блоков или подпрограмм, вызываемых из главной программы, затем - блоков или подпрограмм следующего уровня и т.д.
Задача. Сортировка числовой последовательности
алгоритм программа числовой массив
Дано целое n и вещественные x1, x2, ..., xn. Составить программу печати заданных вещественных чисел в порядке возрастания (не убывания).
Тест. Вход: Введите количество чисел5
Введите числа12.5 6 14 -3 10
Выход: Упорядоченные числа:-3.0 6.0 10.0 12.5 14.0
Разработаем алгоритм программы нисходящим методом.
Для хранения данных нужен массив. Исходные данные вводятся в массив, там сортируются по возрастанию, а затем выводятся. Оформим в виде отдельных подпрограмм ввод данных и сортировку массива.
Функциональную структуру программы можно представить в виде дерева на рис. 2.
Размещено на http://www.allbest.ru/
Рис. 2. Функциональная структура программы
1 этап. Разработка алгоритма функции main().
Алгоритм (на псевдокоде):
1. n = Vvod(x);// Ввод n и массива x
2. Sort (x, n);// Сортировка массива x по возрастанию;
3. Вывод сортированного по возрастанию массива x;
2 этап. Детализируем шаги алгоритма. Это можно делать в любом порядке. Начнем, например, с вывода упорядоченного массива x.
// 3. Вывод массива x
Вывод заголовка "Упорядоченные числа:";
for (i=0; i<n; i++)
Вывод x[i];
Теперь рассмотрим алгоритм функции ввода данных.
int Vvod (float x[])
{
Ввод n;
for (i=0; i<n; i++)
Ввод x[i];
Возврат n;
}
Осталось рассмотреть функцию сортировки массива x. Существует много различных методов сортировки массивов. Рассмотрим метод последовательного нахождения максимума.
Вначале наибольший элемент ищется среди всех n элементов, после чего происходит перестановка его с последним элементом. Далее максимальный элемент ищется уже среди n-1 элементов и меняется местами с предпоследним элементом. Затем эта процедура повторяется для n-2 элементов и т.д. Последний раз наибольший элемент находится из первых двух элементов и переставляется местами со вторым элементом.
2.5 6 14 -3 10// рассматривается n элементов
2.5 6 10 -3 14
2.5 6 10 -3 // рассматривается n-1 элементов
2.5 6 -3 10
2.5 6 -3 // рассматривается n-2 элементов
2.5 -3 6
2.5 - 6 // рассматривается n-3 элементов
-3 2.5
Алгоритм функции сортировки массива x по возрастанию
void Sort (float x[], int n)
{ for (k=n-1; k>0; k-)
{ Определение максимума среди элементов x[0], ..., x[k] и
его индекса imax.
Обмен: x[imax] <-> x[k];
}
3 этап. Рассмотрим определение максимума среди элементов x[0], ..., x[k] и его индекса imax.
imax =0;
for (i =1; i <= k; i++)
if (x[i] > x[imax]) imax = i;
Программа
#include <stdio.h>
#define NMAX 100 /* Макс-е количество входных чисел*/
/* Функция ввода данных * /
int Vvod (float x[])
{
int n; /* Количество чисел */
int i; /* Индекс текущего числа */
printf ("\nВведите количество чисел\n");
scanf ("%d", &n);
printf ("Введите числа\n");
for (i=0; i<n; ++i)
scanf("%f", &x[i]);
return n;
}
/* Функция сортировки x массива по возрастанию */
void Sort (float x[], int n)
{
int k; /* Максимальный индекс просмотра*/
float r;/* Для обмена */
int imax;/* Индекс максимального элемента */
int i; /* Индекс текущего числа */
for (k=n-1; k>0; k-)
{ imax =0;
for (i =1; i <= k; i++)
if (x[i] > x[imax]) imax = i;
/* Обмен x[imax] и x[k] */
r = x[imax];
x[imax] = x[k];
x[k] = r;
}
}
/* Главная функция */
void main (void)
{ float x[NMAX]; /* Обрабатываемые числа*/
int n; /* Количество чисел */
int i; /* Индекс текущего числа */
/* 1. Ввод массива x */
n = Vvod(x);
/* 2. Сортировка массива x по возрастанию */
Sort(x, n);
/* 3. Вывод массива x */
printf("Упорядоченные числа:\n");
for (i=0; i<n; ++i)
printf (" %4.1f", x[i]);
}
Примеры зачетных задач
Рассмотрим примеры задач, предлагаемых на зачете по программированию студентам заочной и очно-заочной форм обучения. Билет включает две задачи разных типов. В 1-й задаче дана готовая программа с подпрограммой, нужно составить к программе схему алгоритма и определить результат работы программы при заданных исходных данных. Ко второй задаче необходимо составить схему алгоритма, программу на языке С и трассировочную таблицу выполнения программы для одного или двух тестов (тесты подобрать самим).
Пример билета:
1. Составить схему к программе:
#include <stdio.h>
int f3 (char s[81])
{ int i, pr=0;
for ( i=0; s[i]!='.'; i++ )
if ( s[i] == ' ' ) pr++;
return pr;
}
void main()
{ char s1[81], s2[81];
gets (s1);
gets (s2);
printf ("%d %d\n", f3(s1), f3(s2));
}
Что выведет программа, если ввести следующие строки:
Зима весна лето.
Осень.
2. Дана числовая последовательность в виде n, x1, x2, ..., xn.
Проверить, упорядочены ли числа x1, x2, ..., xn по убыванию.
Решение задачи 1:
Функция f3 определяет и возвращает главной функции число пробелов в заданной строке. Результат выполнения программы:
2 0
Выводится число пробелов в первой и во второй строках.
Решение задачи 2:
Тесты для проверки программы:
|
№ п/п |
n |
Исходная последовательность |
Ожидаемый результат |
|
|
1 2 3 4 |
5 4 1 4 |
100 45 30.5 36 20 10 5 1.2 -20.4 5 50 20 20 10 |
не упорядочены упорядочены n < 2 упорядочены |
Табл. 1.Трассировочная таблица исполнения алгоритма 2 с тестом №1
|
f = |
1 |
||||||
|
n = |
5 |
||||||
|
xp = |
100 |
45 |
30.5 |
36 |
20 |
||
|
i = |
1 |
2 |
3 |
4 |
5 |
||
|
x = |
45 |
30.5 |
36 |
20 |
|||
|
n < 2 |
нет |
||||||
|
i < n |
да |
да |
да |
да |
нет |
||
|
xp < x |
нет |
нет |
да |
нет |
|||
|
f = 1 |
нет |
Результат: не упорядочены
Программа:
#include <stdio.h>
main( )
{float xp, x; /* предыдущее и текущее числа последовательности */
int f = 1;/* признак, упорядочены ли числа по убыванию */
/* f=1, если упорядочены, 0 - нет */
int n;/* количество чисел */
int i;/* порядковый номер очередного числа */
printf ("\nВведите количество чисел\n");
scanf ("%d", &n);
printf ("\nВведите последовательность чисел\n");
scanf ("%f", &xp);
for (i =1; i<n; i++)
{
scanf ("%f", &x);
if (xp < x) f = 0;
xp = x;
}
if (f) printf ("Числа упорядочены по убыванию");
else printf ("Числа не упорядочены по убыванию");
return 0;
}
Размещено на Allbest.ru
...Подобные документы
Цель, этапы, основные проблемы структурного программирования. Принцип нисходящего проектирования алгоритмов и программ (метод проектирования сверху вниз). Достоинства метода пошаговой детализации. Основные плюсы и минусы методик программирования.
реферат [40,0 K], добавлен 01.04.2010Анализ основных алгоритмов внутренней сортировки массивов данных, сравнение сложности их реализации и производительности. Сортировка пузырьком, методами вставок, выбора, методом Шелла, быстрая сортировка. Операция разделения массива внутренней сортировки.
курсовая работа [161,7 K], добавлен 17.12.2015Решение систем линейных алгебраических уравнений по методу Гаусса. Разработка прикладной программы формирования видеотеки с использованием технологии разработки программ "сверху-вниз". Алгоритм добавления, удаления и корректировки элемента видеотеки.
курсовая работа [305,0 K], добавлен 18.06.2012Создание схем алгоритмов и составление программы на языке Pascal для вычисления значений заданных функций. Сущность и порядок нахождения значения определенного интеграла. Анализ работы подпрограмм. Разработка тестов для проверки правильности алгоритмов.
контрольная работа [831,0 K], добавлен 24.11.2013Понятие массива и правила описания массивов в программах на языке С. Рассмотрение основных алгоритмов обработки одномерных массивов. Примеры программ на языке С для всех рассмотренных алгоритмов. Примеры решения задач по обработке одномерных массивов.
учебное пособие [1,1 M], добавлен 22.02.2011Вычисление значения суммы ряда, абсолютной и относительной погрешности. Упорядочение массива по убыванию элементов сверху вниз и слева направо. Построение графика функции. Текстовая строка, проверка числа открывающихся и закрывающихся скобок в строке.
курсовая работа [875,9 K], добавлен 07.06.2014Обработка массивов элементов любого типа как главное назначение алгоритмов сортировки. Анализ наиболее используемых алгоритмов сортировки: пузырьком, выбором, вставками, методом Шелла и быстрой сортировкой. Основные требования к алгоритмам сортировки.
реферат [189,8 K], добавлен 06.12.2014Методы реализации алгоритмов сортировки и алгоритмов поиска на языках программирования высокого уровня. Программирование алгоритмов сортировки и поиска в рамках создаваемого программного средства на языке Delphi. Создание руководства пользователя.
курсовая работа [1,7 M], добавлен 16.04.2012Изучение алгоритмов внутренней сортировки массивов данных, сравнение сложности их реализации и производительности. Отличительные черты сортировки включением, выбором, разделением, сортировки Шелла, обменной сортировки. Сравнение методов: плюсы и минусы.
курсовая работа [203,8 K], добавлен 03.12.2010Принципы разработки алгоритмов и программ на основе процедурного подхода и на основе объектно-ориентированного подхода. Реализация программы Borland Pascal 7.0, ее интерфейс. Разработка простой программы в среде визуального программирования Delphi.
отчет по практике [934,7 K], добавлен 25.03.2012Понятие "сортировка" как упорядочение элементов некоторой последовательности, ее цель и методы. Разработка алгоритмов, подпрограмм сортировок различного рода, анализ и вычисление среднего времени каждой сортировки, составление графического меню.
курсовая работа [165,4 K], добавлен 24.06.2012Определение понятия, видов и задач сортировки. Рассмотрение основ построения простых и улучшенных алгоритмов сортировки, анализ числа операций. Линейная и пирамидальная организация данных. Основные правила нижней оценки числа операций в алгоритмах.
презентация [274,5 K], добавлен 19.10.2014Сущность и порядок реализации простых методов сортировки при составлении программного алгоритма, их классификация и разновидности, отличительные признаки, характерные свойства. Особенности алгоритмов для сортировки файлов записей, содержащих ключи.
реферат [20,7 K], добавлен 20.05.2010Понятие и свойства алгоритмов: рекурсивного, сортировки и поиска. Простая программа и структурный подход к разработке алгоритмов. Язык блок-схем и проектирования программ (псевдокод). Рассмотрение принципов объектно-ориентированного программирования.
презентация [53,1 K], добавлен 13.10.2013Характеристика предприятия ТОО "Com Sales Group". Составление программ на языке программирования. Составление алгоритмов, разработка численных методов решения задач. Методы откладки программ. Анализ технологии машинной обработки экономической информации.
отчет по практике [1,3 M], добавлен 19.04.2016Краткое описание языка программирования С++. Алгоритм линейного выбора элемента, методов минимального (максимального) элемента и челночной сортировки. Анализ и разработка приложения, организующего сортировку массива данных пятью методами сортировки.
реферат [614,8 K], добавлен 12.04.2014Исследование основных особенностей алгоритмов быстрой и поразрядной сортировки данных. Построение графиков зависимости времени сортировки от количества элементов в файле и от степени перемешенности элементов. Описания сортировки чисел и строковых данных.
лабораторная работа [1,2 M], добавлен 23.07.2012Составление программы сортировки по возрастанию массив из 20 шестнадцатеричных чисел, просматривающей все исходные числа во внешней памяти и выбирающей самое большое число. Блок-схема алгоритма работы программы. Таблица команд и число их выполнения.
курсовая работа [23,1 K], добавлен 24.05.2015Реализация комплекса программ поиска подстроки в тексте алгоритмом прямого поиска и алгоритмом Кнута-Морриса-Пратта. Сравнительный анализ теоретических и экспериментальных оценок эффективности алгоритмов. Разработка структуры программы, ее листинг.
курсовая работа [2,8 M], добавлен 22.01.2015Использование бинарных деревьев для поиска данных. Схемы алгоритмов работы с бинарным деревом. Проектирование алгоритмов и программ. Структура программного комплекса. Язык С# как средство для разработки автоматизированной информационной системы "Адрес".
курсовая работа [914,9 K], добавлен 14.11.2013
