Забавная задачка из блога Джона Грэма-Камминга. Он пишет, что ему ее задали на вступительном экзамене на компьютерный факультет в Оксфорде в 1980-х.
Дана абстрактная машина, которая работает с памятью неограниченного размера. Память состоит из ячеек, пронумерованных от 0, и каждая ячейка содержит целое число. В начале работы программы содержимое всех ячеек неопределенно.
У машины есть три инструкции следующего вида:
Z n - обнулить ячейку n
I n - увеличить на 1 содержимое ячейки n
J n,m,стрелка - сравнить ячейки n и m, и если их содержимое различается, то прыгнуть на инструкцию, на которую указывает стрелка (вместо стрелки в тексте можно использовать метки или номера инструкций).
Программа состоит из последовательности инструкций (с метками/номерами). Программа останавливается, когда закончились инструкции. Например, следующая программа копирует в ячейку 0 содержимое ячейки 20 (предполагая, что оно больше нуля), а потом останавливается. Если в ячейке 20 лежит отрицательное число, она никогда не остановится.
Z 0
loop:
I 0
J 0, 20 -> loop
Задание: написать программу, которая складывает два числа. Перед запуском программы числа помещаются в ячейки 0 и 1. В конце работы программы сумма должна лежать в ячейке 2. Про числа известно, что они целые неотрицательные.
Эта задача не будет сложной для опытного программиста, но есть некоторые тонкости. Интересно также посмотреть, как ее можно сделать покороче. Я справился за 16 инструкций.
Несколько типичных ошибок:
1) не прочитали внимательно, что делает инструкция J
2) не работает, когда один из аргументов 0
3) не работает, когда оба аргумента 0