Ну, вот в этом примере есть два цикла. Соответственно, два инварианта цикла. Их я могу легко сформулировать. А вот рекурсия в этом смысле у меня всегда вызывает затруднения.
>Попробуйте сами прикинуть, что бы вы могли сделать, имея под рукой такой инструмент!
Ну, допустим, прикинули. Прониклись. Дальше-то что?
Путь до того, чтобы что-то попробовать самому, _по меньшей мере_, неприемлемо длинен.
>Только что бы там не было херни в духе «мы используем C# и уже только этим одним лучше 1С с их скриптовым языком и саповцев с ихними ABAP и Java» (для справки, Microsoft создали C# как свою собственную проприетарную версию Java).
Между прочим, это совсем не херня :)
А справок таких лучше не давайте, не надо.
Ну да, я счел очевидным, что новое значение (А) не может испортить других инвариантов.
В целом я ориентировался на синтез правильного алгоритма, а не анализ готового чужого. Последнее, конечно, гораздо геморойнее.
А автоматически — так вообще супер.
Не понял героизма авторов (в оригинале куча заумных формул).
Чтобы написать правильный вариант, достаточно элементарной аккуратности.
Обозначим последовательность элементов в стеке цифрами 1,2,3,4.
Тройки 1,2,3 и 2,3,4 удовлетворяют некоторому соотношению — инварианту. (Двойки тоже, но их опускаем).
Добавляем к стеку элемент 5. Пусть тройка на конце (3,4,5) не удовлетворяет инварианту, выясняем, что сливать надо 3 и 4, обозначим результат как А. Теперь содержимое стека 1,2, А,5. Тройка на конце (2, А,5) удовлетворяет инварианту. Но какого хрена считать, что 1,2, А теперь тоже удовлетворяет инварианту?? Ясно, что нужно ее теперь проверять.
Вы выбрали неудачный инвариант. В книге Вирта «Algorithms and Data Structures» www-old.oberon.ethz.ch/WirthPubl/AD.pdf (есть русский перевод www.ozon.ru/context/detail/id/4803785/ ) используется такой инвариант:
(Ak: 0 <= k < L: a[k] < T) & (Ak: R <= k < N: a[k] >= T)
Т.е., не a[L], а a[R] может быть равно T.
Тогда не требуется дополнительный анализ перед циклом:
L:=0;R:=N;
WHILE L < R DO
m:=(L+R) DIV 2;
IF a[m] < T THEN
L := m+1
ELSE
R := m
END
END
Скачайте демо-версию Спайдер, там ограничение 40 операций. Будет вам и критический путь и позднее расписание за секунду.
А так?
Есть еще один метод — выучить, наконец, законы де Моргана.
Ну, допустим, прикинули. Прониклись. Дальше-то что?
Путь до того, чтобы что-то попробовать самому, _по меньшей мере_, неприемлемо длинен.
Между прочим, это совсем не херня :)
А справок таких лучше не давайте, не надо.
В целом я ориентировался на синтез правильного алгоритма, а не анализ готового чужого. Последнее, конечно, гораздо геморойнее.
А автоматически — так вообще супер.
Чтобы написать правильный вариант, достаточно элементарной аккуратности.
Обозначим последовательность элементов в стеке цифрами 1,2,3,4.
Тройки 1,2,3 и 2,3,4 удовлетворяют некоторому соотношению — инварианту. (Двойки тоже, но их опускаем).
Добавляем к стеку элемент 5. Пусть тройка на конце (3,4,5) не удовлетворяет инварианту, выясняем, что сливать надо 3 и 4, обозначим результат как А. Теперь содержимое стека 1,2, А,5. Тройка на конце (2, А,5) удовлетворяет инварианту. Но какого хрена считать, что 1,2, А теперь тоже удовлетворяет инварианту?? Ясно, что нужно ее теперь проверять.
(Ak: 0 <= k < L: a[k] < T) & (Ak: R <= k < N: a[k] >= T)
Т.е., не a[L], а a[R] может быть равно T.
Тогда не требуется дополнительный анализ перед циклом:
L:=0;R:=N; WHILE L < R DO m:=(L+R) DIV 2; IF a[m] < T THEN L := m+1 ELSE R := m END ENDНадо бы подправить статью, но можно ли сделать это задним числом? А то вдруг какой-нибудь дубль появится.
Возможно, она поможет вам «корректно и элегантно написать его без напрягов» столько раз, сколько потребуется.