TUZ_7-06 Интерпретация программы на Fractran
7.06 Интерпретация программы на Fractran
Fractran – это язык программирования, который использует дробные числа для описания своих необычных программ.
Цель этого задания – реализовать интерпретатор языка Fractran. Чтобы интерпретировать программу на Fractran,
целое число
n умножается на дроби в данном состоянии, пока не будет получено целое число, что сигнализирует об окончании программы.
Первоначально состояние равно
n и обновляется на последующих шагах.
Например, предположим, что дано целое число n, равное 3,
программа, состоящая из дробей program = [(7, 3), (12, 7)],
и предельное количество итераций itera, равное 4.
Попробуем интерпретировать эту программу.
- Инициализируем нулем указатель i, который может принимать значения от 0 до itera – 1.
- Затем умножаем \(\frac{7}{3}\ на\ 3\), получаем \(\frac{21}{3}=7\) и сохраняем результат в temp.
Поскольку temp – целое число, сохраняем его в массив R и обновляем состояние state = temp = 7,
- начинаем выполнять программу program с самого начала, так как на предыдущем шаге было найдено целое число
- Увеличиваем i на единицу: i = 0 + 1 = 1. Начинаем с \(\frac{7}{3}\) и получаем \(temp\ =\ 7\times\frac{7}{3}\ =\ 16.33\) – дробное число,
- поэтому переходим к (12,7) – следующей дроби в программе program. Для \(\frac{12}{7}\) получаем \(temp\ =\ 7\times\frac{12}{7}\ =\ 12\)
- Теперь temp является целым числом, поэтому сохраняем его в R и state
- и снова переходим к началу программы, но уже с состоянием state = 12,
- Увеличиваем i на единицу. Теперь i = 2. Начинаем с \(\frac{7}{3}\) и получаем t\(temp\ =\ 12\times\frac{7}{3}\ =\ 28\).
- temp является целым числом, поэтому сохраняем его в R и state
- Увеличиваем i на единицу. Теперь i = 3. Опять переходим к началу программы и начинаем с \(\frac{7}{3}\).
- Получаем \(temp\ =\ 28\times\frac{7}{3}\ =\ 65.33\) – дробное число,
- поэтому переходим к \(\frac{12}{7}\)– следующей дроби в программе program.
Для \(\frac{12}{7}\) получаем \(temp\ =\ 28\times\frac{12}{7}\ =\ 48\).
- temp является целым числом, поэтому сохраняем его в R и state.
- Теперь i = itera – 1, и это означает, что все итерации выполнены и в R находится результат интерпретации.
Ваша задача: написать функцию, которая принимает положительное целое число
n, массив дробей и число итераций
и возвращает массив целых чисел, созданных программой на Fractran.
В табл. 7.6 показаны ожидаемые результаты для некоторых входных данных.
| Таблица 7.6. Некоторые ожидаемые результаты для задачи интерпретации программы на Fractran |
| n, program, itera |
Ожидаемый результат |
6
(228, 131), (327, 158), (161, 394), (77, 425)
4 |
6 |
2
(345, 162), (108, 125), (90, 45), (293, 277)
5 |
2, 4, 8, 16, 32, 64 |
10
(1, 145), (7, 349), (156, 24)
5 |
10, 65 |