Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Mk_Man
0 / 0 / 0
Регистрация: 22.01.2015
Сообщений: 26
#1

Вывести все возможные варианты разреза трубы

07.02.2015, 00:03. Просмотров 489. Ответов 6
Метки нет (Все метки)

Вводится длина трубы, количество заготовок (1, 2, 3, 4 ил 5), которые можно вырезать из трубы, и длина каждой заготовки. Вывести все возможные варианты разреза трубы.

Например:
Вводим размер трубы - 100
Количество заготовок - 2
Размер первой заготовки - 60
Размер второй заготовки - 30
Получаем:
1) 60 + 30
2) 30 + 30
3) 30 + 30 + 30


помогите решить=)
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
07.02.2015, 00:03
Ответы с готовыми решениями:

Вывести все возможные варианты перестановок от 1 до n
Здравствуйте, у меня есть массив чисел от 1 до n, нужно чтобы выводились все...

Структуры. Вывести все возможные варианты покупки товаров
может кто нибудь помочь составить прогу /* с++ */ 1) С клавиатуры вводятся...

Перебор возможных вариантов разреза трубы
Доброго времени суток! Есть задача:"Вводится длина трубы, количество заготовок...

Рассчитать все возможные варианты для 3 знаков
Дано: 1 2 0 Найти все возможные комбинации 10 разрядного числа (пример:...

Все возможные варианты перестановки символов строки
Дана строка s, состоящая из n символ (n меньше 6) составить все возможные...

6
rao
858 / 415 / 158
Регистрация: 02.04.2014
Сообщений: 1,201
07.02.2015, 13:29 #2
Самое простое решение: рекурсивно перебрать все варианты комбинаций заготовок, проверяя их на допустимость длины. Функция перебора вариантов:

C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void GenerateVariants(string sPrefix, int iMaxLength)
{
    string sOutStr;
 
    for (int iCurType = 0; iCurType < iMaxLength; iCurType++)
    {
        stringstream sCurPref;
        sCurPref << sPrefix << iCurType;
        sOutStr = sCurPref.str();
 
        if (sCurPref.str().length() < iMaxLength)
        {   // Рекурсивные вызовы генерации подвариантов:
            GenerateVariants(sCurPref.str() , iMaxLength);
        } else
        {
            cout << "Current Preffix: " << sCurPref.str() << '\n';
        }
    }
}
 
int iArrayDimensions = 5;
GenerateVariants("", iArrayDimensions);
Результат перебора сохранять куда-нибудь в список, элементы которого сортировать, игнорировать повторяющиеся комбинации (вроде 0-0-1-1-2 и 1-0-1-0-2 и т.п.), после чего, оставшиеся уникальные комбинации проверить на "влезаемость" в размер.
1
Mk_Man
0 / 0 / 0
Регистрация: 22.01.2015
Сообщений: 26
07.02.2015, 14:14  [ТС] #3
rao, а как на ++ написать
C
1
2
sCurPref << sPrefix << iCurType;
        sOutStr = sCurPref.str();
0
rao
858 / 415 / 158
Регистрация: 02.04.2014
Сообщений: 1,201
07.02.2015, 14:55 #4
Mk_Man, "++" подразумевает применение объектно-ориентированного подхода, а не конкретного синтаксиса или используемых типов данных. Т.е. не совсем понятно, что ты имеешь в виду?
Кстати, переменная sOutStr нужна только для отладки.
0
Mk_Man
0 / 0 / 0
Регистрация: 22.01.2015
Сообщений: 26
07.02.2015, 16:04  [ТС] #5
rao, если не тяжело, - объясните, что вы делаете в каждой строчке кода
0
nmcf
6267 / 5575 / 2535
Регистрация: 14.04.2014
Сообщений: 23,468
07.02.2015, 16:33 #6
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
56
57
58
59
60
#include <cstdlib>
#include <iostream>
#include <locale>
#include <vector>
#include <algorithm>
 
using std::cout;
using std::cin;
using std::endl;
using std::locale;
 
 
unsigned L; // длина трубы
std::vector<unsigned> parts; // длины заготовок
std::vector<unsigned> r; // текущий вариант
std::vector< std::vector<unsigned> > result; // варианты разреза трубы
 
void f(size_t i, unsigned l)
{
    for (size_t j = (i == parts.size() - 1) ? (L - l) / parts[i] : 0; j <= (L - l) / parts[i]; ++j)
    {
        r.push_back(j);
        if (i == parts.size() - 1) result.push_back(r);
        else f(i + 1, l + parts[i] * j);
        r.pop_back();
    }
}
 
int main()
{
    locale::global(locale(""));
 
    cout << "Длина трубы: ";
    cin >> L;
    cout << "Количество заготовок: ";
    int n;
    cin >> n;
    cout << "Длины заготовок: ";
    for (int i = 0; i < n; ++i)
    {
        unsigned p;
        cin >> p;
        parts.push_back(p);
    }
    std::sort(parts.rbegin(), parts.rend());
 
    f(0, 0);
 
    cout << "Варианты:" << endl;
    for (std::vector<unsigned> &v : result)
    {
        for (size_t i = 0; i < parts.size(); ++i)
            if (v[i] > 0)
                cout << parts[i] << "*" << v[i] << "  ";
        cout << endl;
    }
 
    cout << endl;
    system("pause");
}
Выводятся только такие варианты, при которых остаток трубы меньше самой маленькой заготовки
0
Миниатюры
Вывести все возможные варианты разреза трубы  
rao
858 / 415 / 158
Регистрация: 02.04.2014
Сообщений: 1,201
07.02.2015, 16:44 #7
не тяжело, но как же ты дальше то справишься?
строка 8: формируется строчка вида "ххххх", где х - тип заготовки. (Например 0 - длинна 60, 1 - длинна 30 и т.д.)
На первой итерации исходная строка sPrefix пустая. Цикл (строка 5) для каждого номера типа вызывает GenerateVariants(...), "наращивая" эту строку. Каждый вложенный вызов функции добавляет к строке один разряд. Визуально процесс можно представить в виде дерева. От "ствола" (т.е. пустой строки) отходит 5 ветвей: строки "0", "1", "2" и т.д. Каждая ветвь, в свою очередь, делится еще на 5 ветвей: строки "00", "01", "02" и т.д. (на ветви "0"), строки "10", "11", "12" и т.д. (на ветви "1"). и так до самого конца. В результате охватывается весь пятимерный массив вариантов.
0
07.02.2015, 16:44
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
07.02.2015, 16:44

Получить все возможные варианты загрузки ящиков
На перевозку 800 кг овощей с базы подготовлены ящики. В них можно загрузить по...

Определить все возможные варианты выплаты суммы N монетами 2 5 10
Нужно написать программу на С++ в консольным режиме.Пользователь вводит...

Как подсчитать все возможные варианты суммы массива
Допустим у нас есть целое число N и массив состоящий из целых чисел, и надо...


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

Или воспользуйтесь поиском по форуму:
7
Ответ Создать тему
Опции темы

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