В Сети обнаружил старую задачу. Покупатель пришел в магазин и взял четыре товара, продавщица рассчитала итоговую сумму на калькуляторе и назвала результат 7 р. 11 коп. Покупатель сказал, что она ошибочно вместо кнопки сложения нажимала кнопку умножения. Продавщица извинилась и пересчитала сумму, но она при этом не изменилась. Какая цена была у товаров ? Задачу можно решить методом прямого перебора, я допускаю, что возможна оптимизация. Есть идеи ?
Ответы
Подписаться на ответы
Инфостарт бот
Сортировка:
Древо развёрнутое
Свернуть все
Цены товаров составляют $1.20, $1.25, $1.50, $3.16
Потому что исходная задача, она про 7 долларов и 11 центов.
Потому что исходная задача, она про 7 долларов и 11 центов.
Имеем 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С
Перебор будет выглядить примерно так (на оптимизированность и производительность не претендует):
В итоге получим не 4 числа а все возможные интерпретации 4х чисел где например в первом полученном обходе первый товар стоил 1.20 руб во втором будет 1.25 итд.
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 итд.
(8) Фактически вывод получается что перебора нельзя миновать, то есть максимум чем можно оптимизировать решение так это как вы описали
1. упорядочивание чисел x,y,z,k,
2. ограничение на сумму включить в верхнюю границу вложенных циклов.
?
2. ограничение на сумму включить в верхнюю границу вложенных циклов.
Интересно, что:
2*2*2*2*2*2*3*3*5*5*5*5*5*5*79 = 711000000
получается, что сумма одной из покупок, должна быть кратна 79 копейкам.
2*2*2*2*2*2*3*3*5*5*5*5*5*5*79 = 711000000
получается, что сумма одной из покупок, должна быть кратна 79 копейкам.
В 1999 году эту задачу спокойно решали аналитически -
В 2022 году 1Сники пытаются решить её брутфорсом.
"Продавщица извинилась", да уж.
В 2022 году 1Сники пытаются решить её брутфорсом.
"Продавщица извинилась", да уж.
Могу утверждать, что brute force в этой задаче использовали не только 1С программисты. Попытайтесь найти решение для 9.38. Оно есть.
Пример быстрого перебора. Входная сумма в копейках.
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
Показать
Для получения уведомлений об ответах подключите телеграм бот:
Инфостарт бот
