Мультиинструментальный Brute Force
Разработка - Математика и алгоритмы
В одной из задач на Project Euler (здесь ссылка на русскую версию) предлагается найти простые 10-значные числа с повторениями. Под повторением понимаются не просто идущие подряд цифры, а все одинаковые цифры, которые встречаются в записи числа. Интересуют простые числа с максимальным количеством повторений. Для цифры 4 существует единственное простое число - 4444444447, в котором четверка повторяется 9 раз. Другим примером чисел, которые удовлетворяют условиям задачи, являются 7778777777 и 17777777777. Максимальное количество повторений семерки в 10-значном простом числе равно 9.
Оценим сложность задач. Для начала определим размер области поиска, а именно, сколько существует простых чисел в диапазоне 10^9...10^10. Для этого заглянем на сайт http://www.wolframalpha.com/ и в поле ввода наберем выражение primepi(10^10)-primepi(10^9). Функция primepi(x) возвращает количество простых чисел, не превосходящих х.
И так наши иголки мы будем искать в стоге из более чем 404 млн. простых чисел. Следующий вопрос - как эти числа получить?
Оказывается, есть люди, которым интересно разрабатывать программы для генерации простых чисел, более того они выкладывают свои разработки в открытом доступе. Достижения автора поражают, его код работает черезвычайно быстро. Мы воспользуемся 64-х разрядным консольным приложением. Начнем с проверки количества простых чисел в интервале поиска. Ответ совпадает с полученным ранее, чего и следовало ожидать.
Это замечательное консольное приложение может находить простые числа в заданном диапазоне и сохранять их во внешний файл. На приведенном изображении мы ищем простые числа в интервале 4444444447,...4444444447+1 и выводим результат сначала на экран, затем в файл.
Если сохранить список чисел из диапазона поиска в одном файле, то он будет занимать на диске 4,51 Гб. При таких размерах приложение Блокнот отказывается файл открывать. А ведь нам надо в дальнейшем обработать полученные числа. Поэтому будем выводить данные порциями с шагом 10^8, начиная с 10*10^8. Результаты сохраним не в текстовый файл, а в базу данных на SQL сервере. На первом шаге создадим в базе данных 90 таблиц c именами PrimeNumber10,PrimeNumber11,...,PrimeNumber99, которые содержат единственный столбец [output] с типом (nvarchar(10),NULL). Таблицы сформируем с помощью простого кода в 1С.
for Num=10 to 99 do
Text="CREATE TABLE [dbo].[PrimeNumber"+num+"]([output] [nvarchar](10) NULL) ON [PRIMARY]";
adoConnect.Execute(Text);
enddo
Здесь adoConnect - это com-объект (COMОбъект("ADODB.Connection")).
На следующем шаге занесем набор простых чисел в наши таблицы. Сделать это можно спомощью такой команды:
Text="DECLARE @start sysname, @step sysname,@cmd sysname;
|
|SET @start='[Num]e8';
|SET @step='-o1e8';
|
|SET @cmd='...\primesieve.exe '+@start+' +@step+' -p'
|
|delete from PrimeNumber[Num]
|
|Insert PrimeNumber[Num] (output)
|EXEC xp_cmdshell @cmd;";
[Num] - это параметр с номером таблицы. Команда выполняется на сервере, поэтому и консольное приложение для генерации простых чисел следует разместить там же. Кроме этого, в настройках сервера необходимо разрешить выполнение команды xp_cmdshell. Запускать вручную данный скрипт мы не будем, а призовем на помощь фоновые задания. Создадим общий модуль ФоновыеЗапросы и пропишем в нем следующую функцию:
Function BackGroundQuery(Text) Export
adoConnect = new COMОбъект("ADODB.Connection");
ConnectString="Driver={SQL Server};Server=...;Database=...;Trusted_Connection=yes";
adoConnect.ConnectionTimeout = 1000;
adoConnect.CommandTimeout = 1000;
adoConnect.Open(ConnectString);
adoConnect.Execute(Text);
adoConnect.Close();
EndFunction
Функция черезвычайно проста, единственное что она делает - отправляет на сервер команду, которую надо выполнить. А теперь оформим ее вызов.
for i=10+iStart to 99 do
query=СтрЗаменить(Text,"[Num]",i);
param=new array;
param.Add(query);
UID=new УникальныйИдентификатор;
mKey=строка(UID);
BgTask=ФоновыеЗадания.Execute(
"ФоновыеЗапросы.BackGroundQuery",
param,mKey,
"Fill prime table i="+i);
i=i+9;
enddo;
Какой бы ни был мощный сервер, и его можно "подвесить". По этой причине я заполнял таблицы порциями по 9 штук, что и отражено в приведенном фрагменте.
Теперь, когда у нас есть исходные данные, можно приступить к извлечению нужных чисел. Для этого воспользуемся поиском по маске через оператор LIKE. Для цифры 0 маска будет единственная: '_00000000_'. При этом искать числа надо только в таблицах с номерами 10,20,30... Всего таких чисел 8. Они приведены ниже.
1000000007 |
1000000009 |
4000000007 |
4000000009 |
6000000001 |
6000000007 |
7000000001 |
9000000001 |
Как показали дальнейшие исследования, максимальное количество повторяющихся цифр равно либо 9, либо 8. В первом случае надо использоваь маски вида:
'_NNNNNNNNN'
'N_NNNNNNNN'
'NN_NNNNNNN'
..........................................................
'NNNNNNNNN_'
Здесь N - цифра в интервале 1..9. Причем для четных цифр остается одна единственная маска - 'NNNNNNNNN_'.
Во втором случае количество возможных масок - 45. Данные маски потребовалось применять для цифр 2 и 8. Тот факт, что эти цифры четные, позволило уменьшить количество перебираемых вариантов. В таблице приведена статистика для всех цифр. Первый столбец содержит повторяющуюся цифру, второй- максимальное количество повторений, третий - количество простых 10-значных чисел c повторением указанной цифры.
Цифра | Кол-во повторений | Количество простых чисел |
0 | 8 | 8 |
1 | 9 | 12 |
2 | 8 | 39 |
3 | 9 | 7 |
4 | 9 | 1 |
5 | 9 | 1 |
6 | 9 | 1 |
7 | 9 | 9 |
8 | 9 | 32 |
9 | 9 | 8 |
Полученное в результате изложенного мультиинструментального BRUTE FORCE метода значение суммы простых чисел с заданным свойством оказалось правильным и позволило автору увеличить счет решенных задач.
Разумеется, данный метод не является оптимальным. Учитывая то, что консольное приложение позволяет проверить число на простоту, эффективнее было бы генерировать числа-кандидаты и отбирать из них те, которые являются простыми. Тем не менее, приведенный подход позволяет расширить свой арсенал и сделать будущую работу более продуктивной.
Просматривая задачи из проекта Эйлер, я обнаружил еще одну проблему, которая успешно решается с помощью изложенного метода. Основная ударная сила - программа генерации простых чисел в нужном диапазоне. Получив список чисел из интервала, определяемого номером строки треугольника,мы можем построить матрицу для поиска простых троек. Приведу некоторые контрольные значения, которые я получил.
Номер строки треугольника | Сумма искомых чисел |
20 000 | 17 399 896 193 |
50 000 | 232 499 865 696 |
100 000 | 549 999 566 882 |
200 000 | 8 980 000 676 761 |
500 000 | 98 375 000 264 623 |
1 000 000 | 463 999 977 061 648 |
Специальные предложения
См. также
Регистры бухгалтерии. Общая информация 111
05.09.2019 6701 YPermitin 22
"Хочу универсально!" [Часть 1] 65
02.09.2019 4901 SeiOkami 35
Иерархия без "В ИЕРАРХИИ" 117
22.08.2019 4913 ildarovich 16
EnterpriseData – часть 3. Загрузка данных, идентификация объектов 62
22.08.2019 4231 ids79 7
Обработчики событий при записи объектов. Зачем и что за чем? 202
25.07.2019 12802 4 AlbinaAAA 23
Как проводятся документы в типовых конфигурациях от 1С 137
24.07.2019 16075 skv_79 32
FizzBuzz на 1С. Чем короче, тем веселее. Варианты принимаются... 8
24.07.2019 2864 vandalsvq 16
Управление качеством кода 136
22.07.2019 8233 Stepa86 29
Что делает "В ИЕРАРХИИ" в запросе? 94
16.07.2019 8182 YPermitin 34
Создание отчетов с помощью СКД - основные понятия и элементы 208
25.06.2019 20982 ids79 17
Реализуем Стек, Очередь и Приоритетную очередь в 1С 52
24.06.2019 7804 RonX01 63
Организация хранения промежуточных данных 3
29.05.2019 1954 scientes 1
Вычисление 200 тысяч знаков числа pi 73
28.05.2019 3983 Oleg_nsk 93
Регистры накопления. Виртуальные таблицы. Часть №1: Обороты 84
20.05.2019 11071 YPermitin 5
Даем названия переменным: как префиксы экономят наше время 10
06.05.2019 3213 Designer1C 69
Заметки по SQL: Срез последних - аналог запроса 15
15.01.2019 6318 IVC_goal 5
Разработка и сценарное тестирование с Vanessa-ADD. Концепция, теория и сквозной пример создания сценария 222
09.01.2019 27568 Vladimir Litvinenko 69
Многопоточное восстановление последовательностей 41
05.12.2018 7250 _ASZ_ 29
Автоматические и управляемые блокировки применительно к типовым конфигурациям 1С 127
10.11.2018 22248 ids79 40
Основные понятия и механизмы оптимизации клиент-серверного взаимодействия в 1C 147
23.08.2018 22869 Rain88 42
Теорема номер тринадцать 15
15.03.2018 9358 vasilev2015 24
Введение в CI для 1С 87
21.11.2017 19331 real_MaxA 22
Как работает серверный вызов в 1С 459
18.11.2017 44246 pahich 77
#Область ВНЕШНИЕ_ВЫЗОВЫ или MVC в 1С, библиотечность и упрощение интеграции кода 43
12.10.2017 14810 for_sale 58
Групповая разработка конфигураций в крупном холдинге 68
15.08.2017 17545 stas_ganiev 15
Автоматизация процесса 1С-разработки 91
07.06.2017 23029 ekaruk 9
Пишем игру Минер. Обработка событий ActiveX в 1С 29
29.05.2017 12732 user621724_Dimav1979 11
Как я доступ на kb.1c.ru получал 91
01.05.2017 22536 ikekoval 33
Улучшение стандарта "Структура модуля" 6
26.03.2017 12325 o.nikolaev 23
"Распределение в запросе" или "избавляемся от перебора" 185
16.12.2016 28631 alexandersh 48
Планы обмена. Квитировать или гарантировать? 24
12.12.2016 14558 zhichkin 9
Некоторые принципы оптимизации запросов 1С (+SQL) 115
17.11.2016 8898 ture 40
Использование git для доработки типовых конфигураций 1С 230
11.10.2016 188459 pumbaE 31
Оптимизация запросов 1С:Предприятие – от теории к практике 116
07.10.2016 32080 bpc222 20
Регистры сведений 1С. Как это устроено. 729
05.08.2016 151050 Sergey.Noskov 155
Переводим расширения на 8.3.8. Памятка. 79
29.07.2016 39711 mrXoxot 12
Подобие Объектно-ориентированного программирования в 1С (ПООПс) 12
24.07.2016 10916 adam26 54
Опыт практического применения методики BDD на 1С. Написание сценариев 121
03.07.2016 20335 oleynik.dv 132
Заметки про запросы. Последовательность. 110
27.05.2016 29631 vasilev2015 31
Оптимизация планирования доставки грузов. Алгоритм кластеризации k-means (метод K-средних). 26
10 стартмани
09.02.2016 26528 mi1man 4
Контур.EDI изнутри, или история командной разработки тиражного продукта на 1С 174
17.11.2015 36045 skif47 88
Порядок записи движений регистров при проведении документа 95
13.11.2015 80528 triton_tver 8
Три способа получить дерево элементов иерархического справочника 52
11.11.2015 63125 32ops 9
Распределение суммы по базе 48
08.11.2015 27732 starik-2005 19
1С с "плюсами" 74
14.10.2015 19970 IntelInside 47
Знакомство с технологией Automation-сервер на примерах 33
28.09.2015 26193 niko11s 10
Критерии отбора 83
24.09.2015 49480 niko11s 13
По ссылке или по значению? Ключевое слово Знач и с чем его едят 196
12.08.2015 37186 Evil Beaver 239
Приемы обработки больших данных в 1С 258
07.08.2015 60324 tormozit 27