Anatoly Vorobey (avva) wrote,
Anatoly Vorobey
avva

Category:

сложить два числа (программистское)

Забавная задачка из блога Джона Грэма-Камминга. Он пишет, что ему ее задали на вступительном экзамене на компьютерный факультет
в Оксфорде в 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 инструкций.

Update: несколько типичных ошибок: 1) не прочитали внимательно, что делает инструкция J; 2) не работает, когда один из аргументов 0; 3) не работает, когда оба аргумента 0.

Но уже в комментах есть несколько правильных версий, в том числе короче моей (я теперь понимаю, что несколько перестраховался в своем дизайне).
Tags: задачка, программирование
Subscribe
  • Post a new comment

    Error

    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 125 comments
Previous
← Ctrl ← Alt
Next
Ctrl → Alt →
Previous
← Ctrl ← Alt
Next
Ctrl → Alt →