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

P.S. Если кто знает ответ заранее - не светите, дайте догадаться другим.

незачёт. текст:

Пока ГСЧ.СлучайноеЧисло(0, 1) Цикл
КонецЦикла;


(0) это невозможно

(1) очевидно, что рано или поздно цикл закончится.

(2) чтоб программист 1С - да не смог алгоритмическую задачку решить?

Если ГСЧ.СлучайноеЧисло(0, 1) = 1 Тогда
 Пока Истина Цикл Сообщить("+"); КонецЦикла;
КонецЕсли;

Задачка гамно

(3) в каком месте это очевидно?

(5) ну хорошо, уточним условие задачи: нужно сказать, возможна ли ситуация, что программа зациклится, либо они всегда будет заканчивать свою работу

+(7) смущает (0, 1) - возьми (0, 4294967295)

(8) вводишь в код ГСЧ и от твоего "всегда" остаётся мокрое место

Требуется написать свой интерпретатор кода 1С?
С обработками всех стандартных функций?

(6) Нормальная задачка, чёйто гамно?

(11) нужно теоретически решить задачу, т.е. предложить принцип ее решения

(13) Задача не имеет решения

(8) это определить можно, и совсем легко с программистской точки зрения.

Задача не интересная, банальная. (главное не забыть про оператор "перейти")

(14) и (15) друг другу противоречат, помоему

(14) вы не прочитали p.s. или проигнорили его

Рез = Вопрос("Уйти в бесконечный цикл?", РежимДиалогаВопрос.ДаНет);
Если Рез = КодВозвратаДиалога.Да Тогда
Пока Истина Цикл
Сообщить("+");
КонецЦикла;
КонецЕсли;
Сообщить("++");

Анализировать каждую строку результата. Искать период. Если строки в некотором периоде повторяются, значит зациклилось.

нужно найти цикличные участки кода без выхода

(18) см уточнение в (8)

(17) Имхо, это очевидно любому мало мальски вменяемому человеку.

(20) а если и нет?

(22) если очевидно  - то значит и доказуемо?

(23) при определенных упрощениях тогда задача решаема.

а вообще я задачу решил!

любой код или исполнится или выподет по ошибке, даже зацикливание выпадет по ошибке нехватки памяти, все зависит только от времени :)

причём тут 1с ?

Ога один и тот же код в 50% случаев будет выполняться бесконечно, в 50% конечное время.
Наслаждайся:

Четное = Секунда(ТекущаяДата())%2;
Пока Четное Цикл
КонецЦикла;

(25) не всегда зацикливание приведет к нехватке памяти

(0) "Придумал задачку по 1С"
Казалось бы причем тут 1с с ее предметной ориентированностью?

(20) про обращение к процедурам и функция ОМ не забыл?

(27) с учетом уточнения (8) ответ - "программа иногда зациклится"

(26) да не причем. Просто для примера.

Выполнить("ПроцедураИзФайла")
Если процедура что-то сообщила пользователю - она конечная, если нет - бесконечная.
Ограничений на время исполнения не было =P

Какой идиот отменил в школах НВП^W^W^W высшее образование для программистов???

wiki:Проблема_остановки

(0) и при чем тут 1С?

(34) ну вот взяли и всем все рассказали.

(14) Имеет. Оно сложное, правда.
(15) Задача весьма неопределённая. Нужно интерпретировать кусок кода. Просто анализом условия не получиться. В условии цикла может быть переменная, значение которой будет меняться в теле цикла. Как тогда поступать? Интерпретировать весь цикл? Со всем богатством встроенных функций языка 1С?

(37) премия Филдса, считайте что у вас в кармане

(0) давно МС и гугл стали принимать на работу одинэсников?..

да, (35)

Пока ЗадолженностьПоЗарплате>0 Цикл
Задолженность = ПолучитьЗадолженностьПоЗарплате();
Сообщить(Задолженность);
КонецЦикла

Как программно определить есть ли тут решение? ;)

(38) год не тот, наверное.

(0) А при чем тут 1С?

(40) еще про рекурсию забыли....

Попытка - Исключение?))

(36) по ссылка написано, что решения нет

(45) я это знаю

(46) т.е. (4) - просто провокация?

(36) Написано же "Теорема. Анализатор не существует.".
В (2) тебе написали то же самое.
Ты что хотел-то?

(47) как и (0)

в чем конкретно заключается провокация я не понял.
если выведется сообщение без таймаута, то очевидно что обработка никогда не завершит свою работу.
с другой стороны если в процедуре нет ни одного цикла, то можно точно сказать, что она не зациклится
неинтересно...

(50) А GoTo?

(50) провокация в том, что существуют дискретные задачи, которые не решаются алгоритмически. Помоему, это прикольный факт.

+(51) Плюс кто знает, что зацепит наш код, возможно какое-нить событие справочника ПередЗаписью например, в котором будет неявный цикл.

(51) да кто в 1С ей пользуется

(54) а рекурсия?

Как вариант, есть способ определить, будет выполнена или нет за заданный интервал времени:
1. Забудем про метки и Перейти.
2. Определяем свою переменную с временем окончания ожидания (ВыполнятьДо = ТекущаяДата() + Nсекунд).
3. Модифицируем код процедуры:
Перед "КонецЦикла" и "Продолжить" вставляем (СтрЗаменить) сравнение "Если ТекущаяДата() > ВыполнятьДо Тогда ВызватьИсключение "Не дождались"; КонецЕсли;"
3. Используем Выполнить(ТекстМодифицированнойПроцедуры), и ловим исключения.

(34) на самом деле есть и другой подход к решению сабжа

1. Анализатор может выявить ЧАСТЬ мест приводящих к зацикливанию.
2. Анализатор может проверить теоретическую достижимость участка кода.
3. Зная что отдельные участки кода достижимы и могут приводить к зацикливанию можно однозначно отнести часть процедур к однозначно "зацикливающимся".
4. Все остальные анализируемые процедуры будут оперировать вероятностями
5. Чем лучше анализатор справляется с пунктами 1 и 2 тем меньше вероятность его ошибки.

примерно по такому принцепу работают эвристические антивирусы....

Предлагаю написать все на ВЕБ интерфейсе PHP, и работать через КОМ соединение :)

(55) Точно, рекурсия спасет теробайтный файлик :)

у меня есть тоже классная задача по 1С:
Как назвать человека который придумывает задачу по программированию и задает ее сообществу изначально прочитав в википедии, что она не имеет решения ?

(59) я про то, что циклы и "Перейти" вспомнили
а рекурсию как средство успешного зацикливания забыли.

(0) В универе проходили такую хрень. У нас это называлось верификация кода. Преподы говорили, раньше любая прога для военного использования, к примеру, подлежала верификации в обязательном порядке. Для каждой из конструкций там свои были методы. Для циклов, например - был персональный метод

Если ГСЧ нету - прокатит

Блин, а был ли там анализ на зацикливание... ХЗ, может и не было))

Вот она, эта хрень

wiki:Проверка_моделей

...вроде бы