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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 11, средняя оценка - 4.82
alibaba314
18 / 18 / 1
Регистрация: 22.03.2009
Сообщений: 58
#1

Найти минимальное подмножество отрезков, объединение которых покрывает заданный отрезок - C++

17.10.2009, 12:23. Просмотров 1452. Ответов 10
Метки нет (Все метки)

всем привет!

помогите мне решить одну задачу:

написать программу. которая для множества заданных отрезков находит минимальное подмножество отрезков. объединение которых покрывает отрезок S=[0,10000]. число отрезков и координаты их концов заданы на входе. Все координаты целочисленные.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
17.10.2009, 12:23
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Найти минимальное подмножество отрезков, объединение которых покрывает заданный отрезок (C++):

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

Дано множество отрезков, найти max объединение - C++
дано множество отрезков.найти max объединение.подскажите плиз алгоритм.

Найти сумму и число тех элементов массива, которые попадают на заданный отрезок - C++
Помогите написать программу по теме: одномерные массивы. Найти сумму и число тех элементов заданного массива X1,X2, … ,Xn, которые...

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

Найти сумму и число тех элементов заданного массива X1,X2, … ,Xn, которые попадают на заданный отрезок. - C++
1. чНайти сумму и число тех элементов заданного массива X1,X2, … ,Xn, которые попадают на заданный отрезок.

Определение потребления топлива на заданный отрезок пути - C++
// transport.cpp: определяет точку входа для консольного приложения. // #include "stdafx.h" #include "locale.h" #include...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
TanT
эволюционирую потихоньку
465 / 463 / 43
Регистрация: 30.06.2009
Сообщений: 1,399
17.10.2009, 12:34 #2
ну так ты начни, хотя бы ввод данных сделай. ошибки поправим, алгоритм обсудим
alibaba314
18 / 18 / 1
Регистрация: 22.03.2009
Сообщений: 58
17.10.2009, 13:44  [ТС] #3
вот алгоритм:

покрывайте отрезок S пошагово. двигаясь слева направо. на каждом шаге будет непокрытая часть [x, 10000] . из оставшихся отрезков выбирайте тот, который урежет непокрытую часть до [y, 10000], где "y" максимальное.
kravam
быдлокодер
1694 / 881 / 44
Регистрация: 04.06.2008
Сообщений: 5,441
17.10.2009, 13:58 #4
Приехали.
Во-первых, надо найти длины всех отрезков
(Например: 34, 567, 21, 457, 432, 45, 543, 10,)

Во-вторых, их надо отсортировать по убыванию
(567, 543, 457, 432, 45, 34, 21, 10)

А потом начинай с самого левого члена этой последовательности и сравнивай его с 10000. Если он меньше, то прибавляй следующий член, сумму снова сравнивай с 10000. Одновременно инкременируй счётчик отрезков

Как только сумма станет больше или равной 10000, значит ты нашёл искомые отрезки. Величина счётчика и есть их минимальное число.
Привет.
TanT
эволюционирую потихоньку
465 / 463 / 43
Регистрация: 30.06.2009
Сообщений: 1,399
17.10.2009, 16:12 #5
пробуем, тестим.
ввод через фаил (в файле только пары (начало и конец) отрезков)
ввод организовал как мне удобно, а не по условию
на вывод отладки можно не заморачиваться, главное это результат
а промежуточный вывод для удобства

const int begDiapason = 0;
const int endDiapason = 100; - границы диапазона

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
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
#define sizeVec(c) int((c).size())
#define all(c) (c).begin(),(c).end()
 
#define LENGTH(a)  ((*a).first) 
#define BEG(a)  ((*a).second.first) 
#define END(a)  ((*a).second.second)        
 
const int begDiapason = 0;
const int endDiapason = 100;
 
typedef  vector<pair< int, pair<int, int> > > SEGMENT;
int main()
{
    char *file="data.txt";
    int beg, end, counter=0;
    bool flag;
    SEGMENT arrSeg;
    SEGMENT::iterator itt;
 
    ifstream f(file);
    if (!(f.is_open()))  // проверка наличия первого файла с текстом
        cout<<"ERROR: not file "<<file;
    else
        while(!f.eof()) // чтении из файла
        {   
            f>>beg; f>>end;
            arrSeg.push_back(make_pair(end-beg, make_pair(beg, end)));
        }
 
 
    // вывод для отладки
    for (SEGMENT::iterator it=arrSeg.begin(); it<arrSeg.end(); it++)
        cout<<"length:"<<LENGTH(it)<<" beg:"<<BEG(it)<<" end:"<<END(it)<<endl;
    cout<<endl;
 
//  sort(all(arrSeg));  reverse(all(arrSeg));  // можно иначе
 
    beg=begDiapason; 
//  for (itt=arrSeg.begin(); itt<arrSeg.end(); itt++)
//     if (beg>=BEG(itt)) 
//      { beg=END(itt); break; }
// 
//  if(beg!=begDiapason) // если после первого поиска не обнаружен отрезок с begDiapason..Х
//  {
//      cout<<++counter<<". length:"<<LENGTH(itt)<<" beg:"<<BEG(itt)<<" end:"<<END(itt)<<endl;
//      arrSeg.erase(itt);
        
        while (!(arrSeg.empty()))
        {
            // достигли конца диапазона
            if (beg>=endDiapason) break;
            // подравниваем все отрезки под текущую позицию бегунка
            for (SEGMENT::iterator it=arrSeg.begin(); it<arrSeg.end(); it++)
                if (beg>BEG(it))    
                    { BEG(it)=beg; LENGTH(it)=END(it)-BEG(it); }
      // сортируем по убыванию (полезные длины отрезков поменялись)
            sort(all(arrSeg));  reverse(all(arrSeg)); 
 
            // ищем максимальный отрезок начинающийся с позиции бегунка
            flag=false;
            for (itt=arrSeg.begin(); itt<arrSeg.end(); itt++)
                if (beg>=BEG(itt)) 
                { flag=true; break; }
 
            if (flag==false) break;
            // если бегунок на отрезке длиной больше нуля
            // инкрементируем счётчик отрезков и по новой
            if (LENGTH(itt)>0)
            {
                cout<<++counter
                    <<". length:"<<LENGTH(itt)
                    <<" beg:"<<BEG(itt)
                    <<" end:"<<END(itt)<<endl;
                beg=END(itt);
                arrSeg.erase(itt);
            }
            else
                break;
        }
        
        if(beg>=endDiapason)
            cout<<"\nmin number segments: "<<counter;
        else
            cout<<"\nit cannot be done: ";
 
    f.close();  cout << endl;   system("PAUSE");
    return 0;
}
odip
Эксперт С++
7157 / 3297 / 59
Регистрация: 17.06.2009
Сообщений: 14,164
17.10.2009, 22:37 #6
Как только сумма станет больше или равной 10000, значит ты нашёл искомые отрезки. Величина счётчика и есть их минимальное число.
2kramav: прочитай внимательно условие задачи.

Добавлено через 2 минуты
Если перебирать тупо, то будет очень много вариантов: 2^N, где N - число отрезков.
А вообще эта задача решается методом динамического программирования.
TanT уже должен сообразить как
TanT
эволюционирую потихоньку
465 / 463 / 43
Регистрация: 30.06.2009
Сообщений: 1,399
17.10.2009, 22:43 #7
Цитата Сообщение от odip Посмотреть сообщение
TanT уже должен сообразить как
odip, мой код выше. но я не совсем уверен, что это о чём вы мне говорили на другой ветки.
как не прискорбно мне это принимать, но я не совсем понял/оценил предложенный вами вариант.
предлагаю попробовать снова осветить вопрос динамического программирования, что, несомненно, будет полезно всем остальным участникам или прям, не стеснясь, вот так ссылкой на источник отправить меня учить мат.часть.
я даже не обижусь.
kravam
быдлокодер
1694 / 881 / 44
Регистрация: 04.06.2008
Сообщений: 5,441
17.10.2009, 23:14 #8
Цитата Сообщение от odip Посмотреть сообщение
2kramav: прочитай внимательно условие задачи.

Добавлено через 2 минуты
Если перебирать тупо, то будет очень много вариантов: 2^N, где N - число отрезков.
А вообще эта задача решается методом динамического программирования.
TanT уже должен сообразить как
А что его читать?
Там вызывает непонимание такая фраза:
"объединение которых покрывает отрезок S=[0,10000]"

Ну, я предположил что речь идёт о

""Сумма длин которых покрывает отрезок S=[0,10000]"
Ну то есть сумма длин которых превышает 10000.

Вот и складываю помаленечку себе.
Теперь о "тупо перебирать"

Не знаю, где Вы увидели два в энной степени, но не у меня, факт.
Мой вариант предполагает n вариантов.
То есть если отрезков 10, то 10 длин рассматриваем и всё. А не 2 в степени 10
Естественно, отсортировав прежде массив этих самых длин.

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

На крайняк голимый код.
Но с комментариями.
Привет.
odip
Эксперт С++
7157 / 3297 / 59
Регистрация: 17.06.2009
Сообщений: 14,164
18.10.2009, 19:14 #9
2kravam:
В условии написано: "число отрезков и координаты их концов заданы на входе".
Если нужна только длина отрезков, то зачем еще координаты концов ?
И зачем тогда указывать что покрыть нужно именно от 0 до 10000 ?
Ты неправильно понял задачу.
Нужно покрывать отрезками, но сами отрезки сдвигать никуда нельзя.
Если отрезок от 100 до 200, то это значит что он покрывает от 100 до 200 и в другое место его не сдвинуть.
Задекларирую свой способ как оптимальный.
Декларируй. Только ты решаешь совсем не ту задачу.
kravam
быдлокодер
1694 / 881 / 44
Регистрация: 04.06.2008
Сообщений: 5,441
18.10.2009, 21:09 #10
Я ничё не понял.
Меня термин покрыть добивает. Не знаю, что он обозначает.
Пусть автор сам решает такие задачи.
odip
Эксперт С++
7157 / 3297 / 59
Регистрация: 17.06.2009
Сообщений: 14,164
19.10.2009, 12:09 #11
Покрыть - это значит накрыть каждую точку диапазона своим отрезком сверху.
Но отрезки можно класть только на те позиции которые указаны для них.
То есть сдвигать отрезок влево или вправо нельзя.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
19.10.2009, 12:09
Привет! Вот еще темы с ответами:

На прямой своими концами заданы N отрезков. Найти точку принадлежащую максимальному числу отрезков - C++
Помогите пожалуйста понять, что от меня хотят и какой(как) разработать алгоритм для решения этой задачи. На прямой своими концами...

Найти два первых элемента в массиве, значения которых не попадают в заданный диапазон - C++
Здравствуйте. Помогите с работой в c++ массивы. 1. Найти два первых элемента в массиве С(17), значения которых не попадают в заданный с...

Определить минимальное количество отрезков единичной длины необходимых для того чтоб покрыть все точки - C++
И снова здравствуйте.Условие:даны N точек с двойной точностью(точки заданные вещественными числами ). Определить минимальное количество...

Массивы: пары соседних членов описывают концы отрезков. Накрывают ли полностью эти отрезки заданный отрезок - Free Pascal
Привет всем. Помогите пожалуйста решить вот эти задачки. 1)В случайной последовательности x1,x2,...,x2n – пары соседних членов х2k-1...


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

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

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