Price puzzle

1. scientes 288 23.10.22 19:17 Сейчас в теме
В Сети обнаружил старую задачу. Покупатель пришел в магазин и взял четыре товара, продавщица рассчитала итоговую сумму на калькуляторе и назвала результат 7 р. 11 коп. Покупатель сказал, что она ошибочно вместо кнопки сложения нажимала кнопку умножения. Продавщица извинилась и пересчитала сумму, но она при этом не изменилась. Какая цена была у товаров ? Задачу можно решить методом прямого перебора, я допускаю, что возможна оптимизация. Есть идеи ?
Ответы
Подписаться на ответы Сортировка: Древо развёрнутое
Свернуть все
2. user1863362 23.10.22 20:15 Сейчас в теме
Цены товаров составляют $1.20, $1.25, $1.50, $3.16
Потому что исходная задача, она про 7 долларов и 11 центов.
3. user856012 13 23.10.22 20:35 Сейчас в теме
(2)
исходная задача, она про 7 долларов и 11 центов.
У автора - импортозамещение! :-)
4. muskul 24.10.22 03:08 Сейчас в теме
система уравнений. по идеи так она и должна решаться
5. scientes 288 24.10.22 07:58 Сейчас в теме
(4)Переменных 4, уравнений 2. Получится выразить две цены, через две оставшихся. Это будут решения квадратного уравнения. И все равно потребуется запускать перебор.
6. scientes 288 24.10.22 09:23 Сейчас в теме
(4) Любопытно, но кроме приведенных решений есть еще одно.
1,2 1,6 1,185 3,125 сумма->7,11 произведение->7,11. Но , как мы помним, в рубле 100 копеек, а не 1000.
7. DENSKR 15 24.10.22 10:34 Сейчас в теме
Имеем 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 итд.
8. scientes 288 24.10.22 10:40 Сейчас в теме
(7) Все верно. Это полный перебор. Самое первое чем его можно ограничить
1. упорядочивание чисел x,y,z,k,
2. ограничение на сумму включить в верхнюю границу вложенных циклов.
9. DENSKR 15 24.10.22 10:43 Сейчас в теме
(8) А каким образом можно реализовать
ограничение на сумму включить в верхнюю границу вложенных циклов
?
10. scientes 288 24.10.22 10:48 Сейчас в теме
(7) Для x=1 По 711 Цикл
Для y=x По 711-x Цикл
Для z=y По 711-x-y Цикл
k= 711-x-y-z;
11. DENSKR 15 24.10.22 10:55 Сейчас в теме
(8) Фактически вывод получается что перебора нельзя миновать, то есть максимум чем можно оптимизировать решение так это как вы описали
1. упорядочивание чисел x,y,z,k,
2. ограничение на сумму включить в верхнюю границу вложенных циклов.
?
12. SlavaKron 24.10.22 11:02 Сейчас в теме
Интересно, что:
2*2*2*2*2*2*3*3*5*5*5*5*5*5*79 = 711000000
получается, что сумма одной из покупок, должна быть кратна 79 копейкам.
13. scientes 288 24.10.22 11:09 Сейчас в теме
(7) Да, это еще один способ оптимизации перебора. Искомые числа должны делиться на 2,3,5 или 79. Других множителей быть не может.
14. user1863362 24.10.22 11:39 Сейчас в теме
В 1999 году эту задачу спокойно решали аналитически - https://web.archive.org/web/20020619105604/http://mathforum.org/library/drmath/view/55897.html
В 2022 году 1Сники пытаются решить её брутфорсом.

"Продавщица извинилась", да уж.
15. SlavaKron 24.10.22 12:20 Сейчас в теме
(14) Предлагаю решить аналитически для суммы 747,32
17. scientes 288 24.10.22 14:07 Сейчас в теме
(15) Удивительно, но для данного примера решение есть. Нашел перебором.

0,4 1,57 1,6 743,75 сумма->747,32 произведение->747,32
18. SlavaKron 24.10.22 14:31 Сейчас в теме
(17) Ну да, специально подобрал. В качестве альтернативной задачи, можно попробовать найти все возможные варианты формулировки, где:
a + b + c + d = a * b * c * d = e, в оговоренном пределе e.
16. scientes 288 24.10.22 12:31 Сейчас в теме
Могу утверждать, что brute force в этой задаче использовали не только 1С программисты. Попытайтесь найти решение для 9.38. Оно есть.
19. scientes 288 24.10.22 15:11 Сейчас в теме
Пример быстрого перебора. Входная сумма в копейках.

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

Показать
20. scientes 288 24.10.22 15:46 Сейчас в теме
Как показывают вычисления, минимальная сумма, для которой задача имеет решение - 644 коп.
Оставьте свое сообщение

Для получения уведомлений об ответах подключите телеграм бот:
Инфостарт бот