Главная | Обратная связь | Поможем написать вашу работу!

II. Программирование и структурирование блок-схем

Стр 1 из 6Следующая ⇒

ПРАКТИКУМ НА ЭВМ

МЕТОДИЧЕСКИЕ УКАЗАНИЯ И ЗАДАЧИ

ДЛЯ ПРОГРАММИРОВАНИЯ ПО ТЕМЕ:

«ОСНОВНЫЕ СТРУКТУРЫ УПРАВЛЕНИЯ»

№1

КАЗАНЬ – 2006

Кугураков В.С., Самитов Р.К., Кугуракова В.В. Практикум на ЭВМ. Методические указания и задачи для программирования по теме: «Основные структуры управления». – Казань: КГУ, 2006. – 39 с.

Пособие предназначено для студентов, обучающихся по специальности «Прикладная математика и информатика» и направлению «Информационные технологии», а также для преподавателей, ведущих практические занятия по информатике, алгоритмическим языкам и программированию. Учебный материал представлен задачами для программирования, которые рекомендуется использовать при изучении темы «Основные структуры управления».

Ó Казанский государственный университет, 2006 г.

Ó Кугураков В.С., Самитов Р.К., Кугуракова В.В.

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. (Выделение квадрата.) Для заданного целого вычислить k – наибольшее целое, при котором m делится на k ² без остатка.

6. (Выделение показателя и степени.) Для заданных целых чисел m, вычислить наибольшее целое k, при котором m делится без остатка на: а) ;б) .

7. (Наибольший общий делитель.) Вычислить d = НОД(m, n) – наибольший общий делитель натуральных чисел m и n, используя следующие соотношения:

(1) если , то НОД(m, n) = НОД(m–n, n);

(2) НОД(m, n) = НОД(n, m);

(3) НОД(n, 0) = n.

8. (Алгоритм Евклида.) В задаче 7 использовать вместо (1) следующее соотношение:

(1¢) если , то НОД(m, n) = НОД(r, n), где r – остаток от деления m на п.

9. (Степенной алгоритм.)

а) Вычислить у = xⁿ ( – целое число), используя следующее соотношения (сведение задачи к меньшему значению n):

	если n четно,
если n нечетно,

где z = x ², – целая часть числа , x ⁰ = 1.

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

10. (Вычисление "основания".) Для заданных целых и , вычислить, используя алгоритм из задачи 9:

а) наименьшее натуральное k, при котором ;

б) наибольшее целое k, при котором .

11. (Простое число.) Целое число , называется простым, если его натуральными делителями являются лишь 1 и само число p (в противном случае число p называется составным). Установить, является ли заданное число простым.

Указание: p – простое число тогда и только тогда, когда ни одно из целых чисел т, для которого , не является его делителем.

12. (Гипотеза Гольдбаха.) Согласно известной гипотезе любое четное число представимо в виде суммы двух простых чисел. Установить, подтверждается ли эта гипотеза для заданного четного числа m.

13. (Эллиптическое сравнение.) Целые числа a и b называются сравнимыми по модулю n, если их остатки при делении на n совпадают. Этот факт обозначается как a º b (mod n). Для заданных целого и a, b Î Z_m = {0,1,..., } установить, имеет ли сравнение (mod m) хотя бы одно решение в целых числах x, y Î Z_m, причем , если b = 0.

14. (Проще, чем Большая Теорема Ферма.) Для заданных целых m, найти n – число решений сравнения (mod m) в целых числах x, y, z Î Z_m = {0,1,..., m– 1}, x y . (Например, сравнение (mod 5) имеет 20 решений, одно из них: x = 3, y = 1, z = 1.)

15. (Совершенные и дружественные числа.)

а) Натуральное число n называется совершенным, если , где – сумма делителей числа n. (Например, 6 – совершенное число, так как 12=1+2+3+6.) Вычислить, сколько имеется совершенных чисел £ 1000000.

б) Натуральные числа a и b называются дружественными, если . Найти все пары (a, b) дружественных чисел, для которых a + b < n, где n – заданное число.

16. (Теорема Лагранжа.) Всякое неотрицательное целое число можно представить в виде суммы четырех квадратов. (Например, 7=1²+1²+1²+2².) Однако для некоторых чисел достаточно и меньшего числа квадратов. (Например, 4=2², 13=2²+3², 6=1²+1²+2².) Вычислить, сколько (минимально) квадратов требуется для указанного представления заданного числа n.

17. (Гипотеза Эйлера.) Леонард Эйлер предполагал, что диафантово уравнение не имеет решений в натуральных числах для любого показателя степени , если .

Опровергнуть данную гипотезу.

Подсказка. Попробуйте простым перебором найти решение уравнения . Решение сущствует! Попутно отметим, что имеется уникальный результат для s = 3, опровергающий гипотезу Эйлера:

422481⁴= 414560⁴+ 217519⁴+ 95800⁴.

II. ПРОГРАММИРОВАНИЕ И СТРУКТУРИРОВАНИЕ БЛОК-СХЕМ

Следующие блок-схемы с одним входом (H – начало) и одним выходом (K – конец), объявляются для данного раздела базисными:

Символы S, S ₁,... (называемые в дальнейшем операторами) служат для обозначения функциональных блоков , каждый из которых представляет некоторую последовательность действий (или вычислений) с одним входом и одним выходом. Символ В обозначает некоторое (логическое) условие, которое может как выполняться (+), так и не выполняться (–). Разветвление интерпретируется следующим образом: если условие В выполняется, то происходит переход на левую ветку, в противном случае – на правую. Стрелки (®) определяют последовательность выполнения операторов. Таким образом, каждая из блок-схем (1) – (5) однозначно определяет порядок выполнения операторов S, S ₁,... в зависимости от выполнения того или иного условия B.

Введем специальный язык для линейной записи блок-схем. Запись блок-схемы на таком языке будет называться программой. Для записи блок-схем (1) – (5) используются следующие конструкции (назовем их базисными операторами):

(1)	begin S₁;...; S_n end	(составной оператор)
(2)	if B then S₁ else S₂	(полный условный оператор)
(3)	if B then S	(неполный условный оператор)
(4)	while B do S	(оператор цикла ПОКА)
(5)	repeat S₁;...; S_n until B	(оператор цикла ПОВТОР)

Определение. Структурной блок-схемой называется любая из базисных блок-схем, а также любая блок-схема, которая может быть получена из структурной блок-схемы заменой некоторых из составляющих ее функциональных блоков на структурные блок-схемы. (Таким образом, программа структурной блок-схемы – это оператор вида (1) – (5), составные части S, S ₁,... которого являются операторами того же вида.)

Одно ограничение. Если S – оператор вида (2), то вместо (3) будем писать

(3')

if B then begin S end

Если такого ограничения не вводить, то существенно разным блок-схемам (6) и (7):

соответствовала бы одна и та же программа

if B₁ then if B₂ then S₁ else S₂.

Для записи неструктурных блок-схем введём дополнительное средство – оператор goto L (переход по стрелке), где L – метка, отмечающая оператор, на который осуществляется переход. Например, блок-схемы, изображенные на рис. 1, могут быть записаны как

1: S₁; if B then begin S₂; goto 1 end и

if B₁ then goto 2 else goto 3; 2: S; 3: if B₂ 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. (Блок-схемы программ.) Составить блок-схемы для заданных фрагментов программ:

a)	if B then begin S₁; if B₁ then begin S₂; S₃ end else ifB₂ thenS₄ end else ifB₃ then beginS₅; S₆; ifB₄ thenS₇ end;
б)	ifB then beginS₁; repeatS₂; S₃ untilB₁ end else ifB₁ thenS₃ elseS₄; ifB₂ then begin ifB₃ then beginS₁; S₂; S₃ end elseS₄; S₅ end else begin whileB₄ doS₆; ifB₅thenS₇; repeatS₈ untilB₆; S₉ end;
в)	whileB do ifB₁ then S₁; if B₂ then repeat S₁; S₂; S₃ untilB₃; ifB₄ then repeatS₄ until B₁ else if B₄ then S₅else whileB₅ do beginS₆; S₇; S₈; if B₆ then S₉ end.

5. (Структурирование программ.) Составить блок-схемы для заданных фрагментов программ. Полученные блок-схемы преобразовать в структурные и заново запрограммировать:

a)	5: if B₁ then begin S₁; S₂; S₃ end; 6: if B₂ then S₄ else goto 5; if B₃ then S₅ else if B₄ then S₆ else if B₅ then goto 6;
б)	2: if B₁ then begin if B₂ then S₁ else while B₃ do S₂; goto 1 end else if B₄ then S₃ else goto 2; 1: if B₃ then S₄ else S₅;
в)	2: S₁; if B₁ then begin S₂; if B₂ then repeat S₃; S₄ until B₃ else if B₄ begin S₅; S₆; S₇; S₈; end end else if B₇ then S₉ else S₁₀; 1: if B₆ then begin S₁₁; goto 1 end else begin while B₇ do S₁₂; goto 2 end; if B₈ then begin repeat S₁₃ until B₉; goto 1 end.

6. (Ограниченные инструментальные средства.) Показать, что любой из трех базисных операторов (2), (4) или (5) может быть выражен через два остальных, если дополнительно разрешено использовать составной оператор (1) и операторы присваивания следующего вида: x:=true и x:=false (или x:=0 и x:=1).

III. НЕБОЛЬШИЕ ПРОГРАММЫ

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

12 3 4 5 6 Следующая ⇒