1. C++ / Говнокод #19534

    +3

    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, 25 Февраля 2016

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

    • ava AndreyZ 25.02.2016 21:41 # 0

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

      • ava bormand 25.02.2016 21:55 # +5 

        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 26.02.2016 00:44 # 0

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

          • ava bot 26.02.2016 00:54 # 0

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

        • ava kegdan 26.02.2016 11:36 # +3

          а у меня длиннее
          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 26.02.2016 15:21 # 0

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

          • ava kegdan 01.03.2016 03:25 # +1

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

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

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

            • ava bormand 01.03.2016 06:51 # 0

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

              • ava kegdan 01.03.2016 07:17 # 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 XYEHOC 01.03.2016 11:47 # 0

                  Ты знак проебал:
                  x = x - (x*x-a)/ 2x
                  x = x-x/2 + a/2x
                  x = (x + a/x)/2
                  Ответить

                  • ava kegdan 01.03.2016 14:31 # 0

                    ну да, ночь была, спать хотел, все такое
                    Ответить

          • ava 3.14159265 21.03.2016 22:14 # 0

            >А про метод ньютона не знал, спасибо.)
            Householder 1st order
            Ответить

    • ava 3_dar 26.02.2016 18:00 # 0

      r - l > что-то

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

      • ava bormand 26.02.2016 21:10 # +1

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

        • ava AndreyZ 01.03.2016 16:01 # 0

          А что не так с этим сравнением? Я не очень понял.
          Ответить

          • ava bormand 01.03.2016 18:56 # 0

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

            • ava roman-kashitsyn 03.03.2016 17:42 # 0

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

              • ava 3_dar 05.03.2016 20:13 # 0

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

                • ava bormand 05.03.2016 23:31 # 0

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

                  • ava 3.14159265 21.03.2016 22:16 # 0

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

    • ava Steve_Brown 29.02.2016 12:01 # 0

      for (...; abs(a - sqrt(2)) < 0.00001 ;...);
      Ответить

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