В Сети обнаружил старую задачу. Покупатель пришел в магазин и взял четыре товара, продавщица рассчитала итоговую сумму на калькуляторе и назвала результат 7 р. 11 коп. Покупатель сказал, что она ошибочно вместо кнопки сложения нажимала кнопку умножения. Продавщица извинилась и пересчитала сумму, но она при этом не изменилась. Какая цена была у товаров ? Задачу можно решить методом прямого перебора, я допускаю, что возможна оптимизация. Есть идеи ?
(4)Переменных 4, уравнений 2. Получится выразить две цены, через две оставшихся. Это будут решения квадратного уравнения. И все равно потребуется запускать перебор.
(4) Любопытно, но кроме приведенных решений есть еще одно.
1,2 1,6 1,185 3,125 сумма->7,11 произведение->7,11. Но , как мы помним, в рубле 100 копеек, а не 1000.
Имеем 2 уравнения:
1) x + y + z + k = 7.11
2) x * y * z * k = 7.11
Переведем все в копейки:
Так как в рубле 100 копеек переведем * 100 и для второго уравнения сумма получится умножим на 100 000 000 = (100^4):
100 * x + 100 * y + 100 * z + 100 * k = 711
100 * x * 100 * y * 100 * z * 100 * k = 711 000 000
С точки зрения алгоритма 1С
Перебор будет выглядить примерно так (на оптимизированность и производительность не претендует):
Для x=1 По 711 Цикл
Для y=1 По 711 Цикл
Для z=1 По 711 Цикл
Для k=1 По 711 Цикл
Если (x+y+z+k = 711) И (x*y*z*k = 711000000) Тогда
//результат делим на 100 но тут у меня сомнения на счет правильности перебора
Сообщить("Стоимость 1 товара: "+ x/100);
Сообщить("Стоимость 2 товара: "+ y/100);
Сообщить("Стоимость 3 товара: " + z/100);
Сообщить("Стоимость 4 товара: " + k/100);
КонецЕсли;
КонецЦикла;
КонецЦикла;
КонецЦикла;
КонецЦикла;
Показать
В итоге получим не 4 числа а все возможные интерпретации 4х чисел где например в первом полученном обходе первый товар стоил 1.20 руб во втором будет 1.25 итд.
(7) Все верно. Это полный перебор. Самое первое чем его можно ограничить
1. упорядочивание чисел x,y,z,k,
2. ограничение на сумму включить в верхнюю границу вложенных циклов.
(17) Ну да, специально подобрал. В качестве альтернативной задачи, можно попробовать найти все возможные варианты формулировки, где:
a + b + c + d = a * b * c * d = e, в оговоренном пределе e.
Пример быстрого перебора. Входная сумма в копейках.
Function PrimeFactor(Знач n)
vt=new ValueTable;
vt.Columns.Add("p");
vt.Columns.Add("c");
j=n;
for p=2 to Round(sqrt(n),0,1) do
c=0;
while (j%p)=0 do
c=c+1;
j=j/p;
enddo;
if c>0 then
r=vt.add();
r.p=p;
r.c=c;
endif;
enddo;
if j<>1 and j<>n then
r=vt.add();
r.p=j;
r.c=1;
endif;
info="";
for each r in vt do
if IsBlankString(info) then
info=info+r.p;
else
info=info+"*"+r.p;
endif;
if r.c>1 then
info=info+"^"+r.c;
endif
enddo;
сообщить("Факторизация входного числа "+info);
return vt;
Endfunction
Function RecurcePrice(pos,vt,m,arr)
if pos = vt.Count() then
arr.Add(m);
return(1);
endif;
count=0;
j=1;
for i=1 to vt[pos].c+1 do
mm=m*j;
count=count+RecurcePrice(pos+1,vt,mm,arr);
j=j*vt[pos].p;
enddo;
return count;
EndFunction
function PricePuzzle(s=711) export
//**************************************************************
// Выполняем разложение входного числа на простые множители
//**************************************************************
vt=PrimeFactor(s);
//*************************************************************
// Добавляем в разложение 2^6 и 5^6
//*************************************************************
arr=new array;
arr.Add(2);arr.Add(5);
for each d in arr do
find=vt.Find(d,"p");
if find=undefined then
find=vt.Add();
find.p=d;
find.c=0;
endif;
find.c=find.c+6;
enddo;
//*************************************************************
// Находим все делители числа s*10^6 и заносим их в массив arr
//*************************************************************
arr=new array;
RecurcePrice(0,vt,1,arr);
s1=s*1000000;
//************************************************************************
// Перебираем все пары делителей числа s*10^6 и
// рассчитываем два других числа, как корни квадратного уравнения
//************************************************************************
for each x in arr do
for each y in arr do
if y<x then
continue;
endif;
if (x+y)<s and (x*y)<=s1 then
b=-(s-x-y);
c=s1/(x*y);
D=b*b-4*c;
if D>0 then
t=Round(Sqrt(D),0,1);
if t*t=D then
z1=(-b-t)/2;
z2=(-b+t)/2;
checks=(x+y+z1+z2)/100;
checkm=(x*y*z1*z2/100000000);
message(""+x/100+" "+y/100+" "+" "+z1/100+" "+z2/100+" сумма->"+checks+" произведение->"+checkm );
endif;
endif;
endif;
enddo;
enddo;
endfunction