С Новым годом! Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Карта форума Темы раздела Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.51/75: Рейтинг темы: голосов - 75, средняя оценка - 4.51
0 / 0 / 0
Регистрация: 11.12.2015
Сообщений: 50
1

Алгоритм Грэхема

24.05.2016, 01:02. Показов 13997. Ответов 3
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Всем доброго времени суток
На завтра надо уже принести алгоритм грэхема, но толком ничего не объяснил преподаватель
Нашёл разные источники, но что не скопирую к себе - всё не работает

1) http://e-maxx.ru/algo/convex_hull_graham
тут ему не нравится "down", говорит, что "а" не определена и хочет добавить пару точек с запятой
2) http://hardfire.ru/graham
говорит, что point, dist, ccw - не определены
наверное нужна какая-то библиотека, но кажется у меня гуглить даже не выходит
3) Алгоритм Грэхема
но там ругается на "down", "a" и просит точку с запятой

Может что-то в студии вообще не так?
Подскажите пожалуйста как исправить в любом из источников, чтобы заработало
0
IT_Exp
Эксперт
8794 / 1073 / 104
Регистрация: 17.06.2006
Сообщений: 12,602
Блог
24.05.2016, 01:02
Ответы с готовыми решениями:

Алгоритм Грэхема
очень надо

Алгоритм грэхема
Добрые люди помогите пожалуйста. Есть код который выполняет алгоритм Грехема. Количество точек...

Алгоритм Грэхема, реализация на С++
Помогите написать реализацию Алгоритма на С++.

Реализация Алгоритма Грэхема на С++
Доброго времени суток, пожалуйста помогите разобраться с написанием программы. Что непонятно: 1)...

3
58 / 62 / 34
Регистрация: 14.03.2014
Сообщений: 916
24.05.2016, 08:35 2
Как то писал такое.
Кликните здесь для просмотра всего текста
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
#include <stack>
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
struct Point {
    double x, y;
    Point(double a = 0, double b = 0) {
        x = a;
        y = b;
    }
    bool operator < (const Point& p) {
        return ((x*p.y - y*p.x)>0);
    } 
    Point operator - (const Point &p) {
        return Point(x - p.x, y - p.y);
    }
    Point operator + (const Point &p) {
        return Point(x + p.x, y + p.y);
    }
};
 
typedef vector<Point> vec_point;
 
vec_point read_verts(const string filename) {
    ifstream f1(filename);
 
    vec_point verts;
    int n;
    Point temp;
 
    f1 >> n;
 
    for (int i = 0; i < n; i++) {
        f1 >> temp.x >> temp.y;
        verts.push_back(temp);
    }
    return verts;
}
 
vec_point Graham(vec_point verts) {
    int min = 0;
    for (int i = 1; i < verts.size(); i++) {
        if (verts[min].y > verts[i].y)
            min = i;
    }
    swap(verts[min], verts[0]);
 
    for (int i = 1; i < verts.size(); i++) {
        verts[i].x -= verts[0].x;
        verts[i].y -= verts[0].y;
    }
 
    sort(verts.begin() + 1, verts.end());
 
    stack<int> Stack;
    Stack.push(0);
    Stack.push(1);
 
    for (int c = 2; c < verts.size(); c++) {
        int a, b;
        do {
            b = Stack.top();
            Stack.pop();
            a = Stack.top();
        } while (!((b - a) < (c - b)));
        Stack.push(b);
        Stack.push(c);
    }
 
    vec_point res;
    while (Stack.size()) {
        int num = Stack.top();
        Stack.pop();
        res.push_back(verts[num] + verts[0]);
    }
    res.push_back(verts[0]);
 
    return res;
}
 
int main() {
    vec_point res = Graham(read_verts("graham.txt"));
    for (int i = 0; i < res.size(); i++)
        cout << res[i].x << ' ' << res[i].y << '\n';
 
    return 0;
}
0
0 / 0 / 0
Регистрация: 11.12.2015
Сообщений: 50
24.05.2016, 16:44  [ТС] 3
Что-то как-то выдало 21 ошибочку
Алгоритм Грэхема


Добавлено через 2 часа 1 минуту
а, нет, обновил студию, теперь ругается на несоответствие типов со знаком и без знака
C++ (Qt)
1
for (int i = 1; i < verts.size(); i++)
Добавлено через 6 минут
сделал переменные беззнаковыми чтобы убрать предупреждения, но всё равно продолжает ругаться Vector out of range
0
58 / 62 / 34
Регистрация: 14.03.2014
Сообщений: 916
24.05.2016, 17:39 4
Попробуй мой второй вариант. Щас просто не охото вдаваться в подробности почему тот не работает. Этот основан на atan2 и берет значения из файла.
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
#include <iostream>
#include<cmath>
#include<stack>
#include<vector>
#include<fstream>
using namespace std;
const double PI = 3.14159265;
//============================================//
 
struct hull
{
    double x;
    double y;
};
 
int Lowest_point(hull *value, const int n)
{
    int k = 0;
    for (int i = 1; i < n; i++)
    {
        if (value[i].y < value->y)
        {
             k = i;
        }
 
    }
    return k;
}
 
void Angle(vector<double>& ps2, hull* point, const int n)
{
    
    ps2.resize(n);
    int j = Lowest_point(point, n);
    for (int i = 0; i < n; i++)
        ps2[i] = atan2(point[i].y - point[j].y, point[i].x - point[j].x) * 180 / PI;
 
    for (int i = 0; i < n; i++)
        cout << ps2[i] << endl;
}
 
void Sort(vector<double> &a, hull *b, const int n)
{
 
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (a[j] > a[i])
            {
                swap(a[i], a[j]);
                swap(b[i], b[j]);
            }
        }
    }
}
 
double result(const hull &p1, const hull &p2, const hull &p3)
{
    return (p2.x - p1.x)*(p3.y - p1.y) - (p3.x - p1.x)*(p2.y - p1.y);
}
 
bool leftTurn(const hull &a, const hull &b, const hull &c)
{
    return result(a, b, c) > 0;
}
 
void Stack(vector<double> &ang, hull *point)
{
    stack<int>S;
    S.push(0);
    S.push(1);
 
    for (int c = 2; c < ang.size(); c++)
    {
        int a, b;
        do
        {
            b = S.top();
            S.pop();
            a = S.top();
        }
 
        while (!leftTurn(point[a], point[b], point[c]));
 
        S.push(b);
        S.push(c);
    }
 
    cout << endl;
    while (!S.empty())
    {
        cout << point[S.top()].x << " " << point[S.top()].y << endl;
        S.pop();
    }
}
 
 
int main()
{
    ifstream inFile;
    inFile.open("point.txt");
 
    if (!inFile.is_open())
    {
        cout << "Could not open the file! ";
        system("pause");
        exit(EXIT_FAILURE);
    }
 
    int N;
    inFile >> N;
 
    hull *ps = new hull[N];
 
    int i = 0;
    while (i < N && inFile.good())
    {
        inFile >> ps[i].x >> ps[i].y;
        ++i;
    }
    vector<double>ps2;
 
    Angle(ps2, ps, N);
    Sort(ps2, ps, N);
    Stack(ps2, ps);
 
    delete[] ps;
    system("pause");
    return 0;
}
Первая цифра в файле это число сколько у тебя будет пар точек.
1
24.05.2016, 17:39
BasicMan
Эксперт
19315 / 2622 / 84
Регистрация: 17.02.2009
Сообщений: 10,364
Блог
24.05.2016, 17:39
Помогаю со студенческими работами здесь

Реализация Алгоритма Грэхема и Джарвиса на С++
Ищу того, кто сделает за деньги с комментариями к каждой строке. В ЛС цену и за какое время.

Нужен алгоритм поиска пути в этом лабиринте (будь то волновой алгоритм или алгоритм правой/левой руки )
#include &quot;stdafx.h&quot; #include &lt;iostream&gt; #include &lt;conio.h&gt; using namespace std; void lab...

Волновой алгоритм поиска (Алгоритм A* / Алгоритм А стар)
Хочу разработать алгоритм для решения головоломки с подвижными дисками (перестановочная...

Алгоритм Грэхема
Помогите, пожалуйста составить Алгоритм Грэхема, есть такой код, но там ничего не понимаю struct...


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

Или воспользуйтесь поиском по форуму:
4
Ответ Создать тему
Блоги программистов
Обновление сайта www.historian.b­y
Reglage 05.01.2025
Обещал подвести итоги 2024 года для сайта. Однако начну с того, что изменилось за неделю. Добавил краткий урок по последовательности действий при анализе вредоносных файлов и значительно улучшил урок. . .
Как использовать GraphQL в C# с HotChocolate
Programming 05.01.2025
GraphQL — это современный подход к разработке API, который позволяет клиентам запрашивать только те данные, которые им необходимы. Это делает взаимодействие с API более гибким и эффективным по. . .
Модель полного двоичного суматора с помощью логических операций (python)
AlexSky-coder 04.01.2025
def binSum(x:list, y:list): s=^y] p=x and y for i in range(1,len(x)): s. append((x^y)^p) p=(x and y)or(p and (x or y)) return s x=list() y=list()
Это мы не проходили, это нам не задавали...(аси­хронный счётчик с управляющим сигналом задержки).
Hrethgir 04.01.2025
Асинхронный счётчик на сумматорах (шестиразрядный по числу диодов на плате, но наверное разрядов будет больше - восемь или шестнадцать, а диоды на старшие), так как триггеры прошли тестирование и. . .
Руководство по созданию бота для Телеграм на Python
IT_Exp 04.01.2025
Боты для Телеграм представляют собой автоматизированные программы, которые выполняют различные задачи, взаимодействуя с пользователями через интерфейс мессенджера. В данной статье мы рассмотрим,. . .
Применение компонентов PrimeVue в Vue.js 3 на TypeScript
BasicMan 04.01.2025
Введение в PrimeVue и настройка окружения PrimeVue представляет собой мощную библиотеку компонентов пользовательского интерфейса для Vue. js 3, которая предоставляет разработчикам богатый набор. . .
Как стать Senior developer
cpp_developer 04.01.2025
В современной индустрии разработки программного обеспечения позиция Senior Developer представляет собой не просто следующую ступень карьерной лестницы, а качественно новый уровень профессионального. . .
Что известно о дате выхода Windows 12 и чего от нее ждать
IT_Exp 04.01.2025
В мире технологий постоянно происходят изменения, и операционные системы не являются исключением. Windows 11, выпущенная в октябре 2021 года, принесла множество инноваций и улучшений, но. . .
Что новенького в .NET Core 9
Programming 04.01.2025
Обзор ключевых изменений в . NET Core 9 Платформа . NET Core продолжает активно развиваться, и версия 9 представляет собой значительный шаг вперед в эволюции этой технологии. Новый релиз. . .
Инструкция по установке python3.13.1 в Debian 12
AlexSky-coder 03.01.2025
sudo apt update sudo apt install build-essential zlib1g-dev libncurses5-dev libgdbm-dev libnss3-dev libssl-dev libreadline-dev libffi-dev wget. . .
Затестил триггеры. архив проекта прилагаю с GOA файлами в настройках архиватора проектов.
Hrethgir 03.01.2025
В этот раз нет закольцованности, потому что от неё только глюки, как я понял, логика не вырезанная. Триггеры очень быстрые если верить измерениям с помощью анализатора от Gowin. Есть ещё регистры,. . .
Python в помощь DevOps
IT_Exp 03.01.2025
Причины использования Python в работе DevOps Python стал неотъемлемой частью мира DevOps, и это не случайно. Этот язык программирования обладает множеством преимуществ, которые делают его. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2025, CyberForum.ru