|
|
Регистрация Восстановить пароль |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
16.05.2016, 14:45 | #1 |
Спокойный псих
Участник клуба
Регистрация: 19.03.2013
Сообщений: 1,538
|
Комбинаторика, расчёт количества значений
Всем привет. Я не знаю, в какой раздел идти с этой темой, поэтому если что - прошу прощения.
Есть следующие условия: 1) длина числа от 1 до 10, где каждый разряд может быть равен от 0 до 9; 2) записи чисел с нулевыми старшими разрядами тоже учитываются; например - 000123 и 123 являются разными значениями, 0123 и 00123 тоже разные; таким образом нулевыми старшими разрядами нужно подгонять длину записей всех чисел до 10. таким образом, общее количество всех возможных вариантов записи равно 11 111 111 110; в комбинаторике я не очень силён, поэтому количество пришлось считать посредством программирования. И да - это ещё не всё. Главное дальше. Нужно посчитать количество чисел, которое соответствуют заданным условиям: 1) длина записи числа кратна двум; 2) запись числа является палиндромом; 3) в записи числа присутствуют ТОЛЬКО числа 4, 5, 6 и 7. Дальше должны быть варианты - об этом дальше. Опять же, посредством программирования я посчитал - количество равно 1 364. И опять же тупым перебором. Моя проблема в том, что тупой перебор одиннадцати миллиардов значений в 5 потоков выполняются примерно 20 минут (с загрузкой 4-ядерного процессора в 95%), а мне ещё надо перебрать все варианты по третьему пункту, и подобрать такую комбинацию, при которой количество палиндромов будет минимально. И выяснить, можно ли сократить эти 1 364 чисел. На счёт вариантов: количество исключаемых чисел, которые формируют палиндромы всегда четыре, и не повторяются. То есть варианты следующие: 1) 0, 1, 2, 3; 2) 0, 1, 2, 4; 3) 0, 1, 2, 5; 4) 0, 1, 2, 6; 5) 0, 1, 2, 7; 6) 0, 1, 2, 8; 7) 0, 1, 2, 9; 8) 0, 1, 3, 2; 9) ну и так далее ... И тут я обнаружил, что мне ещё нужно перебрать варианты перебора. Вот я и обращаюсь к вам за помощью в моём "не очень силён" - комбинаторика. Помогите пожалуйста в решении этой проблемы.
Подпись ? Не, не слышал ...
|
16.05.2016, 16:00 | #2 |
Старожил
Регистрация: 20.04.2008
Сообщений: 5,528
|
P(n) количество чисел в записи которого РОВНО n знаков из полного набора 0..9 = 10**n
PS(n) количество чисел в записи которого РОВНО n знаков из сокращенного набора 4..7 =4**n PP(n) количество чисел в записи которого РОВНО n знаков И число является палиндромом число является палиндромом ЭТО первая БОЛЬШАЯ половина произвольна, остальное однозначно определено по этой половине. БОЛЬШАЯ половина =половине для ЧЕТНЫХ длин (n =2k) n div 2 =k = половине ВКЛЮЧАЮЩЕЙ средний(центральный) элемент для НЕЧЕТНЫХ длин (n=2k+1) (n div 2) + 1 =k+1 PP(2k) =P(k) =10**k // n=2k PP(2k+1) =P(k+1) =10**(k+1) // n=2k+1 А ОДНОзначные числа являются палиндромами?! 0) Код:
Код:
Код:
Код:
программа — запись алгоритма на языке понятном транслятору
Последний раз редактировалось evg_m; 16.05.2016 в 16:11. |
16.05.2016, 16:11 | #3 |
Спокойный псих
Участник клуба
Регистрация: 19.03.2013
Сообщений: 1,538
|
По поводу вариантов (исключаемые числа, формирующие палиндромы) добавилось условие: порядок имеет значение, то есть 0, 1, 2, 3 и 0, 1, 3, 2 - это одно и тоже.
К тому же своим любимым методом тупого перебора я посчитал, что всего у меня 210 таких наборов. Если всё правильно закодить, то при номинальной нагрузке ЦП на расчёт всех вариантов (тупым перебором) уйдёт примерно полтора часа процессорного времени. И тут пришла беда, откуда не ждали ... Я не горю желанием так долго грузить процессор своим быдлокодом. Поэтому встаёт вопрос, как увеличить время выполнения тупого перебора, что бы нагрузка была в пределах 20% ... Как раз, примерно на 8 часов перебора - можно и поспать. evg_m Все числа с нечётной длинной записи отсеиваются изначально.
Подпись ? Не, не слышал ...
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Расчёт количества файлов в папке без учёта скрытых файлов | dfc | Microsoft Office Excel | 2 | 11.10.2013 12:06 |
Определение количества максимальных значений. | denicko | Помощь студентам | 0 | 26.10.2010 17:19 |
Подсчет количества значений на листе | edikamn | Microsoft Office Excel | 5 | 28.09.2010 09:13 |
подсчёт количества пар определённых значений в ячейках | kudich | Microsoft Office Excel | 4 | 08.03.2010 16:14 |
Подсчет количества числовых значений | Amelie_L | Microsoft Office Excel | 2 | 28.01.2010 08:26 |