На одном сайте обнаружил следующую задачу. С помощью всех цифр от 0 до 9 записать равенство X+Y=Z, цифры не должны повторяться, число не может начинаться на 0. Найти все решения. Автор пишет, что эту задачу можно решить с помощью brute force в несколько строчек кода. Он предлагает найти все решения с помощью карандаша и бумаги. Моя программа содержит почти 70 строк. Кто-нибудь знает более короткий способ ?
Ответы
Подписаться на ответы
Инфостарт бот
Сортировка:
Древо развёрнутое
Свернуть все
(1) В первом приближении:
Если верхней границы значения суммы нет, то будет бесконечный цикл
МассивРешений = Новый Массив;
Для X = 1 По 9 Цикл
Для Y = X + 1 Цикл
Если X + Y > 9 Тогда
Прервать;
КонецЕсли;
МассивРешений.Добавить(Формат(X) + " + " + Формат(Y) + " = " + Формат(X+Y));
КонецЦикла;
КонецЦикла; ПоказатьЕсли верхней границы значения суммы нет, то будет бесконечный цикл
(1) 1991 вариант (во вложении).
Код написан "на коленке". мРез - массив строк с вариантами.
Код написан "на коленке". мРез - массив строк с вариантами.
мРез = Новый Массив;
мЦифры = Новый Массив;
мЦифры.Добавить("1");
мЦифры.Добавить("2");
мЦифры.Добавить("3");
мЦифры.Добавить("4");
мЦифры.Добавить("5");
мЦифры.Добавить("6");
мЦифры.Добавить("7");
мЦифры.Добавить("8");
мЦифры.Добавить("9");
мЦифры.Добавить("0");
Для А = 1 По 5000 Цикл
стрА = Формат(А, "ЧГ=0");
Флаг = Истина;
Для н = 0 По 9 Цикл
Если СтрНайти(стрА, мЦифры[н], , 1, 2) > 0 Тогда
Флаг = Ложь;
Прервать;
КонецЕсли;
КонецЦикла;
Если Флаг Тогда
Флаг2= Ложь;
Для Б = А + 1 По 9999 Цикл
стрАБ = стрА + "+" + Формат(Б, "ЧГ=0");
Флаг = Истина;
Для н = 0 По 9 Цикл
Если СтрНайти(стрАБ, мЦифры[н], , 1, 2) > 0 Тогда
Флаг = Ложь;
Прервать;
КонецЕсли;
КонецЦикла;
Если Флаг Тогда
В = А + Б;
стрВ = стрАБ + "=" + Формат(В, "ЧГ=0");
Если СтрДлина(стрВ) > 12 Тогда
Флаг2 = Истина;
Прервать;
КонецЕсли;
Флаг = Истина;
Для н = 0 По 9 Цикл
Если СтрНайти(стрВ, мЦифры[н], , 1, 2) > 0 Тогда
Флаг = Ложь;
Прервать;
КонецЕсли;
КонецЦикла;
Если Флаг Тогда
мРез.Добавить(стрВ);
КонецЕсли;
КонецЕсли;
КонецЦикла;
Если Флаг2 Тогда
Продолжить;
КонецЕсли;
КонецЕсли;
КонецЦикла;
ПоказатьПрикрепленные файлы:
Решение.txt
(21)
Записывается в одну строку: мЦифры = СтрРазделить("0/1/2/3/4/5/6/7/8/9", "/");
Где-то подсмотрел, может пригодится...
мЦифры = Новый Массив;
мЦифры.Добавить("1");
мЦифры.Добавить("2");
мЦифры.Добавить("3");
мЦифры.Добавить("4");
мЦифры.Добавить("5");
мЦифры.Добавить("6");
мЦифры.Добавить("7");
мЦифры.Добавить("8");
мЦифры.Добавить("9");
мЦифры.Добавить("0");
мЦифры.Добавить("1");
мЦифры.Добавить("2");
мЦифры.Добавить("3");
мЦифры.Добавить("4");
мЦифры.Добавить("5");
мЦифры.Добавить("6");
мЦифры.Добавить("7");
мЦифры.Добавить("8");
мЦифры.Добавить("9");
мЦифры.Добавить("0");
Записывается в одну строку: мЦифры = СтрРазделить("0/1/2/3/4/5/6/7/8/9", "/");
Где-то подсмотрел, может пригодится...
(36) А-а-а... Ну тогда так:
Функция Задачка()
мРез = Новый Массив;
Для А = 1 По 5000 Цикл
стрА = Формат(А,"ЧГ=0");
Если НЕ ЕстьПовторыЦифр(стрА) Тогда
Для Б = А + 1 По 9999 Цикл
стрАБ = стрА + Формат(Б,"ЧГ=0");
Если НЕ ЕстьПовторыЦифр(стрАБ) Тогда
В = А + Б;
стрВ = стрАБ + Формат(В,"ЧГ=0");
Если СтрДлина(стрВ) > 10 Тогда
Прервать;
ИначеЕсли СтрДлина(стрВ) = 10 Тогда
Если НЕ ЕстьПовторыЦифр(стрВ) Тогда
мРез.Добавить(Формат(А,"ЧГ=0")+"+"+Формат(Б,"ЧГ=0")+"="+Формат(В,"ЧГ=0"));
КонецЕсли;
КонецЕсли;
КонецЕсли;
КонецЦикла;
КонецЕсли;
КонецЦикла;
Возврат мРез;
КонецФункции
Функция ЕстьПовторыЦифр(стр)
Результат = Ложь;
Для н = 1 По СтрДлина(стр)-1 Цикл
Если СтрНайти(стр, Сред(стр,н,1), , 1, 2) > 0 Тогда
Результат = Истина;
Прервать;
КонецЕсли;
КонецЦикла;
Возврат Результат;
КонецФункции
Показать
(1) еще вариант кода:
мРез = Новый Массив;
Для А = 1 По 5000 Цикл
стрА = Формат(А, "ЧГ=0");
Флаг = Истина;
Для н = 1 По СтрДлина(стрА)-1 Цикл
Если СтрНайти(стрА, Сред(СтрА,н,1), , 1, 2) > 0 Тогда
Флаг = Ложь;
Прервать;
КонецЕсли;
КонецЦикла;
Если Флаг Тогда
Флаг2= Ложь;
Для Б = А + 1 По 9999 Цикл
стрАБ = стрА + "+" + Формат(Б, "ЧГ=0");
Флаг = Истина;
Для н = 1 По СтрДлина(стрАБ)-1 Цикл
Если СтрНайти(стрАБ, Сред(СтрАБ,н,1), , 1, 2) > 0 Тогда
Флаг = Ложь;
Прервать;
КонецЕсли;
КонецЦикла;
Если Флаг Тогда
В = А + Б;
стрВ = стрАБ + "=" + Формат(В, "ЧГ=0");
Если СтрДлина(стрВ) > 12 Тогда
Флаг2 = Истина;
Прервать;
КонецЕсли;
Для н = 1 По СтрДлина(стрВ)-1 Цикл
Если СтрНайти(стрВ, Сред(СтрВ,н,1), , 1, 2) > 0 Тогда
Флаг = Ложь;
Прервать;
КонецЕсли;
КонецЦикла;
Если Флаг Тогда
мРез.Добавить(стрВ);
КонецЕсли;
КонецЕсли;
КонецЦикла;
Если Флаг2 Тогда
Продолжить;
КонецЕсли;
КонецЕсли;
КонецЦикла;
Показать
(25)
Про ВСЕ я как-то упустил. Поправил код. 84 варианта.
Спасибо за задачку ;)
используя один раз ВСЕ цифры из диапазона 0...9
Про ВСЕ я как-то упустил. Поправил код. 84 варианта.
Спасибо за задачку ;)
мРез = Новый Массив;
Для А = 1 По 5000 Цикл
стрА = Формат(А, "ЧГ=0");
Флаг = Истина;
Для н = 1 По СтрДлина(стрА)-1 Цикл
Если СтрНайти(стрА, Сред(СтрА,н,1), , 1, 2) > 0 Тогда
Флаг = Ложь;
Прервать;
КонецЕсли;
КонецЦикла;
Если Флаг Тогда
Для Б = А + 1 По 9999 Цикл
стрАБ = стрА + "+" + Формат(Б, "ЧГ=0");
Флаг = Истина;
Для н = 1 По СтрДлина(стрАБ)-1 Цикл
Если СтрНайти(стрАБ, Сред(СтрАБ,н,1), , 1, 2) > 0 Тогда
Флаг = Ложь;
Прервать;
КонецЕсли;
КонецЦикла;
Если Флаг Тогда
В = А + Б;
стрВ = стрАБ + "=" + Формат(В, "ЧГ=0");
Если СтрДлина(стрВ) > 12 Тогда
Прервать;
КонецЕсли;
Если СтрДлина(стрВ) = 12 Тогда
Для н = 1 По СтрДлина(стрВ)-1 Цикл
Если СтрНайти(стрВ, Сред(СтрВ,н,1), , 1, 2) > 0 Тогда
Флаг = Ложь;
Прервать;
КонецЕсли;
КонецЦикла;
Если Флаг Тогда
мРез.Добавить(стрВ);
КонецЕсли;
КонецЕсли;
КонецЕсли;
КонецЦикла;
КонецЕсли;
КонецЦикла;
Показать
(32)
Функция ПроверкаPuzzle(чЛев,чПрав)
сумма=чЛев+чПрав;
если сумма%9<>0 тогда
возврат ложь;
конецесли;
сумма=Формат(сумма,"ЧГ=0");
слагаемые=Формат(чЛев,"ЧГ=0")+Формат(чПрав,"ЧГ=0"); ;
сДлина=СтрДлина(сумма);
если сДлина+СтрДлина(слагаемые) <> 10 тогда
возврат ложь;
конецесли;
для поз=1 по сДлина цикл
ц=Сред(сумма,поз,1);
если СтрНайти(слагаемые,ц)>0 тогда
возврат ложь;
конецесли;
слагаемые=слагаемые+ц;
конеццикла;
возврат истина;
КонецФункции
Функция РекурсияЦифр(вхМассив,дЛев,дПрав,дОбщ,чЛев,чПрав,текПозиция)
если текПозиция>дОбщ тогда
если дЛев=дПрав тогда
если чЛев>чПрав тогда
возврат 0;
конецесли;
конецесли;
если ПроверкаPuzzle(чЛев,чПрав) тогда
сумма=чЛев+чПрав ;
сообщить(""+чЛев+"+"+чПрав+"="+сумма);
возврат 1;
конецесли;
возврат 0;
конецесли;
если текПозиция = дЛев+1 или текПозиция = 1 тогда
imin=1;
иначе
imin=0;
конецесли;
счетчик=0;
для i=imin по 9 цикл
если вхМассив[i]=0 тогда
если текПозиция <=дЛев тогда
нЛев=чЛев*10+i ;
нПрав=чПрав ;
иначе
нЛев=чЛев ;
нПрав=чПрав*10+i;
конецесли;
вхМассив[i]=1;
счетчик=счетчик+РекурсияЦифр(вхМассив,дЛев,дПрав,дОбщ,нЛев,нПрав,текПозиция+1);
вхМассив[i]=0
конецесли;
конеццикла;
возврат счетчик;
КонецФункции
Функция ЗадачаНаСуммуЦифр() экспорт
вхМассив=новый Массив(10);
для i=0 по 9 цикл
вхМассив[i]=0;
конеццикла;
сообщить("3 3->"+РекурсияЦифр(вхМассив,3,3,6,0,0,1));
сообщить("4 2->"+РекурсияЦифр(вхМассив,4,2,6,0,0,1));
КонецФункции
Показать
(31)
Просто надо подумать сначала.
т.к. числа не могут начинаться с нуля, то число Z не может быть короче, чем X или Y. Соответственно Z уже не может быть короче 4х цифр, т.к. если Z будет из 3х цифр, то или X или Y будет состоять как минимум из 4х цифр. Но и 5 цифр в Z быть не может, т.к. минимальное пятизначное число по условиям задачи это 10234. которую из оставшихся 56789 в сумме получить не получится. Т.е. на X и Y остается 6 цифр. Варианты 5+1 не подходят. Для X и Y остается 2+4 и 3+3.
Это читерство как бы, диапазоны изначально неизвестны.
Просто надо подумать сначала.
т.к. числа не могут начинаться с нуля, то число Z не может быть короче, чем X или Y. Соответственно Z уже не может быть короче 4х цифр, т.к. если Z будет из 3х цифр, то или X или Y будет состоять как минимум из 4х цифр. Но и 5 цифр в Z быть не может, т.к. минимальное пятизначное число по условиям задачи это 10234. которую из оставшихся 56789 в сумме получить не получится. Т.е. на X и Y остается 6 цифр. Варианты 5+1 не подходят. Для X и Y остается 2+4 и 3+3.
(46) Я к тому, что в предложенных решениях стирается грань между предварительной аналитикой и предварительными расчетами.
Искать варианты надо среди пар вида [xxx] + [xxx] и [xx]+[xxxx]
это предварительная оптимизация или пропущенная часть алгоритма? Я вижу в этом некий парадокс. Придумайте алгоритм нахождения синуса 90 градусов. В своих поисках предварительной оптимизации можно придти к тому, что он всегда равен 1. Назвав это умозрительной оптимизацией, ответ захардкодим.
(47)в случае с нахождением значения синуса угла 90 градусов все предельно ясно и значение должно получится таким же при применении любого из методов вычисления, другими словами из общего подхода получается частный, а вот в случае нахождения слагаемых и суммы по определенным правилам - не факт, что можно придумать некую общую закономерность нахождения всех возможных значений, кроме тупого перебора, а выполнив перебор - получаем всего лишь частное решение задачи.
Для шестнадцатиричной системы счисления значения будут заметно другими :)
Для шестнадцатиричной системы счисления значения будут заметно другими :)
(28) Это понятно. Можно сделать две пары циклов, об оптимизации пока не задумывался. Основным было для меня в решении определение условия что комбинация чисел подходит.
Вот запустил с условиями
Для X = 1 По 9999 Цикл
Для Y = X По 9999 Цикл
Время обработки: 11 минут 22 секунд.
Мое решение такое:
Вот запустил с условиями
Для X = 1 По 9999 Цикл
Для Y = X По 9999 Цикл
Время обработки: 11 минут 22 секунд.
Мое решение такое:
Процедура КнопкаВыполнитьНажатие(Кнопка)
ТЗ = Новый ТаблицаЗначений;
ТЗ.Колонки.Добавить("ЧислоX");
ТЗ.Колонки.Добавить("ЧислоY");
ТЗ.Колонки.Добавить("ЧислоZ");
ТЗЦифр = Новый ТаблицаЗначений;
ТЗЦифр.Колонки.Добавить("ЦифраСтрокой");
Для X = 1 По 9999 Цикл
Для Y = X По 9999 Цикл
Z = X + Y;
СтрокаX = СтрЗаменить(Строка(X),Символы.НПП, "");
СтрокаY = СтрЗаменить(Строка(Y),Символы.НПП, "");
СтрокаZ = СтрЗаменить(Строка(Z),Символы.НПП, "");
Если Не (СтрДлина(СтрокаX) + СтрДлина(СтрокаY) + СтрДлина(СтрокаZ)) = 10 Тогда
Продолжить;
КонецЕсли;
ТЗЦифр.Очистить();
ТЗЦифр.Колонки.Добавить("Цифра");
Если ПроверитьНаСоответствиеУсловию(СтрокаX,СтрокаY,СтрокаZ, ТЗЦифр) Тогда
НоваяСтрока = ТЗ.Добавить();
НоваяСтрока.ЧислоX = X;
НоваяСтрока.ЧислоY = Y;
НоваяСтрока.ЧислоZ = Z;
КонецЕсли;
КонецЦикла;
КонецЦикла;
Сообщить("Количество решений = " + ТЗ.Количество());
Для каждого СтрокаТЗ Из ТЗ Цикл
Сообщить(СтрШаблон("%1 + %2 = %3", СтрокаТЗ.ЧислоX, СтрокаТЗ.ЧислоY, СтрокаТЗ.ЧислоZ));
КонецЦикла;
КонецПроцедуры
Функция ПроверитьНаСоответствиеУсловию(X,Y,Z,ТЗЦифр)
РазложитьЧислоНаЦифры(X, ТЗЦифр);
РазложитьЧислоНаЦифры(Y, ТЗЦифр);
РазложитьЧислоНаЦифры(Z, ТЗЦифр);
ИтоговаяСуммаЦифр = ТЗЦифр.Итог("Цифра");
ТЗЦифр.Свернуть("ЦифраСтрокой");
Если ИтоговаяСуммаЦифр = 45 И ТЗЦифр.Количество() = 10 Тогда
Возврат Истина;
Иначе
Возврат Ложь;
КонецЕсли;
КонецФункции // ПроверитьНаСоответствиеУсловию()()
Процедура РазложитьЧислоНаЦифры(ЧислоСтрокой, ТЗЦифр)
Для НомерСимвола = 1 По СтрДлина(ЧислоСтрокой) Цикл
НоваяСтрока = ТЗЦифр.Добавить();
НоваяСтрока.ЦифраСтрокой = Сред(ЧислоСтрокой, НомерСимвола, 1);
НоваяСтрока.Цифра = Число(НоваяСтрока.ЦифраСтрокой);
КонецЦикла;
КонецПроцедуры
Показать
Вариант быстрого перебора для суммы 3-х значных чисел. Ищет нужные комбинации за 0.84 сек.
Функция ПроверкаПеребора(X,Y,Z,словарь)
выражение=Формат(X,"ЧГ=0")+Формат(Y,"ЧГ=0")++Формат(Z,"ЧГ=0");
для каждого i из словарь цикл
если СтрНайти(выражение,i)=0 тогда
возврат ложь;
конецесли;
конеццикла;
возврат истина;
конецФункции
Функция Перебор() экспорт
словарь=новый массив;
словарь=СтрРазделить("0,1,2,3,4,5,6,7,8,9",",");
//----------------------------------------------------------
// Для случая [xxx] [xxx]
// Z=1xxx содержит 0 и делится на 9
// отсюда получаем интервал
// 1026 ....1620
счетчик=0;
для Z=1026 по 1620 цикл
если СтрНайти(строка(z),"0") тогда
//------------------------------------------------------------------------------------
//интервал для X определяется тем, что X
// трехзначное,состоит из разных цифр и не содержит 0 и 1
для X=234 по 987 цикл
Y=Z-X;
если Y<X тогда
прервать;
конецесли;
//проверка, что все цифры разные
если ПроверкаПеребора(X,Y,Z,словарь)=истина тогда
счетчик=счетчик+1;
сообщить(""+X+"+"+Y+"="+Z);
конецесли;
конеццикла;
конецесли;
Z=Z+8; // Z делится на 9
конеццикла;
возврат счетчик;
КонецФункции
Показать
Перебор для случая X=[xxxx] Y=[xx]
Суммарное время на всю задачу 0.5 сек.
Тему, думаю, можно закрывать.
Суммарное время на всю задачу 0.5 сек.
Тему, думаю, можно закрывать.
//----------------------------
// Для случая X=[xxxx] Y=[xx]
//
// Z=имеет вид X0XX и делится на 9
// отсюда получаем интервал
// 2018 ....6021
счетчик=0;
для Z=2016 по 6021 цикл
если ((z-z%100)/100)%10=0 тогда
//---------------------------------------------------------
//интервал для X определяется тем, что X
// 2-значное,состоит из разных цифр и не содержит 0
для Y=12 по 98 цикл
X=Z-Y;
//проверка что все цифры разные
если ПроверкаПеребора(X,Y,Z,словарь)=истина тогда
счетчик=счетчик+1;
сообщить(""+X+"+"+Y+"="+Z);
конецесли;
конеццикла;
конецесли;
Z=Z+8; // Z делится на 9
конеццикла;
Показать
Для получения уведомлений об ответах подключите телеграм бот:
Инфостарт бот