Здравствуйте, Less, Вы писали:

L>Мдя. Задача простенькая. Я свел ее к обратной польской нотации. Пришлось добавить один дополнительный оператор для связки цифр (типа 99, 999, ...). А дальше все вообще просто — строим комбинаторные варианты польских нотаций, простенькая рекурсия и вуаля.

L>Процесс перебора всех конечных вариантов длился около 15 минут. Что интерестно, около половины из них — целые числа (я думал, значительно меньше, так как имеем операцию деления).
L>Нашло 17366 уникальных >= 0 чисел.

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

Здравствуйте, Neo09, Вы писали:

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

Поделитесь пожалуйста кодом!
isemenov (at) maccentre.ru

Здравствуйте, Блудов Павел, Вы писали:

БП>Похоже, у Вас проблемы с хранением дробей. Я храню как числитель и знаменатель. Оба числа целые.

БП>У меня общее количество циферь 17408. Могу выложить весь список (620kb)


Угу. Результат тот-же. 17408 вариантов и 430 — первый.

Дроби я вообще не хранил.
Немного наглючил с плавающей точкой. Не хотел завязыватся на числителе и знаменателе и поэтому юзал плавающую точку.
Поэтому например выражение, которое имеет смысл — 9/(9/(9-9))... вместо того чтобы быть равным 0, вызывало эксэпшин и не исчислялось.

а так... 167,763,361 конечных комбинаций выражений, из них — 94,240,020 целых, из них — 17,408 уникальных >=0
Что интерестно — число 0 имеет самое большое количество представлений — 10,338,912

Здравствуйте, brainhaze, Вы писали:

B>Назовите наименьшее целое число, которое нельзя выразить девятью девятками. Возможно использование арифметических операций (+, -, *, /) и скобок «(» и «)» для выражения чисел.

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

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

читаем внимательно:
Re[2]: Девять девяток

Автор: brainhaze
Дата: 13.09.04

Здравствуйте, ISemenov, Вы писали:

IS>Поделитесь пожалуйста кодом!

Вот код. Написан под Delphi. Переделывать под C++ не хочется.
Протестил еще раз. Под Celeron 1700 работает 25 сек., под AMD 2500+ работает 13 сек.

{$apptype console}
{$B-,I-,O+,Q-,R-}
uses
    SysUtils, Math;

const
    count = 9;
    maxn = 10000;
    z: string = '+-*/';
    nine: array[1..9]of longint = (9, 99, 999, 9999, 99999, 999999, 9999999, 99999999, 999999999);

type
    TMas = array[0..2*count-1]of longint;

var
    i, j, m, l, d, k: longint;
    q: array[0..maxn]of boolean;
    w: array[0..maxn]of TMas;    
    a, b, c: TMas;

procedure backtracking(n: longint);
var
    i, tb, tc: longint;
begin
    if ((m = 0) and (l = 1)) then begin
        if ((c[1] > 0) and (b[1] mod c[1] = 0)) then begin
            d := abs(b[1]) div c[1];
            if ((d <= maxn) and (q[d])) then begin
                q[d] := false;
                w[d] := a;
                if b[1] < 0 then w[d][0] := -(n - 1) else w[d][0] := n - 1;
            end;
        end;
    end
    else begin
        if (m > 0) then begin
            inc(l);
            inc(k);
            tb := b[k-1];
            tc := c[k-1];
            for i := 1 to m do begin
                m := m - i;
                a[n] := nine[i];
                b[k-1] := a[n];
                c[k-1] := 1;
                backtracking(n + 1);
                b[k-1] := tb;
                c[k-1] := tc;
                m := m + i;
            end;
            dec(k);
            dec(l);
        end;
        if (l > 1) then begin
            dec(l);
            dec(k);
            tb := b[k-1];
            tc := c[k-1];
                a[n] := 1;     { + }
                b[k-1] := b[k-1] * c[k] + b[k] * c[k-1];
                c[k-1] := c[k-1] * c[k];
                backtracking(n + 1);
                b[k-1] := tb;
                c[k-1] := tc;

                a[n] := 2;     { - }
                b[k-1] := b[k-1] * c[k] - b[k] * c[k-1];
                c[k-1] := c[k-1] * c[k];
                backtracking(n + 1);
                b[k-1] := tb;
                c[k-1] := tc;

                a[n] := 3;     { * }
                b[k-1] := b[k-1] * b[k];
                c[k-1] := c[k-1] * c[k];
                backtracking(n + 1);
                b[k-1] := tb;
                c[k-1] := tc;

                a[n] := 4;     { / }
                b[k-1] := b[k-1] * c[k];
                c[k-1] := c[k-1] * b[k];
                backtracking(n + 1);
                b[k-1] := tb;
                c[k-1] := tc;
            inc(k);
            inc(l);
        end;
    end;
end;

begin
    assign(output, 'nine.out');
    rewrite(output);
    fillchar(q, sizeof(q), true);
    fillchar(w, sizeof(w), 0);
    l := 0;
    m := count;
    k := 1;
    backtracking(1);
    for i := 1 to maxn do begin
        if q[i] then begin
            writeln(i, ' : No solution');
        end
        else begin
            if (w[i][0] < 0) then write('-( ');
            for j := 1 to abs(w[i][0]) do begin
                if (w[i][j] < 5) then begin
                    write(z[w[i][j]], ' ');
                end
                else begin
                    write(IntToStr(w[i][j]), ' ');
                end;
            end;
            if (w[i][0] < 0) then write(')');
            writeln(' = ', i);
        end;
    end; 
    close(output);
end.

Здравствуйте, Neo09, Вы писали:

N>Здравствуйте, ISemenov, Вы писали:

IS>>Поделитесь пожалуйста кодом!

N>Вот код. Написан под Delphi. Переделывать под C++ не хочется.
N>Протестил еще раз. Под Celeron 1700 работает 25 сек., под AMD 2500+ работает 13 сек.

Красиво.

2 существенные оптимизации по сравнению с моим кодом:
— результат вычисляется по ходу (у меня в конце для каждой комбинации отдельно считается результат)
— 9, 99, ... — просто отдельный массив. я поступил более универсально, но в то-же время наваял более сложный код — я в обратной польской нотации ввел отдельную операцию для слепливания 9-к.

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

Вот и получилась разница в 20 раз по скорости.

Здравствуйте, brainhaze, Вы писали:

B>Назовите наименьшее целое число, которое нельзя выразить девятью девятками. Возможно использование арифметических операций (+, -, *, /) и скобок «(» и «)» для выражения чисел.

алгоритм полного перебора?
знаки +-/* это 4 в 8 степени = 65536
скобки вроде 8! = 40320 (или я неправ)
Всего вариантов = 2 642 411 520, без оптимизации выражения
что вполне по силам гигагерцовому процессору, даже с библиотекой обработки больших чисел за час — другой должен родить...

Здравствуйте, Михаил, Вы писали:

М>алгоритм полного перебора?
М>знаки +-/* это 4 в 8 степени = 65536
М>скобки вроде 8! = 40320 (или я неправ)

Скобки — это число Каталана.

По формуле Эйлера (http://www.combinatorics.by.ru/katalan.htm)

Z(n) = (4n-2)!!!! / (n+1)!
где
x!!!! = x*(x-4)*(x-8)*...*{1..4} -- обобщённый факториал

или, рекуррентно,

Z(1) = 1
Z(n+1) = (4n+2)!!!! / (n+2)! = Z(n)*(4n+2)/(n+2)

Z[1..8] = 1, 2, 5, 14, 42, 132, 429, 1430

Итого, получаем: 4^8 * Z(8) = 93 716 480
Это если не принимать во внимание числа вида 999.

Здравствуйте, Кодт, Вы писали:

К>Здравствуйте, Михаил, Вы писали:

М>>алгоритм полного перебора?
М>>знаки +-/* это 4 в 8 степени = 65536
М>>скобки вроде 8! = 40320 (или я неправ)

К>Скобки — это число Каталана.

К>По формуле Эйлера (http://www.combinatorics.by.ru/katalan.htm)
К>

К>Z(n) = (4n-2)!!!! / (n+1)!
К>где
К>x!!!! = x*(x-4)*(x-8)*...*{1..4} -- обобщённый факториал
К>

К>или, рекуррентно,
К>

К>Z(1) = 1
К>Z(n+1) = (4n+2)!!!! / (n+2)! = Z(n)*(4n+2)/(n+2)
К>

К>Z[1..8] = 1, 2, 5, 14, 42, 132, 429, 1430

К>Итого, получаем: 4^8 * Z(8) = 93 716 480
К>Это если не принимать во внимание числа вида 999.


Как показала практика, так и есть.
Ровно 93 716 480.

Перебор по каждой позиции знаков арифметики — нет проблем.
Нарисовалось двоичное дерево — множество всех вариантов исполнения бинарной операции.
Левая ветка — "отложить", т.е. pop(), правая — "исполнить".
Осталось оформить алгоритм обхода.
кому делать нечего?

Здравствуйте, Михаил, Вы писали:

М>Перебор по каждой позиции знаков арифметики — нет проблем.
М>Нарисовалось двоичное дерево — множество всех вариантов исполнения бинарной операции.
М>Левая ветка — "отложить", т.е. pop(), правая — "исполнить".
М>Осталось оформить алгоритм обхода.
М>кому делать нечего?
А зачем такой перебор? Насколько я понимаю, результаты приведенные выше (и 430, в частности), получены, в основном, другим способом. Идеи следующие.

• Любое число получается в результате применения бинарной операции к двум другим числам. Унарная операция одна (минус), ее можно игнорировать, потому что он имеет значение, когда стоит в первой позиции. А для этого достаточно проверить результаты и в положительной, и в отрицательной области.
  
• Разобьем множество результатов на "уровни". В уровне i хранятся результаты, полученные с использованием i девяток.
  
• Операцию конкатенации (9, 99, 999...) можно тоже не включать, потому что она может применяться только к результатам, полученным лишь с использованием конкатенации. Поэтому проще эти результаты сразу добавить в результирующее множество на соответствующие уровни (9 штук).
  
• Уровень 1 уже заполнен.
  
• Для построения уровня i перебираем пары уровней <1, i-1>, <2, i-2>, ..., <i-1, 1>. В результаты уровня i добавляем результаты применения каждой из бинарных операций к каждой паре результатов из рассматриваемых уровней. Если результат уже есть в уровне i, его можно смело игнорировать (или перезаписывать, но никак не дублировать), потому что нам неважно, как именно получено некоторое число при помощи i девяток.
  
• Скобки получаются неявно, как результат разного порядка применения бинарных операций при заполнении уровней. При выводе результатов, если нужно разложение, скобки можно проставить, если сохранять информацию о том, из каких результатов получен результат верхнего уровня.

Здравствуйте, conraddk, Вы писали:

C>Здравствуйте, Михаил, Вы писали:

М>>Перебор по каждой позиции знаков арифметики — нет проблем.
М>>Нарисовалось двоичное дерево — множество всех вариантов исполнения бинарной операции.
М>>Левая ветка — "отложить", т.е. pop(), правая — "исполнить".
М>>Осталось оформить алгоритм обхода.
М>>кому делать нечего?
C>А зачем такой перебор? Насколько я понимаю, результаты приведенные выше (и 430, в частности), получены, в основном, другим способом. Идеи следующие.
C>

C>
• Любое число получается в результате применения бинарной операции к двум другим числам. Унарная операция одна (минус), ее можно игнорировать, потому что он имеет значение, когда стоит в первой позиции. А для этого достаточно проверить результаты и в положительной, и в отрицательной области.
  C>
• Разобьем множество результатов на "уровни". В уровне i хранятся результаты, полученные с использованием i девяток.
  C>
• Операцию конкатенации (9, 99, 999...) можно тоже не включать, потому что она может применяться только к результатам, полученным лишь с использованием конкатенации. Поэтому проще эти результаты сразу добавить в результирующее множество на соответствующие уровни (9 штук).
  C>
• Уровень 1 уже заполнен.
  C>
• Для построения уровня i перебираем пары уровней <1, i-1>, <2, i-2>, ..., <i-1, 1>. В результаты уровня i добавляем результаты применения каждой из бинарных операций к каждой паре результатов из рассматриваемых уровней. Если результат уже есть в уровне i, его можно смело игнорировать (или перезаписывать, но никак не дублировать), потому что нам неважно, как именно получено некоторое число при помощи i девяток.
  C>
• Скобки получаются неявно, как результат разного порядка применения бинарных операций при заполнении уровней. При выводе результатов, если нужно разложение, скобки можно проставить, если сохранять информацию о том, из каких результатов получен результат верхнего уровня.
  C>

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

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

Вот описание алгоритма обратной польской нотации:
http://algolist.manual.ru/syntax/revpn.php

Здравствуйте, Михаил, Вы писали:

М>Перебор по каждой позиции знаков арифметики — нет проблем.
М>Нарисовалось двоичное дерево — множество всех вариантов исполнения бинарной операции.
М>Левая ветка — "отложить", т.е. pop(), правая — "исполнить".
М>Осталось оформить алгоритм обхода.
М>кому делать нечего?

Бррр! Дерево какое-то там...

Я сделал так: отдельно 9-разрядный вектор знаков операций + — * / и порязрядный перебор.

И отдельно — в обратной польской нотации — формула, где операции заменены знаком "#".
Перестановки начинаются с "999999999########" и заканчиваются "99#9#9#9#9#9#9#9#".
Пусть d(k) — количество цифр, f(k) — количество операторов на отрезке [0;k).
Инварианты:
k = d(k) + f(k)
d(2) = 2, f(2) = 0
d(k) — f(k) >= 1
d(L) — f(L) = 1

Следующая перестановка выглядит так:
Находим самую правую позицию k>2 : s[k]=='9', s[k+1]=='#', для которой d(k)-f(k) >= 3.
Заменяем s[k] = '#'. При этом получается декремент d(k), инкремент f(k): d'(k)-f'(k) >= 1.
То есть инвариант сохранён.
Заполняем s[k..L) — сперва все оставшиеся цифры, затем все оставшиеся операторы.

Последовательность выглядит так:

999999999########
99999999#9#######
99999999##9######
99999999###9#####
99999999####9####
99999999#####9###
99999999######9##
99999999#######9#
9999999#99#######
9999999#9#9######
9999999#9##9#####
9999999#9###9####
9999999#9####9###
9999999#9#####9##
9999999#9######9#
9999999##99######
9999999##9#9#####
и т.д.

Получив очередные векторы операторов и порядка, заменяем # на соответствующие операторы, и вычисляем.

Выглядит это всё так:

init_codes();
init_order();

do
{
  make_expression();
  perform();
}
while( next_codes() || next_order() ); // false если уже была достигнута последняя перестановка

Причём обратите внимание: next_codes, когда доходит до последнего значения, перекручивает в начало (это обычный цепной счётчик). А next_order — не перекручивает. Это и обусловило такое выражение: next_codes()||next_order()

Здравствуйте, Less, Вы писали:

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

L>Суть в том что человек аналитическими комбинаторными методами посчитал точное количество возможных конечных выражений для варианта задачи без конкатинации. У меня алгоритм полного перебора показал такое-же количество. Пэтому мне лично было просто интерестно посмотреть на именно аналитический подход к оценке количества вариантов перебора.
Интересно, да.

БП>>Правильный ответ 195

L>Боюсь, неправильный
L>195 = 99+99-(9+9)/9-9/9

Оригинал задачи (http://www.itasoftware.com/careers/programmers-archive.php)

Nine 9s

Combining nine 9s with any number of the operators +, -, *, /, (, ) , what is the smallest positive integer that cannot be expressed? 
Hints:  
1)The answer isn't zero. You can express zero like this: 
      (9 - 9) * (9 + 9 + 9 + 9 + 9 + 9 + 9)
    Also, zero isn't a positive integer.  
2) The answer isn't one. You can express one like this: 
       9 - (9 * 9 - 9)/9 + 9 - 9 + 9 - 9
 
3) It's not a trick question. 
 
4) Be sure to handle parentheses correctly. 
 
Notes:  
* You cannot exponentiate. 
* You cannot concatenate (for example, put two 9s together to make 99).
* The - operator can be used in either its binary or unary form. 
* Assume base 10.

Так что, "сращивать" девятки нельзя (типа 99, 999 ...). А тут уже понакодировали алгоритмов с учетом "сращивания".

Здравствуйте, Konstantin Nikolaenko, Вы писали:

БП>>>Правильный ответ 195

L>>Боюсь, неправильный
L>>195 = 99+99-(9+9)/9-9/9

KN>Оригинал задачи (http://www.itasoftware.com/careers/programmers-archive.php)

KN>

KN>Nine 9s
...
KN>* You cannot concatenate (for example, put two 9s together to make 99).
...
KN>

KN>Так что, "сращивать" девятки нельзя (типа 99, 999 ...). А тут уже понакодировали алгоритмов с учетом "сращивания".
Если не сращивать, то ответ как раз 195. В оригинальном посте-то про это не было.

Здравствуйте, Konstantin Nikolaenko, Вы писали:

БП>>>Правильный ответ 195

L>>Боюсь, неправильный
L>>195 = 99+99-(9+9)/9-9/9

KN>Оригинал задачи (http://www.itasoftware.com/careers/programmers-archive.php)

KN>

KN>Notes:  
KN>* You cannot exponentiate. 
KN>* You cannot concatenate (for example, put two 9s together to make 99).
KN>

KN>Так что, "сращивать" девятки нельзя (типа 99, 999 ...). А тут уже понакодировали алгоритмов с учетом "сращивания".

Спасибо. А то я занервничал — код переписывать бросился

Здравствуйте, conraddk, Вы писали:

KN>>Так что, "сращивать" девятки нельзя (типа 99, 999 ...). А тут уже понакодировали алгоритмов с учетом "сращивания".

Дык со сращиванием задача становится интереснее!

C>Если не сращивать, то ответ как раз 195. В оригинальном посте-то про это не было.

Если запрещено получать дроби в промежуточных результатах — то 138.

Здравствуйте, Konstantin Nikolaenko, Вы писали:

БП>>>Правильный ответ 195

KN>Оригинал задачи (http://www.itasoftware.com/careers/programmers-archive.php)

KN>Так что, "сращивать" девятки нельзя (типа 99, 999 ...). А тут уже понакодировали алгоритмов с учетом "сращивания".

Без сращивания и говорить-то не о чем.
Я дал студентам лабу про девятки (курс про перебор), а чтобы с RSDN не таскали чужой код, несколько дополнительных ограничений ввел, в том числе запрет "сращивания".
Сделали за пару дней.