recnumb.htm

rec1.htm , rec1a.htm , rec2.htm , rec2a.htm , rec3.htm , recgo.htm

recnumb.zip , recnumb3

Рекурсивные числа

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

     Задача. Найдите такое 10-значное число, в котором первая слева цифра равняется количеству нулей в этом числе, вторая цифра равняется количеству единиц в этом числе, и так далее, десятая цифра равняется количеству девяток в этом числе.

     Например, подходит число 6 210 001 000 . Действительно, в нем 6 нулей, 2 единицы, 1 двойка, 1 шестерка, и других цифр нет.

     Задача обобщается для чисел произвольной разрядности.

     Задача несколько раз мне встречалась в сборниках олимпиадных задач для 10-значного числа, при этом каждый раз приводился только ответ без решения.

     Ответ в этой задаче достаточно любопытен.

Для 2-значных чисел - решений нет,
Для 3-значных чисел - решений нет,
Для 4-значных чисел - два решения - 1210 и 2020,
Для 5-значных чисел - одно решение - 21200,
Для 6-значных чисел - решений нет,
Для 7-значных чисел - одно решение - 3211000,
Для n-значных чисел, n>7 - одно решение -

n-4 , 2 , 1 , 0 , ... , 0 , 1 , 0 , 0 , 0 .

      Решаем задачу при помощи суперкомпилятора.

     Число представляем в виде последовательности скобок по одной для каждой цифры. Цифры записываем в унарной системе счисления (нуль - пустое выражение).

     Получились 4 программы, проверяющие, является ли входное число ответом или не является.

     Все программы совсем маленькие, в результате чего этот пример великолепно выполняет демонстрационную функцию.

     (1). rec1.htm. Здесь по первой цифре - 6 (к примеру) - делается вывод, что в числе есть хотя бы одна шестерка, и в седьмой скобке должно быть указание на это. И так далее. Сначала строятся обращения к функции Rec1, которые потом исполняются.

     (2). rec1a.htm. Отличие в том, что обращение к обработке последуещей цифры происходит после окончания обработки предыдущей.

     (3). rec2.htm. По первой цифре - 6 (к примеру) - делается вывод, что в числе имеется 6 нулей и ищутся эти нули, затем аналогично со второй цифрой и так далее.

     (4). rec2a.htm. Цифры обрабатываются поочередно.

     В задании на суперкомпиляцию указываем значность числа, например, для 7-значного числа

 <RecNumber (e.1) (e.2) (e.3) (e.4) (e.5) (e.6) (e.7) >;

     Пример получился таким хорошим в результате совместного творчества. Аркадий Климов посоветовал исследовать вариант аппликативной прогонки. Валентин Федорович  догадался, что :

     Primer interesen v toj stepeni v kakoj Scp bystrej chem prjamoj perebor. Nado napisat' programmu reshenija prjamym pereborom i prognat' s temi zhe chislami -- poka vozmozhno. Sravnit' s vremenami Scp. Esli budet (kak ja dumaju) bol'shaja raznica -- to budet vazhnyj rezul'tat.

     Теперь перехожу к описанию интересных экспериментов.

     1. Времена суперкомпиляции программ rec1.ref  и  rec1a.ref  практически совпадали. Аналогичное наблюдалось и для программ  rec2.ref  и  rec2a.ref.

     2. Стратегия прогонки - ленивая. Для 4-значного числа программы rec1.ref , rec1a.ref суперкомпилируются за одну секунду, а программы rec2.ref , rec2a.ref - за одну минуту. Для 7-значного числа время суперкомпиляции программы rec1.ref составило 112 секунд.

     3. Рассматриваю STRATEGY Applicative; Здесь получается почти наоборот. Для 4-значного числа время суперкомпиляции программы rec1.ref составило 5 секунд, rec2.ref  - 1 секунда. Для 7-значного числа время суперкомпиляции программы rec2.ref составило 58 секунд - в два раза меньше, чем мы имели раньше.

     Таким образом, если нам понадобится хороший пример на отличие ленивой прогонки от аппликативной, то можно пользоваться этим примером.

     (4). Теперь замечание о вопросе количества вариантов, которые перебирает суперкомпилятор. Если в программе rec1.ref можно вставить ложь и что-то увидеть, то в программе rec2.ref процесс завершается лишь при нужном числе, поэтому я не знаю, как ответить на вопрос о количестве вариантов. Понятно, что такое количество вариантов для исходной программы, количество вариантов для остаточной программы ( = 1 ), для процесса суперкомпиляции - не понятно. Хотя смысл какой-то имеется, если время суперкомпиляции меньше времени исполнения исходной программы.

     (5). Сравниваем время суперкомпиляции программы rec2.htm и время исполнения программы recgo.htm. 

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

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

      Поэтому в программе recgo.ref  при организации перебора я задаю именно такие границы для цифр. Поскольку эта программа однократного использования, то я ничего не старался в ней сделать красиво, как получилось, так и написал. Отмечу только, что с ней было гораздо больше мороки с написанием и отладкой, чем с программой для суперкомпилятора. Объем ее тоже больше.

     В программе recgo.ref последовательно строятся n-значные числа, и для каждого числа происходит обращение к первой программе, которая проверяет, подходит ли число под условие задачи или не подходит.

     Готов выслушивать все замечания, вопросы, пожелания и т.д. по проведению этого эксперимента. Было много вариантов, как все организовать, я выбрал тот, о котором пишу, и не уверен, что все получилось хорошо. Я не знаю никаких методических рекомендаций по проведению сравнения времени суперкомпиляции со временем исполнения исходной программы :-)

     Теперь привожу табличку для 4-значных, 5-значных, 6-значных и 7-значных чисел. 

     Время суперкомпиляции определял по протоколу суперкомпиляции (там имеются времена начала и конца). Время исполнения исходной программы определялось рефал-функцией. Везде сделал округления.

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

     Какой именно перебор организует суперкомпилятор - я даже затрудняюсь сказать.

     Наверное, все же не полный перебор, так как он даже в режиме интерпретации обгоняет полный перебор.

     (6). Схема математического решения. 

     Пусть a0 , a1 , ... , an - цифры искомого n+1-значного числа. Подсчет количества цифр (=n+1) различными способами (от перестановки мест слагаемых сумма не меняется) дает два соотношения

a0 + a1 + ... + an = n+1

0*a0 + 1*a1 + 2*a2 + ... + n*an = n+1

      Т.е., сумма цифр равняется значности числа, и сумма с коэффициентами тоже равняется значности числа.

      Далее идет какой-то перебор возникающих вариантов с учетом большого количества нулей.

     (7). Тексты всех программ и результатов суперкомпиляции можно посмотреть в архивированном приложении recnumb.zip. 

      Описание программы rec3.htm , которая получилась любопытным способом при помощи суперкомпилятора, можно прочитать в recnumb3.htm. Время ее суперкомпиляции уменьшилось до 25 секунд по сравнению с 58 секундами.