МИНИСТЕРСТВО ОБРАЗОВАНИЯ УКРАИНЫ
ВОСТОЧНОУКРАИНСКИЙ НАЦИОНАЛЬНЫЙ
УНИВЕРСИТЕТ им. В. Даля
СЕВЕРОДОНЕЦКИЙ ТЕХНОЛОГИЧЕСКИЙ ИНСТИТУТ
КАФЕДРА КОМПЬЮТЕРНОЙ ИНЖЕНЕРИИ
ПОЯСНИТЕЛЬНАЯ ЗАПИСКА
к курсовой работе по программированию
на тему:
Обработка текстовых файлов
Северодонецк 2009
СОДЕРЖАНИЕ
РЕФЕРАТ
ВВЕДЕНИЕ
1. Анализ технического задания и постановка задачи проектирования
2. Разработка алгоритма программы
3 ОПИСАНИЕ СТРУКТУРЫ ПРОГРАММЫ
3.1 Описание переменных
3.2 Описание вспомогательных процедур и функций
3.3 Алгоритм основной программы
4. ИНСТРУКЦИЯ ОПЕРАТОРУ
ВЫВОДЫ
Перечень ссылок
ПРИЛОЖЕНИЕ А
ПРИЛОЖЕНИЕ Б
ПРИЛОЖЕНИЕ В
РЕФЕРАТ
Цель работы: разработать программу обработки числовых последовательностей с кодом на языке Pascal.
В курсовой работе создана программа, которая реализует выполнение следующих функций: ввод пользователем с клавиатуры последовательности целых чисел, поиск во введенной последовательности нескольких таких чисел, чтобы их сумма делилось на некоторое задаваемое пользователем число. Вывод результата осуществляется на экран монитора и дублируется в текстовый файл на жестком диске или внешнем накопителе. В первом разделе курсовой работы выполнен анализ технического задания, выделены функции, которыми должно обладать разрабатываемое приложение, а также сформулированы требования к нему, произведена постановка задачи на проектирование. Во втором разделе выполняется анализ задачи проектирования, анализируется вид исходных данных и приводится словесный алгоритм работы программы. В третьем разделе рассматриваются алгоритмы разработанных процедур и функций, а также приводятся их описания. К реализованной программе разработана инструкция пользователя, которая приведена в четвертом разделе. Алгоритмы процедур приведены в приложении А. Листинг программы содержится в приложении Б.
Программа разработана с использованием языкаTurbo Pascal.
МАССИВ, ЦИКЛ, ОСТАТОК ОТ ДЕЛЕНИЯ, АЛГОРИТМ, ПРОЦЕДУРА, СОЧЕТАНИЯ
ВВЕДЕНИЕ
Данный курсовой проект был разработан в среде Turbo Pascal 7.0 с базовым языком программирования Pascal. Среди множества языков Pascal является наиболее универсальным и легко изучаемым языком. На сегодня Turbo Pascal получил продолжение в языке Object Pascal с поддержкой всех современных возможностей объектно-ориентированного программирования и в такой мощной системе проектирования как Delphi. Для выполнения данной курсовой работы необходимо разработать алгоритм решения поставленного задания, правильно указав последовательное выполнение соответствующих команд для получения необходимых результатов.
Цель работы заключается в том, чтобы правильно составить алгоритм поставленной задачи по обработке числовой информации, разработать и отладить программу, реализующую разработанный алгоритм.
/>1. Анализ технического задания и постановка задачи проектирования
Согласно заданию дана последовательность из n целых чисел. Необходимо написать программу, выбора из них нескольких чисел так, чтобы сумма выбранных чисел делилась на некоторое число k. Как видим, задание сводится к обработке числовой информации. Пользователю должна быть предоставлена возможность ввода обрабатываемых чисел. Кроме того, перед началом ввода пользователь должен задать количество чисел в последовательности. В качестве дополнительной функции можно предусмотреть вывод информации о программе (ее выполняемых функциях) не экран. Также пользователь должен ввести некоторое целое число k. Далее следует выбрать из предложенной последовательности несколько чисел так, чтобы сумма выбраных чисел делиласьна заданное число k. Пользователю должно быть выдано сообщение, если такая комбинация чисел найдена. Если требуемой комбинации элементов не найдено,то следует выдать соответствующее сообщение, что искомых элементов во введенной последовательности не обнаружено. Также для удобства пользователя можно выводить информацию обо всех возможных сочетаниях элементов и сумму этих элементов. Поскольку чисел может быть довольно много, и вся информация может не поместиться на экран, следует предусмотреть возможность дублирования всей выводимой на экран информации в текстовый файл на жестком диске.
Подытожив все вышесказанное можно сформулировать требования к разрабатываемому программному обеспечению и выполнить постановку задания на проектирование. Так, согласно заданию, программа должна быть реализована в среде Turbo Pascal и должна выполнять следующие функции:
— вывод на экран информации о задании и цели программы;
— ввод пользователем количества чисел последовательности с клавиатуры;
— ввод пользователем последовательности целых чисел;
— перебор всех возможных сочетаний элементов из предложенной последовательности;
— определение сумм элементов в сочетаниях и вывод на экран последовательностей и полученных сумм;
— определение, удовлетворяет ли сумма условию: делится на k без остатка;
— вывод информации на экран, если найдено искомое сочетание элементов;
— вывод информации на экран, если ни одно из сочетаний не удовлетворяет условию задачи;
— возможность сохранения результатов работы в текстовом файле на жестком диске.
Последующие разделы будут посвящены решению поставленных задач и разработке приложения с вышеперечисленными функциями.
2. РАЗРАБОТКА АЛГОРИТМА ПРОГРАММЫ
В предыдущем разделе были сформулированы требования к разрабатываемой программе и к ее функциям. Анализируя требования к программе, можно разработать алгоритм разрабатываемого приложения.
Так, поскольку задание состоит в обработке числовой последовательности, целесообразно хранить числа в массиве. Таким образом, на этапе ввода данных пользователь должен будет задать длину вводимой последовательности и задать сами числа.
Согласно заданию необходимо будет выполнить перебор всех возможных сочетаний элементов. Поскольку число элементов в сочетании условием не задано, то должны будут перебраны все сочетания С1n, С2n,..., Сin, Сnn, для каждого из которых должны будут вычислены суммы. Известно, что />. Количество возможных сочетаний с каждым новым числом растет с довольно высокой скоростью. Поскольку задача учебная, то ограничим искусственно длину последовательности, к примеру, 20 числами. Таким образом, на этапе ввода следует контролировать введенное число n, и в случае когда N больше 20, то целесообразно уведомить пользователя об ограничениях, накладываемых на длину последовательности и запросить повторный ввод числа. Поскольку ошибка может быть неоднократной (умышленный или ошибочный ввод подряд нескольких некорректных значений), то целесообразно будет для ввода каждого числа организовать цикл, условием завершения которого будет корректно введенное значение. Для заполнения элементов массива можно использовать цикл с заданным числом повторений.
После ввода исходных данных необходимо осуществить поиск такого сочетания элементов, сумма которых делится на k без остатка. Для реализации этого поиска можно осуществить перебор всех возможных сочетаний и вычислять для каждого из них сумму элементов. Сочетания следует перебирать сначала по одному элементу, потом по два элемента, затем по три, и так далее, пока не будет найдено искомое сочетание или же пока не достигнем последнего сочетания, в которое входят все N элементов последовательности. --PAGE_BREAK--
Для реализации этого способа выделить следующие подзадачи:
Подзадача генерации сочетаний из заданного количества натуральных чисел от 1 до N. Существуют довольно простые методы генерации подобных сочетаний. В этом случае каждое из таких сгенерированных сочетаний будет задавать номера позиций элементов из исходной последовательности, которые следует взять для посчета суммы. Например, если было сгенерировано сочетание 2, 3 ,5. То оно задает набор из трех чисел исходной последовательности, которые стоят на 2, на 3 и на 5 месте в массиве целых чисел.
Подзадача вычисления суммы чисел в сочетании. То есть, следует извлечь числа с заданными номерами из исходного массива и определить их сумму.
Подзадачу 1 будем запускать в цикле от m=1 до n, где m будет задавать количество чисел в сочетании. После выполнения подзадачи 1 организуем цикл по всем сгенерированным сочетаниям и для каждого из них будем вычислять сумму при помощи подзадачи 2. Для вычисленной суммы будем определять остаток от деления на число k, и если он равен нулю, то искомый набор найден и задачу можно считать решенной.
Согласно заданию необходимо найти хотя бы одно такое сочетание чисел. Поскольку не стоит задачи в нахождении всех возможных сочетаний, то при обнаружении первой же суммы удовлетворяющей условию, процесс поиска можно завершать (можно выйти из цикла перебора сочетаний из из цикла по m) и останется только вывести соответствующее сообщение пользователю.
Для возможности анализа результатов работы целесообразно будет выводить все элементы сочетания и суммы на экран, а также сопровождать вывод на экран, сохранением результатов в текстовом файле на жестком диске.
Детальное описание разработанной программы, алгоритмов и их программной реализации приведено в последующих разделах. Схема алгоритма представлена в Приложении А.
3. ОПИСАНИЕ СТРУКТУРЫ ПРОГРАММЫ
3.1 Описание переменных
В разделе описаний программы осуществляется подключение модуля crt, который необходим для использования функции clrscr (очистка содержимого экрана вывода).
В разделе описания типов приведено два типа:
Arr = array[1..20] of integer; — будет использоваться для задания исходного массива;
Arr2=array[1..1000,0..20] of byte – будет использоваться для хранения сгенерированных сочетаний. Первая размерность будет задавать номер сочетания, а вторая – номера элементов в конкретном сочетании.
Также в разделе описаний переменных описаны переменные, назначение которых приведено в таблице 3.1.
Таблица 3.1– Описание переменных программы
Наименование
Тип
Назначение
N
integer
задается пользователем и хранит длину последовательности чисел
K
integer
переменная, которая задается пользователем и на которую должна делиться искомая сумма без остатка
Chisla
Arr
массив из 20 целых чисел. Массив (или его часть) заполняется пользователем и хранит обрабатываемую последовательность целых чисел
Idx
Arr
массив, в котором хранятся сгенерированные сочетания. Каждая строка задает отдельное сочетание (позиции элементов в массиве Chisla)
i, j
integer
временные переменные, необходимые для организации циклов при переборе элементов последовательности
m
integer
переменная, необходимая для организации цикла по количеству элементов в сочетании
kol
integer
переменная, которая хранит количество сочетаний, сгенерированных на текущем цикле по m
fnd
boolean
логическая переменная, которая используется как флаг, найдена ли искомая сумма (true— если найдена)
tf
text
переменная текстового файла, используется для сохранения результатов работы в текстовом файле
S
string
строковая переменная, используемая для формирования строки вывода с составленным сочетанием и суммой
St
string
вспомогательная строковая переменная, используемая в функциях преобразования целых чисел в строку
3.2 Описание вспомогательных процедур и функций
В программе приведено описание одной вспомогательной процедуры и одной функции.
Процедура Info(var ft:TEXT) предназначена для вывода вспомогательной информации о программе и о задании на курсовую работу. Следует заметить, что процедура дублирует вывод информации на экран монитора и в текстовый файл с результатами выполнения программы. При этом, параметр ft:TEXT как раз и задает файл, в который осуществляется вывод. Условием применения данной процедуры является то, что перед вызовом процедуры файловой переменной ft должно быть назначено имя физического файла на жестком диске при помощи процедуры ASSIGN. Кроме того, файл предварительно должен быть открытым для записи при помощи функции REWRITE. Текст процедуры приведен в строках 15-35.
Процедура GenerateSochet(var Sochet:Arr2;n,m:integer;var kol:integer) предназначена для генерации сочетаний из n натуральныхчисел от 1 до N по m. Сгенерированные последовательности будут возвращаться через параметр Sochet. Параметр N задает количество чисел из которых следует выбирать сочетания. Параметр M задает по сколько чисел участвует в одном сочетании. Через параметр KOL будет возвращено общее количество сгенерированных сочетаний. То есть в выходном массиве Sochet следует просмотреть строки от 1 до KOL это и будут сочетания, причем в каждой строке следует анализировать только элементы от 1 до m. Алгоритм генерации сочетаний приведен на рисунке А.1 приложения А. Код процедуры приведен в строках 49 -70 приложения Б.
Генерация сочетаний выполняется по следующему правилу:
Начальное сочетание образует последовательность 1, 2,… m, а последнее n-m+1,…,n.
Переход к следующему сочетанию осуществляется по следующему правилу: требуется просмотреть текущее сочетание с конца и найти элемент, который можно увеличить. То есть такой элемент что Sochet[kol,i] n-m+i. Далее увеличиваем этот элемент на 1, а оставшуюся часть сочетания заполняем числами натурального ряда большими измененного элемента в порядке их следования.
Функция Summ(Chisla:Arr;Idxs:Arr2;m,nom:integer):integer предназначена для определения суммы чисел соответствующего сочетания, где:
Chisla – масив исходных чисел, которые будут суммироваться;
Idxs – массив сгенерированных сочетаний (содержит только номера позиций);
M – количество элементов в сочетании;
NOM – номер сочетания из массива Idxs, сумму которого нужно найти.
В функции будет анализироваться строка NOM массива Idxs, точнее не вся строка, а только первые M элементов. Эти элементы задают номера чисел в массиве Chsila, которые нужно просуммировать.
Алгоритм выполнения описанных действий приведен на рисунке А.2 приложения А, а код функции приведен в строках 36-48 приложения Б.
3.3 Алгоритм основной программы
Алгоритм выполнения основного тела программы и основных функций приведен на рисунке А.3 в приложении А. Так в процедуре в первую очередь осуществляется очистка экрана инициализация файловой переменной и открытие текстового файла «sochet.res» для записи результатов. Затем производится вывод информации о задании курсовой работы на экран и в файл результатов при помощи вызова процедуры INFO. После этого осуществляется ввод исходных данных, а именно: числа элементов последовательности N и самой последовательности чисел. Ввод исходных данных организован в строках 76-85 листинга в приложении Б. После ввода исходных данных организуется цикл по m (по количеству элементов в сочетании). В теле этого цикла выполняются действия:
— генерируются все возможные сочетания по m натуральных элементов 1… N при помощи процедуры GenerateSochet;
— организуется цикл по i, в котором перебираются все из сгенерированных на предыдущем этапе сочетания и выполняются действия:
— вывод на экран и вфайл элементов сочетания (цикл по j в строках 95-99);
— вычисление суммы при помощи функции SUMM (строка 100); продолжение
--PAGE_BREAK--
— проверка полученой суммы на деление на K (остаток от деления определяется при помощи оператора MOD), (строки 103-113);
Для преобразования целого числа в строку используется процедура STR(a;var S:string), где a задает целое число, а через параметр S возвращается строковое значение. Если сумма Sm удовлетворяет условию и искомое сочетание чисел найдено, устанавливается флаг fnd и осуществляется выход из цикла. В конце программы анализируется значение флага fnd, и если флаг установлен в false, то значит, не была найдена последовательность, удовлетворяющая условию, о чем выводится соответствующее сообщение на экран и в текстовый файл.
4. ИНСТРУКЦИЯ ОПЕРАТОРУ
Разработанная программа представляет собой исполняемый файл SOCHET.EXE размером 8096 байт. В программе выполняется обработка числовой последовательности.
После запуска программы появляется окно, изображенное на рисунке 4.1.
/>
Рисунок 4.1 – Главное окно программы
После этого пользователь может вести длину последовательности. На рисунке 4.2 задан пример реакции программы в случае ошибочного набора.
/>
Рисунок 4.2 – Реакция программы на ошибочный ввод количества N
После корректного ввода длины последовательности пользователь может задать саму последовательность целых чисел.
После корректного ввода программа выполняет перебор всех сочетаний. На рисунке 4.3 показан пример выполнения программы, а содержимое файла sochet.resприведен в приложении В.
/>
Рисунок 4.3– Результат работы программы
На рисунке 4.4 приведен пример выполнения программы, когда среди всех сочетаний не было найдено ни одного, удовлетворяющего условию задачи.
/>
Рисунок 4.4 – Результат работы программы (поиск неудачен)
Функционирование программы полностью соответствует заданию.
ВЫВОДЫ
Данная курсовая работа была выполнена в полном соответствии поставленному заданию и отлажена в среде Turbo Pascal 7.0. В ходе выполнения курсовой работы была разработана программа для обработки числовой последовательности. В результате выполнения данной курсовой работы, я убедилась в широких возможностях языка программирования Turbo Pascal, закрепила практические навыки программирования в cреде Turbo Pascal.
ПЕРЕЧЕНЬ ССЫЛОК
Зуев Е.А. Программирование на языке Turbo Pascal 6.0,7.0. – М.: Радио и связь, Веста, 1993.
Фаронов В.В. Turbo Pascal 7.0. Начальный курс. — М.: Нолидж, 2000.
Йенсен К., Вирт Н. Паскаль. Руководство для пользователя и описание языка. — М.: «Финансы и статистика», 1982. — С. 151.
Вирт Н. Алгоритмы+структуры данных= программы. — М.: «Мир», 1985. — С. 406.
Грогоно П. Программирование на языке Паскаль. — М.: «Мир», 1982. — С. 384.
Перминов О. Н. Язык программирования Паскаль: Справочник. — М.: «Радио и связь», 1989. — С. 128. — ISBN 5-256-00311-9
Культин Н.Б. Delphi 6. Программирование на Object Pascal. — СПб.: «БХВ-Петербург», 2001. — С. 528. — ISBN 5-94157-112-7
8. Моргун А. Н. Программирование на языке Паскаль (Pascal). Основы обработки структур данных. — М.: «Диалектика», 2005. — С. 576. — ISBN 5‐8459‐0935‐X
9. Гранпер Ж., Коттэ Р. Трехмерная графика на Турбо-Паскале
10. Белецкий Я. Турбо-Паскаль с графикой для ПК.- М.: Машиностроение, 1991. — 320 с.
11. Бородич Ю.С. и др. Паскаль для ПК: Справочное пособие. – МН.: Высш. Шк.: БФ ГИТМП «НИКА», 1991. – 365 с.
12. Зуев Е.А. Язык программирования Turbo Pascal 6.0. – М.: Унитех, 1992. – 298 с.
13.Фаронов В.В. Турбо-Паскаль (в 3 книгах). — М.: «МВТУ-ФЕСТО ДИДАКТИК», 1992-1993.
/>ПРИЛОЖЕНИЕ А
Алгоритм программы
/>
Рисунок А.1 – Алгоритм процедуры генерации сочетаний GenerateSochet
/>
Рисунок А.2 – Алгоритм функции определения суммы SUMM
/>
Рисунок А.3 – Алгоритм выполнения тела программы
ПРИЛОЖЕНИЕ Б
Листинг программы
unit Unit1;
program sochet;
uses crt;
type
Arr = array[1..20] of integer;
Arr2=array[1..1000,0..20] of byte;
var
i,j,m,n,k,kol:integer;
Sm: integer;
Idx: Arr2;
Chisla: Arr;
fnd: boolean;
tf:TEXT;
S,St:string;
Procedure Info(var ft:TEXT);
begin
writeln('************************************************************');
writeln('**** КУРСОВАЯ РАБОТА ПО ПРОГРАММИРОВАНИЮ ****');
writeln('** **');
writeln('** Задана последовательность из nчисел **');
writeln('** Выбрать в последовательности несколько таких чисел, **');
writeln('** чтобы их сумма делилась на m. **');
writeln('**** ****');
writeln('************************************************************');
writeln;
writeln(ft,'************************************************************');
writeln(ft,'**** КУРСОВАЯ РАБОТА ПО ПРОГРАММИРОВАНИЮ ****');
writeln(ft,'** **');
writeln(ft,'** Задана последовательность из nчисел **');
writeln(ft,'** Выбрать в последовательности несколько таких чисел, **');
writeln(ft,'** чтобы их сумма делилась на m. **');
writeln(ft,'**** ****');
writeln(ft,'************************************************************');
writeln(ft,''); продолжение
--PAGE_BREAK--
end;
{процедура суммирует числа с номерами, которые заданы в строке nomмассива Idxs}
Function Summ(Chisla:Arr;Idxs:Arr2;m,nom:integer):integer;
var
idx,i,Sm:integer;
begin
Sm:=0;
for i:=1 to m do
begin
idx:= Idxs[nom,i];
Sm:=Sm + Chisla[idx];
end;
Summ:=Sm;
end;
{процедура генерации сочетания из nпо m, для чисел 1,2,…, n}
Procedure GenerateSochet(var Sochet:Arr2; n,m:integer;var kol:integer);
var
ii,jj:integer;
begin
kol:=1;
{ Генерация самого первого сочетания }
for ii:=0 to m do
Sochet[kol,ii]:=ii;
repeat
{ Vivod(Sochet,nom,m);}
kol := kol+1;
for ii:=0 to m do
Sochet[kol,ii]:=Sochet[kol-1,ii];
ii:=m;
while (Sochet[kol,ii]=(n-m+ii))and(ii>0) do
ii:=ii-1; { поиск элемента для изменения }
Sochet[kol,ii]:=Sochet[kol,ii]+1;
for jj:=ii+1 to m do
Sochet[kol,jj]:=Sochet[kol,jj-1]+1; { изменение правой части сочетания }
until ii=0;
end;
begin
clrscr;
assign(tf,'sochet.res');
rewrite(tf);
INFO(tf);
write('Задайте количество чисел n:'); readln(n);
while (n20) do
begin
write('Ошибочный ввод! Задайте количество чисел n(n>0;n
readln(n);
end;
write('Задайте числа :');
for i:=1 to n do
read(Chisla[i]);
write('Задайте k(на него должна делиться сумма без остатка) :'); readln(k);
fnd:=false;
for m:=1 to n do
begin
GenerateSochet(Idx,n,m,kol);
Writeln(' * * * Перебор сочетаний по ',M,' элементов! * * *');
Writeln(tf,' * * * Перебор сочетаний по ',M,' элементов! * * *');
for i:=1 to kol-1 do
begin
S:='';
for j:=1 to m do
begin
Str(Chisla[Idx[i,j]],St);
S := S + St + ' ';
end;
Sm := Summ(Chisla,Idx,m,i);
Str(Sm,St);
S:= S + ' Sum = '+St;
if (Sm mod k) = 0 then
begin
S:=S+ ' Искомая пара!';
writeln(S);
writeln(tf,S);
fnd := true;
break;
end else begin
writeln(S);
writeln(tf,S);
end;
end;
if fnd then break; продолжение
--PAGE_BREAK--
end;
if fnd then begin
writeln('Искомая комбинация найдена!');
writeln(tf,'Искомая комбинация найдена!')
end else begin
writeln('Искомая комбинация чисел НЕ найдена!');
writeln(tf,'Искомая комбинация чисел НЕ найдена!');
end;
Close(tf);
readln;
end.
/>ПРИЛОЖЕНИЕ В
Пример выполнения программы (поиск удачен)
************************************************************
**** КУРСОВАЯ РАБОТА ПО ПРОГРАММИРОВАНИЮ ****
** **
** Задана последовательность из n чисел **
** Выбрать в последовательности несколько таких чисел, **
** чтобы их сумма делилась на m. **
**** ****
************************************************************
* * * Перебор сочетаний по 1 элементов! * * *
2 Sum = 2
13 Sum = 13
27 Sum = 27
9 Sum = 9
8 Sum = 8
* * * Перебор сочетаний по 2 элементов! * * *
2 13 Sum = 15
2 27 Sum = 29
2 9 Sum = 11
2 8 Sum = 10
13 27 Sum = 40
13 9 Sum = 22
13 8 Sum = 21
27 9 Sum = 36
27 8 Sum = 35
9 8 Sum = 17
* * * Перебор сочетаний по 3 элементов! * * *
2 13 27 Sum = 42
2 13 9 Sum = 24
2 13 8 Sum = 23 Искомая пара!
Искомая комбинация найдена!
Пример выполнения программы (поиск неудачен)
************************************************************
**** КУРСОВАЯ РАБОТА ПО ПРОГРАММИРОВАНИЮ **
** **
** Задана последовательность из n чисел **
** Выбрать в последовательности несколько таких чисел, **
** чтобы их сумма делилась на m. **
**** ****
************************************************************
* * * Перебор сочетаний по 1 элементов! * * *
8 Sum = 8
9 Sum = 9
21 Sum = 21
5 Sum = 5
* * * Перебор сочетаний по 2 элементов! * * *
8 9 Sum = 17
8 21 Sum = 29
8 5 Sum = 13
9 21 Sum = 30
9 5 Sum = 14
21 5 Sum = 26
* * * Перебор сочетаний по 3 элементов! * * *
8 9 21 Sum = 38
8 9 5 Sum = 22
8 21 5 Sum = 34
9 21 5 Sum = 35
* * * Перебор сочетаний по 4 элементов! * * *
8 9 21 5 Sum = 43
Искомая комбинация чисел НЕ найдена!