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

На прямой своими концами заданы N отрезков. Найти точку принадлежащую максимальному числу отрезков - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 12, средняя оценка - 4.75
kpoxaa
70 / 31 / 1
Регистрация: 03.08.2012
Сообщений: 446
15.11.2013, 10:42     На прямой своими концами заданы N отрезков. Найти точку принадлежащую максимальному числу отрезков #1
Помогите пожалуйста понять, что от меня хотят и какой(как) разработать алгоритм для решения этой задачи.

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

Ну, понятное дело, что есть прямая. На этой прямой есть n отрезков, допустим длинна отрезков одинаковая. Как именно лучше всего показать в программе эти отрезки? Одномерный массив целых чисел? допустим mas[50];
[i] = 0 - значит нет отрезка(пустота)
[i] = 1 - значит отрезок начался
[i] = 2 - конец отрезка.
Как лучше отобразить этот момент?

И что значит вот эта фраза: своими концами заданы ? Следующий отрезок будет расположен сразу за предыдущим без пропусков? Или как?... не очень понимаю.

И в итоге, имея отрезки нужно : найти точку принадлежащую максимальному числу отрезков. Как это понять? Допустим, на основе предыдущей мысли, предполагаю: есть 2 отрезка, которые идут друг за другом, потом пропуск, потом 3 отрезка друг за другом. Вот максимальное число отрезков. 3 отрезка друг за другом.... точек будет дохера в этом участке из трех отрезков. Выбрать любую?

Помогите плиз разобраться
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
15.11.2013, 10:42     На прямой своими концами заданы N отрезков. Найти точку принадлежащую максимальному числу отрезков
Посмотрите здесь:

C++ В файле заданы координаты концов отрезков. Вывести их на экран
дано множество отрезков.найти max объединение C++
C++ Найти точку пересечения двух отрезков
Найти минимальную суммарную длину n отрезков C++
C++ найти точку, принадлежащую
Найти точку принадлежащую прямой C++
C++ Найти количество отрезков B, размещенных на отрезке A
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Rivory
146 / 112 / 2
Регистрация: 15.01.2013
Сообщений: 266
15.11.2013, 10:56     На прямой своими концами заданы N отрезков. Найти точку принадлежащую максимальному числу отрезков #2
"Заданы своими концами", как я понял, это значит что Вам передается 2 точки. Одна точка - один конец отрезка, вторая - второй. Исходя из этого - отрезки могут накладываться друг на друга. Например [-1,1] и [0,1], тогда точка 0 принадлежит 2м отрезкам сразу. Вот с Вас и спрашивают найти точку, принадлежащую макс. кол-ву отрезков.
kpoxaa
70 / 31 / 1
Регистрация: 03.08.2012
Сообщений: 446
15.11.2013, 10:57  [ТС]     На прямой своими концами заданы N отрезков. Найти точку принадлежащую максимальному числу отрезков #3
Ах да....... спасибо огромное) Я не подумал про это почему-то.
Rivory
146 / 112 / 2
Регистрация: 15.01.2013
Сообщений: 266
15.11.2013, 11:09     На прямой своими концами заданы N отрезков. Найти точку принадлежащую максимальному числу отрезков #4
А из алгоритмов реализации мне в голову только перебор приходит. В задании подразумеваются только целые точки, как я понял, тогда можно пробежаться по всем целым точкам от левой точки самого левого отрезка до правой точки самого правого, и в каждой из этих точек пробегать по массиву всех отрезков, где сравнивать a<x<b, где x - точка, [a,b] - отрезок. Если да, то накапливать счетчик для текущей точки.

Что-то более красивое, чем простой перебор мне в голову не приходит.
ya_noob
_
200 / 144 / 9
Регистрация: 08.10.2011
Сообщений: 432
15.11.2013, 11:10     На прямой своими концами заданы N отрезков. Найти точку принадлежащую максимальному числу отрезков #5
1) координаты отрезков - целые числа или вещественные?
2) каков диапазон значений координат?
kpoxaa
70 / 31 / 1
Регистрация: 03.08.2012
Сообщений: 446
15.11.2013, 11:15  [ТС]     На прямой своими концами заданы N отрезков. Найти точку принадлежащую максимальному числу отрезков #6
Я наверное сделаю целые. А диапазон любой, чтобы не сильно большой был

Добавлено через 1 минуту
Я вообще хочу для каждого отрезка свой объект... вот так как-то попробовать. А он уже будет хранить начало и конец. И наверное как-то там счетчик будет. Пока не придумал.
ya_noob
_
200 / 144 / 9
Регистрация: 08.10.2011
Сообщений: 432
15.11.2013, 11:37     На прямой своими концами заданы N отрезков. Найти точку принадлежащую максимальному числу отрезков #7
если координаты концов отрезков целые неотрицательные числа, то можно завели массив, в котором будут храниться счетчики отрезков, проходящих через каждую точку. считываем поочереди координаты концов отрезков и увеличиваем все счетчики от начала отрезка до конца отрезка. в конце останется только найти максимальное значение в массиве. его индекс и будет искомой точкой.
kpoxaa
70 / 31 / 1
Регистрация: 03.08.2012
Сообщений: 446
15.11.2013, 15:33  [ТС]     На прямой своими концами заданы N отрезков. Найти точку принадлежащую максимальному числу отрезков #8
Вот как получилось: может немного не так работает, но вроде бы правильно

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
#include "stdafx.h"
#include <iostream>
#include <string>
#include <cctype>
#include <conio.h>
#include <locale>
 
using namespace std; 
 
 
class Segment 
{
private: 
    int start; // кордината начала отрезка
    int end;     //  кордината конца отрезка 
    int maxIndexIntersection; // индекс максимального пересечения
    int countIncomingSegm; // счетчик макимально входящих отрезков в этот отрезок
 
public: 
    Segment() 
    {
 
    }
 
    Segment(int start, int end)
    {
        
        this->start = start;
        this->end = end;
        
        maxIndexIntersection = 0;
        countIncomingSegm = 0;
    }
 
    void static searchTerms(Segment *segment, int size) // поиск точки
    {
        for(int i = 0; i<size; i++) // по очереди нужно проверить все отрезки.
        {
            for(int j = 0; j<size; j++)
            {
                if(j == i) continue; // самих себя с самим собой не надо проверять. только отрезки, которые рядом
                if( (segment[j].start >= segment[i].start) && (segment[j].start <= segment[i].end) ) // проверяем, если следующий отрезок, своей начальной точки попадает в промежуток отрезка, на котором мы сейчас находимся
                {
                    segment[i].maxIndexIntersection = segment[j].start; // сохраняем первое вхождение нового отрезка
                    segment[i].countIncomingSegm++; // счетчик вхождений для одного отрезка(сколько отрезков входит в этот отрезок)
                }
            }
        }
        
        int maxCount = 0;
        int finalIndex = -1;
 
        // теперь нужно сделать поиск по счетчику, чтобы узнать какой отрезок содержит в себе максимум других отрезков
        for(int i = 0; i<size; i++)
        {
            if(segment[i].countIncomingSegm>maxCount) // если счетчик объекта хранит в себе больше чем то, что мы уже проверили
            {
                // значит это новый отрезок, который хранит в себе больше отрезков и нам нужен именно он
                maxCount = segment[i].countIncomingSegm; // сохраняем в переменную макисмальное число отрезков из данного объекта
                finalIndex = i; // сохраняем индект этого объекта, чтобы потом без цикла отоброзить данные
            }
        }
 
        if(finalIndex == -1 ) // если переменная осталась непроинициализирована, значит не одной точки не было найдено
        {
            cout<<"На прямой нет пересикающихся отрезков";
        }
        else 
        {
            cout<<"Больше всего отрезков пересекается на прямой в точке: "<<segment[finalIndex].maxIndexIntersection<<endl;
            cout<<"Кординаты отрезка с максимальным пересечением: ["<<segment[finalIndex].start<<"] ["<<segment[finalIndex].end<<"]";
        }
    }
};
 
void main()
{
    setlocale(LC_ALL,"RUSSIAN"); // для русского текста в программе
 
    int number;
    cout<<"Введите количество отрезков: ";
    cin>>number;
 
    Segment *segment = new Segment[number];
 
    for(int i = 0; i<number; i++)
    {
        int start, end;
 
        cout<<"Ввод данных для "<<(i+1)<<" отрезка"<<endl;
        cout<<"Начало отрезка: ";
        cin>>start;
        cout<<"Конец отрезка: ";
        cin>>end;
        cout<<endl;
 
        // если ввели начало отрезка больше чем его конец. то переспрашиваем ввод для этого цикла заново
        if(start>=end) 
        {
            i--;
            continue; //пропускаем интерацию
        }
        segment[i] = Segment(start, end); // создаем объект и передаем в конструктор с параметрами начало и конец отрезка
    }
 
    segment->searchTerms(segment, number); // вызываем стаический метод поиска пересечений
 
    delete segment; // после всех операций хорошим тоном считается очистка выделенной памяти
    
    getch(); // чтобы консоль быстро не закрылась ждем ввода любого символа с клавиатуры
}
Миниатюры
На прямой своими концами заданы N отрезков. Найти точку принадлежащую максимальному числу отрезков  
ya_noob
_
200 / 144 / 9
Регистрация: 08.10.2011
Сообщений: 432
15.11.2013, 17:36     На прямой своими концами заданы N отрезков. Найти точку принадлежащую максимальному числу отрезков #9
kpoxaa, а что выведет ваша программа для набора отрезков: [1, 2], [1, 4], [3, 5], [6, 7], [6, 8], [6, 9] ?
kpoxaa
70 / 31 / 1
Регистрация: 03.08.2012
Сообщений: 446
15.11.2013, 19:20  [ТС]     На прямой своими концами заданы N отрезков. Найти точку принадлежащую максимальному числу отрезков #10
Сейчас посмотрим... лучше помогите доделать, если не верно.

Добавлено через 5 минут
Должно показать первую найденную точку, которая хранит в себе максимум отрезков.

Добавлено через 5 минут
[6, 7], [6, 8], [6, 9] программа должна была найти точку 6. Но почему-то не нашла...

Добавлено через 57 минут
[1, 2], [1, 4], [3, 5], программа считает что 3 здесь общая для всех трех отрезков. Хотя это не так, нужно организовать еще проверку, которая будет при добавлении данных, проверять все предыдущие добавленные объекты и сверяться с новым... сейчас попробую сделать.
ya_noob
_
200 / 144 / 9
Регистрация: 08.10.2011
Сообщений: 432
15.11.2013, 19:53     На прямой своими концами заданы N отрезков. Найти точку принадлежащую максимальному числу отрезков #11
kpoxaa, не до конца понимаю ваш алгоритм, но вроде как вы считаете, что если с некоторым отрезком пересекается наибольшее кол-во отрезков, то в этом отрезке и надо искать нужную точку. так? если так, то вот вам пример: [1, 8], [1, 2], [3, 4], [5, 6], [7, 8], [9, 10], [9, 11], [9, 12]. как видно с отрезком [1, 8] пересекается наибольшее кол-во отрезков (4 шт), но каждая точка на этом отрезке принадлежит только 1 или 2 отрезкам. с отрезком [9, 12] пересекается всего 2 других отрезка, но точка 9 принадлежит 3 отрезкам. следовательно ваша идея неверна и дополнительные проверки не помогут.
kpoxaa
70 / 31 / 1
Регистрация: 03.08.2012
Сообщений: 446
15.11.2013, 20:05  [ТС]     На прямой своими концами заданы N отрезков. Найти точку принадлежащую максимальному числу отрезков #12
тогда я запутался... можете помочь реализовать верный способ?
ya_noob
_
200 / 144 / 9
Регистрация: 08.10.2011
Сообщений: 432
15.11.2013, 20:11     На прямой своими концами заданы N отрезков. Найти точку принадлежащую максимальному числу отрезков #13
kpoxaa, я же вам предлагал алгоритм на предыдущей странице.
kpoxaa
70 / 31 / 1
Регистрация: 03.08.2012
Сообщений: 446
15.11.2013, 20:13  [ТС]     На прямой своими концами заданы N отрезков. Найти точку принадлежащую максимальному числу отрезков #14
он казался запутанным)) хорошо, я попробую
ya_noob
_
200 / 144 / 9
Регистрация: 08.10.2011
Сообщений: 432
15.11.2013, 20:33     На прямой своими концами заданы N отрезков. Найти точку принадлежащую максимальному числу отрезков #15
Цитата Сообщение от kpoxaa Посмотреть сообщение
он казался запутанным
это наверное я плохо умею объяснять, а алгоритм то очень простой.
попытка №2:
пусть прямая представляет собой набор точек с целочисленными неотрицательными координатами. тогда можно представить эту прямую в виде массива, в котором каждая ячейка будет связана с точкой прямой. в этих ячейках будем хранить количество прямых, проходящих через соответствующие точки. тогда индекс максимального значения в массиве будет указывать на искомую точку, т.к. через эту точку проходит максимальное кол-во прямых.
kpoxaa
70 / 31 / 1
Регистрация: 03.08.2012
Сообщений: 446
15.11.2013, 21:12  [ТС]     На прямой своими концами заданы N отрезков. Найти точку принадлежащую максимальному числу отрезков #16
Да, я понял)) А давайте придумаем, что делать если вводят отрицательные значения для отрезка?
ya_noob
_
200 / 144 / 9
Регистрация: 08.10.2011
Сообщений: 432
16.11.2013, 08:34     На прямой своими концами заданы N отрезков. Найти точку принадлежащую максимальному числу отрезков #17
Цитата Сообщение от kpoxaa Посмотреть сообщение
что делать если вводят отрицательные значения для отрезка
сместить все отрезки вправо по координатной оси так, чтобы все значения стали >= 0, а также запомнить величину этого смещения, чтобы потом при выводе ответа восстановить действительное значение искомой точки.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
16.11.2013, 10:39     На прямой своими концами заданы N отрезков. Найти точку принадлежащую максимальному числу отрезков
Еще ссылки по теме:

C++ Даны целые положительные числа А и B. Найти количество отрезков В, размещенных на отрезке А
C++ Есть ли у кого похожий алгоритм: распределения отрезков разной длины внутри отрезков фиксированной длины?
Найти длину ломанной, состоящей из заданного числа отрезков C++
C++ Не используя операции умножения и деления, найти количество отрезков, расположенных на отрезке А
В массивах вещественных чисел X и Y записаны координаты точек на плоскости. Найти длины отрезков C++

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

Или воспользуйтесь поиском по форуму:
viktorius
2 / 2 / 2
Регистрация: 24.02.2013
Сообщений: 105
16.11.2013, 10:39     На прямой своими концами заданы N отрезков. Найти точку принадлежащую максимальному числу отрезков #18
я сделал так:

a.h
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
using namespace std;
//вывести координаты точки наибольшего пересечения отрезков,
//число пересечения и 
//отрезок в этой точке с которым пересекается больше всего отрезков
class Point  
{
    int **segment, n, *arr, count, min, max;
public:
    Point();
    Point(int [][2], int);
    ~Point();
    void Search();
};
a.cpp
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
#include <iostream>
#include "a.h"
using namespace std;
 
Point::Point() : segment(0), n(0), count(0), arr(0), min(0), max(0)
{}
 
Point::Point(int mas[][2], int N) : n(N)
{
    segment = new int*[n];
    max = INT_MIN;
    min = INT_MAX;
    for(int i = 0; i < n; i++)
    {
        segment[i] = new int[2];
        for(int j = 0; j < 2; j++)
        {
            segment[i][j] = mas[i][j];
            if(segment[i][j] > max)
                max = segment[i][j];
            else if(segment[i][j] < min)
                min = segment[i][j];
        }
    }
    if(max > 0 && min >= 0)
        count = max - min;
    else if(max > 0 && min < 0)
        count = max + abs(min);
    else if(max <= 0 && min < 0)
        count = abs(min) - abs(max);
    arr = new int[++count];
    for(int i = 0; i < count; i++)
        arr[i] = 0;
}
 
Point::~Point()
{
    for(int i = 0; i < n; i++)
        delete [] segment[i];
    delete [] segment;
    delete [] arr;
}
 
void Point::Search()
{
    for(int i = 0; i < count; i++)
        for(int j = 0; j < n; j++)
            if(segment[j][0] <= (min + i) && segment[j][1] >= (min + i))
                ++arr[i];
    int Max= INT_MIN, cor;
    for(int i = 0; i < count; i++)
        if(arr[i] > Max)
        {
            Max = arr[i];
            cor = min + i;
        }
    cout<<cor<<" "<<Max<<endl;
    int *zn = new int[n], t = 0;
    for(int i = 0; i < n; i++)
        zn[i] = 0;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            if(i != j && segment[i][0] <= (cor) && segment[i][1] >= (cor) && segment[j][0] <= (cor) && segment[j][1] >= (cor))
                zn[i]++;
    for(int i = 0, m = 0; i < n; i++)
        if(zn[i] > m)
        {
            m = zn[i];
            t = i;
        }
    cout<<"["<<segment[t][0]<<","<<segment[t][1]<<"]"<<endl;
    delete [] zn;
}
main.cpp
C++
1
2
3
4
5
6
7
8
9
10
11
12
#include <iostream>
#include "a.h"
using namespace std;
 
int main()
{
    int a[8][2] = {-5, 8, -1, 4, 2, 5, 3, 7, 7, 9, 9, 12, 10, 11, 9, 12};
    Point ob(a, 8);
    ob.Search();
    system("pause");
    return 0;
}
Yandex
Объявления
16.11.2013, 10:39     На прямой своими концами заданы N отрезков. Найти точку принадлежащую максимальному числу отрезков
Ответ Создать тему
Опции темы

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