Форум программистов, компьютерный форум, киберфорум
Наши страницы

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

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 12, средняя оценка - 4.75
kpoxaa
72 / 33 / 1
Регистрация: 03.08.2012
Сообщений: 447
#1

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

15.11.2013, 10:42. Просмотров 1978. Ответов 17
Метки нет (Все метки)

Помогите пожалуйста понять, что от меня хотят и какой(как) разработать алгоритм для решения этой задачи.

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

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

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

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

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

Найти точку принадлежащую прямой - C++
Имею координаты двух точек, нужно найти точку, которая принадлежит этой прямой. Точка должна быть ближе ко второй вершине, ну или к первой...

Найти точку пересечения двух отрезков - C++
как найти точку пересечения двух отрезков, если даны координаты начала и конца обеих

На плоскости заданы n отрезков координатами концевых точек - C++
На плоскости заданы n отрезков координатами концевых точек. Концы отрезков задаются двумя парами координат (x1,y1), (x2,y2), 1<=i<=n (концы...

В файле заданы координаты концов отрезков. Вывести их на экран - C++
в файле задано координаты концов отрезков. Вівести их на екран. Количество отрезков не известно помогите осуществить ету задачу,...

Есть ли у кого похожий алгоритм: распределения отрезков разной длины внутри отрезков фиксированной длины? - C++
Народ помогите мне с программой распределения отрезков разной длины внутри отрезков фиксированной длины с минимальными остатками. К...

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

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

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

Добавлено через 1 минуту
Я вообще хочу для каждого отрезка свой объект... вот так как-то попробовать. А он уже будет хранить начало и конец. И наверное как-то там счетчик будет. Пока не придумал.
0
ya_noob
_
202 / 146 / 9
Регистрация: 08.10.2011
Сообщений: 432
15.11.2013, 11:37 #7
если координаты концов отрезков целые неотрицательные числа, то можно завели массив, в котором будут храниться счетчики отрезков, проходящих через каждую точку. считываем поочереди координаты концов отрезков и увеличиваем все счетчики от начала отрезка до конца отрезка. в конце останется только найти максимальное значение в массиве. его индекс и будет искомой точкой.
1
kpoxaa
72 / 33 / 1
Регистрация: 03.08.2012
Сообщений: 447
15.11.2013, 15:33  [ТС] #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(); // чтобы консоль быстро не закрылась ждем ввода любого символа с клавиатуры
}
0
Миниатюры
На прямой своими концами заданы N отрезков. Найти точку принадлежащую максимальному числу отрезков  
ya_noob
_
202 / 146 / 9
Регистрация: 08.10.2011
Сообщений: 432
15.11.2013, 17:36 #9
kpoxaa, а что выведет ваша программа для набора отрезков: [1, 2], [1, 4], [3, 5], [6, 7], [6, 8], [6, 9] ?
0
kpoxaa
72 / 33 / 1
Регистрация: 03.08.2012
Сообщений: 447
15.11.2013, 19:20  [ТС] #10
Сейчас посмотрим... лучше помогите доделать, если не верно.

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

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

Добавлено через 57 минут
[1, 2], [1, 4], [3, 5], программа считает что 3 здесь общая для всех трех отрезков. Хотя это не так, нужно организовать еще проверку, которая будет при добавлении данных, проверять все предыдущие добавленные объекты и сверяться с новым... сейчас попробую сделать.
0
ya_noob
_
202 / 146 / 9
Регистрация: 08.10.2011
Сообщений: 432
15.11.2013, 19:53 #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 отрезкам. следовательно ваша идея неверна и дополнительные проверки не помогут.
1
kpoxaa
72 / 33 / 1
Регистрация: 03.08.2012
Сообщений: 447
15.11.2013, 20:05  [ТС] #12
тогда я запутался... можете помочь реализовать верный способ?
0
ya_noob
_
202 / 146 / 9
Регистрация: 08.10.2011
Сообщений: 432
15.11.2013, 20:11 #13
kpoxaa, я же вам предлагал алгоритм на предыдущей странице.
1
kpoxaa
72 / 33 / 1
Регистрация: 03.08.2012
Сообщений: 447
15.11.2013, 20:13  [ТС] #14
он казался запутанным)) хорошо, я попробую
0
ya_noob
_
202 / 146 / 9
Регистрация: 08.10.2011
Сообщений: 432
15.11.2013, 20:33 #15
Цитата Сообщение от kpoxaa Посмотреть сообщение
он казался запутанным
это наверное я плохо умею объяснять, а алгоритм то очень простой.
попытка №2:
пусть прямая представляет собой набор точек с целочисленными неотрицательными координатами. тогда можно представить эту прямую в виде массива, в котором каждая ячейка будет связана с точкой прямой. в этих ячейках будем хранить количество прямых, проходящих через соответствующие точки. тогда индекс максимального значения в массиве будет указывать на искомую точку, т.к. через эту точку проходит максимальное кол-во прямых.
1
15.11.2013, 20:33
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
15.11.2013, 20:33
Привет! Вот еще темы с ответами:

Найти количество отрезков B, размещенных на отрезке A - C++
Задания: 4) Даны положительные числа A и B (A &gt; B). На отрезке длины A размещено максимально возможное количество отрезков длины B...

Найти минимальную суммарную длину n отрезков - C++
Всем привет. Пытаюсь решить задачу и ничего не выходит. Помогите решить. Условие: Пусть n красных и n синих точек на плоскости заданы...

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

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


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

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

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