Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 10.10.2008, 19:20
Новичок

Отправить личное сообщение для vovs Посмотреть профиль Найти все сообщения от vovs
 
Регистрация: 10.12.2007
Адрес: Черкассы, Украина
Сообщений: 6

Задача на перебор все возможных комбинаций
Добрый день, уважаемые,

на днях задали задачку. Сам решить как не представляю. По крайней мере пока что... Поискал в инете - задача бывала на олимпиадах по программированию в вузах.. Может кто сталкивался, может кто подскажет куда начинать копать, какой возможен алгоритм...

Собственно сама задача:
"Дана последовательность цифр 1234567890. Требуется расставить между некоторыми из цифр знаки арифметических операций +, - так, чтобы значение полученного выражения, вычисленное по общепринятым правилам, было равно заданному числу M. Для каждого числа напечатать все возможные варианты расстановки знаков."

На вход подается любое число М, на выходе получаем все возможные варианты..

Спасибо..
  #2  
Старый 10.10.2008, 21:45
Аватар для Schemer
Пользователь

Отправить личное сообщение для Schemer Посмотреть профиль Найти все сообщения от Schemer
 
Регистрация: 26.07.2008
Адрес: Moscow
Сообщений: 93

Ну, у тебя в этой строке 10 цифр, значит 9 мест между ними куда можно поставить + или -. Для каждого места перебери что ставить: +, -, или ничего не ставить, этого всего лишь 3^9 = 19683 вариантов, для каждого варианта подсчитай что получиться каким угодно способов, и выбери из них только те у которых нужная сумма.

Перебор можно организовать например рекурсивно, или (как вариант) в цикле перебрать числа от 0 до 19682, интерпретировать их как числа в 3-ичной системе счисления, где i-я цифра означает что поставить в i-м месте (например 0=ничего, 1=+, 2=-)
  #3  
Старый 12.10.2010, 12:08
гость

 
Сообщений: n/a

Сообщение от Schemer Посмотреть сообщение
Ну, у тебя в этой строке 10 цифр, значит 9 мест между ними куда можно поставить + или -. Для каждого места перебери что ставить: +, -, или ничего не ставить, этого всего лишь 3^9 = 19683 вариантов, для каждого варианта подсчитай что получиться каким угодно способов, и выбери из них только те у которых нужная сумма.

Перебор можно организовать например рекурсивно, или (как вариант) в цикле перебрать числа от 0 до 19682, интерпретировать их как числа в 3-ичной системе счисления, где i-я цифра означает что поставить в i-м месте (например 0=ничего, 1=+, 2=-)
почтеннейший, вы заблуждаетесь: мест, куда можно поставить "+" или "-" не 9 а 10...ведь перед первым числом тоже может быть "-"............
  #4  
Старый 12.10.2010, 13:10
гость

 
Сообщений: n/a

Сообщение от гость Посмотреть сообщение
почтеннейший, вы заблуждаетесь: мест, куда можно поставить "+" или "-" не 9 а 10...ведь перед первым числом тоже может быть "-"............
заблуждаетесь вы. сказано, что надо "расставить между".

но в любом случае, даже если можно и в начале ставить, суть решения не меняется
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Перебор комбинаций слов timugatu Математические алгоритмы (другое) 4 29.11.2009 18:55
поиск всех возможных путей из одной вершины, до другой Xavier Teodonius Графы 5 03.05.2009 16:01
Рекурсивный перебор гость Математические алгоритмы (другое) 1 20.07.2008 03:43
(С++)Перебор купюр с повторениями indolent Математические алгоритмы (другое) 24 06.03.2008 20:56
перебор незарегистрированный Математические алгоритмы 1 17.12.2006 21:17