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

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

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

Программа по резке труб - C++

24.07.2016, 18:44. Просмотров 1345. Ответов 35
Метки нет (Все метки)

Всем доброе время суток, помогите, пожалуйста, решить задачу (друг попросил написать программу,а сам осилить не могу). Парень работает в фирме, которая изготавливает двери для лифтов.
Задача: Есть трубы(заготовки)длину которых мы знаем(обычно 288 дюймов), есть ширина реза пилы, которую мы тоже знаем (обычно 0,18 дюйма).Ему порезать несколько таких заготовок,чтобы сделать тележку(количество и длины получаемых труб мы можем вводить каждый раз разные). Он вводит:
1. длину заготовки
2. ширину реза пилы
3. сколько труб и какой длины ему нужно получить
Конкретный пример:
1.Длина заготовки 288 дюймов
2. Ширина реза пилы 0,18 дюйма
3.Длина труб и их количество :
40 дюймов -3 шт
45 дюймов - 5 шт
42 дюйма - 6 шт
70 дюймов - 3 шт
52,5 дюйма - 2 шт
14,5 дюйма - 3 шт
Нужно,чтобы программа просчитала сколько нужно будет таких заготовок и оптимальную последовательность (в каком порядке нужно резать трубы,чтобы получить минимальный отход с каждой заготовки).
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
24.07.2016, 18:44
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Программа по резке труб (C++):

Выяснить, имеет ли место пересечение кусков труб - C++
Задача БОГ. Помогите, пожалуйста) У меня уйма вопросов. ------------------------------------ 5. Задача о пересечении труб. Для...

Как подготовить файл к плотерной резке - CorelDRAW
Друзья, подскажите как из этого файла сделать векторное изображение для плотерной резки (изготовление трафарета). Опишите алгоритм, чтоб я...

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

Алгоритм генерации труб - Алгоритмы
Всем привет! Создаю грушку похожую на эти: http://online-igra.com.ua/Truboprovod-na-vremya_uoH6Lqv ...

Приоритет труб на мнемосхеме - SCADA
На мнемосхеме пересекаются трубы с нефтью, газом, водой. Какую трубу сделать ниже, какую выше? смотрел ГОСТ 14202-69 "Трубопроводы...

Телескопическая стрела из набора труб - Механика
Вопрос по изготовлению телескопа. Например из квадратных труб. Т.е. 100х100 вставляем в 110х110х5(4), 110х110х5(4) в 120х120х5(4) т .д. В...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
_Ivana
3059 / 1746 / 151
Регистрация: 01.03.2013
Сообщений: 4,929
Записей в блоге: 2
24.07.2016, 19:18 #2
Цитата Сообщение от Hevzy86 Посмотреть сообщение
минимальный отход с каждой заготовки
критерий неформализованный. Ежу понятно, что если надо нарезать в общей длине 80 метров труб от двух заготовок по 50 метров (пренебрегая шириной реза для простоты), то отходов получим 20 метров. А как оптимальнее их распределить на 2 трубы - по 10 метров с каждой или 18 с одной и 2 с другой - это критерием не оговаривается.
Peoples
1157 / 661 / 421
Регистрация: 06.02.2016
Сообщений: 1,713
Записей в блоге: 11
Завершенные тесты: 4
24.07.2016, 19:22 #3
Hevzy86, Допустим для этого примера материала надо: 40*3+45*5+42*6+70*3+52,2*2+14,5*3=954,9 дюймов надо. Заготовка 288 дюймов, значит 954,9/288=3,315, получается, если округлить 4 заготовки, отходов 197,1 дюйм. Разъясните момент с шириной реза, что это и как влияет на отход, или на что-нибудь и про то, что подразумевается под оптимальностью?
Hevzy86
0 / 0 / 0
Регистрация: 24.07.2016
Сообщений: 22
24.07.2016, 19:31  [ТС] #4
Peoples, Как мне объяснил "заказчик", распределение резки труб и является важным(чтоб получить наименьший остаток), извиняюсь, может я не совсем точно описал задачу

Добавлено через 2 минуты
_Ivana, ширину реза надо добавлять к каждой отрезанной трубе, т.к. это ширина самой пилы и, соответственно, эта ширина реза каждый раз когда пила режет металл, просто отнимается от исходной заготовки. Оптимальностью является то,чтобы с каждой заготовки было как можно меньше отходов(т.е. как можно меньше металла выбрасывалось)
IGPIGP
Комп_Оратор)
Эксперт по математике/физике
6447 / 3094 / 306
Регистрация: 04.12.2011
Сообщений: 8,567
Записей в блоге: 4
24.07.2016, 19:44 #5
Цитата Сообщение от Hevzy86 Посмотреть сообщение
(в каком порядке нужно резать трубы,чтобы получить минимальный отход с каждой заготовки
Это неправильное условие (имхо). Наиболее рационально получить:
Цитата Сообщение от Hevzy86 Посмотреть сообщение
минимальный отход с каждой заготовки
кроме последней. То есть, вариант когда на 10 заготовок пришлось в среднем по 20'' отхода, хуже чем если весь отход пришёлся на последнюю заготовку и составил 200''. Так конечно не бывает и по заготовкам будет по мелочи какой-то отход тоже, но нужно стремиться к тому, чтобы отход последней заготовки (последней - для определённости, главное что одной) был максимален.
При такой постановке это вполне рутинная задача.
Цитата Сообщение от Hevzy86 Посмотреть сообщение
ширину реза надо добавлять к каждой отрезанной трубе
Если нужно n кусков, то будет n-1 резов. То есть, не на каждую. Но это не страшно.
Hevzy86
0 / 0 / 0
Регистрация: 24.07.2016
Сообщений: 22
24.07.2016, 19:57  [ТС] #6
IGPIGP,можно и так попробовать,как вы говорите, думаю,неплохо будет. Но у меня знаний и практики не хватает,как это реализовать(если поможете,буду рад), а насчет n-1 резов, согласен
Peoples
1157 / 661 / 421
Регистрация: 06.02.2016
Сообщений: 1,713
Записей в блоге: 11
Завершенные тесты: 4
24.07.2016, 22:31 #7
Не уверен в правильности, надо тестировать
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
61
62
63
64
65
66
#include<iostream>
#include<vector>
#include <cmath>
#include <algorithm>
using namespace std;
int main() {
    setlocale(LC_ALL,"RUS");
    vector<double>val; // вектор дюймов
    vector<int>v; // вектор штук
    vector<double>sum; // сумма дюймов, то есть дюймы* количество 
    // начало
    double zagotovka; // длина заготовки
    double raz;   // длина реза 
    cout<<"Введите длину заготовки: "<<endl;
    cin>>zagotovka;
    cout<<"Введите ширину реза: "<<endl;
    cin>>raz;
    cout<<"Введите сколько категорий труб будет: "<<endl;  // сколько вариант труб разных дюймов 
    int t;
    cin>>t;
    for(int i=0; i<t; i++) {       // вводим данные 
        double dl; 
        double st;
        cout<<"Введите длину трубы: "<<endl;
        cin>>dl;
        val.push_back(dl);
        cout<<"Введите сколько таких труб надо : "<<endl;
        cin>>st;
        v.push_back(st);
        cout<<endl;
    }
 
    for(int i=0; i!=val.size(); i++) {    // сумма длин каждого вида трубы 
        sum.push_back(val[i]*v[i]);
    }
    cout<<endl;
    double s=0;
    for(vector<double>::iterator i=sum.begin(); i!=sum.end(); i++) {     // вся длинна которая нужна для труб 
        s+=*i;
        cout<<*i<<" ";
    }
    int kol=ceil(s/zagotovka);    // количество заготовок, длина которая нужна делится на длину заготовки, округляется до большего, ессли ровного количества не хватит
    double ost=((kol*zagotovka)-s)-((val.size()-1)*raz); // отход с вычетом длины реза 
    double m=zagotovka; // отсюда отпиливаем
    double g=0; // столько отпиливаем
    int coo=0; // счётчик
    cout<<endl;
    for(int i=0; i<kol; i++) {
        do {
            vector<double>::iterator it=min_element(sum.begin(),sum.end());
            g+=*it;
            for(int i=0; i<val.size(); i++)
                if(val[i]*v[i]==*it) {
                    cout<<val[i]<<" Дюйма "<<v[i]<<" штуки"<<endl;     // выводим оптимальный вариант 
                    cout<<endl;
                }
            sum.erase(it);
            m-=g;
            coo++;
        } while(m>0 && g<zagotovka);
    }
    cout<<endl;
    cout<<"Заготовок нужно: "<<kol<<endl;
    cout<<"Отход: "<<ost<<endl;
    return 0;
}
Hevzy86
0 / 0 / 0
Регистрация: 24.07.2016
Сообщений: 22
24.07.2016, 23:56  [ТС] #8
Peoples, Спасибо большое,потсетирую,потом отпишусь о результате
Mr.X
Эксперт С++
3049 / 1694 / 265
Регистрация: 03.05.2010
Сообщений: 3,867
25.07.2016, 14:49 #9
Hevzy86, на самом деле результат еще зависит от количества тележек, которые вы собираетесь изготовить. А об этом у вас вообще не упомянуто. Или имеется в виду серийное производство?
IGPIGP
Комп_Оратор)
Эксперт по математике/физике
6447 / 3094 / 306
Регистрация: 04.12.2011
Сообщений: 8,567
Записей в блоге: 4
25.07.2016, 15:09 #10
Цитата Сообщение от Hevzy86 Посмотреть сообщение
IGPIGP,можно и так попробовать,как вы говорите
Я говорил не обдумав как следует:
Цитата Сообщение от IGPIGP Посмотреть сообщение
При такой постановке это вполне рутинная задача.
Пока подавив в пермутациях (перестановках) копии и реверсивные копии, удалось значительно снизить количество вариантов (от N! ),
но всё едино программа получилась очень чувствительна к количеству частей (особенно различных частей). Установив стек 4M в течении 10-ти минут (точнее не мерял) получаю
три заготовки:
40, 40, 42, 42, 52.5, 70 (286.5 в дет. +0.9 рез = 287.4)
45, 45, 52.5, 70, 70 (282.5 в дет + 0.72 рез = 283.22)
40 (40.18)
Это при вводе для 288/0,18 (заготовка/рез)
и наборе выходных деталей:
3X40,
2X45,
2X42,
3X70,
2X52.5

5 разновидностей деталей общим количеством 12 шт. Общее количестао перестановок 12!=479,001,600, но с учётом некоторой (вышеописанной) оптимизации, удалось оставить только 831600, то есть в 576 раз сократить. Иначе не времени ни стека не хватило бы.
Я решал на скорую руку и методом грубой силы, да и не математик я. Думаю тут требуется более изощрённое матобеспечение, логика и... многопоточность. Кроме всего, применение float, - слишком уж большая роскошь и имеет смыл переходить к челоцисленным вычислениям.
Поскольку 4-х значащих цифр тут вполне хватает то Uint16 должно хватить для отображения входных параметров. Тогда должно быть легче т.к. оно вдвое короче чем float.
Hevzy86
0 / 0 / 0
Регистрация: 24.07.2016
Сообщений: 22
27.07.2016, 00:51  [ТС] #11
Mr.X, их может быть несколько(но не серийное производство)

Добавлено через 7 минут
IGPIGP, спасибо большое за помощь, так то да, быстродействие оч. сильно зависит от кол-ва частей. А можно попросить новый код(который с оптимизацией,хочу его тоже погонять)? Сегодня будем тестировать с "заказчиком" на реальных примерах, я потом отпишусь.

P.S. извиняюсь, что так долго не выходил на связь, основной работы было много
IGPIGP
Комп_Оратор)
Эксперт по математике/физике
6447 / 3094 / 306
Регистрация: 04.12.2011
Сообщений: 8,567
Записей в блоге: 4
27.07.2016, 09:12 #12
Цитата Сообщение от Hevzy86 Посмотреть сообщение
IGPIGP, спасибо большое за помощь, так то да, быстродействие оч. сильно зависит от кол-ва частей.
Не за что. Мне было интересно порешать задачку, которая так простенько формулируется и внешне выглядит так буднично, как покраска водосточной трубы. А суть достаточно непроста. Тут недавно как раз пришлось встретить противоположность. Несложная задача, невозможная в жизни и очень претенциозно сформулированная. Ну я там и высказался:
Не могу разобраться с алгоритмом деления романа на отдельные тома
Неясно лишь вот что:
Цитата Сообщение от Hevzy86 Посмотреть сообщение
помогите, пожалуйста, решить задачу (друг попросил написать программу,а сам осилить не могу). Парень работает в фирме, которая изготавливает двери для лифтов.
Почему же программист не увидел сложности вычислений и не обосновал сокращения ТЗ?
Цитата Сообщение от Hevzy86 Посмотреть сообщение
А можно попросить новый код(который с оптимизацией,хочу его тоже погонять)?
Его нужно подчистить. А главное, он не решает задачу. Достаточно приличный комп не осиливает программу с 13 деталями из 5-ти разновидностей. Так что 12/5 и всё, а это не укладывается в ТЗ, ведь там 22/6(!).
Да и не программист я. По образованию. Будет странно если мой код сойдёт программисту "за отмазку". И я нос задеру. Я себя знаю. В сомнениях я весь, короче.
_Ivana
3059 / 1746 / 151
Регистрация: 01.03.2013
Сообщений: 4,929
Записей в блоге: 2
27.07.2016, 16:58 #13
IGPIGP, есть простейший жадный алгоритм, который в общем случае может не гарантировать оптимальность по какому-либо критерию, но в данном случае имхо устроит ТС и его заказчика на все 100, и будет работать очень быстро для большого количества данных. Реализовывать не хочу, чтобы не помогать халявщику зарабатывать чужими руками и мозгами. Суть - берем первую трубу (или обрезок - если на складе есть остатки обрезков с прошлого раза) и имея требуемые размеры деталей с их количеством, честно и оптимальным образом выбираем ее заполнение деталями - чтобы остаток был минимален. Потом берем вторую трубу/обрезок и т.д. пока детали не кончатся.
IGPIGP
Комп_Оратор)
Эксперт по математике/физике
6447 / 3094 / 306
Регистрация: 04.12.2011
Сообщений: 8,567
Записей в блоге: 4
27.07.2016, 18:11 #14
Цитата Сообщение от _Ivana Посмотреть сообщение
IGPIGP, есть простейший жадный алгоритм,
_Ivana, компромиссных стратегий может быть много. Но они не гарантируют наиболее оптимального результата. Мне в моей реализации пока мешает невозможность вызвать перестановку по её номеру. Нужно все перебрать (выбраковывая кучу ненужных), пока не дойдёшь до нужного номера. Просто хочется самому сесть и накатать void permutation<T>(it_beg, it_end, size_t perm_number)
А из стратегий можно бы применить и такую: сортируем по убыванию и выбираем с головы пока не поместится. Непоместившийся возвращаем и берём следующий. Пока не заполним заготовку. С каждой заготовкой голова остатка должна мельчать и манёвренность при заполнении больше. Так рюкзаки наполнять легче всего когда есть гора снаряжения всякого.
_Ivana
3059 / 1746 / 151
Регистрация: 01.03.2013
Сообщений: 4,929
Записей в блоге: 2
27.07.2016, 21:32 #15
IGPIGP, тогда сразу выплывает несколько вопросов

1) а нужен ли гарантированно оптимальный алгоритм, если он будет делать полный перебор (после всех возможных предварительных отсечений) и будет экспоненциальной сложности? Т.е. добавление одной заготовки увеличит время расчета в 2 раза, и при паре десятков он будет считаться часами? Народ поэтому и придумывает всякие отжиги/муравьев/генетические/жадные и т.п., которые не дают 100% гарантии оптимальности, но дают 99.9....%, а считаются за разумное время. Мне кажется, бизнесмен по постройке лифтов переживет мизерную вероятность неоптимальности

2) по поводу оптимальности, раз уж мы о ней так печемся вот допустим остаток 40 единиц. Что оптимальнее - 10+10+10+10 или 19+7+7+7? Второй вариант, говорите? Хорошо, а 19+7+7+7 и 19+9+6+6? Снова второй? А 19+9+6+6 и 19+9+8+4? Если продолжать, то мы упремся как раз в мой жадный алгоритм, написанный постом выше, гарантирующий минимум каждого следующего остатка, но не гарантирующий общий суммарный минимум (вот такой каламбурчик, да). А ваш критерий максимума максимального остатка не различает все варианты с девятнашками, так что критерий оптимальности придется формализовать строже. И это еще мы не рассматриваем входящие обрезки в качестве исходных труб, а считаем, что у нас всегда только полные новые трубы.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
27.07.2016, 21:32
Привет! Вот еще темы с ответами:

Описать информацию о количестве обсадных труб скважины - Delphi
Имеется задание: Объявить в Delphi класс, позволяющий объекту хранить информацию о количестве обсадных труб скважины. Предусмотреть в...

Определить давление и температуру после соединения труб - Термодинамика и МКТ
Доброго дня. Я программист. Помогите, пожалуйста, решить 2 наверное несложные задачки из школьного курса. Формулы крутятся в голове, но...

Как реализовать угловой градиент для труб - Photoshop
Здравствуйте! в фотошопе разбираюсь довольно хорошо, но вот возникла проблема, которую я не в силах решить самостоятельно, сколько не...

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


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

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

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