Недавно вернулся с Харьковской обласной олимпиады

← →
Ricks (2003-02-02 18:20) [0]

Кое-как попал во второй тур. 2 задачи, вот посмотрите, please:
Сделать программу для нахождения количества решений уравнения (привожу в виде кода, тк там надстрочные, подстрочные итд):
Sqr(X1) + Sqr(X2) + Sqr(X3) + ... + Sqr(XN) = S
где
N и S целые числа (1..100) вводятся с клавиатуры.
Например
N = 2
S = 5
Ответ : 8
И цЫтата с листика (перевожу с украинского, как можу):
примечание: "Множина" ответов:{(1,2);(2,1);(-1, 2) итд}
Попробуйте!

← →
Ricks (2003-02-02 18:41) [1]

Люди, ну почитайте, помогите разобраться, мне интересно ведь :-)

← →
Skyle (2003-02-02 19:00) [2]

Ну давай я попробую. Не проверял особо, так.. идея появилась.
Утверждение: уравнение однородное, поэтому всё множество решений будет перестановками одного какого-то набора. То есть, если мы нашли такое решение, где x1=y1, x2=y2, ..., xn=yn, то все перестановки этого множества будут являться решениями, а все другие решения будут перестановками этого. Дальше так: Пусть X1 изменяется на интервале [0, [sqrt(S)]], где [SQRT(S)](назовём S1) - целая часть от квадратного корня из S. X2 - [0, [SQRT(S-S1)]], .... и будем в рекурсии пробегать все эти значения до нахождения корня. Множество решений (в модулях) будет иметь мощность N. Итоговое - 2N(SQR(x) = SQR(-x)). А вот дальше идёт шаг, в котором я ещё больше не уверен, чем во всём, что я писал до этого: итоговое количество решений равно N!(по модулям) * 2^N (комбинации знаков). Естественно, для этого надо доказать, что этот единственный набор существует. То есть, если набор найден, то ответ : N!*2^N, если нет - 0. Буду рад получить в мыло правильный ответ.

← →
Ricks (2003-02-02 19:20) [3]

> Skyle
Спасибо, что попробовал. Хотя я все-равно ничего не понял :-)

> Буду рад получить в мыло правильный ответ.
Я то это и писал, в надежде, что кто-нибудь решит и объяснит мне бестолковому :-)

← →
Романов Р.В. (2003-02-02 19:21) [4]

Мутная какая то задача. Разве
Sqr(1) + Sqr(2) = 5

← →
Skyle (2003-02-02 19:23) [5]

> Романов Р.В. © (02.02.03 19:21)
> Мутная какая то задача. Разве
> Sqr(1) + Sqr(2) = 5

Это был вопрос? :))

> Ricks © (02.02.03 19:20)
> > Skyle
> Спасибо, что попробовал. Хотя я все-равно ничего не понял
> :-)

Предлагаю перейти в мыло...:)

← →
Ricks (2003-02-02 19:29) [6]

>Skyle
А что в мыльце писать???

>Романов Р.В.
1*1 = 1 2*2 = 4 1+2 = 5
:-))))

← →
Романов Р.В. (2003-02-02 19:32) [7]

Все равно не понял. И еще Система из n уравнений с m неизвестными при n<m имеет бесконечное множество решений.

← →
Ricks (2003-02-02 19:35) [8]

Тьфу, опечатка. :-)
Читай
1*1 = 1 2*2 = 4 1+4 = 5
А насчет решений, я, чесно, не знаю.

← →
Романов Р.В. (2003-02-02 19:44) [9]

Совсем уже забыл что Sqr - квадрат числа, а Sqrt корень :(

Например
X1 := SQRT(2);
X2 := SQRT(3);

SQR(X1) + SQR(X2) = ?

или вот еще

X1 := SQRT(1,5);
X2 := SQRT(3,5);

← →
Skyle (2003-02-02 19:45) [10]

> Романов Р.В. © (02.02.03 19:32)
> Все равно не понял

Кто-то из нас точно не догоняет...:) Либо ты, либо я...:)

> > Skyle
> Спасибо, что попробовал. Хотя я все-равно ничего не понял
> :-)

Давай попробуем здесь ещё раз...:)
утверждение проверять пока не будем, примем за истину. Дальше.
Разберём приведённый тобой пример про x1^2 + X2^2 = 5. Интервал для X1 - от 0 до целой части корня из S, то есть до 2(S1) и может принимать значения {0, 1, 2}. так как при решении считаем, что X1 - бОльшая переменная, и S <> 0, то X1 = {1, 2}. Будем спускаться вниз, то есть скажем, что X1 =2. тогда для X2 остаются значения от 0 до S - S1(кстати, в первом моём посте ошибка - тут читать не S-S1, а S-S1^2, то есть 5-2^2 = 1. Т.е получаем, что X2 принимает значения {0, 1}. Опять идём с конца и получаем интересующий нас набор {1,2}. Далее: количество комбинаций данного набора в модулях - N! (первая переменная может принять N значений из набора, вторая - N - 1 и т.д). Из-за того, что X^2 = (-X)^2 получаем, что может быть ещё и вариация знаков, то есть окончательный ответ - N! * 2^N (N переменных имеют 2 варианта каждого значения). Для предложенного варианта : Ответ = 2!*2^2 = 1*2*2*2 = 8

← →
Skyle (2003-02-02 19:53) [11]

Да, ещё одна поправочка, надеюсь последняя. :)))
Окончательный ответ будет N! * 2^N * Z, где Z - количество уникальных наборов, найденное рекурсией. Это, так сказать, общий случай...:)

← →
Ricks (2003-02-02 19:58) [12]

> Skyle
О! Вроде вдуплил! :-) Слов нет....... :-) Merci

Недавно вернулся с Харьковской обласной олимпиады Найти похожие ветки