опять только программистам будет интересно

[avva]

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

Вернусь теперь к программе, которую писал, и еще чего-нибудь наваяю...

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

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

Задачка такая. Вам дают возрастающую последовательность натуральных чисел x₀, x₁, .... x_N. x₀ равно 0, а самое большое - и последнее - из этих чисел, x_N, является длиной окружности, на которой расположены N точек x₀, ..., x_N-1 - они заданы в виде длин от начальной фиксированной точки. Предположим, например, что последовательность - 0, 3, 9, 11, 12, 25; это значит, что на окружности длиной 25 есть 5 точек; начиная от фиксированной точки O и идя по окружности расстояния от O до них равны 0, 3, 9, 11 и 12. Дано также число k. Спрашивается, можно ли из N точек x₀, ... x_N-1 отобрать k таких, которые образуют правильный k-угольник?

Т.к. расстояния между точками по окружности - натуральные числа, а у правильного k-угольника они все равны и их k, то ясно, что необходимым условием является, чтобы длина окружности x_N делилась на k, и тогда частное от их деления - расстояние по окружности между двумя последовательными вершинами искомого k-угольника. Если это необходимое условие выполняется, требуется ответить на вопрос за O(N) затрат времени и места. Решение с O(N*k) тривиально, да и с O(N) не ужасно сложно, но подумать надо. Возможно, хорошая задачка для интервью.

Comments

[benyx.livejournal.com]

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

[6pack.livejournal.com]

Хочу просто уточнить, 0 же вроде не натуральное число?

[avva.livejournal.com]

На это есть разные точки зрения :) но если вам мешает, подставьте "целое неотрицательное" везде вместо "натуральное".

[vadim-i-z.livejournal.com]

Мою починку бага в языке Перл приняли и вставили в исходники
Представил на секундочку такую же реплику, только о языке не Перл, а, скажем, русском, английском или ином человеческом.
Позавидовал.
И задумался: а у этих-то языков где исходники лежат? У кого?

путаете

[(Anonymous)]

вы путаете исходники языка и исходники реализации. исходники реализации человеческого языка - в словарях, и поправки и изменения в них - дело не столь уж непостижимое :)

Re: путаете

[vadim-i-z.livejournal.com]

Я не путаю, я ищу Демиурга! :-))
А в словарях, кстати, не исходники, словари язык не создают, а фиксируют.

[kot-ivanovich.livejournal.com]

if (x[N]%k) return false;
int count = 0, step = x[N]/k;
for (int i = 1; i < N; ++i)
  if (x[i]%step == 0) ++count;
return count == N-1;

[sh2.livejournal.com]

Не решение. Предположим x[N] = [0, 1, 3, 5, 6], k = 3.
Тогда step=2, а после цикла count = 0, что меньше k-1 = 4 (я полагаю, имелось в виду все-таки k, а не N).
А между тем, 1-3-5 - правильный треугольник.

Правильно похоже вот так:
if (x[N]%k) return false;
int step = x[N]/k, i;
int *count = new int[step];

for (i = 0; i < step; ++i)
count[i] = 0;

for (i = 0; i < N; ++i)
count[x[i]%step]++;

for (i = 0; i < step; ++i)
if (count[i] == k)
{
delete[] count;
return true;
}

delete[] count;
return false;

[kot-ivanovich.livejournal.com]

Mea culpa, mea maxima culpa... You are right (sorry, no Cyrillic keyboard here).

[avva.livejournal.com]

Да, все верно и эффективно.

Дейкстра предлагает несколько другое решение, но по сути то же. Будем хранить список точек со следующим свойством: если точка x находится в этом списка, то либо 0 <= x <= step (step=x[N]/k), либо все числа
x-k, x-2k, x-3k итд. до числа в промежутке [0...step) находились до того в списке. Начинаем с того, что помещаем в список все точки в промежутке от 0 до step. После этого делаем один проход по оставшимся точкам следующим образом: каждый раз смотрим на минимальную точку x в списке, и продвигаемся в общем наборе точек до первой точки >= x+k; если x+k точка, то выбрасываем x из начала списка и вставляем x+k в конец, если не точка, то просто выбрасываем x. Таким образом общее число точек в списке никогда не растет. Если мы дошли до последнего сегмента длиной k, и наш список все еще не пуст, отвечаем "да", иначе "нет".

[muchacho.livejournal.com]

Для последовательности {0, 1, 4, 7, 9} и k=3 ваш код вернет false, хотя 1, 4, 7 образуют равносторонний треугольник.

[avnik.livejournal.com]

Про лисп надо еще безусловнол читать OnLisp товарища Graham'а (http://www.paulgraham.com/books.html)

[avva.livejournal.com]

Да, доберемся.

а так

[(Anonymous)]

// input: int N, k, x[N-1]
if (N%k != 0) return false; // нельзя
int L = N/k; // длина сегмента
int i; // стартовая точка
int j; // проверяемая точка
int ln, l; // проверяемая длина сегмента
int n = k; // количество ненайденных вершин
for(i = 0; n > 0 && x[i] < L; ++i)
// в качестве стартовых точек используются точки в пределе [0, L)
{
n = k - 1;
j = i + 1;
ln = L;
for (; j <= N - n; ++j) {
// неимеет смысла проверять дальше N-n точек
l = x[j] - x[i];
if (l > ln) break; // неимеет смысла продолжать,
// меняем стартовую точку
if (l == ln) {
--n;
ln += L;
}
}
}
return n == 0;

Re: а так

[(Anonymous)]

bug:
int L = N/k; // длина сегмента
должно быть:
int L = x[N]/k; // длина сегмента

Re: а так

[(Anonymous)]

bug:
// input: int N, k, x[N-1]
должно быть:
// input: int N, k, x[N+1]

[smilga.livejournal.com]

Я как-то написал макрос, описывающий общий случай обхода лексикографического дерева (в ту или другую сторону). Фокус там был в том, что макросу передавался в качестве параметра символ identity или reverse, который во-первых вставлялся в качестве имени процедуры в код (где процедура должна была (не) преобразовывать последовательность дочерей данного узла), а во-вторых при самом вычислении макроса применялся (через apply) к списку случаев для cond. Один из очень немногих случаев, когда я встал из-за машины вполне довольный собой.

Это, кстати, очень коммонлисповское, в Схеме такие штучки не проходят (если, конечно, не пользоваться eval-ом, за использование которого всуе программисту полагается немедленное моральное уничтожение).

[ex-ex-annut.livejournal.com]

хм напомнило задачку о двух стаканах и высоте здания
где правильное (оптимальное) решение гораздо более очевидно, чем не оптимального (N*k даже бы в голову не пришло)

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

В линейную панель вставлено 10 лампочек. Лампочки горят. Вероятность того что лампочка сгорит в момент времени t равна t*exp(-t)
Пусть t_i
- момень сгорания лампочки с номером i
Какова вероятность того, что
t_1 < t_2 \cdots < \t_10


На абсолютно гладком столе лежит металическая цепочка массы m и длины l (масса цепочки равномерно распределена по длине)
Половина цепочи свисает со стола, половина лежит на столе, растянута и перпендикулярно краю стола
Какова скорость цепочки в момент отрыва от стола?

[avva.livejournal.com]

Кажется очевидным, что в первой задаче ответ 1/10!, во второй sqrt(l*g), масса не играет роли. Верно?

В линейную панель вставлено 10 лампочек. Лампочки горят. Вероятность того что лампочка сгорит в момент времени t равна t*exp(-t) Пусть t_i - момень сгорания лампочки с номером i Какова вероятность того, что t_1 < t_2 \cdots < \t_10 На абсолютно гладком столе лежит металическая цепочка массы m и длины l (масса цепочки равномерно распределена по длине) Половина цепочи свисает со стола, половина лежит на столе, растянута и перпендикулярно краю стола Какова скорость цепочки в момент отрыва от стола? Options: - View the discussion: http://avva.livejournal.com/1658846.html?thread=37567966 - View all comments on the entry: http://avva.livejournal.com/1658846.html - Reply to the comment: http://avva.livejournal.com/1658846.html?replyto=37567966 - Delete the comment: http://www.livejournal.com/delcomment.bml?journal=avva&id=37567966 -- LiveJournal.com (If you'd prefer to not get these updates, go to http://www.livejournal.com/manage/comments/ and turn off the relevant options.)

[ex-ex-annut.livejournal.com]

Da

Pochemuto nekotorie ludi nachinaut schitat' integrali :)

offtop -but perl-related

[rdanozhki.livejournal.com]

Esli vy esche ne, to - :)
Jerusalem Perl Mongers - hope to see everyone at the coming meeting. It should be very interesting. This invitation is for everyone, not just ex librians, so feel free to invite all of your friends and relatives who know Perl.

Jerusalem Perl Mongers
Meeting October 24, 2006

כל ההרצאות בעברית

* 18:00 – Meeting
* 18:10 – Guy Naamati
Humor in Perl
* 18:50 – Break
* 19:00 – Shaul Zevin
Introduction to Bioperl

== Location ==
Large meeting room
== Food ==
כיבוד קל
burekas, cake, fruit, soft drinks

== Price ==
Free of charge

== Contact ==
Jerusalem.Perl.Monger@gmail.com

Don’t forget to check out http://jerusalem.perl.org.il

[avva.livejournal.com]

mmmm :) I went once about a year ago, have to admit it wasn't too thrilling. How many people are there at the meetings nowadays? Is it still in that place at Malha?