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

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

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

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

11.01.2012, 23:00. Просмотров 1417. Ответов 17
Метки нет (Все метки)

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

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

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

Найти точку D, симметричную точку A относительно стороны BC. - C++
помогите решить пожалуйста...

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

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

Найти в строке точку - C++
Всем привет ! Нужно найти в строке точку. Делаю #include <iostream> #include <string> ...

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

Я вас уверяю, если вы подумаете хотя бы в течении минуты то поймёте алгоритм решения, и тогда я вам помогу с тяжёлым для вас пока программированием и напишу код.
2
slava0394
1 / 1 / 0
Регистрация: 05.12.2011
Сообщений: 39
12.01.2012, 10:18  [ТС] #7
ну по идее это середина отрезка
0
fasked
Эксперт С++
4976 / 2556 / 180
Регистрация: 07.10.2009
Сообщений: 4,311
Записей в блоге: 1
12.01.2012, 10:40 #8
Цитата Сообщение от slava0394 Посмотреть сообщение
ну по идее это середина отрезка
Смотря как расположены отрезки.
0
Байт
Эксперт C
17715 / 11736 / 1872
Регистрация: 24.12.2010
Сообщений: 23,542
12.01.2012, 11:40 #9
Я бы взял концы всех отрезков, и посмотрел бы какому количеству других отрезков они принадлежат.
Условие принадлежности точки x отрезку [a,b]: a <= x <= b
0
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");
}
1
Байт
Эксперт C
17715 / 11736 / 1872
Регистрация: 24.12.2010
Сообщений: 23,542
12.01.2012, 13:33 #11
Цитата Сообщение от Whiteha Посмотреть сообщение
это просто пробежаться по каждой точке отрезка
Любопытно, как вы собираетесь пробежаться по континуму ?
0
Whiteha
Программист
33 / 33 / 4
Регистрация: 08.07.2011
Сообщений: 190
Записей в блоге: 1
12.01.2012, 13:53 #12
Я исходил из дискретности отрезка, автор ведь не указал какому множеству принадлежит отрезок и я выдвинул самую простую версию. Хотя конечно не самую универсальную.=)
0
slava0394
1 / 1 / 0
Регистрация: 05.12.2011
Сообщений: 39
12.01.2012, 14:10  [ТС] #13
жесть
0
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);
}
0
Mr.X
Эксперт С++
3060 / 1705 / 265
Регистрация: 03.05.2010
Сообщений: 3,867
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;
}
0
12.01.2012, 15:29
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
12.01.2012, 15:29
Привет! Вот еще темы с ответами:

Найти точку на окружности - C++
Здравствуйте. Подскажите, пожалуйста. По написанной программе надо найти точку, лежащую на окружности. Было задание :Составить...

Найти точку на прямой - C++
Найти на кривой Y(X)=sin2(2X)cos(4X) точку, абсцисса которой принадлежит интервалу и сумма расстояний от которой до прямых a1x+b1y+c1=0 и...

Найти точку максимума функции - C++
Может кто то подскажет с чего хотя бы начать ? Задания нужно переписывать!

Найти седловую точку матрицы! - C++
Седловой точкой матрицы назовём такой элемент, который является одновременно максимальным в столбце и минимальным в строке. Найти одну,...


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

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

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