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

Поиск:

Ответ в темуСоздание новой темы Создание опроса
> [LISP] Задачка на принадлежность точек прямой 
V
    Опции темы
oekamon
Дата 24.11.2005, 22:30 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



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

Репутация: нет
Всего: нет
Задачка такая:
Дано множество координат точек в виде списка второго уровня вложенности (например, ((1 0) (0 1) (1 2) ...)). Необходимо из всего множества точек найти такую пару, чтобы через эту пару точек можно было бы провести прямую, и эта прямая не содержала бы только эти две точки и никакую третью из данного множества. Точнее, нужно просто указать, есть такая пара, или нет.
Алгоритм примерно такой: создать дополнительный список, содержащий все сочетания точек по три (C(n,k)=n!/(n-k)!k!), а затем для каждой тройки посчитать определитель ((x2 - x1)(y3 - y1) - (x3 - x1)(y2 - y1)). Если определитель не равен 0, то три точки не лежат на одной прямой (по идее, "площадь треугольника, вершины которого - вот эти точки, не равна 0"), и этот случай нам подходит. Возвращаем T, иначе строим прямую для следующей тройки.
Все бы было замечательно, но я не могу придумать, как можно сделать список сочетаний (кто не понял, что такое сочетания - это биномиальные коэффициенты Ньютона, или "цэ из эн по ка").
Заранее благодарю за помощь.
PM MAIL WWW ICQ   Вверх
adejneka
Дата 25.11.2005, 08:40 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


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

Репутация: 2
Всего: 11
Список сочетаний:
Код

(defun combinations (set length)
  (cond ((zerop length) (list '()))
        ((null set) '())
        (t (append (mapcar (lambda (combination) (cons (first set) combination))
                           (combinations (rest set) (1- length)))
                   (combinations (rest set) length)))))

или так:
Код

(defun combinations (set length &optional postfix rest)
  "Все сочетания элементов множества SET длины LENGTH.

Если заданы POSTFIX и REST, к каждому сочетанию добавляются элементы POSTFIX, после чего
весь список сливается с REST:
(append (mapcar (lambda (combination) (append combination postfix))
                (combinations set length))
        rest))"
  (cond ((zerop length) (cons postfix rest))
        ((null set) rest)
        (t (combinations (rest set) length
                         postfix
                         (combinations (rest set) (1- length) (cons (car set) postfix) rest)))))

Цитата

кто не понял, что такое сочетания - это биномиальные коэффициенты Ньютона, или "цэ из эн по ка"


Надо же, а я-то всегда считал, что "цэ" - это количество сочетаний...
PM MAIL   Вверх
oekamon
Дата 26.11.2005, 07:50 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



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

Репутация: нет
Всего: нет
Спасибо огромное, как раз до этого я не мог дойти. Строить прямые - уже намного проще...
Цитата
Надо же, а я-то всегда считал, что "цэ" - это количество сочетаний...

Я, в общем, это и имел в виду, простите, если перепутал...
PM MAIL WWW ICQ   Вверх
Cr@$h
Дата 24.8.2006, 21:50 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Исследователь
***


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

Репутация: 3
Всего: 41

M
Cr@$h		adejneka ++, помог.
PM MAIL ICQ   Вверх
  
 Ответ в темуСоздание новой темы Создание опроса
Правила форума "Центр помощи"

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


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

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

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

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


 




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


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

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