- •Практикум на эвм
- •Казань – 2006
- •Разработка алгоритмов. Графическое изображение (блок-схемы) и словесная запись алгоритмов
- •II. Программирование и структурирование блок-схем
- •If b1 then if b2 then s1 else s2.
- •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.
- •III. Небольшие программы
- •III.1. Последовательная структура управления
- •III.2. Условная структура управления
- •IV. Циклическая структура управления (без индексации)
- •IV.1. Однократные итерационные циклы
- •IV.2. Переход к кратным (вложенным) циклам
- •V. Управление потоками данных
- •Рекомендации по отработке основных приемов программирования
КАЗАНСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
Факультет вычислительной математики и кибернетики
Кафедра теоретической кибернетики
Практикум на эвм
МЕТОДИЧЕСКИЕ УКАЗАНИЯ И ЗАДАЧИ
ДЛЯ ПРОГРАММИРОВАНИЯ ПО ТЕМЕ:
«ОСНОВНЫЕ СТРУКТУРЫ УПРАВЛЕНИЯ»
№1
Казань – 2006
Кугураков В.С., Самитов Р.К., Кугуракова В.В. Практикум на ЭВМ. Методические указания и задачи для программирования по теме: «Основные структуры управления». – Казань: КГУ, 2006. – 39 с.
Пособие предназначено для студентов, обучающихся по специальности «Прикладная математика и информатика» и направлению «Информационные технологии», а также для преподавателей, ведущих практические занятия по информатике, алгоритмическим языкам и программированию. Учебный материал представлен задачами для программирования, которые рекомендуется использовать при изучении темы «Основные структуры управления».
Казанский государственный университет, 2006 г.
Кугураков В.С., Самитов Р.К., Кугуракова В.В.
Разработка алгоритмов. Графическое изображение (блок-схемы) и словесная запись алгоритмов
Для каждой из задач данного раздела требуется разработать алгоритм решения задачи. Следует рассмотреть различные способы записи алгоритмов. Используйте сначала блок-схемы – графический способ изображения алгоритмов. Разработайте собственный язык (жаргон) для словесного описания алгоритмов "по шагам". Для проверки правильности составленного алгоритма следует строить (если это несложно) трассировочные таблицы, "прокручивая" алгоритм на конкретных исходных данных и следя за изменением переменных. Хотя такими отладочными действиями нельзя доказать правильность алгоритма, они во многих случаях позволяют выявить ошибки в алгоритме.
1. (Умножение натуральных чисел.) Вычислить n = m k, используя операции сложения и а) вычитания; б) удваивания и деления пополам. (Операция div деления пополам определена следующим образом: r div 2=s, если r=2s или 2s+1.)
2. (Деление натуральных чисел.) Вычислить частное и остаток при делении m на n, используя операции сложения и вычитания.
3. (Возведение в степень.) Для заданных целых ивычислить , используя операции вычитания и умножения.
4. (Вычисление "показателя".) Для заданных целых m 1 и n 2 вычислить:
а) наименьшее целое k такое, что;
б) наибольшее целое k такое, что;
в) количество цифр в десятичной записи числа m.
5. (Выделение квадрата.) Для заданного целого вычислитьk – наибольшее целое, при котором m делится на k2 без остатка.
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. (Степенной алгоритм.)
а) Вычислить у = xn ( – целое число), используя следующее соотношения (сведение задачи к меньшему значению n):
-
если n четно,
если n нечетно,
где z = x2, – целая часть числа ,x0 = 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 Zm = {0,1,...,} установить, имеет ли сравнение (mod m) хотя бы одно решение в целых числах x, y Zm, причем , если b = 0.
14. (Проще, чем Большая Теорема Ферма.) Для заданных целых m, найти n – число решений сравнения (mod m) в целых числах x, y, z Zm = {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=12+12+12+22.) Однако для некоторых чисел достаточно и меньшего числа квадратов. (Например, 4=22, 13=22+32, 6=12+12+22.) Вычислить, сколько (минимально) квадратов требуется для указанного представления заданного числа n.
17. (Гипотеза Эйлера.) Леонард Эйлер предполагал, что диафантово уравнение не имеет решений в натуральных числах для любого показателя степени , если .
Опровергнуть данную гипотезу.
Подсказка. Попробуйте простым перебором найти решение уравнения . Решение сущствует! Попутно отметим, что имеется уникальный результат для s = 3, опровергающий гипотезу Эйлера:
4224814 = 4145604 + 2175194 + 958004.