Модераторы: Alx, Fixin

Поиск:

Ответ в темуСоздание новой темы Создание опроса
> [Алгоритм] Построение N-угольника, охватывающего все указанные окружности 
V
    Опции темы
KasMP
Дата 8.12.2008, 12:44 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


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

Репутация: 2
Всего: 30
Я нелепо споткнулась на самом неожиданном месте, на поиске самой нижней (правой) точки.
У меня 2 функции:
  • LowermostRightPoint.
    По сути, непосредственно оценками она не занимается, она просто помнит текущую лучшую точку и подкидывает новые точки функции PresentFirstPoint, которая и выполняет всю оценивающую работу (короче можно сказать, что LowermostRightPoint координирует действия, выполняет административную функцию).
  • PresentFirstPoint.
      Она получает:
    • ссылку на массив с координатами;
    • индекс точки, которую нужно сравнить с лучшей текущей (i);
    • индекс текущей лучшей точки (res).
    Сначала она смотрит, меньше ли ордината текущей точки, чем ордината лучшей точки. Если меньше, то, естественно, ты запоминаем номер текущей точки как лучший.
    Если не меньше, то проверяем, а не совпадают ли ординаты. Если совпадают, то более чем логично сравнить абсциссы... Лучшая точка та, у которой абсцисса больше.
    Потом  PresentFirstPoint возвращает в своему руководителю LowermostRightPoint номер лучшей на данный момент точки.
По-моему, все идеально. Но работает, как хочет... То правильно, то выбирает правейшую (нижнюю) точку, то вообще левую верхнюю smile  smile .

Код

// часть поиска нижней правой точки: если текущая точка лучше запомненной, то вернуть индекс текущей (иначе вернуть тот же индекс, который был)
short int PresentFirstPoint (short int coordinate[][2], short int i, short int res)
{
      short int present=coordinate[i][1];
      short int res_present=res;
             
      if (present<coordinate[res][1])
         res_present=i;
         else {
              if (present=coordinate[res][1])
                res_present=(coordinate[i][0]>coordinate[res][0] ? i : res);
         }
      
                       
      return (res_present);
}


Код

// поиск нижней правой точки, возвращает ее номер
short int LowermostRightPoint (short int coordinate[][2], short int number)
{
      short int i, k, res;
      short int present1, present2;
      
      /* if (number%2)
         k=number/2;
         else k=number/2-1; 
         это типа объяснение того, как получилась следующая строчка*/
      k=number/2+number%2-1;
      res=0;
      
      for (i=0; i<=k; ++i) {
          res=PresentFirstPoint(coordinate,i         ,res);
          res=PresentFirstPoint(coordinate,number-i-1,res);
      }
        
      return(res);
}


Добавлено через 4 минуты и 31 секунду
Если кто-то решится помочь, то следующее - для вашего удобства smile ...

Код

// ввод координат точек
void InputCoordinate (short int coordinate[][2], short int number)
{
     short int i;
     for (i=0; i<number; ++i) {
         printf ("Input X for %d tree:\n", i+1); scanf ("%d", &coordinate[i][0]);
         printf ("Input Y for %d tree:\n", i+1); scanf ("%d", &coordinate[i][1]);
     }
}


Код

main() {
       
       // ввод кол-ва точек, их координат
       short int   number;
       printf ("Input a number of trees.\n"); scanf ("%d", &number);
       short int   coordinate[number][2];
       printf ("Input coordinates of trees.\n"); InputCoordinate(coordinate,number);

...
}


Добавлено через 7 минут и 18 секунд
Еще быстрая сортировка не сортирует точки в порядке увеличения угла (уменьшения косинуса) массив... Но уж с этим я должна разобраться!!!!!!!!!
PM MAIL   Вверх
THandle
Дата 8.12.2008, 23:02 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Хранитель Клуба
Group Icon
Награды: 1



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

Репутация: нет
Всего: 372
KasMP, ох... C++... 

Покажи то описание по которому ты пишешь алгоритм. Я попробую сначала на Паскале сделать, а потом перевести... Задачка интересная. smile

Еще, чтобы не возникало подобных тем:
http://forum.vingrad.ru/forum/topic-230265.html

Я сделал зеркало на эту тему во флейм(пока на неделю). Если против этого зеркала имеешь что-то - сразу удалю smile
PM   Вверх
KasMP
Дата 8.12.2008, 23:16 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


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

Репутация: 2
Всего: 30
Цитата(THandle @  8.12.2008,  23:02 Найти цитируемый пост)
Покажи то описание по которому ты пишешь алгоритм. 

Вот smile .
Цитата(THandle @  8.12.2008,  23:02 Найти цитируемый пост)
Еще, чтобы не возникало подобных тем:

Ок, больше не буду smile smile .
Цитата(THandle @  8.12.2008,  23:02 Найти цитируемый пост)
Я сделал зеркало на эту тему во флейм(пока на неделю). Если против этого зеркала имеешь что-то - сразу удалю

Удали, пожалуйста smile .

Добавлено через 8 минут и 44 секунды
Вообще говоря, остальные части алгоритма у меня написаны и должны работать (по крайней мере, на мини-тестиках выполнялись правильно).

А вот с на первый взгляд легкой задачкой определения самой нижней (правой) точки творится что-то нереальное! Вот где у меня ошибка? Я прогоняла на бумажечке разные значения всего - все правильно. Может быть, ошибка в каких-то конкретно моих настройках?
PM MAIL   Вверх
THandle
Дата 9.12.2008, 12:01 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Хранитель Клуба
Group Icon
Награды: 1



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

Репутация: нет
Всего: 372
Цитата(KasMP @  8.12.2008,  23:16 Найти цитируемый пост)
Ок, больше не буду


Да я не против smile Просто кажется что никто в такие темы не заходит/не переходит по ссылкам.

Цитата(KasMP @  8.12.2008,  23:16 Найти цитируемый пост)
Удали, пожалуйста 


Ок.


В общем - делаю сейчас прожку. Для наглядности все точки выводим в виде рисунка на экран(типа как в описании алгоритма).
Получилось найти первый элемент и отсортировать массив. Остальное буду пробовать сделать вечером...
PM   Вверх
KasMP
Дата 9.12.2008, 12:40 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


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

Репутация: 2
Всего: 30
Напишу заголовки моих функций (вдруг ты решишь организовать свои подобным образом smile - будет проще сравнивать smile )...

Код

// ввод координат точек
void InputCoordinate (short int coordinate[][2], short int number)

// часть поиска нижней правой точки: если текущая точка лучше запомненной, то вернуть номер текущей точки
short int PresentFirstPoint (short int coordinate[][2], short int i, short int res)

// поиск нижней правой точки; возвращает ее номер
short int LowermostRightPoint (short int coordinate[][2], short int number)

// возвращает косинус угла между векторами first_i и (1,0)      
float Angle_First_OX (short int coordinate[][2], short int i, short int first_x, short int first_y)

// обменивает местами элементы [i][0] и [j][0], [i][1] и [j][1] массива array
void Swap (float array[][2], short int i, short int j)
/* нужно для двумерного массива, у которого
[i][0] - значения косинусов углов между векторами (first; i) и (1,0)
[i][1] - индекс соответствующей точки */

// быстрая сортировка массива array
void Quicksort (float array[][2], short int left, short int right)

// определяет, образуют ли точки 1-2-3 левый поворот (true - поворот левый)
bool LeftSwerve (short int x1, short int y1, short int x2, short int y2, short int x3, short int y3)

// возвращает расстояние между точками (x1,y1) и (x2,y2)
float Distance (short int x1, short int y1, short int x2, short int y2)

// возвращает периметр многоугольника из точек, индексы которых хранятся в стеке stack[number]; 
float Perimeter (short int stack[], short int coordinate [][2], short int number)


Добавлено через 48 секунд
Цитата(THandle @  9.12.2008,  12:01 Найти цитируемый пост)
Да я не против smile Просто кажется что никто в такие темы не заходит/не переходит по ссылкам.

Как показывает опыт, переходят и даже думают (а иногда де отвечают) smile !
Цитата(THandle @  9.12.2008,  12:01 Найти цитируемый пост)
Ок.

Спасибо smile .
PM MAIL   Вверх
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 smile .
PM MAIL   Вверх
KasMP
Дата 10.12.2008, 02:51 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


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

Репутация: 2
Всего: 30
Ураааааааааааааааааа smile  smile  smile  smile !!!!!
Поздравьте меня smile  smile  smile !!!!!!!! Я нашла ошибку в одной из функций для поиска нижней правой точки!!!!

Просто вместо "==" я по привычке написала "=" smile  smile ! И, соответственно, условие проверялось неправильно и  smile  smile  smile ...
PM MAIL   Вверх
THandle
Дата 10.12.2008, 02:56 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Хранитель Клуба
Group Icon
Награды: 1



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

Репутация: нет
Всего: 372
KasMP, поздравляю!!! smile Интересно как вообще удалось такой код скомпилировать...

А я сейчас сижу, и пытаюсь думать над тем как бы доделать все это не очень кривым образом, хотя больше получается уже спать))
PM   Вверх
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 ...
PM MAIL   Вверх
Ответ в темуСоздание новой темы Создание опроса
0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | Интересные и занимательные задачи по программированию | Следующая тема »

Подписаться на тему | Подписка на этот форум | Скачать/Распечатать тему


 




[ Время генерации скрипта: 0.0569 ]   [ Использовано запросов: 23 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
 По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.