Несколько лет назад увидел объявление о приеме на работу: всякий, предложивший решение на нижеследующую задачу (математическое или программное), будет безоговорочно принят. Так вот она, задача:

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

Вот так вот элегантно. Я эту задачку оставил на форуме компании, и скоро народ стал предлагать решения. Можно руководствоваться перебором (начиная с нуля, выражать все последующие целые), но на удивление большие числа можно получить таким образом. Некоторые варганили программки на Яве, некоторые пытались вывести решение математически.

Идея девяти девяток в'елась в подсознание. Об этом говорили за обедом, или встречаясь на улице. Много месяцев спустя в голову приходили новые идеи и алгоритмы, но решения так и не нашлось. Задачка оказалась редкостным «мозговым вирусом».

И это в технической фирме. Которая если и не первая, то по крайней мере в первой пятерке в своей области. А какая-то непонятная SW фирма такого требует только для приема на работу! Почему-то чувствуешь себя очень тупым и ненужным.

А вы как думаете, какое наименьшее число нельзя выразить подобным образом?

http://brainhaze.blogspot.com/2004/09/blog-post_13.html

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

B>Несколько лет назад увидел объявление о приеме на работу: всякий, предложивший решение на нижеследующую задачу (математическое или программное), будет безоговорочно принят. Так вот она, задача:

Где смеяться?

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

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

-оо

— кто сказал что "-оо" "это не число"? — ладно, для вас но только по-секрету: это в пределе...

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

B>Несколько лет назад увидел объявление о приеме на работу: всякий, предложивший решение на нижеследующую задачу (математическое или программное), будет безоговорочно принят. Так вот она, задача:

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

B>А вы как думаете, какое наименьшее число нельзя выразить подобным образом?

B>http://brainhaze.blogspot.com/2004/09/blog-post_13.html

Имееться в виду выразить число ровно 9 девятками или не больше чем 9 девятками? т.е 1=9/9 выражение правильное?

O>Где смеяться?
здесь

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

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

Минус бесконечность.
Скорее всего решение не пойдет, но тогда нужно уточнить, что число положительное.

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

B>Несколько лет назад увидел объявление о приеме на работу: всякий, предложивший решение на нижеследующую задачу (математическое или программное), будет безоговорочно принят. Так вот она, задача:

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

B>Вот так вот элегантно. Я эту задачку оставил на форуме компании, и скоро народ стал предлагать решения. Можно руководствоваться перебором (начиная с нуля, выражать все последующие целые), но на удивление большие числа можно получить таким образом. Некоторые варганили программки на Яве, некоторые пытались вывести решение математически.

B>Идея девяти девяток в'елась в подсознание. Об этом говорили за обедом, или встречаясь на улице. Много месяцев спустя в голову приходили новые идеи и алгоритмы, но решения так и не нашлось. Задачка оказалась редкостным «мозговым вирусом».

B>И это в технической фирме. Которая если и не первая, то по крайней мере в первой пятерке в своей области. А какая-то непонятная SW фирма такого требует только для приема на работу! Почему-то чувствуешь себя очень тупым и ненужным.

B>А вы как думаете, какое наименьшее число нельзя выразить подобным образом?

B>http://brainhaze.blogspot.com/2004/09/blog-post_13.html

В принципе, наименьшим целым числом будет -8. ну или на худой конец -5555555555555555555555555555.

E>Имееться в виду выразить число ровно 9 девятками или не больше чем 9 девятками? т.е 1=9/9 выражение правильное?

а это не принциписально добавь 0 из остальных например так +( (9-9)*(9+9+9+9+9))

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

D>а это не принциписально добавь 0 из остальных например так +( (9-9)*(9+9+9+9+9))
а если осталась всего-то одна?

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

E>Имееться в виду выразить число ровно 9 девятками или не больше чем 9 девятками? т.е 1=9/9 выражение правильное?

Всегда можно избавиться от лишних 9-ок, например:
четное число 9-ок: +(999-999)
нечетное число 9-ок: +(999-999)*9

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

E>>Имееться в виду выразить число ровно 9 девятками или не больше чем 9 девятками? т.е 1=9/9 выражение правильное?
D>а это не принциписально добавь 0 из остальных например так +( (9-9)*(9+9+9+9+9))

0 = (9-9+9-9+9-9+9-9)/9
1 = 9/9 + (9-9+9-9+9-9)/9
2 = (9+9)/9 + (9-9+9-9+9-9)
3 = (9+9+9)/9 + (9-9+9-9)/9
и так далее...

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

Кстати, если число положительное, тогда рискну предположить, что это
1000000000

O>В принципе, наименьшим целым числом будет -8. ну или на худой конец -5555555555555555555555555555.

ну хорошо, ПОЛОЖИТЕЛЬНОЕ целое число

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

Такие вещи удобно решать с помощью функциональных языков типа ml.
Перебор всевозможных комбинаций итп.
Можно повспоминать на досуге...

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

O>В принципе, наименьшим целым числом будет -8.

Да ну

((9-9)-9/9) * (9-9/9) + (9-9) = -8

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

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

O>>В принципе, наименьшим целым числом будет -8.

А>Да ну

А>((9-9)-9/9) * (9-9/9) + (9-9) = -8

Папа, а как пишется число 8?
Сынок, так же как и бесконечность, повернутая на ПИ пополам...

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

B>Несколько лет назад увидел объявление о приеме на работу: всякий, предложивший решение на нижеследующую задачу (математическое или программное), будет безоговорочно принят. Так вот она, задача:

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

Помоему это очевидно...
-(максимальное_невыражаемое_число)
или операции унарный мнус не присутствует?

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

O>Папа, а как пишется число 8?
O>Сынок, так же как и бесконечность, повернутая на ПИ пополам...

CW или CCW?

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

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

O>>>В принципе, наименьшим целым числом будет -8.

А>>Да ну

А>>((9-9)-9/9) * (9-9/9) + (9-9) = -8

O>Папа, а как пишется число 8?
O>Сынок, так же как и бесконечность, повернутая на ПИ пополам...

Тогда уж :
|
8

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

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

O>>Папа, а как пишется число 8?
O>>Сынок, так же как и бесконечность, повернутая на ПИ пополам...

H>CW или CCW?
А есть разница?

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

O>>>Папа, а как пишется число 8?
O>>>Сынок, так же как и бесконечность, повернутая на ПИ пополам...

H>>CW или CCW?
O>А есть разница?
думаю над этим...

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

В общем есть тупое и очень плохое решение, но пока лучше, чем никакого:

Можно написать программу, строющою все возможные комбинации 9 9-ок, запоминать результаты в массив из 9^9(т. к. это — максимальное число) = элементов ~ 1/5Gb
Ответом будет первый "просвет".
И работать это дожно оооооооооочень долго.
Надо думать дальше...

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

B>Несколько лет назад увидел объявление о приеме на работу: всякий, предложивший решение на нижеследующую задачу (математическое или программное), будет безоговорочно принят. Так вот она, задача:

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

Тут уже народ прикалывался про -оо.
Находим наибольшее по модулю представимое число N. Очевидно, что -N также представимо. Тогда все числа меньшие -|N| непредставимы.

Поищем число N.
Выбросим операции "-" и "/".
У нас есть варианты: A+B, A*B, и десятичная запись 999...9.
Очевидно, что если A<10^a, B<10^b, то A*B <10^(a+b) = 999...9{a+b} + 1
Поэтому, если в формуле A присутствуют k девяток (k >= a), а в B — соответственно m >= b, то получается, что
999...9(k+m) >= 999...9(a+b)
является наилучшим выбором.

Поэтому N = 999999999.

К>Поэтому N = 999999999.

Кстати говоря, если мы ищём наименьшее по модулю число, то диапазон поиска — всего лишь [0;N+1].
Можно и перебором решить...

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

К>Поищем число N.
К>Выбросим операции "-" и "/".
К>У нас есть варианты: A+B, A*B, и десятичная запись 999...9.
К>Очевидно, что если A<10^a, B<10^b, то A*B <10^(a+b) = 999...9{a+b} + 1
К>Поэтому, если в формуле A присутствуют k девяток (k >= a), а в B — соответственно m >= b, то получается, что
К>999...9(k+m) >= 999...9(a+b)
К>является наилучшим выбором.
К>Поэтому N = 999999999.

Во-первых, в задаче надо найти НАИМЕНЬШЕЕ непредставимое число. Для любого названного отрицательно числа найдется еще меньшее непредставимое. Поэтому в таком случает ответ "минус бесконечность".

Во-вторых, автор уже раскололся, что число должно быть положительным.

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

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

IS>Кстати, если число положительное, тогда рискну предположить, что это
IS>1000000000

Мимо, я уже понял.

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

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

9994.
Кто назовет меньше или представит пример разложения?

Могу пояснить свой ход мыслей, если интересно.

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

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

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

IS>9994.
IS>Кто назовет меньше или представит пример разложения?

IS>Могу пояснить свой ход мыслей, если интересно.
Интересно.

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

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

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

IS>9994.
IS>Кто назовет меньше или представит пример разложения?

IS>Могу пояснить свой ход мыслей, если интересно.

Тут у меня программка доработала...
если нигде не облажался, то 177

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

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

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

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

IS>>9994.
IS>>Кто назовет меньше или представит пример разложения?

IS>>Могу пояснить свой ход мыслей, если интересно.
O>Интересно.

Кратчайший вариант записи числа 5 — это 6 девяток (я меньше придумать не смог).
9994 = 9999 — 5. Но если мы "потратили" 4 девятки на 9999, то у нас не хватит 6 девяток для 5.
Я ошибаюсь?

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

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

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

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

IS>>9994.
IS>>Кто назовет меньше или представит пример разложения?

IS>>Могу пояснить свой ход мыслей, если интересно.

А>Тут у меня программка доработала...
А>если нигде не облажался, то 177

Ан нет облажался...
Ответ 176 ?

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

А>Тут у меня программка доработала...
А>если нигде не облажался, то 177

177 = (9 + 9) * 9 + 9 + 9 — (9 + 9 + 9) / 9

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

IS>Здравствуйте, Аноним, Вы писали:

А>>Тут у меня программка доработала...
А>>если нигде не облажался, то 177

IS>177 = (9 + 9) * 9 + 9 + 9 — (9 + 9 + 9) / 9

Да-да-да я там единичку незаметил.

176 — вроде как ответ.

9994 кстати тоже не представляется (судя по логам)

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

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

Будем считать, что под девятками понимаются числа, а не цифры, то есть не может быть вариантов типа (999 — 99).

Разобъём задачу на 2 этапа:
1. Найти это число для себя.
2. Доказать, что это число минимальное.
Для себя это число просто найти перебором.
Оно равно 138.
Доказательство нужно потому, что мы "обрезаем" перебор для X > XMAX, а вообще говоря могут быть два числа X1 > XMAX и X2 > XMAX такие, что X1 — X2 = 138;

Вот код, реализующий перебор:

#include <list>
#include <iostream>

unsigned int const N = 9;
int const XMAX = 1000000;

typedef std::list<int> TCont;

TCont L[N];

inline void PushValue(int i, TCont::value_type Value)
{
    if ((Value < XMAX) && (Value >= 0)) L[i].push_back(Value);
}

inline TCont::value_type MakeDiv(TCont::value_type i, TCont::value_type j)
{
    if ((j != 0) && ((i % j) == 0))
        return i / j;
    else
        return (XMAX + 1);
}

inline TCont::value_type MakeMul(TCont::value_type i, TCont::value_type j)
{
    double Res = i;
    Res *= j;
    if (Res > XMAX)
        return XMAX + 1;
    return (Res + 0.5);
}

int main()
{
    L[0].push_back(9);
    for (int i = 1; i < N; ++i)
    {
        for (int j = 0; j < i; ++j)
        {
            int k = i - j - 1;
            for (TCont::iterator ij = L[j].begin(); ij != L[j].end(); ++ij)
                for (TCont::iterator ik = L[k].begin(); ik != L[k].end(); ++ik)
                    PushValue(i, *ij + *ik);
            for (TCont::iterator ij = L[j].begin(); ij != L[j].end(); ++ij)
                for (TCont::iterator ik = L[k].begin(); ik != L[k].end(); ++ik)
                    PushValue(i, *ij - *ik);
            for (TCont::iterator ij = L[j].begin(); ij != L[j].end(); ++ij)
                for (TCont::iterator ik = L[k].begin(); ik != L[k].end(); ++ik)
                    PushValue(i, MakeMul(*ij,*ik));
            for (TCont::iterator ij = L[j].begin(); ij != L[j].end(); ++ij)
                for (TCont::iterator ik = L[k].begin(); ik != L[k].end(); ++ik)
                    PushValue(i, MakeDiv(*ij,*ik));
        }
        L[i].sort();
        L[i].unique();
        std::cout << "--- " << (i+1) << " ---" << std::endl;
        //for (TCont::iterator ii = L[i].begin(); ii != L[i].end(); ++ii)
        //    std::cout << *ii << std::endl;
    }
    TCont::value_type n = 0;
    for (TCont::iterator i = L[N-1].begin(); i != L[N-1].end(); ++i, ++n)
    {
        TCont::value_type Cur = *i;
        if (Cur != n)
        {
            std::cout << std::endl << "Res = " << n << std::endl;
            break;
        }
    }
    return 0;
}

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

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

IS>>Здравствуйте, Аноним, Вы писали:

А>>>Тут у меня программка доработала...
А>>>если нигде не облажался, то 177

IS>>177 = (9 + 9) * 9 + 9 + 9 — (9 + 9 + 9) / 9

А>Да-да-да я там единичку незаметил.

А>176 — вроде как ответ.

А никто еще не пробовал с многозначными числами? 99, 999 etc

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

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

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

W>Будем считать, что под девятками понимаются числа, а не цифры, то есть не может быть вариантов типа (999 — 99).

W>Разобъём задачу на 2 этапа:
W>1. Найти это число для себя.
W>2. Доказать, что это число минимальное.
W>Для себя это число просто найти перебором.
W>Оно равно 138.

Если под девятками понимать цифры, то есть допустить варианты типа 99, 999 и т.д.,
то минимальное непредставимое число = 257.

Для этого нужно дописать в перебор предыдущего поста ещё 1 строку:

int main()
{
    L[0].push_back(9);
    for (int i = 1; i < N; ++i) L[i].push_back(L[i-1].back() * 10 + 9);
    for (int i = 1; i < N; ++i)
    {
    ...

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

B>Здравствуйте, Аноним, Вы писали:

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

IS>>>Здравствуйте, Аноним, Вы писали:

А>>>>Тут у меня программка доработала...
А>>>>если нигде не облажался, то 177

IS>>>177 = (9 + 9) * 9 + 9 + 9 — (9 + 9 + 9) / 9

А>>Да-да-да я там единичку незаметил.

А>>176 — вроде как ответ.

B>А никто еще не пробовал с многозначными числами? 99, 999 etc

Написал свой код для перебора.
У меня он выдал наименьшее число 238.

Здравствуйте, <Аноним>, Вы писали:

А>176 — вроде как ответ.
Нет.

176 = (9 + 9)*(9 + 9*9 — (9 + 9)/9)/9

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

IS>У меня он выдал наименьшее число 238.

238 = 9*(9+9+9)- (9*9 + 9)/(9+9)

Может быть, 257? У меня такой результат получился. Но при расчетах не использовались дробные промежуточные результаты деления
Кто может разложить это число?
Для всех до 257 у меня есть готовые разложения, могу выложить

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

C>Может быть, 257? У меня такой результат получился. Но при расчетах не использовались дробные промежуточные результаты деления
C>Кто может разложить это число?
C>Для всех до 257 у меня есть готовые разложения, могу выложить
Нашел Дробные промежуточные результаты нельзя выкидывать.
257 = 99-(9+9)*(((9+9)/(9*9))-9)

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

C>>Может быть, 257? У меня такой результат получился. Но при расчетах не использовались дробные промежуточные результаты деления
C>>Кто может разложить это число?
C>>Для всех до 257 у меня есть готовые разложения, могу выложить
C>Нашел Дробные промежуточные результаты нельзя выкидывать.
C>257 = 99-(9+9)*(((9+9)/(9*9))-9)

99-(9+9)*(((9+9)/(9*9))-9) = 261

Действительно, минимальное число = 257

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

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

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

C>>>Может быть, 257? У меня такой результат получился. Но при расчетах не использовались дробные промежуточные результаты деления
C>>>Кто может разложить это число?
C>>>Для всех до 257 у меня есть готовые разложения, могу выложить
C>>Нашел Дробные промежуточные результаты нельзя выкидывать.
C>>257 = 99-(9+9)*(((9+9)/(9*9))-9)

W>99-(9+9)*(((9+9)/(9*9))-9) = 261
Как это?
99-(9+9)*(((9+9)/(9*9))-9) =
99-18*(18/81-729/81) =
99-18*(-79/9)=
99+158=
257

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

Новый кандидат — 430.
Кто возьмется его разломать?

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

W>>99-(9+9)*(((9+9)/(9*9))-9) = 261
C>Как это?
C>99-(9+9)*(((9+9)/(9*9))-9) =
C>99-18*(18/81-729/81) =
C>99-18*(-79/9)=
C>99+158=
C>257

Согласен. Просто считал в целых числах
Я когда решал, считал, что деление допустимо, только когда числа делятся нацело. Тогда ответ = 257.
Если же допускать работу с рациональными дробями, как у Вас в примере, то ответ = 430.

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

W>Согласен. Просто считал в целых числах
W>Я когда решал, считал, что деление допустимо, только когда числа делятся нацело. Тогда ответ = 257.
W>Если же допускать работу с рациональными дробями, как у Вас в примере, то ответ = 430.
Да, похоже на то.

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

B>Несколько лет назад увидел объявление о приеме на работу: всякий, предложивший решение на нижеследующую задачу (математическое или программное), будет безоговорочно принят. Так вот она, задача:

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

Баян двухлетней давности:
http://rsdn.ru/Forum/Message.aspx?mid=21139

Автор: Финченко Юрий
Дата: 11.01.02

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

А по-моему логика такая: пытаемся представить с помощью 9 девяток самое маленькое возможное целое число. Все числа меньше него будут удовлетворять условию (в смысле их нельзя будет представить с помощью 9 девяток).

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

EA>А по-моему логика такая: пытаемся представить с помощью 9 девяток самое маленькое возможное целое число. Все числа меньше него будут удовлетворять условию (в смысле их нельзя будет представить с помощью 9 девяток).

0 = (9-9)*9999999
1 = 9/9 + (9-9)*99999
...

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

БП>Баян двухлетней давности:
БП>http://rsdn.ru/Forum/Message.aspx?mid=21139

Автор: Финченко Юрий
Дата: 11.01.02

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

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

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

B>Несколько лет назад увидел объявление о приеме на работу: всякий, предложивший решение на нижеследующую задачу (математическое или программное), будет безоговорочно принят. Так вот она, задача:

А что за контора? И если будет аналитическое короткое решение, то они сейчас примут на работу?

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

Не в качестве ответа, а так...
40 разложите кому не лень

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

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

Точно. очепятка в коде. Вместо

        if (iFract[1].m_nNumerator != iFract[0].m_nNumerator + 1)
        {
            printf("number %d\n", iFract[0].m_nNumerator + 1);
            break;
        }

должно быть

        if (iFract[1].m_nNumerator != iFract[0].m_nNumerator + 1)
        {
            printf("number %d\n", iFract[1].m_nNumerator + 1);
            break;
        }

Так что правильный ответ 196. Звиняйте

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

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

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

БП>Так что правильный ответ 196. Звиняйте

Не знаю, моя прога нашла для него разложение:

(99+99+(9-9-9-9)/9) = 196

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

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

_MS>Не в качестве ответа, а так...
_MS>40 разложите кому не лень

Пожалуйста:

(9+9+(99+99-9+9)/9) = 40

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

БП>Точно. очепятка в коде. Вместо

Мда... Ошибочка вышла. Нету там опечятки. Проблема в моей голове.

нужно после

    vectIterations[0].push_back(thetype_t::value_type(9, 1));

добавить

    vectIterations[1].push_back(thetype_t::value_type(99, 1));
    vectIterations[2].push_back(thetype_t::value_type(999, 1));
    vectIterations[3].push_back(thetype_t::value_type(9999, 1));
    vectIterations[4].push_back(thetype_t::value_type(99999, 1));
    vectIterations[5].push_back(thetype_t::value_type(999999, 1));
    vectIterations[6].push_back(thetype_t::value_type(9999999, 1));
    vectIterations[7].push_back(thetype_t::value_type(99999999, 1));
    vectIterations[8].push_back(thetype_t::value_type(999999999, 1));

А иначе из двух 9-ок у меня 99 никак не получится.

Новый ответ 430.

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

N>(99+99+(9-9-9-9)/9) = 196
тут

Автор: Блудов Павел
Дата: 14.09.04

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

БП>Новый ответ 430.
Ура, похоже нашли правильное решение. Вряд ли трое сразу ошиблись
Re[5]: Девять девяток

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

Re[5]: Девять девяток

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

Re[3]: ПОЛЬЗУЙТЕСЬ ПОИСКОМ!

Автор: Блудов Павел
Дата: 14.09.04

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

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

Первый пробел — при 393. Второй — 402. Третий — 430.

Гм. Я так вижу, что 3 человек уверены что 430 — первый пробел, а не 3-й. Значит у меня глюк где-то небольшой — видимо пропускаю возможные варианты.

Буду очень признательным если увижу расклады для 393 или 402 (лучше оба сразу )

Аналитически решать не пробовал — лень, если честно.

Если кому нужно решение или таблица с вариантами, мылите на less@ua.fm.

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


Regards

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

L>Буду очень признательным если увижу расклады для 393 или 402 (лучше оба сразу )

393 = (9+((9+9)*(9+((999/9)/9))))
402 = ((9+9)*(9+((9+(999/9))/9)))

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

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

Здравствуйте, 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 не таскали чужой код, несколько дополнительных ограничений ввел, в том числе запрет "сращивания".
Сделали за пару дней.

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

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

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

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

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

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


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

Студенты — народ изобретательный, особенно если это будущие инженеры и если они слишком ленивые чтобы что-то делать

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

L>Студенты — народ изобретательный, особенно если это будущие инженеры и если они слишком ленивые чтобы что-то делать

А для этих целей есть усложнения задачи. Например, вместо девяток — цифры 1..9.
Или пусть построят функцию: минимальное число, непредставимое выражением из одной 1 / двух 2 и т.п.

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

L>>Сделали за пару дней.

L>Тоже мне...
L>Имея готовое програмное решение, которое тут проскакивало, достаточно легко его упростить и выбросить лишний цикл перебора срощенных элементов.

L>Студенты — народ изобретательный, особенно если это будущие инженеры и если они слишком ленивые чтобы что-то делать

Ленивые, конечно, поэтому я внимательно отслеживаю, чтобы не сдавались программы "похожие" на появляющиеся здесь...

А вот самое красивое решение, что я видел
a:*|8{x,,?,//x{x y/:'|x}/+;*;%)}/,-9 9.0
f:{+/j=!#j@:<j:?j@:&x=j:_ x@:&~0>x}
f a

195

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

Т>А вот самое красивое решение, что я видел
Т>a:*|8{x,,?,//x{x y/:'|x}/+;*;%)}/,-9 9.0
Т>f:{+/j=!#j@:<j:?j@:&x=j:_ x@:&~0>x}
Т>f a

Т>195

А!!!! Какой ужас!!!
Краткость — не всегда сестра таланта.

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

Т>А вот самое красивое решение, что я видел

Т>a:*|8{x,,?,//x{x y/:'|x}/:(+;*;%)}/,-9 9.0
Т>f:{+/j=!#j@:<j:?j@:&x=j:_ x@:&~0>x}
Т>f a

Т>195

На чём это?

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

B>Несколько лет назад увидел объявление о приеме на работу: всякий, предложивший решение на нижеследующую задачу (математическое или программное), будет безоговорочно принят. Так вот она, задача:

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

B>Вот так вот элегантно. Я эту задачку оставил на форуме компании, и скоро народ стал предлагать решения. Можно руководствоваться перебором (начиная с нуля, выражать все последующие целые), но на удивление большие числа можно получить таким образом. Некоторые варганили программки на Яве, некоторые пытались вывести решение математически.

B>Идея девяти девяток в'елась в подсознание. Об этом говорили за обедом, или встречаясь на улице. Много месяцев спустя в голову приходили новые идеи и алгоритмы, но решения так и не нашлось. Задачка оказалась редкостным «мозговым вирусом».

B>И это в технической фирме. Которая если и не первая, то по крайней мере в первой пятерке в своей области. А какая-то непонятная SW фирма такого требует только для приема на работу! Почему-то чувствуешь себя очень тупым и ненужным.

B>А вы как думаете, какое наименьшее число нельзя выразить подобным образом?

B>http://brainhaze.blogspot.com/2004/09/blog-post_13.html

9-9-9-9-9-9-9-9-9-1

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

о девяти девятках
по-моему меньше при помощи арифметичских операций нельзя

9-(9*9*9*9*9*9*9*9)

9-(9*9*9*9*9*9*9*9)-1 = нужное число

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

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

kof>о девяти девятках
kof>по-моему меньше при помощи арифметичских операций нельзя

А можно перед тем, как присылать свой ответ, остальные ответы прочитать? Там уже было и насчёт целых чисел вообще, и насчёт неотрицательных тоже.

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

К>На чём это?
Это K, потомок APL и J (http://www.kx.com)