Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 14, средняя оценка - 4.86
Reedemer
1 / 1 / 0
Регистрация: 11.12.2009
Сообщений: 3
#1

Счастливый билет - C++

11.12.2009, 16:46. Просмотров 1899. Ответов 6
Метки нет (Все метки)

Ув. программисты, помогите пожалуйста несчастному студенту решить задачу.
(о вознаграждении договоримся)
Дан массив из 6 целых чисел от 1 до 9, представляющий собой номер автобусного билета. Проверить, является ли данный билет счастливым, то есть, можно ли, используя любые арифмитические операции и круглые скобки, а так же обединяя цифры в число, получить число 100.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
new_in_net
276 / 255 / 4
Регистрация: 11.11.2009
Сообщений: 605
11.12.2009, 17:27     Счастливый билет #2
Это NP полная задача, могу помочь с алгоритмом.
Алгоритм "обхода" примерно таков:
  1. 6 цифр нужно разбить на числа всевозможными способами
  2. между числами расставить круглые скобки всевозможными способами
  3. расставить всевозможными способами знаки между числами и/или скобками, а также знак минуса перед числами и/или скобками
...и считать результат у всех получившихся выражений.

Вариантов будет много. Способов реализации - тоже может не мало.
C++ не знаю - тут не помогу.
Fintroll
1 / 1 / 0
Регистрация: 04.12.2009
Сообщений: 18
11.12.2009, 22:16     Счастливый билет #3
Цитата Сообщение от new_in_net Посмотреть сообщение
Это NP полная задача, могу помочь с алгоритмом.
Алгоритм "обхода" примерно таков:
  1. 6 цифр нужно разбить на числа всевозможными способами
  2. между числами расставить круглые скобки всевозможными способами
  3. расставить всевозможными способами знаки между числами и/или скобками, а также знак минуса перед числами и/или скобками
...и считать результат у всех получившихся выражений.

Вариантов будет много. Способов реализации - тоже может не мало.
C++ не знаю - тут не помогу.
да ну ты брось - там получиться штук 50 условий если не больше - сомневаюсь, что даже самый добрый препод это примет
odip
Эксперт С++
7153 / 3293 / 59
Регистрация: 17.06.2009
Сообщений: 14,164
12.12.2009, 17:24     Счастливый билет #4
Посчитаем варианты.
Значит имеем 6 цифр. Кстати от 0 до 9.
Операции у нас такие: +,-,*,/.
Добавим операцию _: например 1_5 - это значит что мы решили сделать число 15.
Скобки просто задают приоритет.
Значит имеем 5 мест где можно применить 5 операций.
Это 5^5.
Приоритет - это еще не более 5! вариантов.
Итого число вариантов не превышает: 5!*(5^5) == 375000.
Комп посчитает меньше чем за 1 сек
Reedemer
1 / 1 / 0
Регистрация: 11.12.2009
Сообщений: 3
12.12.2009, 23:32  [ТС]     Счастливый билет #5
Цитата Сообщение от odip Посмотреть сообщение
Посчитаем варианты.
Значит имеем 6 цифр. Кстати от 0 до 9.
Операции у нас такие: +,-,*,/.
Добавим операцию _: например 1_5 - это значит что мы решили сделать число 15.
Скобки просто задают приоритет.
Значит имеем 5 мест где можно применить 5 операций.
Это 5^5.
Приоритет - это еще не более 5! вариантов.
Итого число вариантов не превышает: 5!*(5^5) == 375000.
Комп посчитает меньше чем за 1 сек
дааа забивать 375000 формул не варик
подскажите плз хотябы алгоритм по которому решать
odip
Эксперт С++
7153 / 3293 / 59
Регистрация: 17.06.2009
Сообщений: 14,164
13.12.2009, 01:58     Счастливый билет #6
А ты пост вообще внимательно прочитал ?
Это и есть алгоритм.
Несколько вложенных циклов.
5 вложенных циклов для перебора всех операций на 5 мест.
И еще внутри перебор 5! вариантов - для порядка выполнения операций.

Добавлено через 1 минуту
Получив заданные операции и порядок вычисляешь выражение ( если оно вообще вычисляется )
и сравниваешь что результат равен 100.
Выражение может не вычисляться.
1) делить на 0 нельзя
2) деление должно быть нацело - например 8/4 делится, а вот 3/5 нет
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
14.12.2009, 19:05     Счастливый билет
Еще ссылки по теме:

C++ Задача на счастливый билет
Счастливый билет (Лимит Времени) C++
C++ Счастливый билет (номер с n-количеством цифр)
Задача про счастливый билет C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
jhonnysniper
Сообщений: n/a
14.12.2009, 19:05     Счастливый билет #7
Цитата Сообщение от odip Посмотреть сообщение
А ты пост вообще внимательно прочитал ?
Это и есть алгоритм.
Несколько вложенных циклов.
5 вложенных циклов для перебора всех операций на 5 мест.
И еще внутри перебор 5! вариантов - для порядка выполнения операций.

Добавлено через 1 минуту
Получив заданные операции и порядок вычисляешь выражение ( если оно вообще вычисляется )
и сравниваешь что результат равен 100.
Выражение может не вычисляться.
1) делить на 0 нельзя
2) деление должно быть нацело - например 8/4 делится, а вот 3/5 нет
народ у меня похожая задача, только без скобок - расскажите поподробнее а то я что-то нифига не понял насчёт циклов.
Yandex
Объявления
14.12.2009, 19:05     Счастливый билет
Ответ Создать тему
Опции темы

Текущее время: 09:55. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru