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

Множество точек m - C++

Восстановить пароль Регистрация
 
MasoD
 Аватар для MasoD
6 / 6 / 1
Регистрация: 03.10.2010
Сообщений: 44
05.11.2011, 17:04     Множество точек m #1
Трям.

Имеется условие: Задано множество точек m в трехмерном пространстве. Найти такую из них, что шар заданного радиуса с центром в этой точке содержит максимальное число точек из m.

Примерный алгоритм: Проверяем в цикле все точки. Проверяем во вложенном цикле расстояние от текущей точки до одной из остальных. Если оно меньше R - увеличиваем счетчик для этой точки. После этого еще раз проверям все точки, у которой счетчик больше - та и есть искомая.

Но вот с реализацией проблемы. С си знаком всего пол семестра, поэтому никак не получается написать.

Заранее спс.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
05.11.2011, 17:04     Множество точек m
Посмотрите здесь:

C++ множество точек
C++ Множество точек.Найти множество треугльники
C++ на плоскости задано множество точек. Найти все подмножества точек, лежащих на одной прямой.
C++ Задано множество точек в трехмерном пространстве. Найти минимум радиусов шаров с центрами в этих точках, содержащих ровно n точек этого множества
C++ На плоскости задано множество точек. Выбрать три различные точки так, чтобы проходящая через них окружность делила это множество на группы
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Mиxaил
 Аватар для Mиxaил
530 / 435 / 37
Регистрация: 10.12.2009
Сообщений: 1,857
05.11.2011, 18:30     Множество точек m #2
MasoD, ЯП - это лишь способ реализации алгоритма, и ничего больше! Поэтому говорить, что с Си знакомы пол семестра ( этого больше, чем достаточно ), не имеет смысла, если можете реализовать решение этой проблемы математически.

Насчет задачи:
Множество - это ведь отсортированный контейнер. Поэтому не составит труда пробежаться по этому контейнеру, и проверять левые и правые элементы. Расстояние от проверяемой точки до исходной должно быть меньше, чем заданный радиус.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
05.11.2011, 19:29     Множество точек m #3
Цитата Сообщение от Mиxaил Посмотреть сообщение
Поэтому не составит труда пробежаться по этому контейнеру, и проверять левые и правые элементы.
можно только правые
Mиxaил
 Аватар для Mиxaил
530 / 435 / 37
Регистрация: 10.12.2009
Сообщений: 1,857
05.11.2011, 19:32     Множество точек m #4
Цитата Сообщение от valeriikozlov Посмотреть сообщение
можно только правые
Разумно... Согласен!
MasoD
 Аватар для MasoD
6 / 6 / 1
Регистрация: 03.10.2010
Сообщений: 44
06.11.2011, 13:18  [ТС]     Множество точек m #5
Вот, может кому пригодится.
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
#include <iostream>
#include <locale>
#include <cmath>
#include <iomanip>
 
using std::cout;
using std::cin;
using std::endl;
using std::setw;
 
int main()
{
    setlocale(LC_ALL,"Russian");
    struct coord
    {
        int x;
        int y;
        int z;
    };
    const int n = 15;
    coord a[n];
    coord b;
    int amt[n] = {0};
    int R = 0;
    int max = 0;
    double dis = 0.0;
    srand(time(NULL));
    for (int i = 0; i < n; i++)
    {
        a[i].x = rand() % 20;
        a[i].y = rand() % 20;
        a[i].z = rand() % 20;
    }
    cout << endl
        << "Введите радиус: ";
    cin >> R;
    for (int i = 0; i < n; i++) 
        for (int j = i + 1; j < n; j++)
        {                           
            dis = sqrt(pow((a[j].x - a[i].x), 2.0) + pow((a[j].y - a[i].y), 2.0) + pow((a[j].z - a[i].z), 2.0));
            if (dis < R)
                amt[i]++;
        }
    for (int i = 0; i < n; i++)
        if ((amt[i] >= max) && (amt[i] != 0))
        {
            max = amt[i];
            b.x = a[i].x;
            b.y = a[i].y;
            b.z = a[i].z;
        }
    cout << endl
        << "Случайные точки в пространстве:"
        << endl;
    for (int i = 0; i < n; i++)
        cout << setw(4) << "(" << setw(2) << a[i].x << ", " << setw(2) << a[i].y << ", " << setw(2) << a[i].z << ")"
            << endl;
    if (b.x < 0)
        cout << endl
            << "Искомая точка отсутствует."
            << endl;
    else
    {
        cout << endl
            << "Шар радиуса " << R << " с центром в точке " << "(" << b.x << ", " << b.y << ", " << b.z << ")" << " содержит максимальное число точек"
            << endl
            << "из m."
            << endl;
    }
    system("pause");
    return 0;
}
Yandex
Объявления
06.11.2011, 13:18     Множество точек m
Ответ Создать тему
Опции темы

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