Начальное сочетание образует последовательность 1, 2, .. m, а последнее n-m+1,…,n

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;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.

Перечень ссылок

1.  Зуев Е.А. Программирование на языке Turbo Pascal 6.0,7.0. – М.: Радио и связь, Веста, 1993.

2.     Фаронов В.В. Turbo Pascal 7.0. Начальный курс. - М.: Нолидж, 2000.

3.     Йенсен К., Вирт Н. Паскаль. Руководство для пользователя и описание языка. — М.: «Финансы и статистика», 1982. — С. 151.

4.     Вирт Н. Алгоритмы+структуры данных= программы. — М.: «Мир», 1985. — С. 406.

5.     Грогоно П. Программирование на языке Паскаль. — М.: «Мир», 1982. — С. 384.

6.     Перминов О. Н. Язык программирования Паскаль : Справочник. — М.: «Радио и связь», 1989. — С. 128. — ISBN 5-256-00311-9

7.     Культин Н.Б. 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 – Алгоритм выполнения тела программы

 

ПРИЛОЖЕНИЕ Б

Листинг программы

1.         unit Unit1;

2.         program sochet;

3.         uses crt;

4.         type

5.          Arr = array[1..20] of integer;

6.          Arr2=array[1..1000,0..20] of byte;

7.         var

8.          i,j,m,n,k,kol:integer;

9.          Sm : integer;

10.       Idx : Arr2;

11.       Chisla: Arr;

12.       fnd : boolean;

13.       tf:TEXT;

14.       S,St:string;

15.      Procedure Info(var ft:TEXT);

16.      begin

17.       writeln('**********************************************************');

18.       writeln('**** КУРСОВАЯ РАБОТА ПО ПРОГРАММИРОВАНИЮ ****');

19.       writeln('** **');

20.       writeln('** Задана последовательность из n чисел **');

21.       writeln('** Выбрать в последовательности несколько таких чисел, **');

22.       writeln('** чтобы их сумма делилась на m. **');

23.       writeln('**** ****');

24.       writeln('**********************************************************');

25.       writeln;

26.       writeln(ft,'********************************************************');

27.       writeln(ft,'**** КУРСОВАЯ РАБОТА ПО ПРОГРАММИРОВАНИЮ ****');

28.       writeln(ft,'** **');

29.       writeln(ft,'** Задана последовательность из n чисел **');

30.       writeln(ft,'** Выбрать в последовательности несколько таких чисел, **');

31.       writeln(ft,'** чтобы их сумма делилась на m. **');

32.       writeln(ft,'**** ****');

33.       writeln(ft,'********************************************************');

34.       writeln(ft,'');

35.      end;

36.      {процедура суммирует числа с номерами, которые заданы в строке nom массива Idxs}

37.      Function Summ(Chisla:Arr;Idxs:Arr2;m,nom:integer):integer;

38.      var

39.       idx,i,Sm:integer;

40.      begin

41.       Sm:=0;

42.       for i:=1 to m do

43.       begin

44.       idx:= Idxs[nom,i];

45.       Sm:=Sm + Chisla[idx];

46.       end;

47.       Summ:=Sm;

48.      end;

49.      {процедура генерации сочетания из n по m, для чисел 1,2, ... , n}

50.      Procedure GenerateSochet(var Sochet:Arr2; n,m:integer;var kol:integer);

51.      var

52.       ii,jj:integer;

53.      begin

54.       kol:=1;

55.       { Генерация самого первого сочетания }

56.       for ii:=0 to m do

57.       Sochet[kol,ii]:=ii;

58.       repeat

59.       { Vivod(Sochet,nom,m);}

60.       kol := kol+1;

61.       for ii:=0 to m do

62.       Sochet[kol,ii]:=Sochet[kol-1,ii];

63.       ii:=m;

64.       while (Sochet[kol,ii]=(n-m+ii))and(ii>0) do

65.       ii:=ii-1; { поиск элемента для изменения }

66.       Sochet[kol,ii]:=Sochet[kol,ii]+1;

67.       for jj:=ii+1 to m do

68.       Sochet[kol,jj]:=Sochet[kol,jj-1]+1; { изменение правой части сочетания }

69.       until ii=0;

70.      end;

71.      begin

72.       clrscr;

73.       assign(tf,'sochet.res');

74.       rewrite(tf);

75.       INFO(tf);

76.       write('Задайте количество чисел n :'); readln(n);

77.       while (n<1) or (n>20) do

78.       begin

79.       write('Ошибочный ввод! Задайте количество чисел n (n>0;n<21):');

80.       readln(n);

81.       end;

82.       write('Задайте числа :');

83.       for i:=1 to n do

84.       read(Chisla[i]);

85.       write('Задайте k (на него должна делиться сумма без остатка) :'); readln(k);

86.       fnd:=false;

87.       for m:=1 to n do

88.       begin

89.       GenerateSochet(Idx,n,m,kol);

90.       Writeln (' * * * Перебор сочетаний по ',M,' элементов! * * *');

91.       Writeln (tf,' * * * Перебор сочетаний по ',M,' элементов! * * *');

92.       for i:=1 to kol-1 do

93.       begin

94.       S:='';

95.       for j:=1 to m do

96.       begin

97.       Str(Chisla[Idx[i,j]],St);

98.       S := S + St + ' ';

99.       end;

100.     Sm := Summ(Chisla,Idx,m,i);

101.     Str(Sm,St);

102.     S:= S + ' Sum = '+St;

103.     if (Sm mod k) = 0 then

104.     begin

105.     S:=S+ ' Искомая пара!';

106.     writeln(S);

107.    writeln(tf,S);

108.     fnd := true;

109.     break;

110.     end else begin

111.     writeln(S);

112.     writeln(tf,S);

113.     end;

114.     end;

115.     if fnd then break;

116.     end;

117.     if fnd then begin

118.     writeln('Искомая комбинация найдена!');

119.     writeln(tf,'Искомая комбинация найдена!')

120.     end else begin

121.     writeln('Искомая комбинация чисел НЕ найдена!');

122.     writeln(tf,'Искомая комбинация чисел НЕ найдена!');

123.     end;

124.     Close(tf);

125.     readln;

126.    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

Искомая комбинация чисел НЕ найдена!