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

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

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

Перебор - C++

28.07.2011, 18:21. Просмотров 1202. Ответов 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).
Помогите составить нормальный алгоритм перебора. Заранее спасибо.
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
28.07.2011, 18:21
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Перебор (C++):

Перебор - C++
Hi.мне нужно часть кода в котором перебирает все значение пример у нас 2 банки(на много литров),и 10 л воды.Нужно сделать все возможние...

Перебор чисел - C++
Здравствуйте. Допустим, есть у меня 2 числа (до 1000, например). Как мне перебрать все возможные комбинации произведений этих чисел? ...

Перебор комбинаций - C++
Доброго времени суток. Нашел в сети картинку - генератор речей. 4 столбика по 6 фраз в каждом. При переборе слева направо получается...

Перебор списка - C++
Всем привет. Задача: Перебрать все элементы списка(линейный однонаправленный), так что бы поучаствовали все элементы, но не было повторов...

Перебор комбинаций - C++
Здравствуйте! Возникла такая задача. Дан одномерный массив из N цифр,нужно составить все возможные комбинации чисел из этих цифр(числа...

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

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
ValeryLaptev
Эксперт С++
1041 / 820 / 48
Регистрация: 30.04.2011
Сообщений: 1,659
28.07.2011, 19:04 #2
deph, несколько вопросов.
1. Массив чего?
2. Элементы массива различны? Или есть одинаковые?
3. Размер массива какой? Больше-меньше L, больше-меньше n?
0
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 минуту
неужели ничем помочь никто не может?
0
easybudda
Модератор
Эксперт CЭксперт С++
9633 / 5581 / 948
Регистрация: 25.07.2009
Сообщений: 10,715
29.07.2011, 01:31 #4
Цитата Сообщение от deph Посмотреть сообщение
Занимаюсь программированием уже 6 лет.
И никаких идей? Хоть наброски покажите, как сделать пытались...
И примеры входных/выходных данных очень неплохо бы увидеть, а то уже с первого задания не понятно - все варианты из m байт по l байт такие, чтобы байт со значением x входил в l не больше, чем n раз? Так это Вам к математикам...
0
Jupiter
Каратель
Эксперт С++
6554 / 3975 / 226
Регистрация: 26.03.2010
Сообщений: 9,273
Записей в блоге: 1
Завершенные тесты: 2
29.07.2011, 01:32 #5
Цитата Сообщение от deph Посмотреть сообщение
неужели ничем помочь никто не может?
уточните задачу, специализируйте её для конкретного типа, а там глядишь и обобщенное решение найдется
0
deph
0 / 0 / 0
Регистрация: 28.07.2011
Сообщений: 7
29.07.2011, 02:22  [ТС] #6
Цитата Сообщение от easybudda Посмотреть сообщение
И никаких идей? Хоть наброски покажите, как сделать пытались...
И примеры входных/выходных данных очень неплохо бы увидеть, а то уже с первого задания не понятно - все варианты из m байт по l байт такие, чтобы байт со значением x входил в l не больше, чем n раз? Так это Вам к математикам...
я никогда переборами не занимался) в общем я пытался делать напрямую. с помощью рекурсии. но по параметрам проверку сделать нормально не могу. да и работает долго. после обеда кину то что делал.

Добавлено через 2 минуты
Цитата Сообщение от Maxwe11 Посмотреть сообщение
уточните задачу, специализируйте её для конкретного типа, а там глядишь и обобщенное решение найдется
есть две задачи. они обобщены конечно. но мне и обобщенное решение и нужно. соль в этом как раз. конкретику больше никакую тут представить не могу.
0
OstapBender
583 / 521 / 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 раз повторений.
0
deph
0 / 0 / 0
Регистрация: 28.07.2011
Сообщений: 7
29.07.2011, 02:32  [ТС] #8
OstapBender, это когда строка уже готова. вдобавок тут обрезание идет. суть в том что бы сразу генерировать набор строк такой, что бы повторений таких не было.

p.s.: в общем у меня по первой задачке идейка появилась. возможно если получиться от неё можно будет отскочить и ко второй задачке.
0
OstapBender
583 / 521 / 35
Регистрация: 22.03.2011
Сообщений: 1,585
29.07.2011, 02:36 #9
Цитата Сообщение от deph Посмотреть сообщение
суть в том что бы сразу генерировать набор строк такой, что бы повторений таких не было.
а что мешает сначала исключить повторения, а потом крутить вертеть строкой как хош.
0
deph
0 / 0 / 0
Регистрация: 28.07.2011
Сообщений: 7
29.07.2011, 02:44  [ТС] #10
OstapBender, то что перебрав все варианты. их будет очень много. т.е. работать будет долго. так реализовать то очень просто. нагенеровать сначала всевозможные варианты. а потом исключить варианты с повторениями. просто для l>15 время выполнения уже не хилое.
0
ValeryLaptev
Эксперт С++
1041 / 820 / 48
Регистрация: 30.04.2011
Сообщений: 1,659
29.07.2011, 09:46 #11
Цитата Сообщение от easybudda Посмотреть сообщение
И никаких идей? Хоть наброски покажите, как сделать пытались...
И примеры входных/выходных данных очень неплохо бы увидеть, а то уже с первого задания не понятно - все варианты из m байт по l байт такие, чтобы байт со значением x входил в l не больше, чем n раз? Так это Вам к математикам...
Да. Просто надо начинать смотреть с типа генерации перестановок. Алгоритмов в инете - дофига.
0
Mayonez
380 / 272 / 21
Регистрация: 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;   
}
1
deph
0 / 0 / 0
Регистрация: 28.07.2011
Сообщений: 7
29.07.2011, 16:04  [ТС] #13
Mayonez, последний вариант то что нужно) я правда уже первую задачу решил) правда немного иначе) генерировал строки в файлы увеличивающийся длины. и сразу отсеивал неподходящие варианты. и в итоге получился один файл с набором строк и всеми возможными вариантами нужной мне длинны)
для второй задачи использую такой же метод, все массивы слил. и больше параметров сортировки сделал. Работает не так быстро как хотелось, но работает) спасибо)
0
Mayonez
380 / 272 / 21
Регистрация: 26.12.2009
Сообщений: 875
29.07.2011, 16:06 #14
deph, протестируйте, если это то, что надо, то перейду к второй задаче

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

Добавлено через 8 минут
Mayonez, я твою программку под вторую задачу освоил) так что не надо уже да) спасибо большое)
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
29.07.2011, 18:06
Привет! Вот еще темы с ответами:

Перебор символов - C++
Есть такой хороший код для перебора символов: #include &quot;stdio.h&quot; #include &quot;windows.h&quot; #include &lt;conio.h&gt; int main(int argc,...

перебор значений - C++
Вывести на экран в возрастающем порядке все трехзначные числа, в десятичной записи которых нет одинаковых цифр.

Оптимизировать перебор - C++
Неделю учу С++, так что прошу не гадить. Надо уменьшить время работы. Задача: Вступление — Брат мой, Магистр Ордена хочет узнать...

Полный перебор - C++
Здравствуйте. Скорее всего, я пришел не по адресу и мне следовало бы задать свой вопрос где-нибудь в разделе алгоритмов, но не суть. Я всё...


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

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

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