[C#, Этюд] Математика поломалась?
От: nikov США http://www.linkedin.com/in/nikov
Дата: 30.06.10 14:13
Оценка:
Что надо передать в метод Foo, чтобы он вернул true?

using System.Linq;

public class C
{
    public static bool Foo(params int[] arr)
    {
        return 
            arr != null && 
            arr.Distinct().Count() == 3 &&
            arr.All(x => x * x - 12 * x + 35 == 0);
    }
}


(с методами из System.Linq.Enumerable подвоха нет, используется стандартная реализация)
Re: [C#, Этюд] Математика поломалась?
От: samius Япония http://sams-tricks.blogspot.com
Дата: 30.06.10 14:25
Оценка: 2 (1)
Здравствуйте, nikov, Вы писали:

N>Что надо передать в метод Foo, чтобы он вернул true?


Полагаю что любые 3 уникальных из следующих чисел
-2147483643
-2147483641
5
7
Re: [C#, Этюд] Математика поломалась?
От: Aen Sidhe Россия Просто блог
Дата: 30.06.10 14:26
Оценка: 2 (1)
Здравствуйте, nikov, Вы писали:

N>Что надо передать в метод Foo, чтобы он вернул true?


Ну, любой набор по 3 числа из: 5, 7, -2147483643, -2147483641. Возможно ещё какие-нибудь, лень пока проверять.

Вопрос — почему так (естественно, не про 5 и 7)?
С уважением, Анатолий Попов.
ICQ: 995-908
Re[2]: [C#, Этюд] Математика поломалась?
От: samius Япония http://sams-tricks.blogspot.com
Дата: 30.06.10 14:28
Оценка:
Здравствуйте, Aen Sidhe, Вы писали:

AS>Вопрос — почему так (естественно, не про 5 и 7)?


А почему должно быть не так? В чем подвох-то?
Re[3]: [C#, Этюд] Математика поломалась?
От: Aen Sidhe Россия Просто блог
Дата: 30.06.10 14:29
Оценка:
Здравствуйте, samius, Вы писали:

S>Здравствуйте, Aen Sidhe, Вы писали:


AS>>Вопрос — почему так (естественно, не про 5 и 7)?


S>А почему должно быть не так? В чем подвох-то?


Там квадратное уравнение с корнями 5 и 7.
С уважением, Анатолий Попов.
ICQ: 995-908
Re[4]: [C#, Этюд] Математика поломалась?
От: nikov США http://www.linkedin.com/in/nikov
Дата: 30.06.10 14:32
Оценка: :)
Здравствуйте, Aen Sidhe, Вы писали:

S>>А почему должно быть не так? В чем подвох-то?


AS>Там квадратное уравнение с корнями 5 и 7.


В C# у квадратного уравния бывает 4 корня.
Re[2]: [C#, Этюд] Математика поломалась?
От: Aen Sidhe Россия Просто блог
Дата: 30.06.10 14:46
Оценка: +1
Здравствуйте, Aen Sidhe, Вы писали:

AS>Здравствуйте, nikov, Вы писали:


N>>Что надо передать в метод Foo, чтобы он вернул true?


AS>Ну, любой набор по 3 числа из: 5, 7, -2147483643, -2147483641. Возможно ещё какие-нибудь, лень пока проверять.


AS>Вопрос — почему так (естественно, не про 5 и 7)?


Разобрался. Порядок вычислений будет примерно такой:

int x = -2147483643;
int x2 = (x * x) % (2 ^ 31); // 25
int x3 = (-12 * x)  % (2 ^ 31); // int.MaxValue + 1 - 25 - 35;
int x4 = (x2 + x3) % (2 ^ 31); // int.MaxValue + 1 - 35;
int x5 = (x4 + 35) % (2 ^ 31); // 0


Верно?
С уважением, Анатолий Попов.
ICQ: 995-908
Re: [C#, Этюд] Математика поломалась?
От: SE Украина  
Дата: 30.06.10 15:00
Оценка:
Здравствуйте, nikov, Вы писали:

N>Что надо передать в метод Foo, чтобы он вернул true?


-2147483643
-2147483641

брутфорс
Re[2]: [C#, Этюд] Математика поломалась?
От: SE Украина  
Дата: 30.06.10 15:01
Оценка:
Здравствуйте, SE, Вы писали:

SE>Здравствуйте, nikov, Вы писали:


N>>Что надо передать в метод Foo, чтобы он вернул true?


SE>-2147483643

SE>-2147483641

SE>брутфорс


Не успел
Re[2]: [C#, Этюд] Математика поломалась?
От: nikov США http://www.linkedin.com/in/nikov
Дата: 30.06.10 15:02
Оценка: 9 (2)
Здравствуйте, SE, Вы писали:

SE>брутфорс


Гораздо быстрее их можно найти с помощью Pex, в т.ч. для типа long, для которого брутфорс помогает плохо.
Re[3]: [C#, Этюд] Математика поломалась?
От: Aen Sidhe Россия Просто блог
Дата: 30.06.10 15:04
Оценка:
Здравствуйте, nikov, Вы писали:

N>Здравствуйте, SE, Вы писали:


SE>>брутфорс


N>Гораздо быстрее их можно найти с помощью Pex, в т.ч. для типа long, для которого брутфорс помогает плохо.


А он для любых выражений находит или только для простых? Т.е. если там будет что-нибудь послежнее многочлена второй степени — найдёт?
С уважением, Анатолий Попов.
ICQ: 995-908
Re[3]: [C#, Этюд] Математика поломалась?
От: SE Украина  
Дата: 30.06.10 15:22
Оценка:
Здравствуйте, nikov, Вы писали:

SE>>брутфорс


N>Гораздо быстрее их можно найти с помощью Pex, в т.ч. для типа long, для которого брутфорс помогает плохо.


Я попробовал с помошью Pex найти корни поотдельности, но у меня не получилось. Он упорно выдвал только 0 => 35
А можно привести пример этого паззла, корректный с точки зрения Pex?
Re: [C#, Этюд] Математика поломалась?
От: Sharov Россия  
Дата: 30.06.10 15:43
Оценка:
Здравствуйте, nikov, Вы писали:

Спасибо большое, крайне интересная задачка.
Вот тут можно еще попрактиковаться...
Кодом людям нужно помогать!
Re[4]: [C#, Этюд] Математика поломалась?
От: SE Украина  
Дата: 30.06.10 15:49
Оценка:
Здравствуйте, SE, Вы писали:

SE>Здравствуйте, nikov, Вы писали:


SE>>>брутфорс


N>>Гораздо быстрее их можно найти с помощью Pex, в т.ч. для типа long, для которого брутфорс помогает плохо.


SE>Я попробовал с помошью Pex найти корни поотдельности, но у меня не получилось. Он упорно выдвал только 0 => 35

SE>А можно привести пример этого паззла, корректный с точки зрения Pex?

Странно, а сейчас все получилось. Задал Пексу такую задачку:


using System;

public class Program 
{
  public static void Puzzle(int x)
  {
    if(x * x - 12 * x + 35 == 0)
       Console.Write("Ok!");
  }
}


Он мне написал

1 0
2 -2147483643 Solved!
Re[3]: [C#, Этюд] Математика поломалась?
От: samius Япония http://sams-tricks.blogspot.com
Дата: 30.06.10 16:28
Оценка:
Здравствуйте, nikov, Вы писали:

N>Здравствуйте, SE, Вы писали:


SE>>брутфорс


N>Гораздо быстрее их можно найти с помощью Pex, в т.ч. для типа long, для которого брутфорс помогает плохо.


брутфорс для long находит моментально, если искать от long.MinValue
Re[2]: [C#, Этюд] Математика поломалась?
От: olegkr  
Дата: 30.06.10 18:19
Оценка: 5 (1) :))) :))
Здравствуйте, Sharov, Вы писали:

S>Вот тут можно еще попрактиковаться...


Велик и могуч pex!
using System;

public class Program 
{
  public static void Puzzle(int a, int b, int c)
  {
    if (a*a*a + b*b*b == c*c*c)
      Console.Write("Ok!"); 
  }
}


1 0 0 0 Ok!
2 -923659985 -368917183 1695297407
... << RSDN@Home 1.2.0 alpha 4 rev. 1472>>
Re: [C#, Этюд] Математика поломалась?
От: andy1618 Россия  
Дата: 01.07.10 02:58
Оценка:
Здравствуйте, nikov, Вы писали:

N>Что надо передать в метод Foo, чтобы он вернул true?

N>
N>    public static bool Foo(params int[] arr)
N>    ...
N>            arr.All(x => x * x - 12 * x + 35 == 0);
N>


Да, красивая задача на переполнение int.
Такие неочевидности хорошо лечатся директивой
checked{...}
Re[4]: [C#, Этюд] Математика поломалась?
От: nikov США http://www.linkedin.com/in/nikov
Дата: 01.07.10 07:51
Оценка:
Здравствуйте, Aen Sidhe, Вы писали:

N>>Гораздо быстрее их можно найти с помощью Pex, в т.ч. для типа long, для которого брутфорс помогает плохо.


AS>А он для любых выражений находит или только для простых? Т.е. если там будет что-нибудь послежнее многочлена второй степени — найдёт?


Не для всех, до для достаточно широкого класса, в т.ч. и многочленов более высоких степеней.

Кстати, интересно, что если использовать длинную арифметику (в которой можно записать любые числа), и ограничиться операциями сложения и умножения и проверки на равенство, то вопрос о том, выполнимо ли данное условие при каких-то значениях переменных, является алгоритмически неразрешимым (по теореме Матиясевича)
Re[5]: [C#, Этюд] Математика поломалась?
От: nikov США http://www.linkedin.com/in/nikov
Дата: 01.07.10 07:56
Оценка: 17 (3)
Здравствуйте, SE, Вы писали:

SE>2 -2147483643 Solved!


Кстати, Pex интересуется только тем, чтобы выполнить все возможные ветки в коде. Поэтому он и находит только один корень — после того, как он попал в эту ветку, дальнейшие попытки становятся ему не интересными. Но можно переписать код так, чтобы нашлись сразу 4 корня:

using System;

public class Program
{
    public static void Puzzle(int a, int b, int c, int d)
    {
        if (a < b && b < c && c < d &&
            a * a - 12 * a + 35 == 0 &&
            b * b - 12 * b + 35 == 0 &&
            c * c - 12 * c + 35 == 0 &&
            d * d - 12 * d + 35 == 0)
            throw new Exception("Solved");
    }
}
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.