Основы алгоритмизации и программирования

Министерство образования Республики Беларусь

УО «Полоцкий государственный университет»

Факультет информационных технологий

Кафедра технологий программирования

КУРСОВАЯ РАБОТА

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

Выполнил:

Хрол Д.А.

Новополоцк 2010

Содержание

Введение

. Решение задачи №1

. Решение задачи №2

. Решение задачи №3

. Решение задачи №4

. Решение задачи №5

.1 Постановка задачи и выбор метода обработки информации

.2 Форма представления исходных данных

.3 Разработка алгоритма и его описание

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

.4.1 Структура программы

.4.2 Описание подпрограмм

.5 Инструкция по эксплуатации программы

Заключение и выводы

Список использованной литературы

Введение

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

Язык Паскаль относится к процедурно-ориентированным языкам высокого уровня

Достоинства языка Паскаль:

.        относительная простота (т.к. разрабатывался с целью обучения программированию);

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

.        гибкие возможности в отношении используемых структур данных;

.        высокая эффективность программ;

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

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

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

Цели курсовой работы:

−       разработка программ согласно заданию курсовой работы;

−       систематизация и закрепление теоретических знаний и практических умений, полученных за время обучения дисциплины «Основы алгоритмизации и программирования».

1. Решение задачи №1

Постановка задачи и выбор метода обработки информации

Первой задачей курсовой работы является вычисление суммы рядя с точностью ε = 10^-5:

Значение X вводится с клавиатуры.

Математическая формулировка задачи и выбор метода обработки информации

Для решения данной задачи будет использоваться формула, приведенная ниже:

Программный код

программа паскаль задача алгоритм

var, x2k, s, e, eps: real;: integer;: integer;('X='); readln(x);:= 0; eps:= 0.00001; k:= 0;:= 1; x2k:= 1;:= minus * (-1);k:= x2k * x * x;(k);:= minus * x2k / (2 * k * (2 * k - 1));:= s + e;abs(e) < eps;('S=', s:8:5);.

Рисунок 1. Разработка алгоритма и его описание

Инструкция по эксплуатации программы

Пользователь вводит значение X с клавиатуры. Далее происходят вычисления по заданному алгоритму до значения с точностью, равной 10^-5. После нахождения результата сумма выводится на экран.

2. Решение задачи №2

Постановка задачи и выбор метода обработки информации.

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

Форма представления исходных данных

Данные представлены в виде одномерного массива.

Рисунок 2. Разработка алгоритма и его описание

Описание программы. Структура программы.

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

Описание подпрограмм

Подпрограмма MinPosition предназначена для поиска минимального из положительных элементов матрицы:

function MinPosition(a:array [0..s] of array [0..s] of integer):string;,j,min:integer;:string;:=60;i:=0 to s doj:=0 to s do(a[i][j]>0) and (a[i][j]<min) then:=a[i][j];:=inttostr(i)+inttostr(j);;;;:=k;;

Подпрограмма ReplaceElems предназначена для замены элементов строки и столбца, на пересечении которых находится минимальный элемент:

procedure ReplaceElems(var a:array [0..s]of array [0..s] of integer; str, col:integer);,j:integer;j:=0 to s do:=a[str][j];[str][j]:=a[j][col];[j][col]:=tmp;;;

Инструкция по эксплуатации программы

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

3. Решение задачи №3

Постановка задачи и выбор метода обработки информации.

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

Форма представления исходных данных

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

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

.        Каждый лист имеет глубину либо d либо d − 1, d- максимальная глубина дерева.

.        Значение в любой вершине больше, чем значения её потомков.

Удобная структура данных для сортирующего дерева- такой массив Array, что Array[1]- элемент в корне, а потомки элемента Array[i]- Array[2i] и Array[2i+1].

Алгоритм сортировки будет состоять из двух основных шагов:

.        Выстраиваем элементы массива в виде сортирующего дерева:

[i]>=Array[2i][i]>=Array[2i+1],

при 1<=i<n/2

Этот шаг требует O(n) операций.

2.      Будем удалять элементы из корня по одному за раз и перестраивать дерево. То есть на первом шаге обмениваем Array[1] и Array[n], преобразовываем Array[1], Array[2], …, Array[n-1] в сортирующее дерево. Затем переставляем Array[1] и Array[n-1], преобразовываем Array[1], Array[2], …, Array[n-2] в сортирующее дерево. Процесс продолжается до тех пор, пока в сортирующем дереве не останется один элемент. Тогда Array[1], Array[2], …, Array[n]- упорядоченная последовательность. Сортировка организована в виде подпрограммы PyramidalSort.

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

Структура программы

Программа состоит из 2 программ и основной части. Подпрограммы предназначены для преобразования элементов в сортирующее дерево и для сортировки элементов.

Описание подпрограмм

Подпрограмма DownHeap предназначена для преобразования элементов в сортирующее дерево:

procedure DownHeap(index, Count: integer; Current: integer);: Integer;index < Count div 2 do := (index + 1) * 2 - 1;(Child < Count - 1) and (Arr[Child] < Arr[Child + 1]) then:= Child + 1;Current >= Arr[Child] then;[index]:= Arr[Child];:= Child;;[index]:= Current;;

Подпрограмма PyramidalSort предназначена для сортировки дерева:

procedure PyramidalSort(var Arr: mas; Count: integer);: integer;: integer;i:= (Count div 2) - 1 downto 0 do(i, Count, Arr[i]);i:= Count - 1 downto 0 do := Arr[i]; Arr[i]:= Arr[0];(0, i, Current);;

Инструкция по эксплуатации программы

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

4. Решение задачи №4

Постановка задачи и выбор метода обработки информации.

Перед каждым словом исходного предложения напечатать его порядковый номер. Вывести на экран преобразованное предложение. Результат вывести на экран и в текстовый файл.

Форма представления исходных данных

Исходными данными к программе является предложение, представленное в виде последовательности слов и символов.

Рисунок 3. Разработка алгоритма и его описание

Исходный код программы

uses crt;,num:integer;,word,res:string;:text;

writeln('Введите предложение:');

readln(s);:=0;i:=1 to length(s) do(f,’output.txt’);(f);(s[i]<>' ')then(s[i],word,length(word)+1);length(s)=i then:=res+' '+inttostr(num)+' - '+word;;;(word<>'') then(num);res='' then:=res+' '+inttostr(num)+' - '+word;:=res+' '+inttostr(num)+' - '+word;;:='';; end; end;('Результат выполнения');

writeln(res);

writeln(f,res);(f);.

Инструкция по эксплуатации программы

После запуска программы необходимо ввести предложение. В результате выполнения программы на экране будет показано исходное предложение с проставленными перед каждым словом порядковым номерами. Также результат будет записан в файл output.txt.

5. Решение задачи №5

.1 Постановка задачи и выбор метода обработки информации

Создать файл, содержащий сведения о пациентах глазной клиники. Структура записи: фамилия пациента, пол, возраст, место проживания (город), диагноз. На экран и в отдельный файл вывести: количество иногородних пациентов, прибывших в клинику; список пациентов старше X лет с диагнозом Y. Значения X и Y ввести с клавиатуры. Программа должна выполнять следующие дополнительные функции: создание новой базы данных; открытие базы из файла; сохранение базы в файл; добавление записей; удаление записей; поиск записей по одному из полей; сортировку по одному из полей методом, указанным в задаче 3; вывод базы данных на экран; выход из программы. Для реализации основных действий алгоритма использовать подпрограммы. Для обработки записей реализовать динамическую структуру данных односвязный список.

.2 Форма представления исходных данных

Исходными данными к программе являются сведения о пациентах глазной поликлиники.

.3 Разработка алгоритма и его описание

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

Рисунок 4

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

.4.1 Структура программы

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

.4.2 Описание подпрограмм

С помощью процедуры slist_add можно добавлять данные о пациентах в базу:

procedure slist_add(var q: pslist; a: tclient);, n: pslist;:= q;l <> nil then while l^.o <> nil do l:= l^.o;(n);^.a:= a;^.o:= nil;l <> nil then l^.o:= n else q:= n;;

Для удаления записей служит процедура slist_del:

procedure slist_del(var q: pslist; var a: tclient);: pslist;:= q;n <> nil then:= n^.o;:= n^.a;(n);;

end;

Процедура menu_load необходима для загрузки файла базы данных:

procedure menu_load;: string;: file of tclient;: tclient;

write(Введите имя файла для загрузки: ');

readln(f);_destroy(q);(t, f);(t);not eof(t) do(t, a);_add(q, a);;(t);('Данные загружены');_wait;

end;

Процедура menu_save нужна для сохранения существующей базы:

procedure menu_save;: string;: file of tclient;: pslist;

write('Введите имя файла для сохранения: ');

readln(f);(t, f);(t);:= q;o <> nil do(t, o^.a);:= o^.o;;(t);('Данные сохранены');

input_wait;

end;

Процедура поиска записей:menu_search;: string;: pslist;: integer;: boolean;

write(‘ Введите фразу для поиска: ');

readln(p);:= q;:= 0;:= false;o <> nil do(n);(Pos(p, o^.a.name) > 0) or (Pos(p, o^.a.pol) > 0) or (Pos(p, o^.a.town) > 0) or (Pos(p, o^.a.diag) > 0) then:= true;_line(n, o);; := o^.o;;not pres then writeln('Записи не найдены');_wait;

end;

Процедура menu_report выводит на экран и в файл отчет по базе данных:

procedure menu_report;: text;: pslist;: integer;: string;: boolean;(f, 'eye.txt');(f);

writeln('ПЕРЕЧЕНЬ ИНОГОРОДНИХ ПАЦИЕНТОВ');

writeln(f, 'ПЕРЕЧЕНЬ ИНОГОРОДНИХ ПАЦИЕНТОВ);

writeln(f, 'ПЕРЕЧЕНЬ ПАЦИЕНТОВ СТАРШЕ ', a, ' ЛЕТ С ДИАГНОЗОМ "', s, '"');

p:= q;:= false;p <> nil do(p^.a.age >= a) and (p^.a.diag = s) then

writeln(p^.a.name:15, ' ', p^.a.age, ' ëåò');(f, p^.a.name:15, ' ', p^.a.age, ' ëåò');

b:= true;;:= p^.o;;not b then ('Пациенты не найдены');

writeln(f, 'Пациенты не найдены');

end;(f);_wait;;

Для сортировки записей используются две процедуры Sort и DownHeap. Процедура DownHeap преобразует элементы в дерево. Процедура Sort непосредственно сортирует данное дерево.

procedure Sort(var q: pslist; Count: Integer; Field: Integer);DownHeap(index, Count: integer; Current: pslist);: Integer;index < Count div 2 do := (index + 1) * 2 - 1;(Child < Count - 1) and (data_compare(slist_at_pos(q, Child + 1), slist_at_pos(q, Child), Field)) then:= Child + 1;data_compare(Current, slist_at_pos(q, Child), Field) then;_set(slist_at_pos(q, index), slist_at_pos(q, Child));:= Child;;_set(slist_at_pos(q, index), Current);;: integer;: pslist;(Current);i:= (Count div 2) - 1 downto 0 do_set(Current, slist_at_pos(q, i));(i, Count, Current);;i:= Count - 1 downto 0 do _set(Current, slist_at_pos(q, i));_set(slist_at_pos(q, i), slist_at_pos(q, 0));(0, i, Current);;;

5.5 Инструкция по эксплуатации программы

После запуска программы на экране появляется главное меню программы (рисунок 5).

Рисунок 5 - Главное меню

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

После выбора пункта меню «загрузить базу» и «сохранить базу» на экране появится окно, куда необходимо ввести название ранее созданного файла (рисунок 6).

Рисунок 6 - Окно загрузки и сохранения файла базы данных

После выбора пункта меню «добавить запись» на экране появится окно следующего вида, куда необходимо занести информацию о пациенте

.

Рисунок 7 - Добавление записи

Для удаления записи необходимо выбрать пункт «удалить запись», после чего необходимо ввести номер удаляемой записи (рисунок 8).

Рисунок 8 - Удаление записей

Для поиска записей необходимо выполнить пункт меню «поиск записей», далее ввести критерии поиска (рисунок 9).

Рисунок 9 - Поиск записей

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

Заключение и выводы

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

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

.        Вычисление суммы ряда;

.        Обработка одномерных массивов;

.        Обработка матриц;

.        Обработка строк;

.        Работа с файлами, реализация структуры данных «односвязный список».

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

Список использованной литературы

1.      Фаронов В.В. Турбо Паскаль 7.0. Начальный курс: Учебное пособие. - М.: Норидж, 1997.

.        Бородич Ю.С., Вальвачев А.Н., Кузьмич А.И. Паскаль для персональных компьютеров. - Мн.: Выш.шк.; БФГИТМ «НИКА», 1991.

.        Офицеров Д.В., Долгий А.Б., Старых В.А. Программирование на персональных ЭВМ: Практикум: Учеб.пособие. - Мн.: Выш.шк., 1993.

.        Кулагин Н.Б. Программирование в Turbo Pascal 7.0 и Delphi. - СПб.:BHV, 2000.

.        Пильщиков В.Н. Сборник упражнений по языку Паскаль. М.: Наука, 1989.

.        Грогоно П. Программирование на языке Паскаль. - М.: Мир, 1982.

.        Хьюз Дж., Мичтом Дж. Структурный подход к программированию. - М.: Мир, 1980.

.        Мануйлов В.Г. Разработка программного обеспечения на Паскале. - М.: Приор, 1996.

.        Гудман С., Хидетниеми С. Введение в разработку и анализ алгоритмов. - М.:Мир, 1981.

.        Дейкстра Э. Дисциплина программирования. - М.: Мир, 1978. http://lib.ru/ctotor/dejkstra.

.        Фаронов В.В. Практика программирования. М.: МВТУ-ФЕСТО ДИДАКТИК, 1993. http://borlpasc.narod.ru/docym/farpract/oglav.htm

.        CIT Forum (Форум IT технолоний) [Электронный ресурс] Режим доступа: http://www.citforum.ru/database/classics/chen/