загадка в статье кнута

[avva]

Я читаю сейчас старую статью Дональда Кнута про GO TO, и неожиданно наткнулся в ней на... загадку для читателей. Кнут обсуждает разные способы писать код, не используя go to, на примере следующей простой задачи: считать количество появлений каждого числа с помощью линейного поиска.

Предполагается, что у нас уже есть массивы A и B, которые проиндексированы от 1 до M. Все числа, что мы видели до сих пор, записаны в A, а в B - число раз, что мы видели каждое число. Теперь нам дают новое число X, и мы должны либо найти, где оно уже есть в A - простым проходом по всему массиву - и увеличить счетчик в B, или добавить его в конец A.

Самый привычный для Кнута код делает это с помощью goto, но Кнут обсуждает несколько способов сделать это с помощью тогда нового и модного структурного программирования без goto, и разные достоинства и недостатки этих способов. В частности, он приводит две версии на PL/1, см. картинку, и говорит следующее: "вариант (a) лучше, но он содержит пустой цикл - в теле цикла ничего не происходит; более естественным кажется вариант (b), и обычно люди находят именно его. Однако в (b) есть серьезный баг, который не сразу заметили. Можете ли вы найти его? Ответ на странице такой-то."

Попробуйте и вы найти баг в варианте (b). Он связан чисто с логикой кода, не с ошибками переполнения памяти, выходом за пределы массива, или чего-то такого. В качестве подсказки в комментариях я приведу эквивалентный этому коду отрывок на C (в котором будет тот же баг). Но тогда найти его намного легче, предупреждаю сразу.

Comments

[avva]

Эквивалентный код на C:

found = 0;
for (i = 0; i <= M && found == 0; i++)
    if (A[i] == X) found = 1;
if (found == 0) {
    M = i; A[i] = X; B[i] = 0; 
}
B[i] = B[i] + 1;

[aklepatc]

Кажется, в варианте (b) I у нас не тот индекс, для которого A(I) = X, а следующий за ним.

В результате, последняя строчка увеличивает неправильный B(I).

И, да, вокруг нас гораздо больше людей, которые свободно читают на C, чем тех, кто читает на PL/1. Я PL/1 не трогал со студенческих лет.