Разработка базового алгоритма обработки массива данных по заданному условию

Размещено на http://www.allbest.ru

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ

РЕСПУБЛИКИ КАЗАХСТАН

СПЕЦИАЛЬНОСТЬ

«Программное обеспечение вычислительной техники и автоматизированных систем»

КУРСОВОЙ ПРОЕКТ

по предмету: «Основы алгоритмизации и программирования»

на тему: «Разработка базового алгоритма обработки массива данных по заданному условию»

2009

СОДЕРЖАНИЕ

ВВЕДЕНИЕ

1. ОБЩАЯ ЧАСТЬ

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

1.2 Управляющие структуры

1.3 Назначения и область применения

1.4 Технические характеристики

1.5 Генератор случайных чисел

1.6 Массивы

2. СПЕЦИАЛЬНАЯ ЧАСТЬ

2.1 Спецификация программы

2.2 Инструкция по выполнению программы

2.3 Описание программы

2.4 Тестирование программы

ЗАКЛЮЧЕНИЕ

СПИСОК ЛИТЕРАТУРЫ

ПРИЛОЖЕНИЕ

ВВЕДЕНИЕ

Для полноценного функционирования любого проекта все более важным становится создание программного обеспечения для каждого из его компонентов. Сейчас используют много языков программирования. Все они (с помощью программ) позволяют объяснить компьютеру, что мы от него хотим. Язык С++ завоевывает все большую популярность, поскольку его возможности достаточно велики для создания даже самых сложных приложений. Грамотное и высокотехнологичное программное обеспечение необходимо во многих сферах применения: от организации одноранговых сетей для обеспечения протоколов связи до создания комплексного программного обеспечения, позволяющего управлять работой современного промышленного производства.

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

В процессе создания курсовой работы «Разработка базового алгоритма обработки массива данных по заданному условию», был разработан алгоритм решения поставленной задачи. По этому алгоритму на языке C++ составлена и отлажена программа, удачно прошедшая тестирование.

Гораздо проще сначала записать то же самое на специальном языке, языке алгоритмов, а потом перевести записанное на язык программирования.

Одним из наиболее наглядных методов составления алгоритмов является язык схем. Об этом свидетельствует и опыт преподавания программирования. Однако, несмотря на огромное количество хороших книг по программированию, появившихся в последнее время, практически неохваченным остался такой раздел учебной литературы, как изложение методов составления алгоритмов и обучение составление блок-схем. Редко удается написать реальную программу, в которой не производились бы какие - либо расчеты. Однако по большей части в коде не требуется каких - либо серьезных математических вычислений кроме арифметических. Ни язык Си, ни С++ не проектировались специально для численных расчетов. Однако численные расчеты, как правило, возникают в контексте других задач - доступ к базам данных, работа с сетями, управление устройствами, графика, моделирование, финансовый анализ и т.д. С++ стал привлекательным средством вычислений, которые выполняются как часть большой системы. Более того, численные методы вышли далеко за рамки простых циклов над векторами чисел с плавающей точкой. А там, где нужны более сложные структуры данных, становятся полезными мощные средства С++. Поэтому появились специальные средства и приемы для поддержки таких расчетов.

1. ОБЩАЯ ЧАСТЬ

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

Решение задачи на ЭВМ это сложный и трудоёмкий процесс. Любая задача начинается с постановки задачи, на основе словесной формулировки задачи выбираются переменные подлежащие определению. Записываются ограничения и связи между переменными, а совокупности, образующие математическую модель решаемой проблемы анализируется метод решения на этом этапе задачи. Необходимо принять очень важные решения - это использовать ли имеющееся готовое программное обеспечение или разработать собственную программу.

Основные этапы решение задач на ЭВМ:

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

Язык программирования позволяет с помощью фиксированной системы обозначения и правил определить алгоритм, а также описать необходимую структуру данных, которые затем и будут переведены в машинный код. ЭВМ оператор массив число случайный алгоритм

Программа написанная на языке программирования называется исходным текстом.

Алгоритм устанавливает последовательность точно определенных действий, приводящих к решению задачи. При этом последовательность действий может задаваться посредством словесного или графического описаний. Если выбранный для решения задачи численный метод реализован в виде стандартной подпрограммы, то алгоритм обычно сводится к описанию и вводу исходных данных, вызову стандартной подпрограммы и выводу результатов на экран или на печать. Более характерен случай, когда стандартные программы решают, лишь какую - то часть задачи. Здесь эффективным подходом является разделение сложной исходной задачи на некоторые подзадачи, реализуется отдельными модулями. Определяется общая структура алгоритма, взаимодействие между отдельными модулями, детализируется логика. Проектирование программы включает в себя несколько подзадач.

Во-первых, необходимо выбрать язык программирования.

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

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

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

Решения задачи на ЭВМ - выполнение всех предусмотренных программой вычислений и вывод результатов расчетов на экран дисплея или печать.

Словесный способ записи алгоритмов представляет собой описание последовательных этапов обработки данных и задается в произвольном изложении на естественном языке. Способ основан на использовании общественных средств общения между людьми и, сточки зрения написания, трудностей для авторов алгоритмов не приставляет. Однако для «исполнителей» такие описания алгоритмов часто неприемлемы. Они строго не формализуемы, страдают многословностью записей, допускают неоднозначность толкования отдельных предписаний. Поэтому такой способ описание алгоритмов не имеет широкого распространения.

Алгоритм - отличается от обычного представления списка действия следующими свойствами:

1) однозначность - наличие единого правила выполнения действия составляющих алгоритмов;

2) конечность - означает обязательное завершение каждого из действий ставленых алгоритмов и программы в целом;

3) массовость - написанный алгоритм должен принимается для решения целого класса с возможно изменяющимися данными в заданных приделах;

4) результативность - получение конечного результата при работе алгоритма.

Программирование - это процесс разработки программы, данный процесс делится на следующие этапы:

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

Предлагает определение исходных данных, конкретных требований предъявляемых программе на данном этапе, необходимо четко обозначить моменты или вопросы которые необходимо решить для получения конечной программы.

Выбор алгоритма.

На данном этапе мы подбираем подходящий способ решения задач.

Программирование.

Происходит создание программы на выбранном языке программирования, в данном случае это С++.

Ввод программы целевой ЭВМ и конечная ЭВМ.

На этом этапе подразумевается загрузка версий на целевую машину.

Запуск и отладка программы.

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

Испытание программы.

На этом этапе происходит запуск и использование конечной версии, анализ результатов её работы.

Каждая программа С++ - это совокупность функций, каждая из которых должна быть определена или по крайней мере описана до её использования в конкретном модуле программы. В определении функции указываются последовательность действий , выполняемых при её вызове, имя функции, тип функции и совокупность формальных параметров. При разработке своих программ, состоящих из достаточно большого количества программ и функций, следует записывать как библиотеку стандартных функций. Прототипы функций и описание внешних объектов помещают в отдельный файл, который процессорной командой включают в начало каждого из модулей программы.

1.2 Управляющие структуры

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

Блоки и составные операторы.

Любая последовательность операторов, заключенная в фигурные скобки, является составным оператором (блоком). Составной оператор не должен заканчиваться (;). Поскольку ограничителем блока служит сама закрывающаяся скобка. Внутри блока каждый оператор должен ограничиваться (;).

Составной оператор может использоваться везде, где синтаксис языка допускает применение оператора.

Пустой оператор.

Пустой оператор представляется символом (;), перед которым нет выражения. Пустой оператор используется там, где синтаксис языка требует присутствия в данном месте программы оператора, однако по логике программы оператор должен отсутствовать.

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

Операторы ветвления.

К операторам ветвления относятся if, if else,?,switch и go to. Общий вид операторов ветвления следующий:

if (логическое выражение)

оператор;

if (логическое выражение)

оператор_1;

else

оператор_2;

<логическое выражение>?<выражение_1> : <выражение_2>;

Если значение логического выражения истинно, то вычисляется выражение_1, в противном случае вычисляется выражение_2.

switch (выражение целого типа)

{

case значение_1:

последовательность_операторов_1;

break;

case значение_2;

последовательность_операторов_2;

break;

case значение_n:

последовательность_операторов_n;

break;

default:

последовательность_операторов_n+1;

}

Ветку default можно не описывать. Она выполняется, если не одного из вышестоящих выражений не удовлетворено.

Оператор цикла.

В С++ имеются следующие конструкции, позволяющие программировать циклы: while, do while и for. Их структуру можно описать следующим образом:

while (логическое выражение)

оператор;

Цикл с проверкой условия на верху

do

оператор;

while (логическое выражение);

Цикл с проверкой условия внизу

for (инициализация, проверка, новое_значение)

оператор;

1.3 Назначение и области применения

Данная программа предназначена для заполнения массива случайными числами в определенном диапазоне, сортировки чисел по возрастанию и переворачивание массива. Случайные числа очень важны во многих видах моделирования и в играх.

1.4 Технические характеристики

В данной программе используется метод сортировки «пузырька».

Сортировка - это специальный алгоритм обработки в результате, которого происходит упорядочивание элементов.

Постановка задачи - точное описание исходных данных, условий задачи и целей ее решения. Часто задача программирования задается в математической формулировке, поэтому необходимость в выполнении этапов 1 и 2 отпадает. Для решения достаточно сложных задач этап формализации может потребовать значительных усилий и времени.

1.5 Генератор случайных чисел

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

- тестирование алгоритмов;

- имитационное моделирование;

- некоторые задачи численного анализа;

- имитация пользовательского ввода.

Для получения случайных чисел можно использовать различные способы. В общем случае все методы генерирования случайных чисел можно разделить на аппаратные и программные. Устройства или алгоритмы получения случайных чисел называют генераторами случайных чисел (ГСЧ) или датчиками случайных чисел.

Аппаратные ГСЧ представляют собой устройства, преобразующие в цифровую форму какой-либо параметр окружающей среды или физического процесса. Параметр и процесс выбираются таким образом, чтобы обеспечить хорошую «случайность» значений при считывании. Очень часто используются паразитные процессы в электронике (токи утечки, туннельный пробой диодов, цифровой шум видеокамеры, шумы на микрофонном входе звуковой карты и т.п.). Формируемая таким образом последовательность чисел, как правило, носит абсолютно случайный характер и не может быть воспроизведена заново по желанию пользователя.

К программным ГСЧ относятся различные алгоритмы генерирования последовательности чисел, которая по своим характеристикам напоминает случайную. Для формирования очередного числа последовательности используются различные алгебраические преобразования. Одним из первых программных ГСЧ является метод средин квадратов, предложенный в 1946 г. Дж. фон Нейманом. Этот ГСЧ формирует следующий элемент последовательности на основе предыдущего путем возведения его в квадрат и выделения средних цифр полученного числа. Например, мы хотим получить 10-значное число и предыдущее число равнялось 5772156649. Возводим его в квадрат и получаем 33317792380594909201; значит, следующим числом будет 7923805949. Очевидным недостатком этого метода является зацикливание в случае, если очередное число будет равно нулю. Кроме того, существуют и другие сравнительно короткие циклы.

Любые программные ГСЧ, не использующие внешних «источников энтропии» и формирующие очередное число только алгебраическими преобразованиями, не дают чисто случайных чисел. Последовательность на выходе такого ГСЧ выглядит как случайная, но на самом деле подчиняется некоторому закону и, как правило, рано или поздно зацикливается. Такие числа называются псевдослучайными.

Последовательности случайных чисел, формируемых тем или иным ГСЧ, должны удовлетворять ряду требований. Во-первых, числа должны выбираться из определенного множества (чаще всего это действительные числа в интервале от 0 до N). Во-вторых, последовательность должна подчиняться определенному распределению на заданном множестве (чаще всего распределение равномерное). Необязательным является требование воспроизводимости последовательности. Если ГСЧ позволяет воспроизвести заново однажды сформированную последовательность, отладка программ с использованием такого ГСЧ значительно упрощается. Кроме того, требование воспроизводимости часто выдвигается при использовании ГСЧ в криптографии.

Поскольку псевдослучайные числа не являются действительно случайными, качество ГСЧ очень часто оценивается по «случайности» получаемых чисел. В эту оценку могут входить различные показатели, например, длина цикла (количество итераций, после которого ГСЧ зацикливается), взаимозависимости между соседними числами (могут выявляться с помощью различных методов теории вероятностей и математической статистики).

Одна из задач, в которых применяются ГСЧ, - это грубая оценка объемов сложных областей в евклидовом пространстве более чем четырех или пяти измерений. Разумеется, сюда входит и приближенное вычисление интегралов. Обозначим область через R; обычно она определяется рядом неравенств. Предположим, что R - подмножество n_мерного единичного куба K. Вычисление объема множества R методом Монте-Карло сводится к тому, чтобы случайным образом выбрать в K большое число N точек, которые с одинаковой вероятностью могут оказаться в любой части K. Затем подсчитывают число M точек, попавших в R, т.е. удовлетворяющих неравенствам, определяющим R. Тогда M/N есть оценка объема R. Можно показать, что точность такой оценки будет довольно низкой. Тем не менее, выборка из 10 000 точек обеспечит точность около 1%, если только объем не слишком близок к 0 или 1. Такой точности часто бывает достаточно, и добиться лучшего другими методами может оказаться очень трудно.

1.6 Массивы

Массивы - это группа элементов одинакового типа (double, float, int и т.п.). Из объявления массива компилятор должен получить информацию о типе элементов массива и их количестве. Объявление массива имеет два формата:

Спецификатор - типа описатель [константное - выражение];

Спецификатор - типа описатель [ ];

Описатель - это идентификатор массива .

Спецификатор-типа задает тип элементов объявляемого массива. Элементами массива не могут быть функции и элементы типа void.

Константное выражение в квадратных скобках задает количество элементов массива. Константное-выражение при объявлении массива может быть опущено в следующих случаях:

- при объявлении массив инициализируется,

- массив объявлен как формальный параметр функции,

- массив объявлен как ссылка на массив, явно определенный в другом файле.

В языке СИ определены только одномерные массивы, но поскольку элементом массива может быть массив, можно определить и многомерные массивы. Они формализуются списком константных выражений следующих В языке СИ определены только одномерные массивы, но поскольку элементом массива может быть массив, можно определить и многомерные массивы. Они формализуются списком константных выражений следующих за идентификатором массива, причем каждое константное выражение заключается в свои квадратные скобки. Каждое константное выражение в квадратных скобках определяет число элементов по данному измерению массива, так что объявление двухмерного массива содержит два константных выражения, трехмерного - три и т.д. Отметим, что в языке СИ первый элемент массива имеет индекс равный 0.

Примеры:

int a[2][3]; /* представлено в виде матрицы

a[0][0] a[0][1] a[0][2]

a[1][0] a[1][1] a[1][2] */

double b[10]; /* вектор из 10 элементов имеющих тип double */

int w[3][3] = { { 2, 3, 4 },

{ 3, 4, 8 },

{ 1, 0, 9 } };

В последнем примере объявлен массив w[3][3]. Списки, выделенные в фигурные скобки, соответствуют строкам массива, в случае отсутствия скобок инициализация будет выполнена неправильно.

В языке СИ можно использовать сечения массива, как и в других языках высокого уровня (PL1 и т.п.), однако на использование сечений накладывается ряд ограничений. Сечения формируются вследствие опускания одной или нескольких пар квадратных скобок. Пары квадратных скобок можно отбрасывать только справа налево и строго последовательно. Сечения массивов используются при организации вычислительного процесса в функциях языка СИ, разрабатываемых пользователем.

Примеры:

int s[2][3];

Если при обращении к некоторой функции написать s[0], то будет передаваться нулевая строка массива s.

int b[2][3][4];

При обращении к массиву b можно написать, например, b[1][2] и будет передаваться вектор из четырех элементов, а обращение b[1] даст двухмерный массив размером 3 на 4. Нельзя написать b[2][4], подразумевая, что передаваться будет вектор, потому что это не соответствует ограничению наложенному на использование сечений массива.

Пример объявления символьного массива.

char str[] = "объявление символьного массива";

Следует учитывать, что в символьном литерале находится на один элемент больше, так как последний из элементов является управляющей последовательностью '\0'.

2. СПЕЦИАЛЬНАЯ ЧАСТЬ

2.1 Спецификация программы

В данную программу входит обработка массива данных.

Благодаря тому, что Си++ является машинно-независимым и широко доступным языком, прикладные программы, написанные на Си++, могут работать без изменений на большинстве компьютерных систем.

Таблица 1 - Системные требования

Характеристика	Значение
Операционная система	MS-DOS
Оперативная память	2кб
Память на жестком диске	45,2кб
Микропроцессор	Х86

2.2 Инструкция по выполнению программы

Для того чтобы выполнить работу программы необходимо сделать следующее:

1) введите количество элементов в массиве;

2) нажмите клавишу ENTER;

3) выберите нужное действие;

4) нажмите 1 для сортировки массива;

5) нажмите 2 для переворачивания массива.

2.3 Описание программы

Целью проекта является заполнение массива случайными числами в диапазоне от 0 до 100 и сортировки массива по возрастанию, переворачивание массива. Рассмотрим случай когда необходимо выполнить упорядочивание «сортировку» чисел по возрастанию.

Пусть дан массив чисел.

Int m [ ] = { 5 , 1 , 7 , 18 , 8 , 3 }

Для сортировки данного массива можно применить один из известных методов сортировки. Самым простым но зато самым не эффективным является метод «пузырька»

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

{

for (int j = 0; j < n-1; j++)

{

if (m [j] > m [j+1])

{

int c;

c = m [j+1];

m [j+1] = m [j];

m [j] = c;

}

}

}

2.4 Тестирование программы

После компиляции программы, программа просит пользователя ввести необходимое количество элементов массива. После ввода количества элементов массива на экран выводится строка случайных чисел - (Рисунок 1)



Рисунок 1 - Заполнение массива случайными числами

После заполнения массива случайными числами программа предлагает выбрать действия:

1) сортировка;

2) переворачивание.

Рисунок 2 - Выбор действий работы с массивом

После выбора сортировки на экране появляется отсортированный массив по возрастанию - (Рисунок 3.)



Рисунок 3 - Сортировка массива по возрастанию

После выбора переворачивания на экране выводится массив в обратном порядке - (Рисунок 4.)

Рисунок 4 - Выбор переворачивания массива

После выполнения действий заданных пользователем выводится сообщение о выборе дальнейших действий:

1) продолжение работы;

2) завершение работы.

(Рисунок 5.)

Рисунок 5 - Выбор действий после для продолжения работы или завершения работы программы

ЗАКЛЮЧЕНИЕ

В процессе разработки курсовой работы «Разработка базового алгоритма обработки массива данных по заданному условию», был разработан алгоритм решения задачи. По этому алгоритму на языке Си++ разработана и отлажена программа, показавшая верное решение поставленной задачи.

В основу программы включен алгоритм сортировки «пузырька» и методы работы языка Си со случайными числами.

В результате заполнения массива случайными числами выполняется два действия: сортировка массива по возрастанию, переворачивание массива. Интерфейс программы прост и понятен, пользователь понимает что от него требуется.

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

Особое внимание уделялось разумному выделению памяти под объекты во время выполнения программы, поэтому все функции были тщательно отлажены.

СПИСОК ЛИТЕРАТУРЫ

1) Павловская Т.А. «С/C++. Программирование на языке высокого уровня» - СПб.: Питер, 2002;

2) Березин Б.И., Березин С.Б. «Начальный курс С и С++» - СПб.: Питер, 2002;

3) Подбельский В.В., Фомин С.С. «Программирование на языке Си»: Учеб. пособие. - М.: Финансы и статистика, 1998;

4) Франка П. «С++: учебный курс» - СПб.: Питер, 2001;

5) Дэвис Стефан Р. «С++ для «чайников»», 4-е издание.: Перев. с англ.: Уч. пос. - М.: Издательский дом «Вильямс», 2001;

6) Пашенков В.В. «Язык программирования Си». - М.: Центр НТТМ «Алгоритм», 1990.

ПРИЛОЖЕНИЕ

Код программы

# include<conio.h>

# include<stdlib.h>

# include<stdio.h>

void main()

{

do{

clrscr();

printf(“\nПрограмма заполнения массива случайными числами\n”);

randomize();

printf(“Введите размер массива:”);

int n;

scanf(“%i”,&n);

int *m=new int [n];

int a;

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

{

m[i] = random (100);

printf (“%i ”,m[i]);

}

printf(“\nВыберите действие:\n”

“\n1-сортировка:\n”

“\n2-переворачивание:\n”);

scanf(“%i”,&a);

if(a==1)

{

printf(“\n Сортировка массива \n”);

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

{

for(int j=0;j<n-1;j++)

{

if(m[j]>m[j+1])

{

int c;

c=m[j+1];

m[j+1]=m[j];

m[j]=c;

}

}

}

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

{

printf(“%i ”,m[i]);

}

}

if(a==2)

{

printf(“\n Переворачивание массива \n”);

for( i=n-1;i>=0;i--)

{

printf(“%i ”,m[i]);

}

}

printf(“\nДля проделжения нажмите 3\nДля завершения работы нажмите <Enter>”);

}

while (getch()=='3');

}

Размещено на Allbest.ru

...