Ogoun 22 янв 2011 в 23:54

Рисуем многочлен Бернштейна для произвольного числа опорных точек

1 мин

+19

Комментарии 36

Petrify 23 янв 2011 в 01:00

Начинать с двух точек много, чтобы разобраться в кривых разного порядка лучше начинать с 1 точки. Так нагляднее. Верхнее ограничение тоже забавно — неужели есть необходимость разбираться с такими сложными кривыми? Если по фану, то сделали бы 100 — красивые штуки хоть получались бы — например развязку в Москве нарисовать можно было бы.

Ogoun 23 янв 2011 в 02:07

Я бином делал по простому, через факториал, чтобы переполнение не вызывать ограничил тринадцатью опорными точками. Можно сменить типы в расчетах в исходниках и увеличить количество.

Ofigenen 23 янв 2011 в 03:52


private int Factorial(int i)
{
    int ret = 1;
    while (i > 1) ret *= i--;
    return ret;
}

Красивее так:


private int Factorial(int i)
{
    if (i == 0) return 1;
    return i * Factorial(i--);
}

Извините за занудство.

-3

Xab 23 янв 2011 в 05:16

спорный вопрос. бытует мнение, что несколько выходов (aka return) из функции не есть комильфо, посему через переменную как-то правильнее. тем более ваш вариант с рекурсией, совсем уж извращенство. хочется «красоты», в этом смысле, используйте лямбда выражения :)

TheShock 23 янв 2011 в 05:39

Ну с несколькими ретурнами — это тема для холиваров. Я чаще встречаю людей, кто так не считает, чем кто так считает. Вроде, это устаревшее мнение, берущее корни из Паскаля в силу определённых нюансов.

HomoLuden 23 янв 2011 в 20:16

Как мне кажется, функциональное программирование действительно красиво. А лямбда — это еще не ФП. Зато представленный пример с рекурсией как раз «в духе» ФП. И уж никак не извращенство.

Xab 23 янв 2011 в 21:01

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

TheShock 23 янв 2011 в 05:37

тогда уж:

private int Factorial(int i)
{
    return i == 0 ? 1 : i * Factorial(i-1);
}

+11

moadib 23 янв 2011 в 09:53

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

Зачем усложнять тривиальные вещи? Пожалейте stack :)

liq 23 янв 2011 в 10:43

В данном случае вообще нет необходимости считать факториал, можно забить табличку от 0 до 20, 21! уже не влезет в int64.

Ogoun 23 янв 2011 в 11:12

Так и сделано, при выборе количества точек биномиальный коэффициент для них вычисляется один раз и заносится в табличку. Откуда при расчетах и берется. Конечно можно совсем статически табличку забить, но это немного усложнит расчет и сделает его менее читабельным, а на производительность не повлияет.

AlexTikhonov 23 янв 2011 в 16:00

Если среда выполнения поддерживает «хвостовую рекурсию», то stack чувствует себя очень хорошо при подобных вариантах. Да и скорость не хуже.

А запись через рекурсию более точно подходит под математическое определение факториала.

Так почему бы не записать так, чтоб понятно было даже «доменному специалисту» (в данном случае — математику)? :)

TheShock 23 янв 2011 в 20:55

Зачем усложнять тривиальные вещи?

Зачем усложнять тривиальные вещи, если можно использовать рекурсию вместо цикла? ;)
Имхо, всему своё место.

Ogoun 23 янв 2011 в 11:10

Написал специально без рекурсии, на случай расширения, чтобы в будущем стек не забивать)

mace 23 янв 2011 в 14:17

Вот только ваш код не работает.

Ogoun 23 янв 2011 в 14:48

А подробнее? У меня почему то все работает. Какая ошибка? Алгоритмическая, программная, и где?

mace 23 янв 2011 в 14:52

Постфиксный декремент.
Нужен префиксный:

private int Factorial(int i)
{
    if (i == 0) return 1;
    return i * Factorial(--i);
}

а еще лучше:

private int Factorial(int i)
{
    if (i == 0) return 1;
    return i * Factorial(i-1);
}

Ogoun 23 янв 2011 в 14:54

Не посмотрел к какому комменту ваш ответ, подумал про свой код.)

Ofigenen 23 янв 2011 в 17:12

В 4 часа ночи писал. Спасибо Вам за поправку, а остальным — за ценные комментарии. Мне есть еще чему учиться.

hellman 23 янв 2011 в 19:12

Действительно? :)

TheShock 23 янв 2011 в 20:03

Не нашёл своего варианта с тернарным оператором. Видимо «Lazy Python Programmer».

EvilBlueBeaver 24 янв 2011 в 00:14

Ваш вариант не содержит хвостового вызова и потому в языках с его оптимизацией оптимизирован не будет
А в .Net (точнее в C#) лучше рекурсию не использовать вовсе, поскольку там нет оптимизации хвостовых вызовов на уровне компилятора. Хотя в CLR инструкция все же присутсвует. Хотя может со времен .NET 3.5 что-то изменилось, честно не в курсе.

Хотя применительно в данному примеру это неважно, поскольку здесь не такая большая глубина, чтобы заметить разницу или получить StackOwerflow

Ofigenen 24 янв 2011 в 00:41

Понял я уже, что в 4 утра спать надо, а не умничать. :) С университета просто отложилось в памяти, что факториал считается рекурсивной функцией.

EvilBlueBeaver 24 янв 2011 в 01:07

Рекурсией тоже надо уметь правильно пользоваться ;)

VenomBlood 24 янв 2011 в 01:34

private static Int64 Factorial(int n)
{
    // Due to Int64 limits
    if (n > 20)
    {
        throw new ArgumentException("Factorial parameter can not be greater than 20.", "n");
    }

    if (n == 0)
    {
    	return 1;
    }
	
    Int64 result = 1;
    for (int i = 1; i <= n; i++)
    {
        result *= i;
    }
	
    return result;
}

VenomBlood 24 янв 2011 в 01:55

Забыл проверку на отрицательные числа.
Вообще, если уж считать бином — то лучше бы сделать оптимизации, позволяющие не ограничиваться влезанием полного факториала в разрядную сетку.

hardex 23 янв 2011 в 13:27

ifolder? Неужели не существует нормальных файл-хостингов?

Ogoun 23 янв 2011 в 13:32

Если знаете лучше, дайте линк. ifolder пока не подводил.

-2

hardex 23 янв 2011 в 13:33

Смотреть рекламу и ждать чтобы скачать файл — это нормально? Используйте zalil.ru или rghost.

Ogoun 23 янв 2011 в 13:39

Довыложил:
zalil.ru/30386914

grcool 23 янв 2011 в 16:34

По этой причине я передумал качать файл))

AlexTikhonov 23 янв 2011 в 18:07

Честно говоря не вижу причины не создать проект на том же code.google.com — сорсы залить в Mercurial, а откомпилинную версию в Downloads

Имхо не намного сложнее чем на всякие файло-помойки, зато возможностей намного больше.