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

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

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

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

24.07.2016, 18:44. Просмотров 1217. Ответов 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++ Выяснить, имеет ли место пересечение кусков труб

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
IGPIGP
Комп_Оратор)
Эксперт по математике/физике
6413 / 3052 / 300
Регистрация: 04.12.2011
Сообщений: 8,273
Записей в блоге: 3
30.07.2016, 20:35     Программа по резке труб #21
Цитата Сообщение от Hevzy86 Посмотреть сообщение
IGPIGP, программа работает(особенно мне понравилась скорость)
То что у меня получилось работает медленно. И это моя вина так как не было времени . Но я не показывал ничего, так что это не мне спасибо.
_Ivana
2840 / 1665 / 143
Регистрация: 01.03.2013
Сообщений: 4,765
Записей в блоге: 2
30.07.2016, 21:25     Программа по резке труб #22
Цитата Сообщение от Hevzy86 Посмотреть сообщение
ну не то что халявщик, я не лентяй
Цитата Сообщение от Hevzy86 Посмотреть сообщение
как мне кажется,это метод простого перебора всех вариаций для каждой трубы, так? Если да,то он будет медленно работать(при добавлении каждой новой трубы количество вариантов,которых надо перебрать увеличивается в десятки раз
Предлагаю квест - вы пишете (с помощью форума, друзей или самостоятельно) ваш вариант программы, как будет готов - упоминаете меня в этой ветке, я набросаю реализацию своего алгоритма, и мы сравним результаты и скорость на разных объемах входных данных.
Hevzy86
0 / 0 / 0
Регистрация: 24.07.2016
Сообщений: 22
30.07.2016, 22:41  [ТС]     Программа по резке труб #23
_Ivana, заманчивое предложение, если что-то путное сделаю, обязательно так и поступлю

Добавлено через 2 минуты
IGPIGP, да, точно Peoples, помог, за что ему спасибо, его вариант сейчас тестирую
IGPIGP
Комп_Оратор)
Эксперт по математике/физике
6413 / 3052 / 300
Регистрация: 04.12.2011
Сообщений: 8,273
Записей в блоге: 3
31.07.2016, 20:35     Программа по резке труб #24
Цитата Сообщение от _Ivana Посмотреть сообщение
Предлагаю квест
Можно ваще соревнование объявить. "Ударим трубопроводом, по бездорожью и разгильдяйству!"
Программу писать тяжело. Я посидел, погрыз карандаш и быстро нашёл вариант порезки тестового набора от ТС:
1-я заготовка:
3х14,5
2х40
1х45
2х52,5
_______273,5
2-я заготовка:
1х40
4х42
1х700
_______278,0
3-я заготовка:
3х45
2х700
_______275,0
4-я заготовка:
2х42
1х45
_______129,0 (остаток 159,0)

Кто лучше разрежет?
_Ivana
2840 / 1665 / 143
Регистрация: 01.03.2013
Сообщений: 4,765
Записей в блоге: 2
31.07.2016, 22:09     Программа по резке труб #25
Цитата Сообщение от IGPIGP Посмотреть сообщение
Кто лучше разрежет?
Ну вот так режет мой кот на коленке (ширину распила специально не учитывал, но ее учесть раз плюнуть - у вас она тоже явно не учтена, хотя может для этого вы и оставляли сопли обрезков с каждой трубы)
Код
1-я заготовка:
4 * 42
3 * 40
Итого 288, остаток 0

2-я заготовка:
1 * 70
2 * 52.5
2 * 42
2 * 14.5
Итого 288, остаток 0

3-я заготовка:
2 * 70
3 * 45
Итого 275, остаток 13

4-я заготовка:
2 * 45
1 * 14.5
Итого 104.5, остаток 183.5
Compilation time: 0.32 sec, absolute running time: 0.14 sec, cpu time: 0 sec
IGPIGP
Комп_Оратор)
Эксперт по математике/физике
6413 / 3052 / 300
Регистрация: 04.12.2011
Сообщений: 8,273
Записей в блоге: 3
31.07.2016, 22:16     Программа по резке труб #26
Цитата Сообщение от _Ivana Посмотреть сообщение
хотя может для этого вы и оставляли сопли обрезков с каждой трубы
Это не я. Это программа. Если бы я, действительно, стал карандаш кушать, то уже многовато бы съел.
Толщину реза надо учесть не потому, что кто-то там на мехножовке будет материться. Им там не впревой. А потому, что иначе не сравнить нам наши карандаши.
_Ivana
2840 / 1665 / 143
Регистрация: 01.03.2013
Сообщений: 4,765
Записей в блоге: 2
31.07.2016, 22:27     Программа по резке труб #27
Я думал вы и вправду карандашом на бумажке решили прикинуть Щас учту ширину распила, каминг сун

Обещанный каминг сун Что скажете?
Код
1-я заготовка:
2 * 70
2 * 52.5
1 * 42
Итого (с учетом ширины разреза) 287.9, остаток 0.1

2-я заготовка:
3 * 45
1 * 42
2 * 40
2 * 14.5
Итого (с учетом ширины разреза) 287.44, остаток 0.56

3-я заготовка:
1 * 70
2 * 45
3 * 42
Итого (с учетом ширины разреза) 287.08, остаток 0.92

4-я заготовка:
1 * 42
1 * 40
1 * 14.5
Итого (с учетом ширины разреза) 97.04, остаток 190.96
Compilation time: 0.32 sec, absolute running time: 0.13 sec, cpu time: 0 sec
IGPIGP
Комп_Оратор)
Эксперт по математике/физике
6413 / 3052 / 300
Регистрация: 04.12.2011
Сообщений: 8,273
Записей в блоге: 3
31.07.2016, 22:40     Программа по резке труб #28
Цитата Сообщение от _Ivana Посмотреть сообщение
Обещанный каминг сун
Это просто ал би бэк... Как минимум. Я бы даже сказал, - туби континьед. Методом обрезания.
Просто отличный результат.
_Ivana
2840 / 1665 / 143
Регистрация: 01.03.2013
Сообщений: 4,765
Записей в блоге: 2
31.07.2016, 22:47     Программа по резке труб #29
Мне тоже так кажется Мы еще не сравнивали время наших вариантов, но мне мой кот с болгаркой нравится

Хотя я при описании алгоритма предупреждал, что он не гарантирует минимум последнего обрезка - в этом можно убедиться, если сравнить приведенные выше результаты для нулевой ширины разреза: последний обрезок меньше, чем при ненулевой ширине разреза. Это связано с жадностью кота - очень он уж любит каждую очередную трубу наиболее оптимальным образом распиливать. Но зато весьма быстро это делает, можем закинуть побольше деталей . А эпизодическая неоптимальность имхо заказчика должна устроить.
Hevzy86
0 / 0 / 0
Регистрация: 24.07.2016
Сообщений: 22
31.07.2016, 23:07  [ТС]     Программа по резке труб #30
ельный просмотр
Доброе время суток, товарищи, мой друг предложил вариант перебора всех вариантов последовательностей( в примере 13 деталей) работает оч. медленно(минут 20-25 у меня), и я сам не понимаю до конца логику его работы(не пойму как тут рекурсия работает)
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
// _solution.cpp : Defines the entry point for the console application.
//
 
#include "stdafx.h"
#include <conio.h>
#include <windows.h>
#include "iostream"
#include <cstdlib>
const unsigned long long n = 13;
using namespace  std;
unsigned long long total = 0;
int used[n], a[n];
 
void generate( unsigned long long x) 
{
  int i;
  if(x == n)
  {     total++; 
    //cout<<"x= "<< x << endl;
  }
  else
    for(i = 0; i < n; ++i)
      if(!used[i]) {
       // cout<<"used[i]= "<< used[i] << endl;
        used[i] = 1;
        a[x] = i + 1;
        generate(x + 1);
        used[i] = 0;
      }
}
 
int main() {
 
  for(int i = 0; i < n; ++i)
    used[i] = 0;
 
  generate(0);
  
  printf("done - %llu", total);
  Beep (659.26,200);
          Beep (659.26,200);
          Sleep (200);
          Beep (659.26,200);
          Sleep (100);
          Beep (523.26,200);
          Beep (659.26,200);
          Sleep(200);
          Beep (783.98,200);
          Sleep(400);
          Beep (391.99,200);
  getch();
  
    return 1;
}
AVIK
13 / 13 / 5
Регистрация: 02.01.2014
Сообщений: 59
31.07.2016, 23:44     Программа по резке труб #31
есть у меня такой быдлокод в завалах, поанализируй Transposition build(boost::multiprecision::cpp_int number, int size), это оно (принимает номер перестановки и количество элементов в ней)

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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <iterator>
#include <algorithm>
#include <cstdint>
 
#include <boost/multiprecision/cpp_int.hpp>
#include <boost/lexical_cast.hpp>
 
class Transposition
{
private:
    std::vector<int> __data;
public:
    Transposition(std::vector<int> data) : __data(data) {}
    Transposition(): __data(std::vector<int>()) {}
    size_t get_size()
    {
        return __data.size();
    }
    std::vector<int> get_data()
    {
        return __data;
    }
    friend std::ostream & operator << (std::ostream & output_stream, Transposition & TR)
    {
        std::copy(TR.__data.begin(), TR.__data.end(), std::ostream_iterator<int>(output_stream, " "));
        return output_stream;
    }
    friend std::istream & operator >> (std::istream & input_stream, Transposition & TR)
    {
        std::copy(std::istream_iterator<int>(input_stream), std::istream_iterator<int>(), back_inserter(TR.__data));
        return input_stream;
    }
    friend bool operator == (Transposition & __1, Transposition & __2)
    {
        if(__1.get_size() != __2.get_size())
            return false;
        for(size_t i = 0; i < __1.get_size(); i++)
            if(__1.__data[i] != __2.__data[i])
                return false;
        return true;
    }
    friend bool operator < (Transposition & __1, Transposition & __2)
    {
        for(size_t i = 0; i < std::min(__1.get_size(), __2.get_size()); i++)
            if(__1.__data[i] < __2.__data[i])
                return true;
            else
                if(__1.__data[i] > __2.__data[i])
                    return false;
        return __1.get_size();
    }
    friend Transposition operator * (Transposition & __1, Transposition & __2)
    {
        std::vector<int> result_data(__1.get_size());
        for(size_t i = 0; i < result_data.size(); i++)
            result_data[i] = __1.__data[__2.__data[i] - 1];
        return Transposition(result_data);
    }
};
 
class TranspositionBulder
{
private:
    std::map<int, boost::multiprecision::cpp_int> factorial_cache;
    boost::multiprecision::cpp_int factorial(int d)
    {
        if(d <= 1)
            return boost::multiprecision::cpp_int(1);
        else
        {
            std::map<int, boost::multiprecision::cpp_int>::iterator iter = factorial_cache.find(d);
            if(iter != factorial_cache.end())
                return iter->second;
            else
            {
                factorial_cache[d] = d * factorial(d - 1);
                return factorial_cache[d];
            }
        }
    }
    std::vector<int> build_recursion(boost::multiprecision::cpp_int number, int size)
    {
        if(number >= factorial(size))
            return std::vector<int>(size, 0);
        if(size == 0)
            return std::vector<int>();
        else
        {
            std::vector<int> result, tmp;
            result.push_back(boost::lexical_cast<int>(number / factorial(size - 1)));
            tmp = build_recursion(number % factorial(size - 1), size - 1);
            std::copy(tmp.begin(), tmp.end(), std::back_inserter(result));
            return result;
        }
    }
 
public:
    Transposition build(boost::multiprecision::cpp_int number, int size)
    {
        std::vector<int> buffer = build_recursion(number, size);
        std::set<int> used;
        for(int i = 0; i < size; i++)
            used.insert(i);
        std::vector<int> result;
        for(int i = 0; i < size; i++)
        {
            std::set<int>::iterator it = used.begin();
            for(int j = 0; j < buffer[i]; j++)
                it++;
            result.push_back(*it);
            used.erase(it);
        }
        for(std::vector<int>::iterator it = result.begin(); it != result.end(); it++)
            (*it)++;
        return Transposition(result);
    }
    boost::multiprecision::cpp_int get_index(Transposition TR)
    {
        boost::multiprecision::cpp_int index = 0;
        std::vector<int> data = TR.get_data();
        for(size_t i = 0; i < TR.get_size(); i++)
        {
 
        }
        return index;
    }
};
IGPIGP
Комп_Оратор)
Эксперт по математике/физике
6413 / 3052 / 300
Регистрация: 04.12.2011
Сообщений: 8,273
Записей в блоге: 3
31.07.2016, 23:45     Программа по резке труб #32
Представленный вариант считался с толщиной реза 1,8 вместо 0,18. Ошибся при перводе в целые.
Цитата Сообщение от _Ivana Посмотреть сообщение
Мы еще не сравнивали время наших вариантов
Время у меня грустное - около 3-х минут. Но что ещё обиднее, несмотря на то, что перебираю всё (и даже много лишнего), но результат хуже. Неверно подсчитываю критерий выбора. Нужно подумать.
Вот вариант где всё очень похоже на правду, но чуть хуже чем у Вас:
3x14,5
3x40
1x52,5
1x70
____________287,26
3x42
2x45
1x70
____________286,9
3x42
2x45
1x70
____________286,9
45
52,5
___________97,86 (тут 2 реза так как деталей 3 штуки - две выходные и остаток)
Буду думать бэк.
_Ivana
2840 / 1665 / 143
Регистрация: 01.03.2013
Сообщений: 4,765
Записей в блоге: 2
31.07.2016, 23:51     Программа по резке труб #33
Цитата Сообщение от IGPIGP Посмотреть сообщение
Но что ещё обиднее, несмотря на то, что перебираю всё (и даже много лишнего), но результат хуже.
Звучит действительно забавно

Ладно, свой тривиальный алгоритм я в деталях уже рассказал. Если будут еще входные данные - пишите, напилим
ЗЫ и ссылка тут пробегала вроде грамотная, хоть сам и не читал (чукча не читатель )
Hevzy86
0 / 0 / 0
Регистрация: 24.07.2016
Сообщений: 22
04.08.2016, 01:17  [ТС]     Программа по резке труб #34
Доброе время суток, извиняюсь за долгое отсутствие(тяжелая физическая работа-не всегда есть время и силы на компьютер)IGPIGP, 3 минуты это гораздо лучше,чем 25, уже хорошо) Вот вариант от Peoples (работает быстро, фишка,что он собирает сначала наименьшую длину труб и пилит их по возрастающей)
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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#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)-((t-1)*raz); // отход с вычетом длины реза 
    double m=zagotovka; // отсюда отпиливаем
    double g=0; // столько отпиливаем
    // счётчик
    cout<<endl;
    vector<double>otx;
      vector<int>ot;
    for(int i=0; i<kol; i++) {
         int coo=0;
        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;
                }
                  otx.push_back(*it);
            sum.erase(it);
            m-=g;
            coo++;
        } while(m>0 && g<zagotovka);
         ot.push_back(coo);
    }
    cout<<endl;
    cout<<"Заготовок нужно: "<<kol<<endl;
    cout<<"Отход: "<<ost<<endl;
    cout<<endl;
    vector<double> dss;
    int q=0;
    for(vector<int>::iterator  i=ot.begin();i!=ot.end();i++){
        double ss=0;
    for(vector<double>::size_type iter=q;iter!=q+*i;iter++){
        ss+=otx[iter]+raz;
    }
    q+=*i;
    dss.push_back(ss);
}
   cout<<endl;
   for(vector<double>::size_type iter=0;iter!=dss.size();iter++)
    if(iter==dss.size()-1){
         cout<<(zagotovka-dss[iter])+raz<<endl;
       } else  cout<<(zagotovka-dss[iter])<<endl;
    
    return 0;
}
Hevzy86
0 / 0 / 0
Регистрация: 24.07.2016
Сообщений: 22
23.08.2016, 00:00  [ТС]     Программа по резке труб #35
Доброе время суток всем, есть пробема в приведенном выше коде от Peoples: иногда программа вылетает с такими ошибками(я так понимаю, какой-то из double итераторов ссылается на несуществующий элемент ), но в строках 70,71 у меня закоментированный код. Помогите,плиз исправить ошибку(вылазит, когда количество категорий труб ставлю маленькое значение: 1,2,3). Заранее всем спасибо
Hevzy86
0 / 0 / 0
Регистрация: 24.07.2016
Сообщений: 22
23.08.2016, 00:39  [ТС]     Программа по резке труб #36
Программа по резке труб

Программа по резке труб
Yandex
Объявления
23.08.2016, 00:39     Программа по резке труб
Ответ Создать тему
Опции темы

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