|
Модераторы: Alx, Fixin |
|
Фолко |
|
|||
Новичок Профиль Группа: Участник Сообщений: 41 Регистрация: 9.4.2006 Где: Belarus Репутация: нет Всего: нет |
Добрый день!
Расскажу сначала о постановке задачи, мне она показалась интересной, может вам она тоже понравится и кто-нибудь подскажет какую идею, как реализовать подходящий алгоритм. Задача: Есть автобусный билетик из 6 цифр (например 123123), требуется расставить знаки +-*/() между цифрами билетика и получить число 100. Менять порядок цифр нельзя, но можно составлять числа из цифр билетика (например 12 + 312 + 3). Более подробно задачка описана здесь - http://habrahabr.ru/blogs/i_am_clever/40036/. Пример:0 7 9 6 6 4: (7*6)+(9*6)+4= 42 +54 + 4 = 100 1 4 8 4 3 9: 148-4*(3+9) = 100 Хочу сделать чтобы програмка показывала все варианты билетика. Заранее спасибо! |
|||
|
||||
Akina |
|
|||
Советчик Профиль Группа: Модератор Сообщений: 20570 Регистрация: 8.4.2004 Где: Зеленоград Репутация: 2 Всего: 453 |
Существует конечное число расстановок указанных знаков и, соответственно, выстраиваемых выражений. Так что задача фактически сводится к перебору всех возможных вариантов.
-------------------- О(б)суждение моих действий - в соответствующей теме, пожалуйста. Или в РМ. И высшая инстанция - Администрация форума. |
|||
|
||||
maxdiver |
|
|||
Опытный Профиль Группа: Участник Сообщений: 381 Регистрация: 29.1.2008 Где: Саратов Репутация: 2 Всего: 18 |
Посчитаем для каждого подотрезка a[l..r] множество всех чисел, которые могут быть получены из него, обозначим его d[l][r]. Тогда ответом будет d[1][n].
Научимся считать это множество. Пусть мы хотим найти значение d[l][r]. Если l=r, тогда вариантов у нас два - это a[l] и -a[l]. Если же l<r, то то, если мы рассмотрим любое выражение, построенное на этом отрезке a[l..r], то в нём найдётся операция, выполняемая последней. Переберём позицию m=l+1..r-1 этой операции и саму операцию (+-*/) , тогда в множество d[l][r] надо добавить все элементы вида d[l][m-1] <операция> d[m+1][r]. Оставшийся случай - когда мы из всех цифр a[l..r] делаем одно число, т.е. в d[l][r] надо добавить ещё a[l..r]. Это решение мне кажется более изящным и надёжным, чем полный перебор. P.S. Почти такая задача попадалась на каком-то контесте недавно. Московская олимпиада что ли... Или четвертьфинал чей-то... Это сообщение отредактировал(а) maxdiver - 15.2.2009, 21:45 |
|||
|
||||
DmitryMainichev |
|
|||
Новичок Профиль Группа: Участник Сообщений: 2 Регистрация: 7.5.2010 Репутация: нет Всего: нет |
А теперь ответьте, чем полный перебор (решение 1) отличается от вашего варианта (решение 2)?
Очевидно же, что результат будет один и тот же, просто алгоритм перебора в решении 2 указан явно, а в решении 1 просто указано направление. |
|||
|
||||
primepornre1 |
|
|||
Новичок Профиль Группа: Участник Сообщений: 1 Регистрация: 28.9.2020 Репутация: нет Всего: нет |
Модератор: Сообщение скрыто. |
|||
|
||||
0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей) | |
0 Пользователей: | |
« Предыдущая тема | Интересные и занимательные задачи по программированию | Следующая тема » |
|
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности Powered by Invision Power Board(R) 1.3 © 2003 IPS, Inc. |