Математическая задача для приема на работу

electricbird

Несколько лет назад увидел объявление о приеме на работу: всякий, предложивший решение на нижеследующую задачу (математическое или программное будет безоговорочно принят. Так вот она, задача:
Назовите наименьшее целое число, которое нельзя выразить девятью девятками. Возможно использование арифметических операций (+, -, *, /) и скобок «(» и «)» для выражения чисел.
Вот так вот элегантно. Я эту задачку оставил на форуме компании, и скоро народ стал предлагать решения. Можно руководствоваться перебором (начиная с нуля, выражать все последующие целые но на удивление большие числа можно получить таким образом. Некоторые варганили программки на Яве, некоторые пытались вывести решение математически.
Идея девяти девяток в'елась в подсознание. Об этом говорили за обедом, или встречаясь на улице. Много месяцев спустя в голову приходили новые идеи и алгоритмы, но решения так и не нашлось. Задачка оказалась редкостным «мозговым вирусом».
И это в технической фирме. Которая если и не первая, то по крайней мере в первой пятерке в своей области. А какая-то непонятная SW firma такого требует только для приема на работу! Почему-то чувствуешь себя очень тупым и ненужным.
А вы как думаете, какое наименьшее число нельзя выразить подобным образом?

пожалуй, всё-таки сюда, а не в анекдоты

satyana

про положительность ничего не вижу.
Если ее не требуется, то тогда любое число меньше -9*9*9*9*9*9*9*9*9 нельзя выразить...

electricbird

>Если ее не требуется
поскольку задача предполагается корректной .... то требуется, конечно

oleg1966

Множество, состоящее из натуральных чисел, нуля и чисел, противоположных натуральным, называется множеством целых чисел.
Гы, лол! - это я про отрицательную полуось.... =)

satyana

ну перебирать-то там в худшем случае до 9999*99999+1
и че, до сих пор никто не нашел?

stm7543347

-999*999*999 не покатит?

haltay

А решение вообще известно? Мне кажется, что правильный ответ - 41

dalcaev

+ 9 + 9 + 9 + (9 х 9 + 9)/(9 + 9) == 41

natunchik

На реткость йопнутая формулироффка.
Если число - целое, то ответ: не существует такого. Потому что -2^100 точно нельзя, а если некоторое n < -2^100 нельзя, то и n-1 нельзя. Вот.
Если число положительное, то можно по бырому написАть перебор. Аналитического решения, скорее всего, не существует.
Если положительное наибольшее которое _можно_ требуется, то это 999999999 если можно цифры ставить рядом без знаков (доказываеццо по индукции) или 9*9*9*9*9*9*9*9*9 - если нельзя (очевидно).
ЗЫ: Прикольна. Я тоже чуфствую, что ответ -47. Нравицца мне такое число!

Vitaminka

(9*9+9/9)/(9/9+9/9)

Vitaminka

у меня лучше

dalcaev

монопенисуально
47 = 9 + 9 + 9 + 9 + 9 +9/9 + 9/9

Vitaminka

господа не пишите числа, которые сами не проверили
один хер напишем как его представить

ABEPC

Действительно непонятно задача сформулирована...
1. Наверно имеются ввиду все же натуральные числа (целые >0)
2. Можно ли использовать такие комбинации чисел, как 99, 999 и т.д.
3. Нужно ли использовать ровно 9 девяток (или скажем 8 можно?)

sasha_m

Да, формулировка вообще 0. Fj, что-то я туплю:
Если число - целое, то ответ: не существует такого. Потому что -2^100 точно нельзя, а если некоторое n < -2^100 нельзя, то и n-1 нельзя. Вот.
Что-то ты не то сказал, точне я не понял тебя.
можно же решить: Ты составляешь максимальное положительное число, и ставишь перед ним минус, и вычитаешь из него 1 и получишь МИНИМАЛЬНОЕ КОТОРОЕ НЕЛЬЗЯ получить из 9 девяток + арифметические действия.
А все остальное так и есть.

ABEPC

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

sasha_m

Да да! Я ступил. Понятно.

ABEPC

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

natunchik

Поздно. Я уже написАл прогу.
За секунду она нашла все числа, которые можно представить таким образом (не используя чисел вида 99, 999 етс). Их, кстати, всего 4528
Первыми в списке не встречаются 138, 139.

natunchik

Если можно использовать много девяток рядом - то 257. Ответ, в смысле.

zuzaka

Задачка из Перельмана: как тремя двойками и любыми знаками алгебраических действий записать любое натуральное число?

lilith000007

Как 1 выражается?

_shmel_

а че только 8 девяток?

natunchik

А всего чисел 16721. В предыдущем случае тоже +1 к количеству чисел - я их номера с нуля начинал выводить =)
Лажа, короче.
Прога для областной олимпиады по информатике.
Метод решения называеццо "Динамическое Программирование".

Vitaminka

задачка по философии как с помощью десяти слов описать любое натуральное число

Vitaminka

подумал что меньше тем лучше
но прибавить одну не проблема

_shmel_

Я че-то не понимаю, или 9/9 +9/9 + 9/9 +9/9 +9 = 13 ?

natunchik

Как 1 выражается?

эээ. Ниппу =)
Прога считает спецыфическим алгоритмом, в который надо немножко говна дописывать, чтобы узнать КАК выражать данное число. Могу дать код - сам подправишь. Код на шарпе.

Vitaminka

да

natunchik

Что характерно, если разрешить использование менее 9 девяток, то ответ тоже 257. И тоже 138 в случае, если 99 етс. нельзя. Возможно, это не спроста. А возможно и спроста...
ЗЫ: Меня примут на работу? А? =)

zuzaka

Если разрешено использование значков квадратного корня и log, то любое целое число выражается девятью девятками. (9+9)/9 = 2, и задача сводится к задаче с тремя двойками

teraskin

Если можно использовать в качестве промежуточных значений - рациональные числа
то 257 = (99+9+9)*(9-9+9)/(9*9 а ответ 430

teraskin

Держи на здоровье
1 = (9-(9-(9-(9-(9-(-(9-(9*9/9

natunchik

Ух ты как интересно ее генеришь, судя по виду... А покажы прогу!

teraskin

Вечером выложу (часов в 8-9 заодно напишу в общих чертах, как работает
P.S. Язык проги - Ocaml

natunchik

Поскольку в 9 я уже буду спать, то на всякий случай выложу свою =)


using System;
using System.Collections;
namespace _9
{
/// <summary>
/// Summary description for Class1.
/// </summary>
class Class1
{
private static SortedList [] DArray = new SortedList[9];
/// <summary>
/// The main entry point for the application.
/// </summary>
[STAThread]
static void Main(string[] args)
{
DArray[0] = new SortedList(1);
DArray[0].Add(9, null);
for ( int i = 1; i < 9; i ++ )
{
Console.WriteLine("New iteration: {0}; allocating {1} elements", i, DArray[i - 1].Count);
DArray[i] = new SortedList(DArray[i-1]);
// rovno 9 devjatok
//DArray[i] = new SortedList(DArray[i-1].Count);
for ( int j = 0; j < i; j++)
{
for ( int l1 = 0; l1 < DArray[j].Count; l1++ )
{
for ( int l2 = 0; l2 < DArray[i - j - 1].Count; l2++ )
{
int i1 = (int)DArray[j].GetKey(l1);
int i2 = (int)DArray[i - j - 1].GetKey(l2);
int res = i1 + i2;
if ( ! DArray[i].ContainsKey(res) )
{
DArray[i].Add(res, null);
}

res = i1 - i2;
if ( (res > 0) && ( ! DArray[i].ContainsKey(res) ) )
{
DArray[i].Add(res, null);
}
res = i1 * i2;
if ( ( ! DArray[i].ContainsKey(res) ) )
{
DArray[i].Add(res, null);
}
res = i1 / i2;
if ( ( (res * i2) == i1) && ( ! DArray[i].ContainsKey(res) ) )
{
DArray[i].Add(res, null);
}
}
}
}
int nines = 9;
for ( int pow = 0; pow < i; pow++ )
{
nines = nines*10 + 9;
}
if ( ! DArray[i].ContainsKey(nines) )
{
// Esli zakomentit, to ne budet 99, 999 etc.
DArray[i].Add(nines, null);
}
}
int k = 0;
for ( int i = 0; i < DArray[8].Count; i++ )
{
k++;
if ( (k & 0xFF) == 0 )
{
Console.ReadLine;
}
Console.WriteLine("item {0} = {1}", i, DArray[8].GetKey(i;
}
Console.ReadLine;
}
}
}

dysh

int res = i1 / i2;
Твоя программа явно не хочет использовать рациональные в качестве промежуточных значений...

lera__m

= (9*9 + 9) / 9 -9 +9-9+9-9 - например

teraskin

Загрузил прогу по адресу
так как в сумме там рабочих примерно 750 строк в нескольких файлах
Также есть старая версия (generator.ml.old которая умела делать гораздо больше (степени, факториалы и т.д. те правила тоже в архиве (rules а под девятки я ее всего лишь немного модифицировал.
Реально она работает похоже на твою прогу, т.е. идет динамика и строятся все возможные рациональные числа (в некотором диапазоне) из цифр от i-ой до j-ой по номеру в исходном числе. (она с произвольным входным числом может работать). При подсчетах используются только неотрицательные числа (экономия как памяти (примерно в 2 раза так и перебора (примерно в 4 раза соответственно не используется операция унарный минус, а вместо бинарного - абсолютная величина разности (в оригинале были также операции положительная и отрицательная степень). Собственно при выводе построения из разности может получиться (a - b) или -(a-b в зависимости от того, кто больше. Далее, я иду в первую очередь по операциям, а уже внутри каждой операции по спискам для первого и второго операнда. Это позволяет использовать монотонность списков (т.е. если в какой-то момент при сложении или умножении наступило переполнение, то дальше увеличивать второй аргумент смысла не имеет). Также в списки не включаются числа со слишком большим числителем или знаменателем (в этой задаче 1000000000, т.е. входят все числа, в оригинале 100000, чтобы бороться со слишком большими степенями).
Относительно производительности - вариант для девяток нормально считается на 9-цифровых числах (не более 1-2 минут на процессоре 1500 мегагерц, 512м памяти). Оригинальная версия - со степенями и т.д. - на 5-цифровых числах (порядка 5 минут на такой же конфигурации, на 6 цифр нужно очень много памяти, т.е. за разумное время посчитать не реально).

natunchik

Дописал чуть-чуть прогу для рациональных промежуточных значений (просто вместо интов заюзал всюду самописный классец).
Да, 430.
Да, 40 секунд считает на athlon64 3000+.
Забавно, что 8 девяток оно считает полторы секунды, а все остальное время считает девятую итерацию. Откуда, кстати, мысль: если б это была олимпиадная задачка, можно было бы на последней итерации не считать все числа (их порядка 120000 выходит а проверять для конкретных чисел возможность их получения, активно используя монотонность. Тогда бы оно бы может быть уложилось бы в 10 секунд =)
На самом деле забавная задачка. Я получил удовольствие =)
ЗЫ: А откуда она таки взята? Было бы прикольно туда кинуть сцылку на етот тред =)
ЗЗЫ: Я уже нашел блог, откуда она взята, и кинул там сцылку на этот тред =)

railok

можно ?
0=(99/9)-(9+9)/9-9+9-9

stm7929259

/9-9/9-9/9+9=8
Оставить комментарий
Имя или ник:
Комментарий: