2. Разработка алгоритма программы

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

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

Согласно заданию необходимо будет выполнить перебор всех возможных сочетаний элементов. Поскольку число элементов в сочетании условием не задано, то должны будут перебраны все сочетания С1n, С2n, Сin, Сnn, для каждого из которых должны будут вычислены суммы. Известно, что

Количество возможных сочетаний с каждым новым числом растет с довольно высокой скоростью. Поскольку задача учебная, то ограничим искусственно длину последовательности, к примеру, 20 числами. Таким образом, на этапе ввода следует контролировать введенное число n, и в случае когда N больше 20, то целесообразно уведомить пользователя об ограничениях, накладываемых на длину последовательности и запросить повторный ввод числа. Поскольку ошибка может быть неоднократной (умышленный или ошибочный ввод подряд нескольких некорректных значений), то целесообразно будет для ввода каждого числа организовать цикл, условием завершения которого будет корректно введенное значение. Для заполнения элементов массива можно использовать цикл с заданным числом повторений.

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

Для реализации этого способа выделить следующие подзадачи:

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(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 приложения Б.

Генерация сочетаний выполняется по следующем правилу:


Информация о работе «Обработка текстовых файлов»
Раздел: Информатика, программирование
Количество знаков с пробелами: 26318
Количество таблиц: 3
Количество изображений: 7

Похожие работы

Скачать
37399
0
0

... это особые объекты – бегунки. Нижние бегунки – правый и левый – отвечают за отступ основного текста от границ страницы, а верхний бегунок – за абзацный отступ. - 10 - 4. Текстовый процессор Microsoft Word. Microsoft Word – основа любого офиса и, пожалуй, самая нужная и популярная программа во всем Microsoft Office. Эта программа ...

Скачать
19063
0
0

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

Скачать
15589
0
0

... . Переключателем между режимами вставки и замены служит клавиша Ins. При вставке все последующие символы сдвигаются вправо. При замене текущий символ исчезает. Документы, создаваемые в редакторе MS-DOS Editor, можно сохранять в текстовых файлах, для этого следует пользоваться меню File Save. Меню File Save As... позволит сохранить файл под другим именем. Для очистки редактора и начала работы ...

Скачать
19336
5
4

... экране и требует сдвига (прокрутки) вверх-вниз или влево-вправо. В нижней части Главного окна Word 2003 находится строка состояния, на которую выводится информация о положении текстового курсора в документе и о текущем режиме работы [3, С. 5-6]. Создание оглавления, сносок и колонтитулов Оглавление представляет собой список заголовков документа. Оно используется для просмотра тем, обсуждаемых в ...

0 комментариев


Наверх