загадка в статье кнута
Я читаю сейчас старую статью Дональда Кнута про GO TO, и неожиданно наткнулся в ней на... загадку для читателей. Кнут обсуждает разные способы писать код, не используя go to, на примере следующей простой задачи: считать количество появлений каждого числа с помощью линейного поиска.
Предполагается, что у нас уже есть массивы A и B, которые проиндексированы от 1 до M. Все числа, что мы видели до сих пор, записаны в A, а в B - число раз, что мы видели каждое число. Теперь нам дают новое число X, и мы должны либо найти, где оно уже есть в A - простым проходом по всему массиву - и увеличить счетчик в B, или добавить его в конец A.
Самый привычный для Кнута код делает это с помощью goto, но Кнут обсуждает несколько способов сделать это с помощью тогда нового и модного структурного программирования без goto, и разные достоинства и недостатки этих способов. В частности, он приводит две версии на PL/1, см. картинку, и говорит следующее: "вариант (a) лучше, но он содержит пустой цикл - в теле цикла ничего не происходит; более естественным кажется вариант (b), и обычно люди находят именно его. Однако в (b) есть серьезный баг, который не сразу заметили. Можете ли вы найти его? Ответ на странице такой-то."
Попробуйте и вы найти баг в варианте (b). Он связан чисто с логикой кода, не с ошибками переполнения памяти, выходом за пределы массива, или чего-то такого. В качестве подсказки в комментариях я приведу эквивалентный этому коду отрывок на C (в котором будет тот же баг). Но тогда найти его намного легче, предупреждаю сразу.