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

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 в приложении А. Так в процедуре в первую очередь осуществляется очистка экрана инициализация файловой переменной и открытие текстового файла «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

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

Страницы: 1, 2