К числу 9 применили (в некотором порядке) четыре операции: умножили на 3, разделили на 3, отняли 3 и прибавили 3. Какое наибольшее число могло при этом получиться?

Можно, разумеется, пребрать все 24 варианта, не так уж и долго. Но ведь наверняка существует и эвристическое решение, как к нему притти?

задан 24 Сен '17 10:55

наверное вычитать, потом делить, потом складывать, потом умножать. Вычитаем, чтобы когда поделить - уменьшить вычитаемое, складываем, а потом умножаем, чтобы увеличить слагаемое. Но есть ощущение, что это работает не всегда.

(24 Сен '17 11:11) Williams Wol...

@Williams Wol...: Ваш вариант даёт число 9. Помимо него, есть ещё такой способ: делить (1), складывать (4), умножать (12), вычитать (9). Других вариантов нет, и 9 -- наибольшее значение. А наименьшее значение равно -3. В 16 случаях из 24 результат равен 3. Я, конечно, полный перебор применял. Сейчас попробую рассуждать чуть по-другому.

(24 Сен '17 12:10) falcao
10|600 символов нужно символов осталось
1

Здесь в принципе проходит идея из динамического программирования (принцип Беллмана). Дело в том, что все операции монотонны: чем больше исходное число, тем больше результат. Поэтому у оптимального решения все подпоследовательности должны быть оптимальными (относительно перестановок).

Чтобы сократить число перебираемых вариантов, рассмотрим всевозможные пары операций. Их 6, и это меньше 24, а при большом числе получается n(n-1)/2 вместо n!, то есть ощутимо меньше. Будем обозначать операции в виде С, В, У, Д. Тогда получается следующая несложная "алгебра": СВ=ВС (порядок не важен), СУ > УС (первое превращает x в 3x+9, второе в 3x+3), СД < ДС, ВУ < УВ, ВД > ДВ, УД=ДУ.

Отсюда ясно, что в оптимальной последовательности не должно быть пар УС, СД, ВУ, ДВ. Также нет троек УДС, УВС (перестановки УД=ДУ, ВС=СВ дают "запрещённое" УС), СУД (sic! :)), СВД, ВСУ, ВДУ, ДУВ, ДСВ (Дом Студента на Вернадского :)). Теперь проверке подлежат СУВД, ВДСУ, УВДС, ДСУВ, то есть всего 4 варианта. Результатом будут числа 5, 9, 5, 9.

Хотя тут тоже перебираются варианты, но всё происходит под контролем, и сами опимальные конфигурации получаются естественным путём. Разницу между значениями 5 и 9 всё равно приходится замечать при помощи прямой проверки. Но "мусорные" варианты сразу отбрасываются.

ссылка

отвечен 24 Сен '17 12:49

@falcao, большое спасибо!

(26 Сен '17 0:28) Аллочка Шакед
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×1,399
×1,114
×310
×150
×128

задан
24 Сен '17 10:55

показан
963 раза

обновлен
26 Сен '17 0:28

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru