II. Программирование и структурирование блок-схем
Стр 1 из 6Следующая ⇒ ПРАКТИКУМ НА ЭВМ
МЕТОДИЧЕСКИЕ УКАЗАНИЯ И ЗАДАЧИ ДЛЯ ПРОГРАММИРОВАНИЯ ПО ТЕМЕ: «ОСНОВНЫЕ СТРУКТУРЫ УПРАВЛЕНИЯ»
№1 КАЗАНЬ – 2006
Кугураков В.С., Самитов Р.К., Кугуракова В.В. Практикум на ЭВМ. Методические указания и задачи для программирования по теме: «Основные структуры управления». – Казань: КГУ, 2006. – 39 с.
Пособие предназначено для студентов, обучающихся по специальности «Прикладная математика и информатика» и направлению «Информационные технологии», а также для преподавателей, ведущих практические занятия по информатике, алгоритмическим языкам и программированию. Учебный материал представлен задачами для программирования, которые рекомендуется использовать при изучении темы «Основные структуры управления».
Ó Кугураков В.С., Самитов Р.К., Кугуракова В.В. I. РАЗРАБОТКА АЛГОРИТМОВ.
Для каждой из задач данного раздела требуется разработать алгоритм решения задачи. Следует рассмотреть различные способы записи алгоритмов. Используйте сначала блок-схемы – графический способ изображения алгоритмов. Разработайте собственный язык (жаргон) для словесного описания алгоритмов "по шагам". Для проверки правильности составленного алгоритма следует строить (если это несложно) трассировочные таблицы, "прокручивая" алгоритм на конкретных исходных данных и следя за изменением переменных. Хотя такими отладочными действиями нельзя доказать правильность алгоритма, они во многих случаях позволяют выявить ошибки в алгоритме. 1. (Умножение натуральных чисел.) Вычислить n = m × k, используя операции сложения и а) вычитания; б) удваивания и деления пополам. (Операция div деления пополам определена следующим образом: r div2 =s, если r= 2 s или 2 s+ 1.)
2. (Деление натуральных чисел.) Вычислить частное и остаток при делении m на n, используя операции сложения и вычитания. 3. (Возведение в степень.) Для заданных целых 4. (Вычисление "показателя".) Для заданных целых m ³ 1 и n ³ 2 вычислить: а) наименьшее целое k такое, что б) наибольшее целое k такое, что в) количество цифр в десятичной записи числа m. 5. (Выделение квадрата.) Для заданного целого 6. (Выделение показателя и степени.) Для заданных целых чисел m, 7. (Наибольший общий делитель.) Вычислить d = НОД(m, n) – наибольший общий делитель натуральных чисел m и n, используя следующие соотношения: (1) если (2) НОД(m, n) = НОД(n, m); (3) НОД(n, 0) = n. 8. (Алгоритм Евклида.) В задаче 7 использовать вместо (1) следующее соотношение: (1¢) если 9. (Степенной алгоритм.) а) Вычислить у = xn (
где z = x 2, б) "Прокрутить" данный алгоритм для нескольких значений n и построить соответствующие трассировочные таблицы. Доказать правильность этого алгоритма и сравнить его с алгоритмом, полученным для задачи 3, оценивая (приближенно) число используемых операций. 10. (Вычисление "основания".) Для заданных целых а) наименьшее натуральное k, при котором б) наибольшее целое k, при котором
11. (Простое число.) Целое число Указание: p – простое число тогда и только тогда, когда ни одно из целых чисел т, для которого 12. (Гипотеза Гольдбаха.) Согласно известной гипотезе любое четное число 13. (Эллиптическое сравнение.) Целые числа a и b называются сравнимыми по модулю n, если их остатки при делении на n совпадают. Этот факт обозначается как a º b (mod n). Для заданных целого 14. (Проще, чем Большая Теорема Ферма.) Для заданных целых m, 15. (Совершенные и дружественные числа.) а) Натуральное число n называется совершенным, если б) Натуральные числа a и b называются дружественными, если 16. (Теорема Лагранжа.) Всякое неотрицательное целое число можно представить в виде суммы четырех квадратов. (Например, 7=12+12+12+22.) Однако для некоторых чисел достаточно и меньшего числа квадратов. (Например, 4=22, 13=22+32, 6=12+12+22.) Вычислить, сколько (минимально) квадратов требуется для указанного представления заданного числа n. 17. (Гипотеза Эйлера.) Леонард Эйлер предполагал, что диафантово уравнение Опровергнуть данную гипотезу. Подсказка. Попробуйте простым перебором найти решение уравнения 4224814 = 4145604 + 2175194 + 958004. II. ПРОГРАММИРОВАНИЕ И СТРУКТУРИРОВАНИЕ БЛОК-СХЕМ
Следующие блок-схемы с одним входом (H – начало) и одним выходом (K – конец), объявляются для данного раздела базисными:
Введем специальный язык для линейной записи блок-схем. Запись блок-схемы на таком языке будет называться программой. Для записи блок-схем (1) – (5) используются следующие конструкции (назовем их базисными операторами):
Определение. Структурной блок-схемой называется любая из базисных блок-схем, а также любая блок-схема, которая может быть получена из структурной блок-схемы заменой некоторых из составляющих ее функциональных блоков на структурные блок-схемы. (Таким образом, программа структурной блок-схемы – это оператор вида (1) – (5), составные части S, S 1,... которого являются операторами того же вида.) Одно ограничение. Если S – оператор вида (2), то вместо (3) будем писать
Если такого ограничения не вводить, то существенно разным блок-схемам (6) и (7):
соответствовала бы одна и та же программа if B1 then if B2 then S1 else S2. Для записи неструктурных блок-схем введём дополнительное средство – оператор goto L (переход по стрелке), где L – метка, отмечающая оператор, на который осуществляется переход. Например, блок-схемы, изображенные на рис. 1, могут быть записаны как
1: S1; if B then begin S2; goto 1 end и if B1 then goto 2 else goto 3; 2: S; 3: if B2 then goto 2. Известно, что любая блок-схема с одним входом и одним выходом без зацикливаний и недостижимых операторов может быть структурирована, т.е. приведена к "эквивалентной" структурной форме, если согласиться на дублирование операторов и введение в блок-схему некоторых дополнительных операторов, вычисляющих "флажки". Например, блок-схемы на рис. 1 могут быть структурированы, как показано на рис. 2. 1. (Написание программ.) Написать программы по заданным блок-схемам (8) – 24) на стр. 10 и 11, используя: а) составные и условные операторы (схемы (8) – (15)); б) базисные операторы, т.е. составные, условные и цикла (схемы (16) – (21)); в) составные, условные операторы и операторы перехода (схемы (22) – (24)). 2. (Структурирование блок-схем.) Блок-схемы (25) – (30) на стр. 12 преобразовать в их структурные эквиваленты. 3. (Структурирование и программирование.) Написать программы для блок-схем (31) – (42) на стр. 12 – 13. Блок-схемы предварительно преобразовать в структурные. 4. (Блок-схемы программ.) Составить блок-схемы для заданных фрагментов программ:
5. (Структурирование программ.) Составить блок-схемы для заданных фрагментов программ. Полученные блок-схемы преобразовать в структурные и заново запрограммировать:
6. (Ограниченные инструментальные средства.) Показать, что любой из трех базисных операторов (2), (4) или (5) может быть выражен через два остальных, если дополнительно разрешено использовать составной оператор (1) и операторы присваивания следующего вида: x:=true и x:=false (или x:=0 и x:=1).
Для каждого из заданий этого раздела требуется написать программу вычисления некоторой величины по заданной формуле. Программу необходимо соответствующим образом оформить: предусмотреть определение констант и описание переменных; исходные данные определить вводом; результаты напечатать.
Читайте также: Алгоритмизация и программирование. Технологии программирования. Языки программирования высокого уровня. 1 страница Воспользуйтесь поиском по сайту: ![]() ©2015 - 2025 megalektsii.ru Все авторские права принадлежат авторам лекционных материалов. Обратная связь с нами...
|