geese

geese.htm

Детская задачка.

Летит стая гусей, а навстречу ей - один гусь. Один гусь и говорит "Здравствуйте, сто гусей !". На что вожак отвечает :

- нас не 100 гусей. Вот если взять всех нас, до еще столько, да еще пол-столько, да еще четверть столько, до еще тебя гуся, то получится ровно сто гусей.

Спрашивается, сколько гусей в стае ?

Будем решать эту задачу при помощи суперкомпилятора. Пишем программу, которая по количеству гусей, определяет, подходит ли это количество под вопрос.

*$MST_FROM_ENTRY;

$ENTRY Go {
  e.1 =  <Eq (<A e.1>) (<G100 >)>;
 }

A {
 'gggg' e.1 = 'gggg'  
              'gggg'
              'gg'
              'g'
              <A e.1>;
  = 'g' ;
 }

Eq {
  ( ) ( ) = T;
  ('g' e.1) ('g' e.2) = <Eq (e.1) (e.2)>;
  (e.1) (e.2) = F;
 }

G100 {
 = 'gggggggggggggggggggggggggggggggggggggggggggggggggg'
   'gggggggggggggggggggggggggggggggggggggggggggggggggg' ;
 }

Комментарии, ввиду простоты программы, излишни. Суперкомпилируем эту программу и получаем

* InputFormat: <Go e.41 >
$ENTRY Go {
 'gggggggggggggggggggggggggggggggggggggggg' e.41  = F ;
 'gggggggggggggggggggggggggggggggggggg'  = T ;
 'gggggggggggggggggggggggggggggggg'  = F ;
 'gggggggggggggggggggggggggggg'  = F ;
 'gggggggggggggggggggggggg'  = F ;
 'gggggggggggggggggggg'  = F ;
 'gggggggggggggggg'  = F ;
 'gggggggggggg'  = F ;
 'gggggggg'  = F ;
 'gggg'  = F ;
  = F ;
}

Если 36 гусей, то истина, иначе - ложь. Представляет интерес первое предложение - мы не только нашли ответ, но и доказали, что других решений нет.

Теперь убираем в функции Eq третье предложение, получаем

$ENTRY Go {
 'gggggggggggggggggggggggggggggggggggg'  = T ;
}

Пробуем изменить 100 гусей на 101 гуся, получаем

$ENTRY Go {
 'gggggggggggggggggggggggggggggggggggggggg' e.41  = F ;
 'gggggggggggggggggggggggggggggggggggg'  = F ;
 'gggggggggggggggggggggggggggggggg'  = F ;
 'gggggggggggggggggggggggggggg'  = F ;
 'gggggggggggggggggggggggg'  = F ;
 'gggggggggggggggggggg'  = F ;
 'gggggggggggggggg'  = F ;
 'gggggggggggg'  = F ;
 'gggggggg'  = F ;
 'gggg'  = F ;
  = F ;
}

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

$ENTRY Go {
  = F ;
 'gggg'  = F ;
 'gggggggg'  = F ;
 'gggggggggggg'  = F ;
 'gggggggggggggggg'  = F ;
 'gggggggggggggggggggg'  = F ;
 'gggggggggggggggggggggggg'  = F ;
 'gggggggggggggggggggggggggggg'  = F ;
 'gggggggggggggggggggggggggggggggg'  = F ;
 'gggggggggggggggggggggggggggggggggggg'  = T ;
 'gggggggggggggggggggggggggggggggggggggggg' e.41  = F ;
}

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

*$MST_FROM_ENTRY;

$ENTRY Go {
  e.1 =  <Eq (<A e.1>) (<G100 >)>;
 }

A {
 e.1 = <G e.1>
       <G e.1>
       <G12 e.1>
       <G14 e.1>
       'g';
 }

G {
 e.1 = e.1;
 }

G12 {
  = ;
 'gg' e.1 = 'g' <G12 e.1>;
 }

G14 {
  = ;
 'gggg' e.1 = 'g' <G14 e.1>;
 }

Eq {
  ( ) ( ) = T;
  ('g' e.1) ('g' e.2) = <Eq (e.1) (e.2)>;
  (e.1) (e.2) = F;
 }

G100 {
 =
   'gggggggggggggggggggggggggggggggggggggggggggggggggg'
   'gggggggggggggggggggggggggggggggggggggggggggggggggg' ;
 }

Суперкомпилятор работал 11 минут, но справился с этой задачей. В результирующей программе сто предложений, поэтому ее не приводим. Если же в функции Eq убрать ложь, то опять за 11 минут получается программа из одного предложения.