Статья Автор: Лебедев Дмитрий

TUZ_7-06 Интерпретация программы на Fractran

TUZ_7-06 Интерпретация программы на Fractran

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

Алгоритм
Алгоритм интерпретации программы на Fractran использует дроби для генерации последовательности чисел.
Он принимает начальное число n и множество дробей program, умножает начальное число на каждую дробь (по очереди),
а затем проверяет, можно ли упростить результат до целого числа.
Если это возможно, то целое число добавляется в список и становится новым начальным числом для следующей итерации.
Процесс продолжается до тех пор, пока не будет выполнено определенное количество итераций
или пока не перестанут генерироваться целые числа.
Вот под робное описание шагов, выполняемых алгоритмом.
  1.  Принимаются три параметра: n, program и itera, где
    n – начальное значение, program – список дробей, представленных в виде кортежей (числитель, знаменатель),
    и itera – количество итераций.
  2.  Затем создается список result, в который помещается начальное значение n,
    и устанавливаются числитель numerator и знаменатель denominator равными n и 1 соответственно.
  3.  Далее запускается цикл, выполняющий itera итераций, а внутри этого цикла запускается еще один цикл,
    перебирающий дроби в списке program.
  4.   Для каждой дроби алгоритм умножает числитель numerator на первое число в дроби
    и знаменатель denominator на второе число в дроби.
  5.  После этого вычисляется наибольший общий делитель (НОД) для получившихся
    числителя и знаменателя вызовом функции и числитель со знаменателем делятся на НОД (чтобы упростить дробь).
  6.  Если получившийся знаменатель равен 1, то алгоритм добавляет числитель в список результатов result
    (потому что это целое число), обновляет числитель и знаменатель до уменьшенных значений и выходит из внутреннего цикла.
  7. После того как внешний цикл выполнит заданное количество итераций, алгоритм возвращает список сгенерированных значений.


Пропустить Навигационные Ссылки.
Чтобы оставить комментарий нужна авторизация
Печать