gifts2017

Задача о числах мудрецов

Опубликовал Валерий (scientes) в раздел Программирование - Практика программирования

Решаем головоломку средствами 1С

Однажды мне попалась вот такая задача:

Пусть x и y два целых числа 1<x<y притом x + y≤100. Салли сказали только сумму x + y, а вот Полю произведение xy. Салли и Пол честнейшие ребята, это всем известно, они и друг другу отродясь не врали.
И вот такой вышел у них разговор:
Пол: «Не знаю я, что это за числа.»
Салли: «Тоже новость. Я знаю, что ты не знаешь.»
Пол: «Ну твоя то сумма мне теперь известна.»
Салли: «Да уж и мне теперь твое произведение.»
Каковы числа? 

Идея решения пришла быстро, но отыскать его с помощью бумаги и карандаша оказалось трудно, поэтому пришлось обратиться к 1С.

Сначала определим алгоритм поиска. Хочу поблагодарить Сергея (ildarovich) за сделанное замечание, это позволило исправить первоначальный вариант, который давал правильные решения, но содержал ошибку

На первом шаге сформируем таблицу, в которой перечислены все пары чисел, удовлетворяющие условиям задачи (больше 1, плюс ограничение на сумму) и рассчитаны значения их суммы и произведения. Среди  строк таблицы есть такие, которые содержат уникальные значения в колонке сумма или произведение, например, произведение простых чисел будет уникальным или куб простого числа тоже имеет единственное разложение на два множителя. Сформируем две таблицы tOneMult и tOneSum. Эти таблицы содержат неповторяющиеся значения произведения и суммы из исходной таблицы. Теперь подготовим еще одну вспомогательную таблицу pt, в ней будут храниться все значения поля сумма из таблицы с начальными данными из тех строк, для которых значение поля произведение попадает в таблицу tOneMult. На следующем шаге удалим из исходной таблицы те записи, которые позволяют Полю и Салли сразу найти решение. А именно, удалим строки котрорые содержат значения в колонке сумма или произведение из таблиц tOneSum или tOneMult.   Теперь добавим в нашу таблицу колонку, которую назовем IsNotPrimeSum. Таблицу назовем T1. Если сумма чисел в строке может быть записана как сумма двух чисел, которые можно однозначно определить по их произведению, то в эту колонку мы занесем 0, в противном случае 1. Обратимся к условию задачи. Когда Салли отвечает Полу: "Тоже новость. Я знаю, что ты не знаешь.", это означает, что известная ему сумма не может быть записана как сумма двух чисел, которые однозначно определяются из их произведения. Получив, эту дополнительную информацию, Пол анализирует разложение известного  ему произведения на множители и отбрасывает те, у которых сумма множителей не удовлетворяет вышеназванному условию, в результате у него остается  единственный вариант. Чтобы найти такие произведения, сгруппируем предыдущую таблицу по полю произведение, а к полю IsNotPrimeSum применим функцию SUM(). Оставим только те строки, для которых значение агрегатной функции равно 1. Теперь из таблицы Т1 выберем все строки с найденными на предыдущем шаге значениями произведения и значениями поля IsNotPrime=1. Из полученного множества выберем строки, которые содержат неповторяющиеся значения суммы сомножителей. Ну и последний шаг - отобрать из таблицы Т1 строки с найденными значениями суммы и произведения. Числа из отобранных строк будут решениями нашей задачи. 

Приведу код, который я использовал при поиске решения. Сначала текст вспомогательной функции, которая помещает таблицу значений во временную таблицу, чтобы появилась возможность обращаться к ней в запросе. Аргумент МТТ - это ссылка на объект типа МенеджерВременныхТаблиц.

 

//********************************************************
// Поместить таблицу значений во временную таблицу
//********************************************************

Функция PutToTemporaryTable(vt,name,MTT)
	ТекстЗапроса="ВЫБРАТЬ
	             |	ВходнаяТаблица.*
		     |ПОМЕСТИТЬ ВременнаяТаблица
	             |ИЗ
	             |	&мТЗ КАК ВходнаяТаблица
	             |;";
		            
	запрос=новый Запрос;
	запрос.Параметры.Вставить("мТЗ",vt);
	запрос.текст=СтрЗаменить(ТекстЗапроса,"ВременнаяТаблица",name);
	запрос.TempTablesManager=MTT;
	запрос.Выполнить();

КонецФункции

Теперь функция, в которой реализован приведенный выше алгоритм.

 

Function ProblemSumAndMult(size=100) export
	
	TypeNumber=new TypeDescription("Number");

	
	UpLimit=size;
	
		
	vt=new ValueTable;
	vt.Columns.Add("a",TypeNumber);
	vt.Columns.Add("b",TypeNumber);
	vt.Columns.Add("sum",TypeNumber);
	vt.Columns.Add("mult",TypeNumber);
	
	for i=2 to UpLimit do
		for j=i+1 to UpLimit-i do
			s=i+j;
			row=vt.Add();
			row.a=i;
			row.b=j;
			row.sum=s;
			row.mult=i*j;
		enddo;
	enddo;	
	
	
	TTM=new TempTablesManager;
	query=new Query;
	query.TempTablesManager=TTM;
	
	
	PutToTemporaryTable(vt,"vt",TTM);
	query.Text="SELECT
	           |	vt.a,
	           |	vt.b,
	           |	vt.sum AS sum,
	           |	vt.mult AS mult,
	           |	1 AS count
	           |INTO mInitTable
	           |FROM
	           |	vt AS vt
	           |;
	           |
	           |////////////////////////////////////////////////////////////////////////////////
	           |SELECT
	           |	tInitTable.mult,
	           |	SUM(tInitTable.count) AS count
	           |INTO tOneMult
	           |FROM
	           |	mInitTable AS tInitTable
	           |
	           |GROUP BY
	           |	tInitTable.mult
	           |
	           |HAVING
	           |	SUM(tInitTable.count) = 1
	           |;
	           |
	           |////////////////////////////////////////////////////////////////////////////////
	           |SELECT
	           |	tInitTable.sum,
	           |	SUM(tInitTable.count) AS count
	           |INTO tOneSum
	           |FROM
	           |	mInitTable AS tInitTable
	           |
	           |GROUP BY
	           |	tInitTable.sum
	           |
	           |HAVING
	           |	SUM(tInitTable.count) = 1
	           |;
	           |
	           |////////////////////////////////////////////////////////////////////////////////
	           |SELECT DISTINCT
	           |	mInitTable.sum
	           |INTO pt
	           |FROM
	           |	mInitTable AS mInitTable
	           |		INNER JOIN tOneMult AS tOneMult
	           |		ON mInitTable.mult = tOneMult.mult
	           |;
	           |
	           |////////////////////////////////////////////////////////////////////////////////
	           |SELECT
	           |	mInitTable.a,
	           |	mInitTable.b,
	           |	mInitTable.sum,
	           |	mInitTable.mult,
	           |	mInitTable.count
	           |INTO tFilter
	           |FROM
	           |	mInitTable AS mInitTable
	           |WHERE
	           |	NOT mInitTable.sum IN
	           |				(SELECT
	           |					tOneSum.sum
	           |				FROM
	           |					tOneSum)
	           |	AND NOT mInitTable.mult IN
	           |				(SELECT
	           |					tOneMult.mult
	           |				FROM
	           |					tOneMult)
	           |;
	           |
	           |////////////////////////////////////////////////////////////////////////////////
	           |DROP mInitTable
	           |;
	           |
	           |////////////////////////////////////////////////////////////////////////////////
	           |DROP tOneMult
	           |;
	           |
	           |////////////////////////////////////////////////////////////////////////////////
	           |DROP tOneSum
	           |;
	           |
	           |////////////////////////////////////////////////////////////////////////////////
	           |SELECT
	           |	tFilter.a,
	           |	tFilter.b,
	           |	tFilter.sum,
	           |	tFilter.mult,
	           |	tFilter.count,
	           |	CASE
	           |		WHEN pt.sum IS NULL 
	           |			THEN 1
	           |		ELSE 0
	           |	END AS IsNotPrimeSum
	           |INTO T1
	           |FROM
	           |	tFilter AS tFilter
	           |		LEFT JOIN pt AS pt
	           |		ON tFilter.sum = pt.sum
	           |;
	           |
	           |////////////////////////////////////////////////////////////////////////////////
	           |SELECT
	           |	T1.mult,
	           |	SUM(T1.IsNotPrimeSum) AS IsNotPrimeSum
	           |INTO CandidateMult
	           |FROM
	           |	T1 AS T1
	           |
	           |GROUP BY
	           |	T1.mult
	           |
	           |HAVING
	           |	SUM(T1.IsNotPrimeSum) = 1
	           |;
	           |
	           |////////////////////////////////////////////////////////////////////////////////
	           |SELECT
	           |	T1.sum,
	           |	SUM(T1.count) AS count
	           |INTO CandidateSum
	           |FROM
	           |	T1 AS T1
	           |		INNER JOIN CandidateMult AS CandidateMult
	           |		ON T1.mult = CandidateMult.mult
	           |WHERE
	           |	T1.IsNotPrimeSum = 1
	           |
	           |GROUP BY
	           |	T1.sum
	           |
	           |HAVING
	           |	SUM(T1.count) = 1
	           |;
	           |
	           |////////////////////////////////////////////////////////////////////////////////
	           |SELECT
	           |	T1.a,
	           |	T1.b,
	           |	T1.sum,
	           |	T1.mult,
	           |	T1.count,
	           |	T1.IsNotPrimeSum
	           |INTO Solution
	           |FROM
	           |	T1 AS T1
	           |		INNER JOIN CandidateSum AS CandidateSum
	           |		ON T1.sum = CandidateSum.sum
	           |		INNER JOIN CandidateMult AS CandidateMult
	           |		ON T1.mult = CandidateMult.mult
	           |;
	           |
	           |////////////////////////////////////////////////////////////////////////////////
	           |SELECT
	           |	Solution.a,
	           |	Solution.b,
	           |	Solution.sum,
	           |	Solution.mult,
	           |	Solution.count,
	           |	Solution.IsNotPrimeSum
	           |FROM
	           |	Solution AS Solution";
			   
			   
     table=query.Execute().Unload(QueryResultIteration.Linear);			   

	 for each row in  table do
	     message("a="+row.a+" b="+row.b);
	 enddo;	 
	 
EndFunction	

Ответ приводить не буду. Приведу результаты своих исследований. В условиях задачи сумма чисел меньше или равна 100. Первое решение появляется, когда верхний предел становится равен 65. Второе решение появляется при верхнем пределе 1685.

Послесловие.

В начале статьи я благодарю Сергея (ildarovich) за сделанное замечание. Он указал, что два различных числа больше единицы  однозначно определяются по их произведению не только в случае, когда эти числа простые, но и в двух других, когда их произведение является либо кубом либо четвертой степенью простого числа. Во всех найденных мной в Сети решениях задачи о мудрецах говорится только о произведении простых чисел. Впрочем, с таким заявлением я поспешил, в этой статье такие варианты рассматриваются. Проведем поиск решения на конкретном примере . И так у нас есть таблица, которая содержит суммы двух чисел и их произведение. Значения произведений мы можем разбить на две группы, в первую отнесем  повторяющиеся значения, во вторую неповторяющиеся.

Таблица с данными
На приведенном рисунке в левой таблице содержатся неповторяющиеся произведения, в правой повторяющиеся. Данные построены для случая, когда сумма сомножителей меньше или равна 11. Внимательный читатель сразу заметит, что к неповторяющимся отнесено произведение 20, хотя 20 равно 4*5 и 2*10. Точно так же не подходят под критерий неповторяющихся произведения 28 и 30. Все дело в ограничении на сумму.  Для числа 20 сумма множителей 4 и 5 равна 9 и эта пара попадает в исследуемый набор, а сумма множителей 2 и 10 равна 12, что больше верхнего предела. Поэтому эта пара в наборе отсутствует.  Отсюда первый вывод , то куда попадет произведение из исходной последовательности зависит от ограничения на сумму сомножителей.

Разбиение на 2 множества при ограничении на сумму 16

Если мы будем рассматривать набор чисел, для которых сумма множителей меньше 16, то увидим что значения 20,28 и 30 исчезли из левой таблицы. Это подтверждают данные на приведенном рисунке. Следующий шаг заключается в поиске таких значений из колонки Сумма, которые не встречаются в левой таблице, но присутствуют в правой. В последнем примере таким числом является 11. И обнаружить мы это можем только начиная с суммы множителей равной 16.  Вот и второе наблюдение, список чисел, которые не выражаются в виде суммы сомножителей, чье произведение не повторяется в рассматриваемом наборе, зависит от размера этого набора. Ниже приведен список таких чисел. В колонке Предел проставлено значения верхнего предела суммы множителей, при котором появляется данное значение. Такие суммы назовем числами Салли.

Таблица сумм

Решения нашей задачи нам нужно искать среди таких пар, у которых значение суммы содержится в приведенном выше наборе. Найденные пары опять разобьем на две группу. В первую занесем те значения, которые не содержат повторяющиеся значения из колонки Произведение, во вторую отнесем пары с повторяющимися значениями произведения. Ниже приводятся таблицы для случая, когда сумма множителей меньше 64.

Сумма меньше 64

Левая таблица показана не полностью. Обратим внимание на две пары из левой таблицы - (17;52) и (17;70). Увеличим верхнюю границу до 65. Согласно нашим данным при этом ограничении появляется число Салли равное 37.

Решение для верхней границы 65

37 можно представить в виде суммы двух чисел 2 и 35. Их произведение равно 70. Значит произведение со значением 70 стало повторяющимся, появилось две пары (17;70) и (37;70). Поэтому пара (17;70) из левой таблицы уйдет. И в левой таблице появится пара (17;52) , у которой значение из колонки Сумма уникальное. И эта пара будет первым решением  задачи о числах мудрецов.

В изложенном подходе мы обрабатывали исключительно набор данных образованных парами, составленными из значений суммы и произведения двух множителей. В этом случае состав множества чисел, которые мы назвали числа Салли, определяется верхней границей для суммы сомножителей. В тоже время, существует альтернативный подход для построения чисел Салли. На первом шаге мы можем сгенерировать ряд простых чисел. На следующем  составить множество из попарной суммы простых чисел и сумм вида (p+p*p), а также (p+p*p*p), где p - это простое число. А затем найти числа, которые не вошли в указанный набор, но больше его нижней границы и меньше верхней. Именно такой подход я использовал в первой редакции статьи, но не включил в рассмотрение кубы и четвертые степени простых чисел. Результаты, которые дает запрос Сергея (ildarovich) и подход с использованием генерации чисел Салли совпадают. Отличие заключается в значении суммы множителей, при которых эти решения появляются. Ниже приводится ряд образованный значениями ограничений на сумму, при которых появляются новые решения задачи, если использовать генератор чисел Салли - 37,439,757,991,1267,1925,2023,2227,2323.  Запрос Сергея дает первое решение при верхней границе - 65 (это показано в разобранном примере) , второе при верхней границе 1685.

Ну и наконец, заключительная таблица с числами мудрецов.

       число А              число В           Сумма      Произведение
4 13 17 52
4 61 65 244
16 73 89 168
16 111 127 1 776
64 73 137 4 672
32 131 163 4 192
4 229 233 916
32 311 343 9 952
64 309 373 19 776

См. также

Подписаться Добавить вознаграждение

Комментарии

1. Александр Гремячкин (itvdonsk) 06.02.15 05:34
И всего-то в задаче не указано что числа простые. Кажется автор телепат 80 уровня.
PheelSAV; GreenDragon; mrmasson; Dmirily; +4 Ответить 1
2. Алексей Роза (DoctorRoza) 06.02.15 08:37
Решать головоломки с помощью 1С - мое нутро отвергает это напрочь! Только хардкор, только С++/Java! :)
3. Антон Антонов (monkbest) 06.02.15 10:02
Не очень понятно, почему это обязательно простые числа?
4. Игорь Пашутин (Alien_job) 06.02.15 10:25
конечно не простые, автор об этом пишет в первом же абзаце
5. Валерий (scientes) 06.02.15 10:32
(1) itvdonsk, Я прочитал замечание о простых числах и внес изменение в текст статьи, чтобы этот момент сразу стал понятен.
6. Игорь Пашутин (Alien_job) 06.02.15 10:59
7. Валерий (scientes) 06.02.15 11:28
(6) Alien_job, если будет желание поэкспериментируйте со значением ограничения на сумму. Первое решение появится только тогда, когда верхняя граница равна 37, хотя сумма чисел решения будет меньше этого значения. 4 и 61 тоже самое, я сначала думал, что это ошибка в моей программе. Но нет, так и должно быть.
8. Валерий Дяченко (davealone) 06.02.15 11:31
Допустим мы отсеяли все простые, но дальше если сумма и произведение известны, почему не решить головоломку как систему уравнений? Есть:
X + Y = SUM -> Y = SUM - X
X * Y = PROD - > SUM*X - X^2 = PROD -> X^2 - SUM*X + PROD = 0
Получим обычное квадратное уравнение, у которого меньший корень єто X, а больший Y
9. Игорь Пашутин (Alien_job) 06.02.15 11:33
(8) davealone, мы не знаем суммы и произведения
10. Игорь Пашутин (Alien_job) 06.02.15 11:33
(8) davealone, мы не знаем суммы и произведения(7) scientes,
11. Игорь Пашутин (Alien_job) 06.02.15 11:35
(7) scientes, да, экспериментирую. Но не представляю причину отсутствия решения при ограничении на сумму ммм меньше 37
12. Игорь Пашутин (Alien_job) 06.02.15 11:44
(7) scientes, "Среди строк таблицы есть такие, которые содержат уникальные значения в колонке сумма или произведение, например, произведение простых чисел будет уникальным. Такие данные нам надо удалить." Почему вы удаляете уникальные произведения?
13. Валерий (scientes) 06.02.15 11:59
(12) Alien_job, ни Пол, ни Салли не знают решение. Значит известные им значения суммы и произведения не позволяют назвать числа. Поэтому варианты с уникальными значениями мы и удаляем. Скажем, если бы Полу назвали произведение 143, он разложил его на множители 11 и 13. Это разложение единственное, он сразу называет ответ.
14. Михаил Гусев (Идальго) 06.02.15 17:24
Если числа непростые, то рассмотрим давайте пару (4, 15). Так, Салли сказали сумму = 19, ну и Полу = 60. Понятно, что Пол не знает из каких двух множетелей получается сложное число 60, веть это может быть пара (2, 30) или (3, 20) или (4, 15) или (5, 12) или (6, 10). От того, знает/не знает Салли, что Пол не знает пару этих чисел - ничего не меняется. Да и сам Салли на самом деле не знает из каких слагаемых образовалась сумма = 19. Поэтому, я думаю чего-то не хватает в условии. Хотя может и ошибаюсь?
15. Сергей (ildarovich) 06.02.15 23:45
Не знаю, где я ошибся, но вот решение, которое никак не хочет второй вариант на 439 показывать. Это всего один запрос и более короткий, чем у автора. Работает в консоли.
ВЫБРАТЬ
	0 КАК Х
ПОМЕСТИТЬ Бит

ОБЪЕДИНИТЬ

ВЫБРАТЬ
	1
;

////////////////////////////////////////////////////////////­////////////////////
ВЫБРАТЬ
	Бит0.Х + 2 * (Бит1.Х + 2 * (Бит2.Х + 2 * (Бит3.Х + 2 * (Бит4.Х + 2 * (Бит5.Х + 2 * (Бит6.Х + 2 * (Бит7.Х + 2 * (Бит8.Х + 2 * Бит9.Х)))))))) КАК Х
ПОМЕСТИТЬ Ряд
ИЗ
	Бит КАК Бит9,
	Бит КАК Бит8,
	Бит КАК Бит7,
	Бит КАК Бит6,
	Бит КАК Бит5,
	Бит КАК Бит4,
	Бит КАК Бит3,
	Бит КАК Бит2,
	Бит КАК Бит1,
	Бит КАК Бит0
;

////////////////////////////////////////////////////////////­////////////////////
ВЫБРАТЬ
	Ряд1.Х КАК Х,
	Ряд2.Х КАК У,
	Ряд1.Х + Ряд2.Х КАК Сумма,
	Ряд1.Х * Ряд2.Х КАК ХУ
ПОМЕСТИТЬ Пробы
ИЗ
	Ряд КАК Ряд1,
	Ряд КАК Ряд2
ГДЕ
	Ряд1.Х < &Предел / 2
	И Ряд2.Х < &Предел - 1
	И 1 < Ряд1.Х
	И Ряд1.Х < Ряд2.Х
	И Ряд1.Х + Ряд2.Х <= &Предел
;

////////////////////////////////////////////////////////////­////////////////////
ВЫБРАТЬ РАЗЛИЧНЫЕ
	Пробы.Сумма
ПОМЕСТИТЬ ТабуСумм
ИЗ
	Пробы КАК Пробы
ГДЕ
	Пробы.ХУ В
			(ВЫБРАТЬ
				Пробы.ХУ
			ИЗ
				Пробы КАК Пробы
			СГРУППИРОВАТЬ ПО
						Пробы.ХУ
			ИМЕЮЩИЕ
				КОЛИЧЕСТВО(*) = 1)
;

////////////////////////////////////////////////////////////­////////////////////
ВЫБРАТЬ
	ЧислаСалли.ХУ
ПОМЕСТИТЬ ЧислаПоля
ИЗ
	Пробы КАК ЧислаСалли
ГДЕ
	НЕ ЧислаСалли.Сумма В
				(ВЫБРАТЬ
					ТабуСумм.Сумма
				ИЗ
					ТабуСумм)

СГРУППИРОВАТЬ ПО
	ЧислаСалли.ХУ

ИМЕЮЩИЕ
	КОЛИЧЕСТВО(РАЗЛИЧНЫЕ ЧислаСалли.Сумма) = 1
;

////////////////////////////////////////////////////////////­////////////////////
ВЫБРАТЬ
	ЧислаСалли.Сумма,
	МАКСИМУМ(ЧислаПоля.ХУ) КАК Произведение,
	МАКСИМУМ(ЧислаСалли.Х) КАК Х,
	МАКСИМУМ(ЧислаСалли.У) КАК У
ИЗ
	Пробы КАК ЧислаСалли
		ВНУТРЕННЕЕ СОЕДИНЕНИЕ ЧислаПоля КАК ЧислаПоля
		ПО ЧислаСалли.ХУ = ЧислаПоля.ХУ
ГДЕ
	НЕ ЧислаСалли.Сумма В
				(ВЫБРАТЬ
					ТабуСумм.Сумма
				ИЗ
					ТабуСумм)

СГРУППИРОВАТЬ ПО
	ЧислаСалли.Сумма

ИМЕЮЩИЕ
	КОЛИЧЕСТВО(РАЗЛИЧНЫЕ ЧислаПоля.ХУ) = 1
...Показать Скрыть
А возможно, ошибки и нет, а ошибка в исходной статье? Дело в том, что предположение про простые числа - не совсем верное. Вот, например 8 разлагается на сомножители однозначно, но не является произведением двух простых чисел.
16. Serg (Sykoku) 11.02.15 11:36
Я думал, что решали ЛОГИЧЕСКУЮ задачу про мудрецов в колпаках (http://eruditor.ru/z/?2). А тут...

Бухгалтерам надо предложить так баланс составлять: берем и заносим все составляющие в массивы и потом выбираем пересекающиеся по условиям цифры.

Решать арифметические задачи методом подбора - это еще додуматься надо...
17. Валерий (scientes) 11.02.15 11:54
(16) Sykoku, Я полагаю, что это не арифметическая задача. Ответ получается в результате выполнения запроса. В Послесловии разобрано как этот запрос работает. Все методы решения, которые я видел, в той или иной форме реализуют этот алгоритм.
Для написания сообщения необходимо авторизоваться
Прикрепить файл
Дополнительные параметры ответа