Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > IT форум > Помощь студентам
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 16.05.2016, 14:45   #1
OmegaBerkut
Спокойный псих
Участник клуба
 
Аватар для OmegaBerkut
 
Регистрация: 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) ну и так далее ... И тут я обнаружил, что мне ещё нужно перебрать варианты перебора.
Вот я и обращаюсь к вам за помощью в моём "не очень силён" - комбинаторика. Помогите пожалуйста в решении этой проблемы.
Подпись ? Не, не слышал ...
OmegaBerkut вне форума Ответить с цитированием
Старый 16.05.2016, 16:00   #2
evg_m
Старожил
 
Регистрация: 20.04.2008
Сообщений: 5,515
По умолчанию

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)
Код:
   P(1)  //    однозначные =10**1 =00000000010
 + P(2)  //    двузначные  =10**2 =00000000100
 + ... 
 + P(10) // десятизначные =10**10 =10000000000
                         итого    =11111111110
1)
Код:
P(2) + P(4) + P(6) + ... + P(10) // суммируем только четные длины
                                         =1010101010
3)
Код:
PS(1) + PS(2) + ... + PS(10) = 4**1 + ... 4**10
2)
Код:
   PP(1) + PP(2) + ... + PP(9) + PP(10) =
   P(1)   +P(1)   + ...  +P(5) + P(5) =  
 2*(P(1) + ... + P(5)) = 2*(10 + ... +100000 ) = 2*111110 =2222220
программа — запись алгоритма на языке понятном транслятору

Последний раз редактировалось evg_m; 16.05.2016 в 16:11.
evg_m вне форума Ответить с цитированием
Старый 16.05.2016, 16:11   #3
OmegaBerkut
Спокойный псих
Участник клуба
 
Аватар для OmegaBerkut
 
Регистрация: 19.03.2013
Сообщений: 1,538
По умолчанию

По поводу вариантов (исключаемые числа, формирующие палиндромы) добавилось условие: порядок имеет значение, то есть 0, 1, 2, 3 и 0, 1, 3, 2 - это одно и тоже.
К тому же своим любимым методом тупого перебора я посчитал, что всего у меня 210 таких наборов.
Если всё правильно закодить, то при номинальной нагрузке ЦП на расчёт всех вариантов (тупым перебором) уйдёт примерно полтора часа процессорного времени.
И тут пришла беда, откуда не ждали ... Я не горю желанием так долго грузить процессор своим быдлокодом. Поэтому встаёт вопрос, как увеличить время выполнения тупого перебора, что бы нагрузка была в пределах 20% ... Как раз, примерно на 8 часов перебора - можно и поспать.

evg_m
Все числа с нечётной длинной записи отсеиваются изначально.
Подпись ? Не, не слышал ...
OmegaBerkut вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Расчёт количества файлов в папке без учёта скрытых файлов 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