Этот ... Лисп , Задачки на суд

[Platonis]

Народ!!! На ваше жестокое и беспощадное обозрение выставляю следующую задачку...

(Открытый кубок МГУ-COSS 1-й этап "Гран-при Беларуси" (1 октября 2005 г.))

Перегрин слишком пристально интересовался палантиром, который выбросил ГРима. Гэндольф решил отвлечь любопытного хоббита и стал измерять палантир хитрой линейкой. "А что у тебя за странная линейка?" - спросил Перегрин. "А это магическая линейка. На ней между любыми двумя делениями нет одинакового расстояния" - пояснил маг <...>
"А таких линеек много?" - спросил Перегрин. "То есть много?" - попросил уточнить маг. "Ну..." - тут хоббиту ударило в голову выпитое пиво, и он заговорил непонятными словами: "Линейка - это целых неотрицательных чисел A1<=A2<=...<=An такой, что все разности Aj - Ai, 1<= i < j <= N, попарно различны. Так вот если я напишу ограничение сверху и снизу для каждого деления, сколько существует различных линеек?"
Довольный Перегрин подумал, что поставил мага в тупик, но тот нашел ответ: "А посчитай-ка ты сам".

Помогите хоббиту найти ответ на собственный вопрос, то есть посчитать по заданным наборам Li и Ri количество подобных линеек, таких, что A1 = 0 и для любого i, 2<= i <=N выполнено Li<=Ai<=Ri. Ведь ему так интересно посмотреть, что за шарик выкинули из Ортханка...

Контрольный пример:
L = {0 4 8 12}
R = {4 8 12 16}

Ответ: 61

Для справки: в математике такой набор чисел называется линейкой Голомба.

Свою программу не смог проверить (вылетает)
А также принимаю все улучшения или более эффективные алгоритмы.
Прокоментирую свое решение...
Решал в лоб (очень тупой метод Сложность проги при наихудших обстоятельствах 50!*10! или 50!), т. е. Проходил все комбинации линейки... при каждой новой итерации увеличиваю значение последнего деления линейки, если он выходит за рамки соответствующего ограничителя, переписываю его на наименьший из заданного интервала и увеличиваю предыдущее деление на единицу, если же и оно превысило предел своего интервала, повторю эту же операцию но с предпоследним значением.


Самое громоздкое решние заключается в поиске всех разностей, хотелось бы его улучшить. Ну, и подозреваю, что существует линейное решение данной задачи или в крайнем случае степенной, но никак не факториальный.

(defun main (L R)
    (cond ((or (null L) (null R)) nil)
          (t (solve (reverse (cons 0 L)) (reverse (cons 1 R)) (reverse (cons 0 L)) 0))
    )
)
 
(defun solve (L R curRuler res)
    (cond ((= (car (reverse curRuler)) 1) res)
          ((checkRuler curRuler '(0)) (solve L R (inc curRuler L R 1) (1+ res)))
          (t (solve L R (inc curRuler L R 1) res))
    )
)
 
(defun inc (curRuler L R cf)
    (cond ((null curRuler) nil)
          ((= (car curRuler) (car R)) (cons (car L) (inc (cdr curRuler) (cdr L) (cdr R) 1)))
          (t (cons (+ cf (car curRuler)) (cdr curRuler)))
    )
)
 
(defun checkRuler (ruler passedDifs)
    (cond ((null (cdr ruler)) T)
          (t ((lambda (x)
                  (cond ((null x) nil)
                        (t (checkRuler (cdr ruler) (append x passedDifs)))
                  )
              ) (checkCur (car ruler) (cdr ruler) passedDifs nil)
             )
          )
    )
    
)
 
(defun checkCur (cur rest passedDifs newDifs)
    (cond ((null rest) newDifs)
          ((or (member (- cur (car rest)) passedDifs) (member (- cur (car rest)) newDifs)) nil)
          (t (checkCur cur (cdr rest) passedDifs (cons (- cur (car rest)) newDifs)))
    )
)
(print (main '(0 4) '(4 8)))

P. S. Если найдете баг, просьба предложить исправленный вариант, или указать место. Скорее всего, ошибка (если она будет) заключается в пограничных интервалах, возможно я их просто не учту или наоборот дважды увеличу результат.

А также есть тривиальная задчка. Проверить многоугольник на выпуклость.

Идея решения лежит в документе, документ в папке, папка в корне, корень тама, где не знамо.

Текст программы:

(defun main (p)
    (cond ((> (length p) 2) (checkAllPoints (length p) p))
          (t '(Not enougth parameters))
    )
    
)
 
;Checks all points for crossProduts
(defun checkAllPoints (iters p)
    (cond ((null (solve (car p) (cdr p) (checkForPositive (car p) (cdr p)))) nil)
          ((zerop iters) T)
          (t (checkAllPoints (1- iters) (append (cdr p) (list (car p))))
          )
    
    )
)
 
; we need to check it because for convex polygones crossProducts of all triangles are eigther all negative or positive
(defun checkForPositive (p0 p)
    (cond ((> (crossProduct p0 (car p) (cadr p)) 0) T)
          (t nil)
    )
)
 
; CrossProdut is calculated as (x1*y2 - x2*y1), where x1 is (p1.x - p0.x), x2 is (p2.x - p0.x), the same with y-coords
(defun crossProduct (p0 p1 p2)
    (- (* (- (car p1)
             (car p0)
          )
          (- (cdr p2)
             (cdr p0)
          )
       )
       (* (- (car p2)
             (car p0)
          )
          (- (cdr p1)
             (cdr p0)
          )
       )
    )
    
)
 
(defun solve (p0 p isPositive)
    (cond ((null (cadr p)) T)
          ((equal (checkForPositive p0 p) isPositive) (solve p0 (cdr p) isPositive))
          (t nil)
    )
)
 
(print (main '((1 . 1) (5 . 1) (4 . 2) (5 . 4))))
;Bingo!!! It works

Прикреплённый файлИдея_решения.doc (31 Кбайт, скачиваний: 190)

[Platonis]

Так, я немного не понял??? Почему никто не отзывается, я вроде русским языком писал и решение уже сделано остается только оценить. Что пугает людей оставить парочку строк по этой теме?

[Ho Im]

Неинтересность темы в отдельно взятый промежуток времени совокупности всех смотревших. О.

[Platonis]

Значит никто не может лучше предложить.. Очень жаль...
Ho Im, а какая тема тогда на твой взгляд интересней? Может быть:
"Эй ребята решите-ка мне задачки такие-то и такие-то".

А я же по обмену опытом. Моет кто и усовершенствует решение.

[Ho Im]

Цитата

Ho Im, а какая тема тогда на твой взгляд интересней? Может быть:
"Эй ребята решите-ка мне задачки такие-то и такие-то".

Такие темы мне стоят в горле.

Преподаватели должны находить таких сачкующих студентов, после чего засовывать им
указку в одно место, медленно, со вкусом, без вазелину. Это вызовет отток мозга
обратно в голову.

А еще меня задолбал тот факт, что лисп считают только достойным преподавания, но не
практического применения.

[Platonis]

Цитата Ho Im @ 02.02.06, 16:50

Преподаватели должны находить таких сачкующих студентов, после чего засовывать им
указку в одно место, медленно, со вкусом, без вазелину. Это вызовет отток мозга
обратно в голову.

Надеюсь ты меня не причисляешь к их числу, я уже давно сессию закрыл, и чисто увлекаюсь Лиспом.

Насчет

Цитата Ho Im @ 02.02.06, 16:50

А еще меня задолбал тот факт, что лисп считают только достойным преподавания, но не практического применения.

Я допустим не считаю, что он не достоен практического применения. Просто его время еще не пришло, рекурсия в наше время дорого стоит, и вообще это опасная штука... А лисп - язык рекурсий, так что...

Ты бы лучше заценил задачки, чем обвинять в неинтересности.

[Ho Im]

Цитата

Я допустим не считаю, что он не достоен практического применения. Просто его время еще не пришло, рекурсия в наше время дорого стоит, и вообще это опасная штука... А лисп - язык рекурсий, так что...

С каких пор хвостовая рекурсия стала дорогостоящей? В 70-е -- 80-е годы была дешевой, когда воевали за каждый байтик, а сейчас, когда память куры не клюют, стала вдруг...?

Цитата

Ты бы лучше заценил задачки, чем обвинять в неинтересности.

Я сейчас несколько более другие задачки решаю, так что извини... Если бы я расставлял радары (или для чего еще линейки Голомба могут быть нужны?), оно бы представило для меня интерес. Подозреваю, что другие высказали в сердце своем то же мнение. То, что пока никто не заинтересовался, не значит, что так оно будет потом, и не повод вспыливать.

А почему оно так... А вот те в тему (интересные задачки != задачки, за которые можно покушать): http://c2.com/cgi/wiki?AreBusinessAppsBoring

А именно "boring" имеет спрос

[Alexey Dejneka]

Цитата

А лисп - язык рекурсий, так что...

(Глубокий вздох.) И зачем я вообще писал в этот форум?

[Ho Im]

Цитата

А лисп - язык рекурсий, так что...

Лисп -- это язык языков. Это даже не язык скобок (его можно превратить в инфиксный).

[Platonis]

Что ж, никому не интересно, всем до свидания.