Модераторы: Alx, Fixin
  

Поиск:

Ответ в темуСоздание новой темы Создание опроса
> Автобусные билетики, Составить число 100 из цифр билетика 
:(
    Опции темы
Фолко
Дата 14.2.2009, 13:38 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 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 

Хочу сделать чтобы програмка показывала все варианты билетика. smile

Заранее спасибо!
PM MAIL ICQ   Вверх
Akina
Дата 14.2.2009, 22:10 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Советчик
****


Профиль
Группа: Модератор
Сообщений: 20570
Регистрация: 8.4.2004
Где: Зеленоград

Репутация: 2
Всего: 453



Существует конечное число расстановок указанных знаков и, соответственно, выстраиваемых выражений. Так что задача фактически сводится к перебору всех возможных вариантов.


--------------------
 О(б)суждение моих действий - в соответствующей теме, пожалуйста. Или в РМ. И высшая инстанция - Администрация форума.

PM MAIL WWW ICQ Jabber   Вверх
maxdiver
Дата 15.2.2009, 20:48 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 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
PM MAIL WWW ICQ   Вверх
DmitryMainichev
Дата 7.5.2010, 07:06 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 2
Регистрация: 7.5.2010

Репутация: нет
Всего: нет



А теперь ответьте, чем полный перебор (решение 1) отличается от вашего варианта (решение 2)?

Очевидно же, что результат будет один и тот же, просто алгоритм перебора в решении 2 указан явно, а в решении 1 просто указано направление.
PM MAIL   Вверх
primepornre1
Дата 28.9.2020, 19:14 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 1
Регистрация: 28.9.2020

Репутация: нет
Всего: нет




Модератор: Сообщение скрыто.

PM MAIL WWW   Вверх
  
Ответ в темуСоздание новой темы Создание опроса
1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | Интересные и занимательные задачи по программированию | Следующая тема »


 




[ Время генерации скрипта: 0.1079 ]   [ Использовано запросов: 21 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.