Целью работы является практическое изучение процесса спецификации программы с помощью операционной семантики.

Лабораторная работа № 4. Операционная семантика

Цель работы

Целью работы является практическое изучение процесса спецификации программы с помощью операционной семантики.

Содержание отчета

Итоговым документом выполнения лабораторной работы является отчет, состоящий из следующих пунктов.

1. Титульный лист.

2. Цель работы.

3. Текст задания.

4. Решение задачи, представленное с помощью языка ПЯК.

5. Пример выполнения разработанной ПЯК-программы на SMS-машине с обоснованием выбора входных данных.

6. Выводы.

Теоретические сведения

1) абстракция вычислительной машины; 2) математические функции; 3) математическая логика.

Система переходов

Определение 1. Термины и условные обозначения системы переходов . 1) обозначает бинарное отношение на множестве , которое является…

Абстрактная машина

Синтаксис языка ПЯК

Команды

SMC-машина

Управляющий стек

Пример выполнения ПЯК-программы на SMC-машине

При этом

Переходы SMC-машины

Целочисленные выражения

Константа

Адрес(1) если

Составной оператор

Оператор(2) если

 

Логические выражения

Константа

Составной оператор

Оператор(2) если

 

Команды

Присваивание Присвоить(3) Ветвление

Варианты заданий

1. Даны целые числа m, n (0 < m ≤ 12, 0 ≤ n < 60), указывающие момент времени: «m часов, n минут». Определить наименьшее время (полных минут), которое должно пройти до того момента, когда часовая и минутная стрелки на циферблате совпадут.

2. Даны натуральное число a, натуральное число n. Вычислить .

3. Доказать, что любую целочисленную денежную сумму, большую 7 руб., можно выплатить без сдачи трешками и пятерками.

4. Для данного n > 7 найти такие целые неотрицательные a и b, что 3a + 5b = n.

5. Поле шахматной доски определяется парой натуральных чисел, каждое из которых не превосходит восьми: первое число – номер вертикали (счете слева направо), второе – номер по горизонтали (счете снизу вверх). Даны натуральные числа k, l, m, n, каждое из которых не превосходит восьми. Требуется выяснить, являются ли поля (k, l) и (m, n), полями одного цвета.

6. На поле (k, l) расположен ферзь. Угрожает ли он полю (m, n)?

7. На поле (k, l) расположен конь. Угрожает ли он полю (m, n)?

8. Выяснить, можно ли с поля (k, l) одним ходом ладьи попасть на поле (m, n). Если нет, то выяснить, как это можно сделать за два хода (поле, на которое приводит первый ход).

9. Выяснить, можно ли с поля (k, l) одним ходом слона попасть на поле (m, n). Если нет, то выяснить, как это можно сделать за два хода (поле, на которое приводит первый ход).

10. Выяснить, можно ли с поля (k, l) одним ходом ферзя попасть на поле (m, n). Если нет, то выяснить, как это можно сделать за два хода (поле, на которое приводит первый ход).

11. Дано натуральное число a. Вычислить f(a), если

12. Дано натуральное число a. Вычислить f(a), если

13. Дано натуральное число a. Вычислить f(a), если

14. Алгоритм Евклида нахождения наибольшего общего делителя (НОД) неотрицательных целых чисел основан на следующих свойствах этой величины. Пусть m и n – одновременно не равные нулю целые неотрицательные числа и пусть m ≥ n. Тогда, если n = 0, то НОД (n, m) = m, а если n ≠ 0, то для чисел m, n и r, где r – остаток от деления m на n, выполняется равенство НОД (m, n) = НОД (n, r). Например, НОД (5, 6) = НОД (6, 3) = НОД (3, 0) = 3. Даны натуральные числа n, m. Используя алгоритм Евклида, найти наибольший общий делитель n и m.

15. Даны натуральные числа n, m. Найти наименьшее общее кратное n и m.(Как здесь может помочь алгоритм Евклида ?).

16. Даны натуральные числа m и n. Найти такие натуральные p и q, не имеющие общих делителей, что p/q = m/n.

17. Пусть Дано натуральное число n. Получить .

18. Дано натуральное число n (n ≤ 9999). Является ли это число палиндромом с учетом четырех цифр, как, например, числа 2222, 6116, 0440 и т. д.?

19. Дано натуральное число n (n ≤ 9999). Верно ли, что это число содержит ровно три одинаковые цифры, как, например, числа 6676, 4544, 0006 и т. д.?

20. Дано натуральное число n (n ≤ 9999). Верно ли, что все четыре цифры числа различны?

21. Дано натуральное число x. Вычислить .

22. Дано натуральное число n. Вычислить .

23. Даны натуральные числа х, а, натуральное число n. Вычислить .

24. Даны натуральное число a, натуральное число n. Вычислить .

25. Даны натуральное число a, натуральное число n. Вычислить .

26. Дано натуральное число х. Вычислить .

27. Дано натуральное число а. Найти среди чисел первое, большее а.

28. Дано натуральное число а. Найти среди чисел такое наименьшее n, что .

29. Дано натуральное число n. Найти знакочередующуюся сумму цифр числа n (пусть запись n в десятичной системе есть ; найти ).

30. Даны натуральное число a, натуральное число n. Вычислить .