?

Log in

No account? Create an account
сложить два числа (программистское) - Поклонник деепричастий [entries|archive|friends|userinfo]
Anatoly Vorobey

[ website | Website ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Links
[Links:| English-language weblog ]

сложить два числа (программистское) [май. 12, 2015|05:19 pm]
Anatoly Vorobey
[Tags|, ]

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

Но уже в комментах есть несколько правильных версий, в том числе короче моей (я теперь понимаю, что несколько перестраховался в своем дизайне).
СсылкаОтветить

Comments:
Страница 1 из 3
<<[1] [2] [3] >>
[User Picture]From: n_r_dreams
2015-05-12 02:49 pm
//кто что, а тестировщик как всегда...
«Если в ячейке 20 лежит отрицательное число, она никогда не остановится.»
Простите, но неположительное, а не отрицательное.
(Ответить) (Thread)
[User Picture]From: paracloud
2015-05-12 02:52 pm
Интересно, что там за тонкости и какое решение в 16 инструкций.
У меня получилось 7 инструкций (три чтобы положить в ячейку 2 копию 0, используя пример выше, четыре чтобы добавить туда же столько инкрементов, сколько задано яцейкой 1, используя память 3 как дополнительный счётчик:

Z 2
loop_0:
I 2
J 2, 0 -> loop_0
Z 3
loop_1:
I 2
I 3
J 3, 1 -> loop_1
(Ответить) (Thread)
[User Picture]From: sleeping_death
2015-05-12 02:54 pm
не-а. ноль?
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: sleeping_death
2015-05-12 02:52 pm
Z 2
Z 3
J 0,3, XZero
L1:
I 2
J 0,2,L1
XZero:
J 1,3,YZero
L2:
I 2
I 3
J 1,3,L2
YZero:
(Ответить) (Thread)
[User Picture]From: meshko
2015-05-12 03:09 pm
J 0,3, XZero

перейдет если первое число не 0 и мы его не прибавим
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: unbe
2015-05-12 02:54 pm
Z 2
J 2, 0 -> loop2:
loop1:
I 2
J 2, 0 -> loop1
Z 3
J 3, 1 -> end
loop2:
I 2
I 3
J 3, 1 -> loop2
end:
(Ответить) (Thread)
[User Picture]From: unbe
2015-05-12 02:57 pm
баги %)
У sleeping_death выше идея та же, но багов меньше.
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: loqva
2015-05-12 02:55 pm

Z 2

Z 2
Z 3 // make a counter
J 0,2 ->add1 // Is @0 == 0?
loop: I 2
J 0,2 -> loop
// copied @0 to @2
add1: J 1 3->end // Is @1 ==0?
loop2: I 2
I 3
J 1,3 ->loop2
end: Z 3 // just the end label
(Ответить) (Thread)
[User Picture]From: gianthare
2015-05-12 02:59 pm
14 если не требовать команды на сетке end, иначе там можно поставить nop == J 0,0,end
Плюс одна запорченная ячейка номер 3

Z 2
Z3
J 0,2 -> L0 // m_0 <> 0
J 1,2 -> L1 // m_1 <> 0
I 3
J 2,3 -> end // both are zero
L0: I 2 // copy m_0 to m_2
J 0,2,l0
J 1,3 -> L1 // m_1 <> 0
I 3
J 1,3 -> end // m_1 is zero
L1: I 2 // move m_1 to m_2 using m_3 as counter
I 3
J 1,3,l1
End:



Edited at 2015-05-12 15:15 (UTC)
(Ответить) (Thread)
[User Picture]From: avva
2015-05-12 03:16 pm
Команда на сетке end необходима, прыжок всегда на инструкцию.
Кажется, действительно сэкономил одну инструкцию по сравнению с моей версией, браво :)
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: dims12
2015-05-12 03:01 pm
У меня получилось так:

        Z 2
loop1:  I 2
        J 2, 0, loop1
loop2:  Z 3
        I 2
        I 3
        J 1, 3, loop2

(Ответить) (Thread)
[User Picture]From: dims12
2015-05-12 03:07 pm
Да, ступил с нулями.
(Ответить) (Thread)
From: (Anonymous)
2015-05-12 03:12 pm

О нет, только не это.

Чтобы я после рабочего дня ещё этим занимался... Мои мозги это жалкая раздавленная работой лепёшка. Спать.
(Ответить) (Thread)
[User Picture]From: toshick
2015-05-12 03:15 pm
по-моему, многие не прочитали, что условие перехода - неравенство, а не равенство операндов
13 инструкций:

Z 2
Z 3 -- буфер цикла
Z 4
I 4 -- гарантированная единица для безусловного перехода

J 0 2 loop1 -- если X0 <> 0, идем суммировать
J 3 4 end1 -- иначе goto end1

Loop1:
I 2 -- поединично переносим X0 в ячейку 2
J 0 2 loop1 -- ячейка 2 - переменная цикла

end1:
J 1 3 loop2 -- если X1 <> 0, идем суммировать
J 3 4 end2 -- иначе goto end2

Loop2:
I 2 -- суммируем в ячейке 2
I 3 -- увеличиваем переменную цикла
J 1 3 loop2 -- ячейка 3 - переменная цикла
end2: -- все

update - ага, если переход возможен только на инструкцию, то добавляем еще одну бессмысленную I4 и получаем 14

Edited at 2015-05-12 15:24 (UTC)
(Ответить) (Thread)
[User Picture]From: dims12
2015-05-12 03:53 pm
Лично я прочитал, что делает инструкция, просто ступил, что инкремент один раз выполняется в любом случае
(Ответить) (Parent) (Thread)
[User Picture]From: gul_kiev
2015-05-12 03:22 pm
У меня получилось 13.
Ну или 14, если переход всегда должен быть на какую-то инструкцию.

Z 2
Z 4
I 4
J 2 0 l1
J 4 0 l2
l1:
I 2
J 2 0 l1
l2:
Z 3
J 3 1 l3
J 4 1 l4
l3:
I 2
I 3
J 3 1 l3
l4:
(Ответить) (Thread)
[User Picture]From: spamsink
2015-05-12 03:23 pm
Более интересной представляется следующая задачка:
Определить, чему равно неопределенное число в ячейке 0, занеся абсолютное значение в ячейку 1, а знак - в ячейку 2.
(Ответить) (Thread)
[User Picture]From: avva
2015-05-12 03:28 pm
Притом, что числа неограниченные, да?

Отличное задание! Я вижу в общих чертах, как... надо подумать и написать.
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: dims12
2015-05-12 03:23 pm
А вот так?

        Z 3
        Z 2
do2:    I 3
do1:    I 2
        J 2, 3, loop
        Z 3
        Z 2
loop:   J 0, 2, do1
        J 1, 2, do2


думаю...

(нифига)

Edited at 2015-05-12 15:52 (UTC)
(Ответить) (Thread)
[User Picture]From: gegmopo4
2015-05-12 03:25 pm
11.
    Z 2
    Z 3
    I 3
    J 2, 3 -> b
a:  I 2
b:  J 0, 2 -> a
    Z 4
    J 4, 3 -> d
c:  I 2
    I 4
d:  J 1, 4 -> c

Не ясно, можно ли изменить значения в ячейках 0 и 1. Если можно, возможно есть короче решение.
(Ответить) (Thread)
[User Picture]From: unbe
2015-05-12 03:32 pm
А вот это неплохо.
(Ответить) (Parent) (Thread)
[User Picture]From: n_r_dreams
2015-05-12 03:25 pm
Z 2
Z 3
J 0, 3 -> lbl2 //if [0]!=0
lbl1:
J 1, 3 -> lbl3 //if [1]!=0
I 3
J 1, 3 -> lbl4
lbl2:
I 2
J 0, 2 -> lbl2
J 3, 2 -> lbl1
lbl3:
I 2
I 3
J 1, 3 -> lbl3
lbl4:
Z 3

Тоже 14. Помогите найти контрпример, я не верю, что оно работает :)

Edited at 2015-05-12 15:27 (UTC)
(Ответить) (Thread)
Страница 1 из 3
<<[1] [2] [3] >>