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

найти точку, принадлежащую - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 4.67
slava0394
1 / 1 / 0
Регистрация: 05.12.2011
Сообщений: 39
11.01.2012, 23:00     найти точку, принадлежащую #1
дано множество отрезков на прямой. найти точку, которая принадлежит наибольшему количеству отрезков, определить это количество
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Байт
 Аватар для Байт
14004 / 8835 / 1234
Регистрация: 24.12.2010
Сообщений: 16,014
11.01.2012, 23:49     найти точку, принадлежащую #2
slava0394, Какие-то усилия прикладывали? В чем сложности? Ваши наработки?
slava0394
1 / 1 / 0
Регистрация: 05.12.2011
Сообщений: 39
11.01.2012, 23:58  [ТС]     найти точку, принадлежащую #3
у меня плохо с программрованием. не знаю вообще с чего здесь начать
Whiteha
Программист
33 / 33 / 4
Регистрация: 08.07.2011
Сообщений: 190
Записей в блоге: 1
12.01.2012, 00:01     найти точку, принадлежащую #4
Ну алгоритмически то вы можете рассказать вашу версию?(задание то уж совсем простое), тогда как минимум с меня код=)
slava0394
1 / 1 / 0
Регистрация: 05.12.2011
Сообщений: 39
12.01.2012, 00:05  [ТС]     найти точку, принадлежащую #5
объснте мне плиз. для вас оно простое, а для того кто программированием только с этого года вообще стал заниматься сложновато немного. может знаете хороший источник теории?
Whiteha
Программист
33 / 33 / 4
Регистрация: 08.07.2011
Сообщений: 190
Записей в блоге: 1
12.01.2012, 00:21     найти точку, принадлежащую #6
Это не программирование, это школьная математика=\
Ну сами подумайте - пускай у нас есть дискретный отрезок конечной длины, на нём заданы другие отрезки(так же конечной длинны) и нужно найти точку которая принадлежит наибольшему количеству отрезков...

Я вас уверяю, если вы подумаете хотя бы в течении минуты то поймёте алгоритм решения, и тогда я вам помогу с тяжёлым для вас пока программированием и напишу код.
slava0394
1 / 1 / 0
Регистрация: 05.12.2011
Сообщений: 39
12.01.2012, 10:18  [ТС]     найти точку, принадлежащую #7
ну по идее это середина отрезка
fasked
Эксперт C++
 Аватар для fasked
4925 / 2505 / 180
Регистрация: 07.10.2009
Сообщений: 4,306
Записей в блоге: 1
12.01.2012, 10:40     найти точку, принадлежащую #8
Цитата Сообщение от slava0394 Посмотреть сообщение
ну по идее это середина отрезка
Смотря как расположены отрезки.
Байт
 Аватар для Байт
14004 / 8835 / 1234
Регистрация: 24.12.2010
Сообщений: 16,014
12.01.2012, 11:40     найти точку, принадлежащую #9
Я бы взял концы всех отрезков, и посмотрел бы какому количеству других отрезков они принадлежат.
Условие принадлежности точки x отрезку [a,b]: a <= x <= b
Whiteha
Программист
33 / 33 / 4
Регистрация: 08.07.2011
Сообщений: 190
Записей в блоге: 1
12.01.2012, 13:27     найти точку, принадлежащую #10
Первое что мне пришло на ум - это просто пробежаться по каждой точке отрезка и проверить её на равенство a <= x <= b для каждого из подотрезков, считая параллельно для точки число таких пересечений.
Так можно найти не только точку с максимальным количеством пересечений, но и отрезок, но тк нужна только одна точка, то на мой взгляд выглядеть это будет как-то так:
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
#include <iostream>
using namespace std;
 
pair <int, int> segm;
int len, num;
 
int main ()
{
    setlocale(LC_ALL, "");
    cout << "Введите длину основного отрезка: " << endl; cin >> len;
    len++; // Ввели 6, получили отрезок от 0 до 6 включительно.
    segm.first = 0; 
    segm.second = len;
    cout << "Введите число отрезков которые включает в себя основной: " << endl; cin >> num;
    pair <int, int> *vs = new pair <int, int> [num];
    for (int i = 0, buf = 0; i < num; i++)
    {
        cout << "Начало " << i + 1 << " отрезка: "; cin >> buf;
        if (buf >= segm.first && buf <= segm.second) vs[i].first = buf;
        cout << "Конец " << i + 1 << " отрезка: "; cin >> buf;
        if (buf >= segm.first && buf <= segm.second) vs[i].second = buf;
    }
    
    int *count = new int [len]; // Для подсчёта числа пересечений в данной точке
    int inmax = 0, nmax = 0;
 
    for (int i = 0; i < len; i++)
    {
        count[i] = 0;
        for (int j = 0; j < num; j++)
        {
            if (i >= vs[j].first &&  i <= vs[j].second) count[i] ++;
        }
        if (nmax < count[i]) { nmax = count[i]; inmax = i;}
 
        cout  << " count = " << count[i] << endl;
    }
    cout << "Максимальное число пересечений в точке " << inmax << " равно " << nmax << endl;
 
    system("pause");
}
Байт
 Аватар для Байт
14004 / 8835 / 1234
Регистрация: 24.12.2010
Сообщений: 16,014
12.01.2012, 13:33     найти точку, принадлежащую #11
Цитата Сообщение от Whiteha Посмотреть сообщение
это просто пробежаться по каждой точке отрезка
Любопытно, как вы собираетесь пробежаться по континуму ?
Whiteha
Программист
33 / 33 / 4
Регистрация: 08.07.2011
Сообщений: 190
Записей в блоге: 1
12.01.2012, 13:53     найти точку, принадлежащую #12
Я исходил из дискретности отрезка, автор ведь не указал какому множеству принадлежит отрезок и я выдвинул самую простую версию. Хотя конечно не самую универсальную.=)
slava0394
1 / 1 / 0
Регистрация: 05.12.2011
Сообщений: 39
12.01.2012, 14:10  [ТС]     найти точку, принадлежащую #13
жесть
ExcellencE
20 / 20 / 2
Регистрация: 22.08.2011
Сообщений: 79
12.01.2012, 14:16     найти точку, принадлежащую #14
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include "stdafx.h"
 
#include <stdio.h>
#include <stdlib.h>
 
int main (void)
{
    int mas[2][6]= {{1,2,3,4,5,6},{3,4,5,6,7,3}};
    int count =0, k; 
    for(int i =0;i<6;i++)
    {   
        int x= mas[0][i], tmpCount=0;
        for(int j =0;j<6;j++)
        {
            if(mas[1][j] >= x && x<=mas[2][j]) tmpCount++;
        }
        if(count < tmpCount) {count = tmpCount;k = x;}
    }
    printf("%d   %d", k, count);
    scanf("%d",&k);
}
Mr.X
Эксперт С++
 Аватар для Mr.X
2807 / 1583 / 248
Регистрация: 03.05.2010
Сообщений: 3,695
12.01.2012, 15:29     найти точку, принадлежащую #15
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
132
133
134
135
136
137
138
139
/////////////////////////////////////////////////////////////////////////////////////////
//Дано множество отрезков на прямой. Найти точку, которая принадлежит наибольшему 
//количеству отрезков, определить это количество.
/////////////////////////////////////////////////////////////////////////////////////////
#include <complex>
#include <iostream>
#include <map>
#include <vector>
/////////////////////////////////////////////////////////////////////////////////////////
typedef double                          T_coord;
typedef std::complex    <T_coord>       T_segment;
typedef std::vector     <T_segment>     T_segments;
/////////////////////////////////////////////////////////////////////////////////////////
struct  T_counters
{    
    int  left_counter_;
    int  right_counter_;
    //-----------------------------------------------------------------------------------
    T_counters()
        :
        left_counter_   (),
        right_counter_  ()
    {}
};
/////////////////////////////////////////////////////////////////////////////////////////
typedef std::map<T_coord, T_counters>   T_segm_end_points;
/////////////////////////////////////////////////////////////////////////////////////////
void  fill_segm_end_points
    (
        const T_segments&   segments,
        T_segm_end_points&  segm_end_points
    )
 
{
    for(
        T_segments::const_iterator  segm_it = segments.begin();
        segm_it != segments.end();
        ++segm_it
       )
    {
        ++segm_end_points[segm_it->real()].left_counter_;
        ++segm_end_points[segm_it->imag()].right_counter_;
    }
}
/////////////////////////////////////////////////////////////////////////////////////////
void  get_max_segm_counter_and_max_segm_counter_point
    (
        const T_segments&   segments,
        int&                max_segm_counter,
        T_coord&            max_segm_counter_point    
    )
{
    T_segm_end_points  segm_end_points;
 
    fill_segm_end_points
        (
            segments,
            segm_end_points
        );
 
    int  cur_segm_counter = 0;
 
    for(
        T_segm_end_points::iterator  
        segm_end_point_it = segm_end_points.begin();
        segm_end_point_it != segm_end_points.end();
        ++segm_end_point_it
       )
    {
        cur_segm_counter += segm_end_point_it->second   .left_counter_;
        cur_segm_counter -= segm_end_point_it->second   .right_counter_;
 
        if(
                segm_end_point_it   ==  segm_end_points.begin()
            ||  cur_segm_counter    >   max_segm_counter
          )
        {
            max_segm_counter = cur_segm_counter;
            T_segm_end_points::iterator  next_it = segm_end_point_it;
            std::advance(next_it, 1);
            max_segm_counter_point = (segm_end_point_it->first + next_it->first) / 2.0;
        }
    }
}
/////////////////////////////////////////////////////////////////////////////////////////
void  input_segments(T_segments&  segments)
{
    int  segments_total = 0;
    do
    {
        std::cout << "Введите количесто заданных отрезков на прямой: ";
        
        std::cin >> segments_total;    
    }while(segments_total <= 0);
 
    std::cout << "Введите координаты "
              << segments_total
              << " отрезков в виде (1.2,3.4):"
              << std::endl;
 
    segments.resize(segments_total);
    for(int  i = 0; i < segments_total;)
    {        
        std::cout << "\t#"
                  << i + 1
                  << ": ";
        
        std::cin >> segments[i];
        if( segments[i].real() < segments[i].imag() )
        {
            ++i;
        }
    }
}
/////////////////////////////////////////////////////////////////////////////////////////
int main()
{
    std::locale::global(std::locale(""));
    T_segments  segments;
 
    input_segments(segments);
    
    int         max_segm_counter        = 0;
    T_coord     max_segm_counter_point  = 0;
 
    get_max_segm_counter_and_max_segm_counter_point
        (
            segments,
            max_segm_counter,
            max_segm_counter_point
        );
 
    std::cout << "Наибольшему количеству отрезков ("
              << max_segm_counter
              << ") принадлежит точка "
              << max_segm_counter_point
              << "."
              << std::endl;
}
BRcr
 Аватар для BRcr
4003 / 2292 / 155
Регистрация: 03.02.2011
Сообщений: 5,064
Записей в блоге: 10
12.01.2012, 16:05     найти точку, принадлежащую #16
Цитата Сообщение от slava0394 Посмотреть сообщение
жесть
Фигня Вот то, что Mr.X сваял, то - да, жесть, она самая. Сразу видно, что у человека до того рука набита, что на пальцах, наверно, уже мозоли от клавиатуры.
Mr.X
Эксперт С++
 Аватар для Mr.X
2807 / 1583 / 248
Регистрация: 03.05.2010
Сообщений: 3,695
13.01.2012, 00:25     найти точку, принадлежащую #17
Цитата Сообщение от BRcr Посмотреть сообщение
Вот то, что Mr.X сваял, то - да, жесть
Действительно, два счетчика в мэпе - это жесть, можно использовать один:
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
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
/////////////////////////////////////////////////////////////////////////////////////////
//Дано множество отрезков на прямой. Найти точку, которая принадлежит наибольшему 
//количеству отрезков, определить это количество.
/////////////////////////////////////////////////////////////////////////////////////////
#include <algorithm>
#include <complex>
#include <iostream>
#include <iterator>
#include <map>
#include <numeric>
#include <vector>
/////////////////////////////////////////////////////////////////////////////////////////
typedef double                                  T_coord;
typedef int                                     T_counter;
typedef std::complex    <T_coord>               T_segment;
typedef std::vector     <T_segment>             T_segments;
typedef std::map        <T_coord, T_counter>    T_segm_end_points;
typedef std::vector     <T_counter>             T_counters;
/////////////////////////////////////////////////////////////////////////////////////////
void  fill_segm_end_points
    (
        const T_segments&   segments,
        T_segm_end_points&  segm_end_points
    )
{
    for(
        T_segments::const_iterator  segm_it = segments.begin();
        segm_it != segments.end();
        ++segm_it
       )
    {
        ++segm_end_points[segm_it->real()];
        --segm_end_points[segm_it->imag()];
    }
}
/////////////////////////////////////////////////////////////////////////////////////////
void  get_max_segm_counter_and_max_segm_counter_point
    (
        const T_segments&   segments,
        T_counter&          max_segm_counter,
        T_coord&            max_segm_counter_point    
    )
{
    T_segm_end_points  segm_end_points;
 
    fill_segm_end_points
        (
            segments,
            segm_end_points
        );
 
    struct  T_get_counter
    {
        T_counter  operator() (const T_segm_end_points::value_type&  segm_end_points_elem)
        {
            return  segm_end_points_elem.second;
        }
    };
 
    T_counters  counters;
    std::transform
        (
            segm_end_points.begin(),
            segm_end_points.end(),
            std::back_inserter(counters),
            T_get_counter()
        );
 
    T_counters  counters_sums;
    std::partial_sum
        (
            counters.begin(),
            counters.end(),
            std::back_inserter(counters_sums)
        );
    
    T_counters::iterator  max_sum_it  =     std::max_element
                                                (
                                                    counters_sums.begin(),
                                                    counters_sums.end()
                                                );
 
    max_segm_counter    = *max_sum_it;
 
    int  max_sum_dist   =   std::distance
                                (
                                    counters_sums.begin(),
                                    max_sum_it
                                );
 
    T_segm_end_points::const_iterator  L = segm_end_points.begin();
    std::advance(L, max_sum_dist);
    T_segm_end_points::const_iterator  R = L;
    std::advance(L, 1);
 
    max_segm_counter_point = (L->first + R->first) / 2.0;
}
/////////////////////////////////////////////////////////////////////////////////////////
void  input_segments(T_segments&  segments)
{
    int  segments_total = 0;
    do
    {
        std::cout << "Введите количесто заданных отрезков на прямой: ";
        
        std::cin >> segments_total;    
    }while(segments_total <= 0);
 
    std::cout << "Введите координаты "
              << segments_total
              << " отрезков в виде (1.2,3.4):"
              << std::endl;
 
    segments.resize(segments_total);
    for(int  i = 0; i < segments_total;)
    {        
        std::cout << "\t#"
                  << i + 1
                  << ": ";
        
        std::cin >> segments[i];
        if( segments[i].real() < segments[i].imag() )
        {
            ++i;
        }
    }
}
/////////////////////////////////////////////////////////////////////////////////////////
int main()
{
    std::locale::global(std::locale(""));
    T_segments  segments;
 
    input_segments(segments);
    
    T_counter   max_segm_counter        = 0;
    T_coord     max_segm_counter_point  = 0;
 
    get_max_segm_counter_and_max_segm_counter_point
        (
            segments,
            max_segm_counter,
            max_segm_counter_point
        );
 
    std::cout << "Наибольшему количеству отрезков ("
              << max_segm_counter
              << ") принадлежит точка "
              << max_segm_counter_point
              << "."
              << std::endl;
}
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
13.01.2012, 11:49     найти точку, принадлежащую
Еще ссылки по теме:

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

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

Или воспользуйтесь поиском по форуму:
slava0394
1 / 1 / 0
Регистрация: 05.12.2011
Сообщений: 39
13.01.2012, 11:49  [ТС]     найти точку, принадлежащую #18
нифига себе) она работает?
Yandex
Объявления
13.01.2012, 11:49     найти точку, принадлежащую
Ответ Создать тему
Опции темы

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