W Cat: Система Диофанта

= Привет! Показал я твой «шторм» соседу. Он сказал, что это смертельно опасная задача.

— Да?

= Моряк или умрет со смеху или убьет составителя.

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

А я никак не оставлю тему квадратных уравнений, и вроде все сказано, поставлена точка, но появляются новые идеи......

— Для разминки приведу забавное доказательство теоремы Виетта.

Напишем базовую формулу: x 2— bx + c = 0 мы знаем что b — это сумма, а с ...

= Уже сто раз говорил...

— Не злись. Давай развернем эту запись. Я не хочу для обозначения корней писать x 1, x 2, а то от х в глазах рябить будет. Давай использовать i и j.

x 2- (i+j)*x + i*j = 0

преобразуем

x 2- ix - jx + ij = 0

= Ну, и чего получилось?

— Фокус, покус! Ведь i и j это корни уравнения. Подставь-ка вместо x - i или j.

= Да. Действительно забавно, простейшей алгеброй все доказано.

— Обрати внимание, нигде не сказано, что j и i — целые, это могут быть любые числа и не только числа.

— Но давай пойдем дальше. Есть разные способы решения КУ, в том числе графические.

= Да, читал я. Не точно, не всегда достижимо, только, что наглядно.

— Вот наглядность мне сейчас и нужна, да и еще кое что. Рассмотрим только один способ.

Как видишь, строится парабола и места пересечения с осью абсцисс (y = 0) и будут корнями. Чтобы построить параболу ax 2— bx + c = 0, для начала нужно знать координаты вершины

= Что-то подозрительно знакома мордочка у y 0.

— Дело упрощается тем, что в нашем случае a = 1.

— Смотри, у нас есть координата x 0вершины параболы, она простейша [ -b/2] корни КУ находятся на одинаковом расстоянии от этого числа. Вообще x 0очень хитрое число, ЛЮБЫЕ два числа отстоящие от него на одинаковыерасстояния, дают в сумме b.

Остается только подобрать два симметричных относительно x 0числа дающих в произведении c.

= Т.е. это другой способ, и про первый можно забыть.

— Забывать ничего не будем! Первый метод «со Множителей» если так сойдутся звезды позволит там «молниеносно» решить КУ, второй « Слагаемых» гарантирует успех, но немного медленнее.

— Не забывай о коварстве составителей. Если y 0окажется положительной, то парабола не пересечет ось абсцисс, т.е корней не будет...

= То-то я вижу, что-то знакомое — дискриминант.

— Не совсем, но родственник дискриминанта пусть это будет Д( Д= — дискриминант ).

Давай спланируем алгоритм действий.

1. оцениваем знак выражения 4c — b 2, ежели минус идем далее (этот пункт можно удалить, если мы решаем подготовленные Питоном КУ).

2. оцениваем знаки корней по известной нам таблице.

3. если удается, находим корни в соМножителях

4. ну а если дошли до этого пункта, делаем глубокомысленный вид (тренируем актерское мастерство) и начинаем перебор.

= Например?

— Хорошо, поехали:

x 2- 22x - 75 = 0

1. [- 75] — ясно что Дотрицателен

2. [ - - ] - один корень отрицателен, но положительный больше

3. [ 75 ] допустим нам лень искать делители, но пятерка там точно есть.

4. [x 0= 11] обозначим смещение корней относительно точки x 0как z. Допустим отрицательный корень [ -5 ] тогда z = 16 и следовательно x 2= 11 + 16 = 27

= Все отлично!

— Погоди, что-то тут не так, 27 * 5 = 135, не сходится. Т.е. [-5] слишком далеко ушло в минус. Давай попробуем предыдущее простое число [-3] тогда z = 14 и следовательно x 2= 11 + 14 = 25 и 25 * 3 = 75. Вот теперь — все отлично.

= А можно было сделать проще, без всяких z. Когда предположен один корень второй просто вычисляется x 2= b — x 1т.е. 22 - (-3) = 25.

— Ты мыслишь, значит ты существуешь!!!

— Повторю свое заклинание «только постоянные экзерсисы приведут тебя к успеху».

= Я только не совсем понял для чего нам x 0.

— Ну скажем, это якорь на который мы ориентируемся при поиске корня. Для поиска можно воспользоваться двоичным поиском.

= А это что такое?

— Лучше показать это на примере.

Я задумываю число больше 0 и меньше 100 (ну вот записываю «задумано 43»). Ты говоришь предположение, в ответ я могу дать 3 возможных ответа «задуманное больше», «задуманное меньше» и «Поздравляю».

= 99?

— Задуманное меньше.

= 98?

— Задуманное меньше. Но прервем игру. Выбранная тобой стратегия не рациональна. Если задумано 1, то тебе придется задать 99 вопросов.