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

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

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

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

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

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

Выполнил:

Хрол Д.А.

Новополоцк 2010

Введение

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

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

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

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

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

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

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

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

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

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

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

Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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 of array 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]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[i]>=Array[i]>=Array,

при 1<=i

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

2.Будем удалять элементы из корня по одному за раз и перестраивать дерево. То есть на первом шаге обмениваем Array и Array[n], преобразовываем Array, Array, …, Array в сортирующее дерево. Затем переставляем Array и Array, преобразовываем Array, Array, …, Array в сортирующее дерево. Процесс продолжается до тех пор, пока в сортирующем дереве не останется один элемент. Тогда Array, Array, …, 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 < Arr) then:= Child + 1;Current >= Arr then;:= Arr;:= Child;;:= 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, 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(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);;

Процедура 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;

Процедура 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);("Данные сохранены");

Процедура поиска записей: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;

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

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

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

p:= q;p <> nil dop^.a.town <> TOWN then(p^.a.name:15, " ", p^.a.town);(f, p^.a.name:15, " ", p^.a.town);;:= p^.o;;(Введите возраст для поиска: "); readln(a);("Введите диагноз: "); readln(s);("ПЕРЕЧЕНЬ ПАЦИЕНТОВ СТАРШЕ ", a, " ЛЕТ С ДИАГНОЗОМ "", s, """);

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/

Западно-Казахский Аграрно-Технический университет Жангир-хана

Кафедра: «Информатики»

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

Подготовил: Иванов П.

Проверил: Кухта В.С.

Уральск 2010

1.Понятие алгоритма и его свойства

2.Способы описания алгоритмов

3.Основные структурные алгоритмические конструкции

4. Список литературы

Понятие алгоритма и его свойства

Алгоритм – описанная на некотором языке точная конечная система правил, определяющая содержание и порядок действий над некоторыми объектами, строгое выполнение которых дает решение поставленной задачи. Понятие алгоритма, являющееся фундаментальным в математике и информатике, возникло задолго до появления средств вычислительной техники. Слово «алгоритм» появилось в средние века, когда европейцы познакомились со способами выполнения арифметических действий в десятичной системе счисления; описанными узбекским математиком Муххамедом бен Аль-Хорезми («аль-Хорезми» - человек из города Хорезми; в настоящее время город Хива в Хорезмской области Узбекистана). Слово алгоритм – есть результат европейского произношения слов аль-Хорезми. Первоначально под алгоритмом понимали способ выполнения арифметических действий над десятичными числами. В дальнейшем это понятие стали использовать для обозначения любой последовательности действий, приводящей к решению поставленной задачи.

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

Значение слова «алгоритм» очень схоже со значениями слов «рецепт», «метод», «процесс». Однако, в отличие от рецепта или процесса, алгоритм характеризуется следующими свойствами: дискретностью, массовостью, определенностью, результативностью, формальностью.

Дискретность(разрывность – противоположно непрерывности) – это свойство алгоритма, характеризующее его структуру: каждый алгоритм состоит из отдельных законченных действий, говорят: «Делится на шаги».

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

Определенность(детерминированность, точность) - свойство алгоритма, указывающее на то, что каждый шаг алгоритма должен быть строго определен и не допускать различных толкований; также строго должен быть определен порядок выполнения отдельных шагов. Помните сказку про Ивана-царевича? «Шел Иван-царевич по дороге, дошел до развилки. Видит большой камень, на нем надпись: «Прямо пойдешь - голову потеряешь, направо пойдешь - жену найдешь, налево пойдешь – разбогатеешь». Стоит Иван и думает, что дальше делать». Таких инструкций алгоритм содержать не может.

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

Формальность – это свойство указывает на то, что любой исполнитель, способный воспринимать и выполнять инструкции алгоритма, действует формально, т.е. отвлекается от содержания поставленной задачи и лишь строго выполняет инструкции. Рассуждать «что, как и почему?» должен разработчик алгоритма, а исполнитель формально (не думая) поочередно исполняет предложенные команды и получает необходимый результат.

Способы описания алгоритмов

Рассмотрим следующие способы описания алгоритма: словесное описание, псевдокод, блок-схема, программа.

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

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

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

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

Блок-схема – описание структуры алгоритма с помощью геометрических фигур с линиями-связями, показывающими порядок выполнения отдельных инструкций. Этот способ имеет ряд преимуществ. Благодаря наглядности, он обеспечивает «читаемость» алгоритма и явно отображает порядок выполнения отдельных команд. В блок-схеме каждой формальной конструкции соответствует определенная геометрическая фигура пли связанная линиями совокупность фигур.

Рассмотрим некоторые основные конструкции, использующиеся для построения блок-схем алгоритмов программ, регламентированные ГОСТ 19.701-90.

Блок, характеризующий начало/конец алгоритма (для подпрограмм - вызов/возврат)

Блок - процесс, предназначенный для описания отдельных действий

Блок - Предопределенный процесс, предназначенный для обращения к вспомогательным алгоритмам (подпрограммам)

Блок - ввода/вывода с неопределенного носителя или описания исходных данных

Блок - решение (проверка условия или условный блок)

Блок - границы цикла, описывающий циклические процессы типа: «цикл с предусловием», «цикл с постусловием»

Соединительные блоки

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

Программа – описание структуры алгоритма на языке алгоритмического программирования.

Основные структурные алгоритмические конструкции

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

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

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

Рис. 1. Полное ветвление

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

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

ФЕДЕРАЛЬНОЕ АГЕНСТВО ПО ОБРАЗОВАНИЮ

САРАПУЛЬСКИЙ ПРОМЫШЛЕННО-ЭКОНОМИЧЕСКИЙ ТЕХНИКУМ

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

КОНТРОЛЬНАЯ РАБОТА

ПО ДИСЦИПЛИНЕ

«ОСНОВЫ АЛГОРИТМИЗАЦИИ И ПРОГРАММИРОВАНИЯ»

ВЫПОЛНИЛ СТУДЕНТ

ГР. АСУ-31СЗ СУХИХ А.В.

ПРОВЕРИЛ

ПРЕПОДАВАТЕЛЬ МЫМРИНА М.Л.

2005/2006 уч. год

1. ПОНЯТИЕ АЛГОРИТМА 3

2. ЭЛЕМЕНТЫ ЯЗЫКА TURBO PASCAL 13

2.1. Алфавит 13

2.2. Идентификаторы 14

2.3. Комментарии 14

3. ЛЕКСИКА ЯЗЫКА С++ 16

4. ЛИТЕРАТУРА 21

1. ПОНЯТИЕ АЛГОРИТМА

Одним из фундаментальных понятий в информатике является понятие алгоритма. Происхождение самого термина «алгоритм» связано с математикой. Это слово происходит от Algorithmi – латинского написания имени Мухаммеда аль-Хорезми (787 – 850) выдающегося математика средневекового Востока. В своей книге "Об индийском счете" он сформулировал правила записи натуральных чисел с помощью арабских цифр и правила действий над ними столбиком. В дальнейшем алгоритмом стали называть точное предписание, определяющее последовательность действий, обеспечивающую получение требуемого результата из исходных данных. Алгоритм может быть предназначен для выполнения его человеком или автоматическим устройством. Создание алгоритма, пусть даже самого простого, - процесс творческий. Он доступен исключительно живым существам, а долгое время считалось, что только человеку. В XII в. был выполнен латинский перевод его математического трактата, из которого европейцы узнали о десятичной позиционной системе счисления и правилах арифметики многозначных чисел. Именно эти правила в то время называли алгоритмами.

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

Такими свойствами являются:

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

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

Результативность (конечность) – алгоритм должен приводить к решению задачи за конечное число шагов.

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

На основании этих свойств иногда дается определение алгоритма, например: “Алгоритм – это последовательность математических, логических или вместе взятых операций, отличающихся детерменированностью, массовостью, направленностью и приводящая к решению всех задач данного класса за конечное число шагов”. Такая трактовка понятия “алгоритм” является неполной и неточной. Во-первых, неверно связывать алгоритм с решением какой-либо задачи. Алгоритм вообще может не решать никакой задачи. Во-вторых, понятие “массовость” относится не к алгоритмам как к таковым, а к математическим методам в целом. Решение поставленных практикой задач математическими методами основано на абстрагировании – мы выделяем ряд существенных признаков, характерных для некоторого круга явлений, и строим на основании этих признаков математическую модель, отбрасывая несущественные признаки каждого конкретного явления. В этом смысле любая математическая модель обладает свойством массовости. Если в рамках построенной модели мы решаем задачу и решение представляем в виде алгоритма, то решение будет “массовым” благодаря природе математических методов, а не благодаря “массовости” алгоритма.

Разъясняя понятие алгоритма, часто приводят примеры “бытовых алгоритмов”: вскипятить воду, открыть дверь ключом, перейти улицу и т. д.: рецепты приготовления какого-либо лекарства или кулинарные рецепты являются алгоритмами. Но для того, чтобы приготовить лекарство по рецепту, необходимо знать фармакологию, а для приготовления блюда по кулинарному рецепту нужно уметь варить. Между тем исполнение алгоритма – это бездумное, автоматическое выполнение предписаний, которое в принципе не требует никаких знаний. Если бы кулинарные рецепты представляли собой алгоритмы, то у нас просто не было бы такой специальности – повар.

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

Само выражение “свойства алгоритма” некорректно. Свойствами обладают объективно существующие реальности. Можно говорить, например, о свойствах какого-либо вещества. Алгоритм – искусственная конструкция, которую мы сооружаем для достижения своих целей. Чтобы алгоритм выполнил свое предназначение, его необходимо строить по определенным правилам. Поэтому нужно говорить не о свойствах алгоритма, а о правилах построения алгоритма, или о требованиях, предъявляемых к алгоритму.

Первое правило – при построении алгоритма прежде всего необходимо задать множество объектов, с которыми будет работать алгоритм. Формализованное (закодированное) представление этих объектов носит название данных. Алгоритм приступает к работе с некоторым набором данных, которые называются входными, и в результате своей работы выдает данные, которые называются выходными. Таким образом, алгоритм преобразует входные данные в выходные.

Это правило позволяет сразу отделить алгоритмы от “методов” и “способов”. Пока мы не имеем формализованных входных данных, мы не можем построить алгоритм.

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

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

Третье правило – дискретность. Алгоритм строится из отдельных шагов (действий, операций, команд). Множество шагов, из которых составлен алгоритм, конечно.

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

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

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

Любая работа на компьютере – это есть обработка информации. Работу компьютера можно схематически изобразить следующим образом:

“Информация” слева и “информация” справа – это разные информации. Компьютер воспринимает информацию извне и в качестве результата своей работы выдает новую информацию. Информация, с которой работает компьютер, носит название “данные”.

Компьютер преобразует информацию по определенным правилам. Эти правила (операции, команды) заранее занесены в память компьютера. В совокупности эти правила преобразования информации называются алгоритмом. Данные, которые поступают в компьютер, называются входными данными. Результат работы компьютера – выходные данные. Таким образом, алгоритм преобразует входные данные в выходные:

Теперь можно поставить вопрос: а может ли человек обрабатывать информацию? Конечно, может. В качестве примера можно привести обычный школьный урок: учитель задает вопрос (входные данные), ученик отвечает (выходные данные). Самый простой пример: учитель дает задание – умножить 6 на 3 и результат написать на доске. Здесь числа 6 и 3 – входные данные, операция умножения – алгоритм, результат умножения – выходные данные:

Вывод: решение математических задач – частный случай преобразования информации. Компьютер (по-английски означает вычислитель, на русском языке – ЭВМ, электронная вычислительная машина) был создан как раз для выполнения математических расчетов.

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

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

Трактовка работы алгоритма как преобразования входных данных в выходные естественным образом подводит нас к рассмотрению понятия “постановка задачи”. Для того чтобы составить алгоритм решения задачи, необходимо из условия выделить те величины, которые будут входными данными и четко сформулировать, какие именно величины требуется найти. Другими словами, условие задачи требуется сформулировать в виде “Дано... Требуется” – это и есть постановка задачи.

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

Программирования , рассматриваемого в учебном пособии. В...

Р

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

Скачать:

Предварительный просмотр:

Министерство образования Саратовской области

Государственное автономное профессиональное образовательное учреждение Саратовской области «Энгельсский политехникум»

(ГАПОУ СО «Энгельсский политехникум»)

Р абочая программа учебной дисциплины

ОП.17 ОСНОВЫ АЛГОРИТМИЗАЦИИ И ПРОГРАММИРОВАНИЯ

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

для специальностей технического профиля 09.02.05.Прикладная информатика (по отраслям))

на базе основного общего образования

с получением среднего общего образования

2016 г.

Рекомендована Экспертной комиссией согласно приказа министерства образования Саратовской области от 13.01.2011 года № 28 «О подготовке основных профессиональных образовательных программ среднего профессионального образования»

разработана на основе Федерального государственного образовательного стандарта по специальностям среднего профессионального образования (далее – СПО)

09.02.05 - Прикладная информатика (по отраслям)

Организация-разработчик: ГАПОУ СО «Энгельсский политехникум»

Разработчики:

Ивашов Юрий Александрович, преподаватель

1. ПАСПОРТ ПРОГРАММЫ УЧЕБНОЙ ДИСЦИПЛИНЫ

ОСНОВЫ АЛГОРИТМИЗАЦИИ И ПРОГРАММИРОВАНИЯ

название программы учебной дисциплины

1.1. Область применения программы

Рабочая программа учебной дисциплины «Основы алгоритмизации и программирования» соответствует требованиям ФГОС по специальности 09.02.05 - Прикладная информатика (по отраслям) базовой подготовки и работодателей.

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

Учебная дисциплина направлена на формирование общих и профессиональных компетенций:

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

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

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

ОК 5. Использовать информационно-коммуникационные технологии в профессиональной деятельности.

ОК 6. Работать в коллективе и команде, эффективно общаться с коллегами, руководством, потребителями.

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

ОК 8. Самостоятельно определять задачи профессионального и личностного развития, заниматься самообразованием, осознанно планировать повышение квалификации.

ОК 9. Ориентироваться в условиях частой смены технологий в профессиональной деятельности.

ПК 1.1. Обрабатывать статический информационный контент.

ПК 1.2. Обрабатывать динамический информационный контент

ПК 2.3. Разрабатывать и публиковать программное обеспечение и информационные ресурсы отраслевой направленности со статическим, динамическим и интерактивным контентом.

ПК 2.4. Проводить отладку и тестирование программного обеспечения отраслевой направленности.

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

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

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

1.2. Цели и задачи дисциплины – требования к результатам освоения дисциплины:

В результате освоения дисциплины обучающийся должены:

уметь:

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

знать:

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

• базовые и динамические структуры данных и операции над ними;
• операторы языка Pascal, C, C++.

Максимальной учебной нагрузки обучающегося 180 часов , в том числе:

обязательной аудиторной учебной нагрузки обучающегося 120 часов ;

самостоятельной работы обучающегося 60 часов .

2. СТРУКТУРА И СОДЕРЖАНИЕ УЧЕБНОЙ ДИСЦИПЛИНЫ

2.1. Объем учебной дисциплины и виды учебной работы

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

3. УСЛОВИЯ РЕАЛИЗАЦИИ ПРОГРАММЫ ПРОФЕССИОНАЛЬНОГО МОДУЛЯ

3.1 Реализация программы дисциплины требует наличия учебного кабинета основы алгоритмизации и программирования, с подключением к сети Интернет.

Оборудование кабинета:

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

Программное обеспечение рабочих мест:

• Операционная система;
• Браузер;
• Антивирусное ПО;
• Среда программирования.

3.2. Информационное обеспечение обучения

Основные источники:

1. Семакин, И. Г., Шестаков, А. П. Основы алгоритмизации программирования (учебник для СПО). [Текст]/ И. Г. Семакин, А. П. Шестаков – Москва, 2012 г. – 400 с.
2. Колдаев, В. Д. Основы алгоритмизации и программирования. [Текст]/ В. Д. Колдаев – Москва, 2011 г.
3. Андреева Т.А. Программирование на языке Pascal: учеб. пособие. Бином. Лаборатория знаний, 2011. 234 с.
4. Некрасов В.П. Turbo Pascal 7.0. Основы программирования. Ч. 1. Екатеринбург: Изд-во УрГУПС, 2011. 60 с.
5. Епанешников А.М. Программирование в среде Turbo Pascal 7.0: учеб. пособие. 4-е изд., испр. М.: Диалог-МИФИ, 2010. 367 с.
6. Репаков, Г.Г. Turbo Pascal для студентов и школьников / Г.Г. Репаков. - СПб.: БХВ- Петербург, 2009,- 245с.
7. Хореев, П.Б. Технология объектно-ориентированного программирования: учебное пособие для вузов / П. Б. Хорев. - Москва: Академия, 2008. - 448с
8. Голицына О.Л, Партыка Т.Л., Попов И.И. Языки программирования. 2-е изд., перераб. и доп./ Голицына О.Л, Партыка Т.Л., Попов И.И. – М.: Издательство «Форум», 2010. - 400 с. (Допущено Министерством образования и науки Российской Федерации)

Дополнительная литература

1. Голицина, О. Л., Попов, И.И Основы алгоритмизации и программирования. [Текст]/ О. Л. Голицина, И. И. Попов – Москва, 2004 г.
2. Могилев, А. В., Пак, Н. И., Хеннер, Е. К. Информатика. [Текст]/ А. В. Могилев, Н. И. Пак, Е. К. Хеннер – Москва, 2004 г.
3. Могилев, А. В., Пак, Н. И., Хеннер, Е. К. Практикум по информатике. [Текст]/ А. В. Могилев, Н. И. Пак, Е. К. Хеннер – Москва, 2005 г.
4. Семакин, И. Информатика. Задачник-практикум. Том 1. - [Текст]/ И. Семакин – Москва. 2011 г.
5. Попов В.Б. Turbo Pascal для школьников: Учеб. пособие. - 3-е изд., доп. – М.: Финансы и статистика, 2010. – 352 с.

4. КОНТРОЛЬ И ОЦЕНКА РЕЗУЛЬТАТОВ ОСВОЕНИЯ УЧЕБНОЙ ДИСЦИПЛИНЫ

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

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

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

Основы алгоритмизации и программирования. Семакин И.Г., Шестаков А.П.

3-е изд. - М.: 2016. - 304 с.

В учебнике рассмотрены основы принципы алгоритмизации и программирования на базе языка Паскаль (версия Турбо Паскаль 7.0) Даны основные понятия объектно-ориентированного программирования и его реализация на языке Турбо Паскаль. Описана интегрированная среда программирования Delphi и визуальная технология создания графического интерфейса программ. Показана разработка программных модулей в этой среде. Учебник может быть использован при изучении общепрофессиональной дисциплины ОП «Основы алгоритмизации и программирования» в соответствии с требованиями ФГОС СПО для специальностей 230113 «Компьютерные системы и комплексы» и 230401 «Информационные системы (по отраслям)» укрупненной группы специальностей 230000 «Информатика и вычислительная техника». Для студентов средних профессиональных учебных заведений.

Формат: pdf

Размер: 7,3 Мб

Смотреть, скачать: drive.google

ОГЛАВЛЕНИЕ
Предисловие 4
Глава 1. Основные принципы алгоритмизации и программирования 8
1.1. Алгоритмы и величины 9
1.2. Линейные вычислительные алгоритмы 13
1.3. Ветвления и циклы в вычислительных алгоритмах 17
1.4. Логические основы алгоритмизации 26
1.5. Вспомогательные алгоритмы и процедуры 30
1.6. Основы структурного программирования 33
1.7. Развитие языков и технологий программирования 39
1.8. Структура и способы описания языков программирования высокого уровня 44
Глава 2. Программирование на языке Паскаль 49
2.1. Первое знакомство с языком Паскаль 50
2.2. Некоторые сведения о системах программирования на Паскале 56
2.3. Элементы языка Турбо Паскаль 57
2.4. Концепция типов данных 59
2.5. Арифметические операции, функции, выражения. Оператор присваивания 64
2.6. Ввод данных с клавиатуры и вывод на экран 70
2.7. Управление символьным выводом на экран 75
2.8. Логические величины, операции, выражения 81
2.9. Функции, связывающие различные типы данных 83
2.10. Программирование ветвящихся алгоритмов 86
2.11. Программирование циклических алгоритмов 90
2.12. Подпрограммы 96
2.13. Вычисление рекуррентных последовательностей 104
2.14. Графические средства Турбо Паскаля 113
2.15. Символьные строки 123
2.16. Массивы 129
2.17. Рекурсивные подпрограммы 139
2.18. Множества 144
2.19. Файлы 151
2.20. Комбинированный тип данных 162
2.21. Указатели и динамические структуры данных 168
2.22. Внешние подпрограммы и модули 179
Глава 3. Методы построения алгоритмов 189
3.1. Метод последовательной детализации 190
3.2. Рекурсивные методы 19В
3.3. Методы перебора в задачах поиска 201
3.4. Методы сортировки данных и сложность алгоритмов 208
Глава 4. Объектно-ориентированное программирование 217
4.1. Что такое объектно-ориентированное программирование 218
4.2. Объекты в Турбо Паскале 221
4.3. Интегрированная среда программирования Delphi 230
4.4. Компоненты Delphi. Свойства компонентов 234
4.5. Событийно-управляемое программирование 248
4.6. Технология создания приложенийв Delphi 253
4.7. Примеры разработки приложений Delphi 256
4.8. Иерархия классов 269
Приложения 275
Турбо Паскаль. Модуль CRT 275
Турбо Паскаль. Модуль GRAPH 278
DELPHI, Некоторые подпрогаммы 291
Список литературы 298