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 коп.
Оставьте свое сообщение
Вакансии
Программист 1С
Москва
зарплата от 180 000 руб. до 220 000 руб.
Полный день

Аналитик 1С / Бизнес-аналитик
Нижний Новгород
зарплата от 100 000 руб. до 250 000 руб.
Временный (на проект)

Программист 1С
Москва
зарплата от 250 000 руб.
Полный день

Программист 1C
Волгоград
зарплата от 200 000 руб.
Полный день

Аналитик
Санкт-Петербург
зарплата от 200 000 руб. до 250 000 руб.
Полный день