VPF::[Алгоритм] Построение N-угольника

KasMP

Дата 9.12.2008, 12:56 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Завсегдатай
Сообщений: 586
Регистрация: 8.8.2006

Репутация: 2
Всего: 30

Вобщем, у меня проблемы с определением нижней правой точки (уже описывала подробно) и с быстрой сортировкой.

Быстрая сортировка представлена тремя функциями и должна сортировать элементы массива angle[number][2] с индексами [i][0] по убыванию (параллельно переставляя соседей с индексами [i][1]).
Массив

Код

float angle[number][2]

содержит:

[i][0] - значения косинусов углов между векторами first_i и (1,0)
[i][1] - индекс соответствующей точки

Все это сделано так:

Код


// обменивает местами элементы [i][0] и [j][0], [i][1] и [j][1] массива array
void Swap (float array[][2], short int i, short int j)
{
     float t;
     t=array[i][0]; array[i][0]=array[j][0]; array[j][0]=t;
     t=array[i][1]; array[i][1]=array[j][1]; array[j][1]=t;
}


// возвращает новую позицию элементов array[left][0|1]
int Border (float array[][2], short int left, short int right)
{
     short int i=left;
    
     for (short int j=left; j<=right; j++)
        if (array[j][0]<=array[left][0]) {
           Swap(array,i,j);
           i++;
        }
        
     return(i-1);
}


// быстрая сортировка массива array
void Quicksort (float array[][2], short int left, short int right)
{      
     if (left>=right) return;
     int c=Border(array,left,right);
     Quicksort(array,left,c-1); Quicksort (array,c+1,right);
}

Добавлено через 3 минуты и 6 секунд
Кстати, сначала я собиралась при сортировке не переставлять сами элементы, а создать дополнительный массив-вектор, в котором будут переставляться уже только индекс соответствующих элементов.
Я уже отказалась от этого. Чувствую, скоро скачусь до пузырька я его О(n^3) smile

KasMP

Дата 10.12.2008, 02:51 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Завсегдатай
Сообщений: 586
Регистрация: 8.8.2006

Репутация: 2
Всего: 30

Ураааааааааааааааааа smile

!!!!!
Поздравьте меня smile

!!!!!!!! Я нашла ошибку в одной из функций для поиска нижней правой точки!!!!

Просто вместо "==" я по привычке написала "=" smile

! И, соответственно, условие проверялось неправильно и smile

...

THandle

Дата 10.12.2008, 02:56 (ссылка)

(нет голосов)

Загрузка ...

Хранитель Клуба
Group Icon

Награды: 1

Профиль
Группа: Админ
Сообщений: 3639
Регистрация: 31.7.2007
Где: Moscow, Dubai

Репутация: нет
Всего: 372

KasMP, поздравляю!!! smile

Интересно как вообще удалось такой код скомпилировать...

А я сейчас сижу, и пытаюсь думать над тем как бы доделать все это не очень кривым образом, хотя больше получается уже спать))

KasMP

Дата 10.12.2008, 03:00 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Завсегдатай
Сообщений: 586
Регистрация: 8.8.2006

Репутация: 2
Всего: 30

Цитата(THandle @ 10.12.2008, 02:56

)

Интересно как вообще удалось такой код скомпилировать...

Там получалось что-то типа "2 присвоить 1" (2 <- 1). Впринципе, это вполне может дать в итоге 1 и быть всегда верным smile

.
Подумаю об этом потом, пока надо дальше делать smile

...

1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Интересные и занимательные задачи по программированию \| Следующая тема »