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

Алгоритм перебора - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 38, средняя оценка - 4.76
NIch
 Аватар для NIch
399 / 310 / 27
Регистрация: 17.03.2010
Сообщений: 1,120
18.06.2011, 11:09     Алгоритм перебора #1
Всем доброго времени суток!
Уважаемые форумчане подскажите алгоритм полного перебора, можно без кода, лишь ход действий.
Конкретнее. В кармане некоторое количество монет. Какие суммы денег возможны из данного количества. Например: есть 3 монеты. Возможны варианты: 1+1+5=7 копеек, 5+10+10=25 копеек и т.п. Вынес себе весь мозг, так ниче и не придумал. Пробовал разные варианты но все не то. Если кто знает, как решить подскажите.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
iama
 Аватар для iama
1249 / 974 / 48
Регистрация: 30.07.2010
Сообщений: 5,297
18.06.2011, 11:15     Алгоритм перебора #2
А возможные стоимости монет задаются? Пронумеровать их натуральными числами от 1 до N, тогда задача аналогична этой (см. разбор)
NIch
 Аватар для NIch
399 / 310 / 27
Регистрация: 17.03.2010
Сообщений: 1,120
18.06.2011, 11:34  [ТС]     Алгоритм перебора #3
Возможные стоимости монет как в реальности 1,5,10,25,50...Их можно задать в коде программы...
Все верно по ссылке...Задача сводится к алгоритму полного перебора...Вот у меня загвоздка, не могу понять как задать сам цикл перебора...Повторюсь мне код не важен, сам напишу, мне важен алготритм, хоть на пальцах хоть на псевдоязыке)
iama
 Аватар для iama
1249 / 974 / 48
Регистрация: 30.07.2010
Сообщений: 5,297
18.06.2011, 11:52     Алгоритм перебора #4
То есть вам нужен список наборов вроде
Код
1 1 1
1 1 2
1 1 3
1 1 4
1 2 1 
1 2 2 
1 2 3
1 2 4
1 3 1
...
Тут несложно вывести функцию, которая будет делать из предыдущего набора следующий, пробуйте. Не выйдет - спрашивайте, в чем сложности.
NIch
 Аватар для NIch
399 / 310 / 27
Регистрация: 17.03.2010
Сообщений: 1,120
19.06.2011, 20:33  [ТС]     Алгоритм перебора #5
Тут напрашивается рекурсия, вот тока чета не пойму что делать...
Сделал так, объявил массив из 5 элементов - цена монет... Другой массив, равный коичеству монет... Потом циклом перебирал... цикл for не подходит, пробовал while с проверкой на равенство всех монет последнему значению цены... Но выходит не так как надо... И застопорился...
Голимый брут форс...
Я прикину кой чего и выложу...
grizlik78
Эксперт C++
 Аватар для grizlik78
1882 / 1414 / 101
Регистрация: 29.05.2011
Сообщений: 2,958
19.06.2011, 20:45     Алгоритм перебора #6
Вот здесь я реализовывал такую функцию с названием next_combination. "Енумы" там, конечно, ни к чему, но принцип абсолютно тот же.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
21.06.2011, 15:07     Алгоритм перебора
Еще ссылки по теме:

Оптимизация полного перебора C++
Алгоритм перебора цифр 0 и 1 в четырехзначном числе C++

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

Или воспользуйтесь поиском по форуму:
NIch
 Аватар для NIch
399 / 310 / 27
Регистрация: 17.03.2010
Сообщений: 1,120
21.06.2011, 15:07  [ТС]     Алгоритм перебора #7
Вот тут кое чего нашел:
http://www.bearcave.com/random_hacks/permute.html
Исправлю под себя и выкину готовый код...
Yandex
Объявления
21.06.2011, 15:07     Алгоритм перебора
Ответ Создать тему
Опции темы

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