Кресты / Говнокод #19534 Ссылка на оригинал

0

  1. 1
  2. 2
  3. 3
int main() { 
for (float n = 0, l = 0, q = scanf("%f", &n), r = n, m = (l + r) / 2; r - l > 0.00001 || 0 * printf("%f", l); m*m <= n ? l = m : r = m, m = (l + r) / 2); 
}

Просто бинпоиск в одну строчку)

Запостил: AndreyZ AndreyZ, (Updated )

Комментарии (21) RSS

  • ava AndreyZ # Ссылка на оригинал 0

    Этот код двоичным поиском ищет квадратный корень из числа с плавающей точкой.
    Ответить

    • ava bormand # Ссылка на оригинал 0 ⇈ 

      for(float a=0,_=scanf("%f",&a),x=a,y=x+1;fabs(y-x)>0.00001||!printf("%f",x);y=x,x=(x+a/x)/2);
      А чё не ньютоном?
      Ответить

      • ava bot # Ссылка на оригинал 0 ⇈

        Потому что Ньютон на #CF байт старее Ломоносова.
        Ответить

        • ava bot # Ссылка на оригинал 0 ⇈

          Бля. На #44 же. Вот ведь блять перепил... Нахуй так жить?..
          Ответить

      • ava kegdan # Ссылка на оригинал 0 ⇈

        а у меня длиннее
        for (double a = Double.Parse(Console.ReadLine()), xp = a+1, x = a; Math.Abs(x - xp) > 0.000001 || new Func<bool>(() =>{Console.WriteLine(x);return false; }).Invoke(); xp = x, x = (x + a / x) / 2) ;
        Ответить

      • ava AndreyZ # Ссылка на оригинал 0 ⇈

        Цель была написать бинпоиск, а поиск корня был примером(вместо него может быть любая монотонная функция). А про метод ньютона не знал, спасибо.)
        Ответить

        • ava kegdan # Ссылка на оригинал 0 ⇈

          >> А про метод ньютона не знал, спасибо.)

          x = sqrt(a) -> x*x = a -> x = a/x -> x+x = x+ a/x -> x = (x+a/x)/2

          А хрень с сложением от того, что x = a/x очень фигово вычисляется итеративно
          Ответить

          • ava bormand # Ссылка на оригинал 0 ⇈

            Где-то статья попадалась, где метод ньютона вывели из бинарного поиска...
            Ответить

            • ava kegdan # Ссылка на оригинал 0 ⇈

              Ну общая формула типа x = x - f(x)/f'(x), для х таких, что f(x) = 0

              у нас f(x) = x*x-a
              f'(x) = 2x

              откуда
              x = x - (x*x-a)/ 2x
              x = x-x/2 - a/2x
              x = (x - a/x)/2

              это все, что я знаю
              Ответить

  • ava 3_dar # Ссылка на оригинал 0

    r - l > что-то

    Вот так опасно проверять же. А вдруг там очень близкие большие числа (порядка FLOAT_MAX)
    Ответить

    • ava bormand # Ссылка на оригинал 0 ⇈

      Да не надо там флоат макс... Это сравнение на числах порядка 1000 уже загнётся. У флоата же мантисса в районе 7 десятичных цифр.
      Ответить

        • ava bormand # Ссылка на оригинал 0 ⇈

          Ну для простоты покажу на десятичных числах. Ты считаешь корень от 1000003. Пусть у тебя флоат хранит ровно 7 значащих цифр и расчёт добрался до L = 1000.001, а R = 1000.002 (реальный ответ ~1000.0014999). Ты считаешь M = 1000.0015, но т.к. точность ограничена, оно округляется до 1000.002. Его квадрат 1000004 больше искомого, т.е. делаем R = M... Дальше понятно? 🙂
          Ответить

          • ava roman-kashitsyn # Ссылка на оригинал 0 ⇈

            В бинпоиске похожая проблема возникает, когда диапазон сужается. Чтобы поиск завершался, пишут l = m + 1 и r = m - 1 (если r включается). И тут, видимо, надо эпсилон добавлять/вычитать.
            Ответить

            • ava 3_dar # Ссылка на оригинал 0 ⇈

              Можно ограничить число итераций, но это костыль. И еще вроде можно смотреть изменилось-ли r-l.
              Ответить

              • ava bormand # Ссылка на оригинал 0 ⇈

                > изменилось-ли r-l
                Тогда уж просто перед присваиванием сравнить m и заменяемое им число. Если одинаковые - дальше крутить цикл смысла нету.
                Ответить

                • ava 3.14159265 # Ссылка на оригинал 0 ⇈

                  Простите, а не проще ли сконвертить float через union к инту и проверить равенство после & битовой маски (исключив младшие N бит. N выбрать по вкусу). Я даже в сраных жавах так делал. Брат жив.
                  Ответить

Добавить комментарий

Помни, guest, за тобой могут следить!

    А не использовать ли нам bbcode?

    ↑
    8
    ↓