• 

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



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

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

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

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

Другие популярные посты

 • 

#крп #свободу_стрелкову #максим_калашников Максим КалашниковМЫ И ОНИУ меня крайне тяжко на душе. Но говорить нынче буду сугубо рациональн...

2 комментария Источник