Модераторы: Poseidon
  

Поиск:

Ответ в темуСоздание новой темы Создание опроса
> [Pasсal] Двумерный массив 
V
    Опции темы
Mitya
Дата 9.3.2007, 16:18 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 7
Регистрация: 5.3.2007

Репутация: нет
Всего: нет
Массив KOORD[1..2,1..n] представляет собой координаты N точек на плоскости: 1-я строка - абсциссы, 2-я строка - ординаты. Найти номера двух точек, расстояние между которыми максимально.

X  1  3  4  2  4
Y  2  3  5  4  1

В данном случае N=5



Всем огромное спасибо!
PM MAIL   Вверх
Strannik
Дата 9.3.2007, 19:57 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Бывалый
*


Профиль
Группа: Участник
Сообщений: 154
Регистрация: 25.1.2007

Репутация: 1
Всего: 2
Алгоритм тупой (O(N^2)) или умный (O(NlogN)) нужен?
PM MAIL   Вверх
Mitya
Дата 9.3.2007, 21:25 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 7
Регистрация: 5.3.2007

Репутация: нет
Всего: нет
Цитата(Strannik @  9.3.2007,  19:57 Найти цитируемый пост)
Алгоритм тупой (O(N^2)) или умный (O(NlogN)) нужен? 


А циклом for  нельзя? Просто я еще учусь, а такого даже не знаю... там я написал for i:=1 to 2 do for j:=1 to n do begin А вот дальше - ступор...
PM MAIL   Вверх
Kuvaldis
Дата 9.3.2007, 21:57 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


механик-вредитель
***


Профиль
Группа: Участник Клуба
Сообщений: 1189
Регистрация: 16.6.2006
Где: Минск

Репутация: 32
Всего: 61
Код

const
    MAX = 100;

type
  Point = record
      x, y : integer;
  end;

var
    list : array [1..MAX] of Point;
    n, i, k : integer;
    max_len : real;
    curr_len : real;
    pos1, pos2 : integer;

// функция расстояния между точками    
function PointLen(a, b : Point) : real;
begin
      PointLen := sqrt( sqr(a.x - b.x) + sqr(a.y - b.y) );
end;

begin
    writeln('Input points count');
    readln(n);
    writeln('Input points');
    for i := 1 to n do
    begin
        writeln(i, ' point coordinates (x, y)');
        read( list[i].x );
        read( list[i].y );
    end;

    pos1 := 1;                       // начальная инициализация
    pos2 := 2;
    max_len := PointLen(list[1], list[2]);

    // основные циклы поиска
    for i := 1 to n - 1 do begin
        for k := i + 1 to n do  begin
            curr_len := PointLen( list[i], list[k] );
            if (curr_len > max_len) then begin
               max_len := curr_len;
               pos1 := i;
               pos2 := k;
            end;
        end;
    end;

    writeln('MaxLen = ', max_len : 0 : 2);
    writeln('Positions: ', pos1 : 4, pos2 : 4);
    readln;
    readln;
end.




--------------------
Помни - когда ты спишь, враг не дремлет
Спи чаще и дольше, изматывай врага бессоницей
PM MAIL ICQ   Вверх
FireSnake
Дата 9.3.2007, 22:43 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Бывалый
*


Профиль
Группа: Участник
Сообщений: 201
Регистрация: 15.9.2006
Где: Украина, Донецк

Репутация: нет
Всего: 1
Эт ж что за умный сложностью NlogN? Поделиси соображениями.

Это сообщение отредактировал(а) FireSnake - 9.3.2007, 22:45
PM MAIL ICQ   Вверх
Strannik
Дата 10.3.2007, 12:09 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Бывалый
*


Профиль
Группа: Участник
Сообщений: 154
Регистрация: 25.1.2007

Репутация: 1
Всего: 2
RTFM(кормен).
А если честно - я его сам не знаю... Но в кормене в разделе "Вычислительная геометрия" он точно есть.
PM MAIL   Вверх
MBo
Дата 10.3.2007, 12:39 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Бывалый
*


Профиль
Группа: Участник
Сообщений: 234
Регистрация: 10.6.2002

Репутация: 7
Всего: 18
Для нахождения пары с максимальным расстоянием за NLogN можно построить выпуклую оболочку (Convex Hull, есть метод с асимптотикой O(Nh), где h - число точек в оболочке, на практике методы обычно близки по скорости, если распределение точек не специально хитрое), наиболее удаленные точки будут ей принадлежать

Кроме того, есть методы с делением облака точек на клетки. Если клеток достаточно много, то достаточно проверять расстояния до небольшого количества дальних клеток
PM MAIL   Вверх
Strannik
Дата 10.3.2007, 13:42 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Бывалый
*


Профиль
Группа: Участник
Сообщений: 154
Регистрация: 25.1.2007

Репутация: 1
Всего: 2
Цитата
 
наиболее удаленные точки будут ей принадлежать

А если все точки входят в выпуклую оболочку? Если я правильно понял - тогда всё равно квадрат выйдет...
В кормене алгоритм типа "разделяй и властвуй"... надо будет разобратся...
PM MAIL   Вверх
FireSnake
Дата 10.3.2007, 21:40 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Бывалый
*


Профиль
Группа: Участник
Сообщений: 201
Регистрация: 15.9.2006
Где: Украина, Донецк

Репутация: нет
Всего: 1
Странник прав, оболочка строится за квадрат.

Цитата

RTFM(кормен)


Кормен это точно FM:)

Это сообщение отредактировал(а) FireSnake - 10.3.2007, 21:42
PM MAIL ICQ   Вверх
MBo
Дата 10.3.2007, 23:09 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Бывалый
*


Профиль
Группа: Участник
Сообщений: 234
Регистрация: 10.6.2002

Репутация: 7
Всего: 18
Strannik, 
>А если все точки входят в выпуклую оболочку? Если я правильно понял - тогда всё равно квадрат выйдет...

Выпуклая оболочка строится за O(NLogN), например, по Грэхему. Асимптотика в его методе не зависит от количества точек в оболочке, а обусловлена сортировкой 
Расстояние между наиболее удаленными точками на ней находится за линейное время (Rotating Calipers)




FireSnake, 
>оболочка строится за квадрат.
Можно и за экспоненциальное время, но незачем, если есть методы с гарантированным NLogN
PM MAIL   Вверх
Strannik
Дата 12.3.2007, 14:44 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Бывалый
*


Профиль
Группа: Участник
Сообщений: 154
Регистрация: 25.1.2007

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

Выпуклая оболочка строится за O(NLogN)

Это так, я не то имел ввиду...
Цитата

Расстояние между наиболее удаленными точками на ней находится за линейное время (Rotating Calipers)

Об этом по подробнее можно?

Добавлено @ 14:48 
Цитата

тогда всё равно квадрат выйдет

Я имел ввиду поиск двух наиболее удалённых...
PM MAIL   Вверх
MBo
Дата 12.3.2007, 15:31 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Бывалый
*


Профиль
Группа: Участник
Сообщений: 234
Регистрация: 10.6.2002

Репутация: 7
Всего: 18
>Об этом по подробнее можно?
гуглом много находится. Вот одна из первых ссылок
http://cgm.cs.mcgill.ca/~orm/rotcal.frame.html
PM MAIL   Вверх
Mitya
Дата 14.3.2007, 15:23 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 7
Регистрация: 5.3.2007

Репутация: нет
Всего: нет
Огромное спасибо всем, кто помог и помогает людям!!! Низкий всем Вам поклон!
PM MAIL   Вверх
  
 Ответ в темуСоздание новой темы Создание опроса
Правила форума "Центр помощи"

ВНИМАНИЕ! Прежде чем создавать темы, или писать сообщения в данный раздел, ознакомьтесь, пожалуйста, с Правилами форума и конкретно этого раздела.
Несоблюдение правил может повлечь за собой самые строгие меры от закрытия/удаления темы до бана пользователя!


  • Название темы должно отражать её суть! (Не следует добавлять туда слова "помогите", "срочно" и т.п.)
  • При создании темы, первым делом в квадратных скобках укажите область, из которой исходит вопрос (язык, дисциплина, диплом). Пример: [C++].
  • В названии темы не нужно указывать происхождение задачи (например "школьная задача", "задача из учебника" и т.п.), не нужно указывать ее сложность ("простая задача", "легкий вопрос" и т.п.). Все это можно писать в тексте самой задачи.
  • Если Вы ошиблись при вводе названия темы, отправьте письмо любому из модераторов раздела (через личные сообщения или report).
  • Для подсветки кода пользуйтесь тегами [code][/code] (выделяйте код и нажимаете на кнопку "Код"). Не забывайте выбирать при этом соответствующий язык.
  • Помните: один топик - один вопрос!
  • В данном разделе запрещено поднимать темы, т.е. при отсутствии ответов на Ваш вопрос добавлять новые ответы к теме, тем самым поднимая тему на верх списка.
  • Если вы хотите, чтобы вашу проблему решили при помощи определенного алгоритма, то не забудьте описать его!
  • Если вопрос решён, то воспользуйтесь ссылкой "Пометить как решённый", которая находится под кнопками создания темы или специальным флажком при ответе.

Более подробно с правилами данного раздела Вы можете ознакомится в этой теме.

Если Вам помогли и атмосфера форума Вам понравилась, то заходите к нам чаще! С уважением, Poseidon, Rodman
 
0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | Центр помощи | Следующая тема »

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


 




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


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

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