Обработка текстовых файлов (стр. 2 из 3)
Для реализации этого способа выделить следующие подзадачи:
1) Подзадача генерации сочетаний из заданного количества натуральных чисел от 1 до N. Существуют довольно простые методы генерации подобных сочетаний. В этом случае каждое из таких сгенерированных сочетаний будет задавать номера позиций элементов из исходной последовательности, которые следует взять для посчета суммы. Например, если было сгенерировано сочетание 2, 3 ,5. То оно задает набор из трех чисел исходной последовательности, которые стоят на 2, на 3 и на 5 месте в массиве целых чисел.
2) Подзадача вычисления суммы чисел в сочетании. То есть, следует извлечь числа с заданными номерами из исходного массива и определить их сумму.
Подзадачу 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(varft: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. Начальное сочетание образует последовательность 1, 2, .. m, а последнее n-m+1,…,n.
2. Переход к следующему сочетанию осуществляется по следующему правилу: требуется просмотреть текущее сочетание с конца и найти элемент, который можно увеличить. То есть такой элемент что 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);
- проверка полученной суммы на деление на K (остаток от деления определяется при помощи оператора MOD), (строки 103-113);
Для преобразования целого числа в строку используется процедура STR(a;varS:string), где a задает целое число, а через параметр S возвращается строковое значение.
Если сумма Smудовлетворяет условию и искомое сочетание чисел найдено, устанавливается флаг fnd и осуществляется выход из цикла.
В конце программы анализируется значение флага fnd , и если флаг установлен в false, то значит не была найдена последовательность, удовлетворяющая условию, о чем выводится соответствующее сообщение на экран и в текстовый файл.
Разработанная программа представляет собой исполняемый файл SOCHET.EXE размером 8096 байт. В программе выполняется обработка числовой последовательности.
После запуска программы появляется окно, изображенное на рисунке 4.1.
Рисунок 4.1 – Главное окно программы
После этого пользователь может вести длину последовательности. На рисунке 4.2 задан пример реакции программы в случае ошибочного набора.
Рисунок 4.2 – Реакция программы на ошибочный ввод количества N
После корректного ввода длины последовательности пользователь может задать саму последовательность целых чисел.
После корректного ввода программа выполняет перебор всех сочетаний. На рисунке 4.3 показан пример выполнения программы, а содержимое файла sochet.res приведен в приложении В.
Рисунок 4.3 – Результат работы программы