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

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

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

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

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

Ув. программисты, помогите пожалуйста несчастному студенту решить задачу.
(о вознаграждении договоримся)
Дан массив из 6 целых чисел от 1 до 9, представляющий собой номер автобусного билета. Проверить, является ли данный билет счастливым, то есть, можно ли, используя любые арифмитические операции и круглые скобки, а так же обединяя цифры в число, получить число 100.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
11.12.2009, 16:46
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Счастливый билет (C++):

счастливый билет - C++
нам дается номер билета ,нужно проверить ,если мы будем разделять этот номер ,сумма цифр до раздела должна быть равна сумме цифр после...

счастливый билет - C++
Вводится шестизначное число .Определить является ли билет с этим номером счастливым ?с оптимизацией времени решения на турбо си!прошу...

Счастливый билет - C++
Всем привет помогите с решением задачи.Вводится шестизначное число .Определить является ли билет с этим номером счастливым ?Нужно...

Счастливый билет! - C++
билет с шестизначным номером считается счастливым если сумма трех старших цифр совпадает с суммой трех младших. допустим что в билетной...

Задача на счастливый билет - C++
Определить , является ли заданное с клавиатуры шестизначное число четным , счастливым (сумма первых трех цифр равна сумме последних трех...

Почти счастливый билет - C++
В гугле полно задач про "Счастливые билеты", а у меня возникла проблема с "Почти счастливыми билетами. Вот задача - Назовем “почти...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
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
Эксперт С++
7157 / 3297 / 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
Эксперт С++
7157 / 3297 / 59
Регистрация: 17.06.2009
Сообщений: 14,164
13.12.2009, 01:58 #6
А ты пост вообще внимательно прочитал ?
Это и есть алгоритм.
Несколько вложенных циклов.
5 вложенных циклов для перебора всех операций на 5 мест.
И еще внутри перебор 5! вариантов - для порядка выполнения операций.

Добавлено через 1 минуту
Получив заданные операции и порядок вычисляешь выражение ( если оно вообще вычисляется )
и сравниваешь что результат равен 100.
Выражение может не вычисляться.
1) делить на 0 нельзя
2) деление должно быть нацело - например 8/4 делится, а вот 3/5 нет
jhonnysniper
Сообщений: n/a
14.12.2009, 19:05 #7
Цитата Сообщение от odip Посмотреть сообщение
А ты пост вообще внимательно прочитал ?
Это и есть алгоритм.
Несколько вложенных циклов.
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++
Всем привет! Контестер пишет Time Limit. Подскажите что можно сделать чтоб моя программа работала быстрее. Что можно изменить или добавить?...

Написать код(счастливый билет) - C++
Помогите пж. написать код:)

Счастливый билет (номер с n-количеством цифр) - C++
Билет называется счастливым, если его можно разрезать прямой линией на две части таким образом, что оказавшиеся на них числа имеют...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
14.12.2009, 19:05
Ответ Создать тему
Опции темы

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