Здравствуйте, 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 у меня есть готовые разложения, могу выложить