Задачка для собеседования

[Peter Almazov]

Совпадает с моим.

Хотя нет, поспешил. Строго говоря, мой вариант был такой: "все отличия распечатаны".
Речь идет об интервалах [0,i) и [0,j)

[Valery Solovey]

Так и нормальный инвариант же. Почему он не устраивает?

[Peter Almazov]

Вот не нравится чем-то.
Непонятно, по какому закону расширять интервалы.

[albobin]

Если обозначить j(i) как j при котором b[ j ]=a[ i ], то
для  i=0   j<=j(0)
для i>0   j(i-1)<j<=j(i)
Собственно это же сойдёт и за инвариант.

Можно играть и с таким инвариантом  a[ i ]=b[ j ] , даже тот цикл от Trurl, если интерпретировать его как "два в одном", рассматривая итерацию по i как "главную" 
Вообщем как-то так, особо не гоняясь за строгостью (лень)

PS. борьба с курсивом

[trurl]

Так и нормальный инвариант же. Почему он не устраивает?

А какая от него польза?

[Valery Solovey]

Вот не нравится чем-то.
Непонятно, по какому закону расширять интервалы.

То есть, непонятно, как двигаться вперёд? У нас есть два непересекающихся множества элементов. Элементы одного множества - это поддиапазоны чисел, одинаковых в обоих массивах, а элементы другого множества - это поддиапазоны чисел из второго массива, не встречающиеся в первом. Поддиапазоны непрерывны и максимальны.
Можно считать, что у нас последовательность (или массив) чередующихся элементов из обоих множеств. И инвариант говорит нам, что все элементы слева от курсора обработаны. Только обработка зависит от типа элемента, тогда как в обычном массиве обработка однородна.
Обработка элемента из первого множества заключается в его пропуске (и это делается в первой части цикла), а обработка элемента второго множества - вывод его на печать.

[Valery Solovey]

А какая от него польза?

Не очень понимаю. Польза от инвариантов? Применительно к чему?

[Peter Almazov]

Так и нормальный инвариант же. Почему он не устраивает?

А какая от него польза?

Как говорил Info21: "Всегда вспоминаю Зинаиду Гиппиус."

[Geniepro]

А какая от него польза?

Не очень понимаю. Польза от инвариантов? Применительно к чему?

Инвариант цикла должен помогать правильному построению цикла, иначе, следуя принципу бритвы Оккама, этот инвариант нинужен!

[DIzer]

А какая от него польза?

Не очень понимаю. Польза от инвариантов? Применительно к чему?

Инвариант цикла должен помогать правильному построению цикла, иначе, следуя принципу бритвы Оккама, этот инвариант нинужен!

Geniepro, проблема не в этом... а в том,  что в силу недонозначности инварианта помноженной неоднозначность алгоритма, которая, в свою очередь помножается  на различия в восприятии и некоторую субьективность  понятия "нужен"  (в данном контексте)   -  то что полезно для Петра может быть бесполезно для Вас (и наоборот).

[DIzer]

Например , Петр  утверждает что априори полезен... и поэтому на каждый чих .. ПЫТАЕТСЯ его отыскать - как результат  он больше времени анализирует задачу (как следствие лучше ее понимает) и его навыки в этом анализе совершенствуются (с определенной степенью эффективности).. и как следствие -  частота сделанных им ошибок  меньше.. То есть что мы имеем.. - несомненную пользу.. даже в том случае если метода полное г. (эффект плацебо).

[DIzer]

А вот, Geniepro, пример случая когда эта метода БЕЗУСЛОВНО ПО ФАКТУ  ВРЕДНА - у меня таких 50% на группу -  когда текущая степень понимания человеком решаемой задачи не позволяет ему выделить последовательность действий (алгоритм). В этом случае - эта метода просто отвлекает его от того , что РЕАЛЬНО нужно делать. Как следствие - задача вовремя не решается , а самое паскудное то, что в него входит ощущение неуверенности в своих силах...

[Peter Almazov]

Вот не нравится чем-то.
Непонятно, по какому закону расширять интервалы.

Не нравится тем, что никак не отражает существенную несимметричность ролей массивов (а задача подло провоцирует на симметричность).
Более правильный вариант выглядит так. Обозначим массивы как a и b, индексы - i и j.
Массив b  в некотором роде главный. Массив a – играет роль генератора эталонных символов. Полный инвариант выглядит так: "для обработанной области массива b напечатаны все отличия, и из генератора "выбраны" все символы, встретившиеся (в нужном порядке) в b".
Отсюда логично следует тело цикла.
Берем очередной необработанный символ из массива b. Если он не совпадает с текущим символом генератора, то печатаем его. Иначе "забираем" символ из генератора (продвигаем вперед i). Конец если. Расширяем обработанную область (продвигаем вперед j).

Я трактовал последний 0 в массиве "a" как конец работы генератора. Другие авторы, не нарушая условий задачи, трактовали его как обычный символ, который никогда не встретится внутри массива b.

[Peter Almazov]

Как говорил Info21: "Всегда вспоминаю Зинаиду Гиппиус."

Новые посетители могут не понять междусобойчика. "Если надо объяснять, то не надо объяснять".
З. Гиппиус.

[albobin]

По поводу инварианта a[ i ]=b[ j ] в двух словах.

Имеем в основе два  прохода по всем элементам массивов a[] и b[]
i:=0 ; while a[ i ] # 0 do i:=i+1 end
и
j:=0 ; while b[ j ] # 0 do j:=j+1 end

Все варианты решений - это организация тем или иным макаром  "переключений" с одного цикла на другой и обратно.
На каждый шаг по массиву a[] организуем не менее 1 шага по массиву b[] для восстановления инварианта (совпадение значений)
а вот в "процессе" восстановления инварианта как раз и происходит "полезная работа" в этой задаче