PYTHON
Напишите программу для решения уравнения ax=b относительно х в целых числах. Учтите, что a может принимать любые значения, в том числе и 0.
Входные данные
На вход программе подаются целые числа a, b, по модулю не превосходящие 30 000.
Выходные данные
Требуется вывести целый корень уравнения, если он существует и единственный. Если уравнение не имеет корней, то вывести no solution. Если уравнение имеет больше одного целого корня, то вывести many solutions.
Пример. Найти минимум функции P(x,y,z) при заданных ограничениях.
Как видно из условия, имеется пять ограничений.
Конечно, в данном случае можно решить задачу методом простого перебора параметров с каким-то шагом, сначала найти примерное положение минимума (или минимумов, если их несколько), а потом уменьшить шаг и повторить поиск, но методом Монте-Карло задача решается намного изящнее.
function f(x, y, z: real): real;
begin
f := sin(2 * x) + cos(3 * y) + sqr(sin(4 * z + 1))
end;
var
x, y, z, p, x1, y1, z1, p1: real;
i, n: longint;
begin
Write('Введите число проб: ');
Readln(n);
Randomize;
p1 := 1e20;
for i := 1 to n do
begin
repeat
x := 4 * Random - 2;
y := 3 * Random - 1.5;
z := 10 * Random - 5
until (x>0) and (x*z>=0);
p := f(x, y, z);
if p1 > p then begin
x1 := x; y1 := y; z1 := z; p1 := p
end;
end;
Writeln('n=', n:8, ' ', x1:0:4, ' ', y1:0:4, ' ', z1:0:4, ' Минимум=', p1)
end.
Тестовое решение (при разных количествах проб):
Введите число проб: 1000
n= 1000 1.9111 -1.0660 0.5749 Минимум=-1.6029403376222
n= 10000 1.9931 -1.0176 2.0465 Минимум=-1.68773775014315
Введите число проб: 100000
n= 100000 1.9985 -1.0401 0.5191 Минимум=-1.75037309941284
Введите число проб: 1000000
n= 1000000 1.9997 1.0378 3.6868 Минимум=-1.7544874244815
Введите число проб: 10000000
n=10000000 1.9995 1.0471 2.1027 Минимум=-1.75595433108399
Вычисление даже для 10 миллионов проб выполняется около 5 секунд, так что быстродействие метода прекрасное
Анализ результатов показывает, что наша целевая функция имеет значительное количество экстремумов, что связано с наличием в ней трех периодических функций. Значение аргумента х практически определено (оно меняется незначительно), его можно зафиксировать и продолжить поиск уже для функции двух переменных, границы которых также следует сузить в районе полученных значений.
Посмотрим, как будут отыскиваться экстремумы с теми же ограничениями на те же параметры, если целевую функцию заменить на непериодическую:
В программе при этом надо будет только изменить формулу целевой функции:
f := 3.5*sqr(x)+2.4*sqr(y-1)-6.18*y*z
Тестовое решение:
Введите число проб: 1000
n= 1000 0.4468 1.3516 4.9403 Минимум=-40.2712691657245
n= 10000 0.1716 1.4677 4.8246 Минимум=-43.1319690531051
Введите число проб: 100000
n= 100000 0.0283 1.4920 4.9365 Минимум=-44.9334596263254
Введите число проб: 1000000
n= 1000000 0.0320 1.4891 4.9963 Минимум=-45.3999805516411
Введите число проб: 10000000
n=10000000 0.1106 1.4998 4.9993 Минимум=-45.6964653852599
Хорошо видно, что параметры y и z уже после 10 тысяч проб практически не меняются, а параметр х меняется в значительных пределах. Дальнейший путь решения - зафиксировать с некоторой точностью найденные значения параметров и продолжить поиск значения уже одной переменной в области [0;0.15], или также зафиксировать найденное значение функции и решить полученное уравнение относительно х.