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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 4.78
deph
0 / 0 / 0
Регистрация: 28.07.2011
Сообщений: 7
#1

Перебор - C++

28.07.2011, 18:21. Просмотров 1163. Ответов 14
Метки нет (Все метки)

Ребят, помогите решить две задачи. Занимаюсь программированием уже 6 лет. Но тут в ступор встал.
1 задача:
есть массив. из него нужно получить все возможные варианты строк заданной длинной(пусть будет l), и кол-во повторений элементов массива в строке не более n(порядок не важен,главное что бы не повторялись более чем n раз)

2 задача:
подобная, но усложнена тем, что массивов теперь 3. ну и добавлены следующие параметры. строки так же должны быть длинной l. x1 элемент из первого массива, x2 элемента из второго массива, x3 элемента из третьего. при чем n<=x1<=n1, m<=x2<=m1, p<=x3<=p1. Естественно x1+x2+x3=l. И так же есть нюанс с повторениями. из первого массива не более d1. из второго не более d2. из третьего не более d3.

Так же важна скорость. мой компилятор g++ (ubuntu 11.04).
Помогите составить нормальный алгоритм перебора. Заранее спасибо.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
28.07.2011, 18:21     Перебор
Посмотрите здесь:

Перебор списка C++
C++ Перебор комбинаций
C++ Перебор чисел
Перебор текста C++
C++ Перебор символов
Перебор значений C++
Полный перебор C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
ValeryLaptev
Эксперт С++
1030 / 809 / 48
Регистрация: 30.04.2011
Сообщений: 1,651
28.07.2011, 19:04     Перебор #2
deph, несколько вопросов.
1. Массив чего?
2. Элементы массива различны? Или есть одинаковые?
3. Размер массива какой? Больше-меньше L, больше-меньше n?
deph
0 / 0 / 0
Регистрация: 28.07.2011
Сообщений: 7
29.07.2011, 01:14  [ТС]     Перебор #3
массивы могут быть разными. проблема в этом. но упор буду делать на char.
кол-во элементов может быть и меньше и больше любого из параметров.

Добавлено через 1 минуту
Цитата Сообщение от ValeryLaptev Посмотреть сообщение
deph, несколько вопросов.
1. Массив чего?
2. Элементы массива различны? Или есть одинаковые?
3. Размер массива какой? Больше-меньше L, больше-меньше n?
в первой задаче. размер массива меньше l, но больше n.
во второй задаче может быть и так и так.
и все элементы массива различны естественно.

Добавлено через 6 часов 1 минуту
неужели ничем помочь никто не может?
easybudda
Эксперт С++
9412 / 5435 / 917
Регистрация: 25.07.2009
Сообщений: 10,428
29.07.2011, 01:31     Перебор #4
Цитата Сообщение от deph Посмотреть сообщение
Занимаюсь программированием уже 6 лет.
И никаких идей? Хоть наброски покажите, как сделать пытались...
И примеры входных/выходных данных очень неплохо бы увидеть, а то уже с первого задания не понятно - все варианты из m байт по l байт такие, чтобы байт со значением x входил в l не больше, чем n раз? Так это Вам к математикам...
Jupiter
Каратель
Эксперт C++
6549 / 3969 / 226
Регистрация: 26.03.2010
Сообщений: 9,273
Записей в блоге: 1
Завершенные тесты: 2
29.07.2011, 01:32     Перебор #5
Цитата Сообщение от deph Посмотреть сообщение
неужели ничем помочь никто не может?
уточните задачу, специализируйте её для конкретного типа, а там глядишь и обобщенное решение найдется
deph
0 / 0 / 0
Регистрация: 28.07.2011
Сообщений: 7
29.07.2011, 02:22  [ТС]     Перебор #6
Цитата Сообщение от easybudda Посмотреть сообщение
И никаких идей? Хоть наброски покажите, как сделать пытались...
И примеры входных/выходных данных очень неплохо бы увидеть, а то уже с первого задания не понятно - все варианты из m байт по l байт такие, чтобы байт со значением x входил в l не больше, чем n раз? Так это Вам к математикам...
я никогда переборами не занимался) в общем я пытался делать напрямую. с помощью рекурсии. но по параметрам проверку сделать нормально не могу. да и работает долго. после обеда кину то что делал.

Добавлено через 2 минуты
Цитата Сообщение от Maxwe11 Посмотреть сообщение
уточните задачу, специализируйте её для конкретного типа, а там глядишь и обобщенное решение найдется
есть две задачи. они обобщены конечно. но мне и обобщенное решение и нужно. соль в этом как раз. конкретику больше никакую тут представить не могу.
OstapBender
582 / 520 / 35
Регистрация: 22.03.2011
Сообщений: 1,585
29.07.2011, 02:28     Перебор #7
задачи для меня пока непосильные, единственное чего могу посоветовать - сразу убрать
повторяющиеся больше N раз значения из массива.
код
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
    std::string str = "qqqqetytaaatuapkjnmacwvctuawmj";
    std::string new_str;
 
    int n = 2;
 
    std::map<char,int> mp;
 
    for (int i=0; i<str.length(); i++) {
        
        mp[str[i]]++;
 
        if (mp[str[i]]<=n)
            new_str+=str[i];
 
    }
 
    std::cout << new_str;

теперь в новой строке не больше N раз повторений.
deph
0 / 0 / 0
Регистрация: 28.07.2011
Сообщений: 7
29.07.2011, 02:32  [ТС]     Перебор #8
OstapBender, это когда строка уже готова. вдобавок тут обрезание идет. суть в том что бы сразу генерировать набор строк такой, что бы повторений таких не было.

p.s.: в общем у меня по первой задачке идейка появилась. возможно если получиться от неё можно будет отскочить и ко второй задачке.
OstapBender
582 / 520 / 35
Регистрация: 22.03.2011
Сообщений: 1,585
29.07.2011, 02:36     Перебор #9
Цитата Сообщение от deph Посмотреть сообщение
суть в том что бы сразу генерировать набор строк такой, что бы повторений таких не было.
а что мешает сначала исключить повторения, а потом крутить вертеть строкой как хош.
deph
0 / 0 / 0
Регистрация: 28.07.2011
Сообщений: 7
29.07.2011, 02:44  [ТС]     Перебор #10
OstapBender, то что перебрав все варианты. их будет очень много. т.е. работать будет долго. так реализовать то очень просто. нагенеровать сначала всевозможные варианты. а потом исключить варианты с повторениями. просто для l>15 время выполнения уже не хилое.
ValeryLaptev
Эксперт С++
1030 / 809 / 48
Регистрация: 30.04.2011
Сообщений: 1,651
29.07.2011, 09:46     Перебор #11
Цитата Сообщение от easybudda Посмотреть сообщение
И никаких идей? Хоть наброски покажите, как сделать пытались...
И примеры входных/выходных данных очень неплохо бы увидеть, а то уже с первого задания не понятно - все варианты из m байт по l байт такие, чтобы байт со значением x входил в l не больше, чем n раз? Так это Вам к математикам...
Да. Просто надо начинать смотреть с типа генерации перестановок. Алгоритмов в инете - дофига.
Mayonez
380 / 272 / 20
Регистрация: 26.12.2009
Сообщений: 875
29.07.2011, 12:50     Перебор #12
deph, пока зделал такое:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
/////////////////////////////////////////////////////////////
int length;
std::string s;
std::string result;
std::vector<bool> used;
/////////////////////////////////////////////////////////////
void r(int now)
{
    if(now == length)
    {
        std::cout << result << std::endl;   
        return;
    }
 
    for(int i = 0; i < s.length(); i++)
        if(!used[i])
        {
            used[i] = true;
            result.at(now) = s.at(i);
            r(now+1);
            used[i] = 0;
        }
}
/////////////////////////////////////////////////////////////
int main()
{
    std::cin >> s;
    std::cin >> length;
    result.resize(length, ' ');
    used.resize(s.length(), false);
    r(0);
    
    return 0;   
}
генерирует ВСЕ перестановки тоесть для 4 символов будет 4! вариантов. Не учитывает повторов

Добавлено через 5 минут
Цитата Сообщение от deph Посмотреть сообщение
есть массив. из него нужно получить все возможные варианты строк заданной длинной(пусть будет l),
это тоже делает. количество вариантов будет количество комбинаций из s.length() по length

Добавлено через 33 секунды
Цитата Сообщение от deph Посмотреть сообщение
и кол-во повторений элементов массива в строке не более n(порядок не важен,главное что бы не повторялись более чем n раз)
а это не совсем понял...

Добавлено через 2 минуты
насколько я понял то должно быть так:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <iostream>
#include <map>
#include <string>
#include <vector>
/////////////////////////////////////////////////////////////
int length;
int n;
std::string s;
std::string result;
std::vector<bool> used;
std::map<char, int> repeat;
/////////////////////////////////////////////////////////////
void buildMap()
{
    for(int i = 0; i < s.length(); i++)
        repeat.insert(std::make_pair(s.at(i), 0));  
}
 
void r(int now)
{
    if(now == length)
    {
        std::cout << result << std::endl;   
        return;
    }
 
    for(int i = 0; i < s.length(); i++)
        if(!used[i] && repeat.find(s.at(i))->second < n)
        {
            used[i] = true;
            repeat.find(s.at(i))->second++;
            result.at(now) = s.at(i);
            r(now+1);
            used[i] = 0;
            repeat.find(s.at(i))->second--;
        }
}
/////////////////////////////////////////////////////////////
int main()
{
    std::locale::global(std::locale(""));
    std::cout << "Ââåäèòå ñòðîêó:\n";
    std::cin  >> s;
    std::cout << "Ââåäèòå äëèГ*Г*Гі ГЈГҐГ*åðèðóåìîé ïîäñòðîêè:\n";
    std::cin  >> length;
    std::cout << "Ââåäèòå êîëè÷åñòâî ïîâòîðîâ îäèГ*Г*êîâûõ ñèìâîëîâ Гў ñòðîêå:\n";
    std::cin  >> n;
    
    buildMap();
    result.resize(length, ' ');
    used.resize(s.length(), false);
    r(0);
    
    return 0;   
}
deph
0 / 0 / 0
Регистрация: 28.07.2011
Сообщений: 7
29.07.2011, 16:04  [ТС]     Перебор #13
Mayonez, последний вариант то что нужно) я правда уже первую задачу решил) правда немного иначе) генерировал строки в файлы увеличивающийся длины. и сразу отсеивал неподходящие варианты. и в итоге получился один файл с набором строк и всеми возможными вариантами нужной мне длинны)
для второй задачи использую такой же метод, все массивы слил. и больше параметров сортировки сделал. Работает не так быстро как хотелось, но работает) спасибо)
Mayonez
380 / 272 / 20
Регистрация: 26.12.2009
Сообщений: 875
29.07.2011, 16:06     Перебор #14
deph, протестируйте, если это то, что надо, то перейду к второй задаче

Добавлено через 39 секунд
так уже не нужно?
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
29.07.2011, 18:06     Перебор
Еще ссылки по теме:

Оптимизировать перебор C++
C++ перебор значений
Перебор комбинаций C++
C++ Cделать перебор id-ов
Перебор C++

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

Или воспользуйтесь поиском по форуму:
deph
0 / 0 / 0
Регистрация: 28.07.2011
Сообщений: 7
29.07.2011, 18:06  [ТС]     Перебор #15
Mayonez, это то что нужно) спасибо) правда я вперед сделал, и работает медленней)
а по поводу второй, не много встрял с сортировкой. отсеивает и нужные варианты иногда.

Добавлено через 8 минут
Mayonez, я твою программку под вторую задачу освоил) так что не надо уже да) спасибо большое)
Yandex
Объявления
29.07.2011, 18:06     Перебор
Ответ Создать тему
Опции темы

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