|
Здравствуйте. Дан отрезок чисел от a до b. Допустим, от 233 до 1566. Найти кол-во чисел на этом отрезке, которые не делятся ни на 2, ни на 3, ни на 7, ни на 9, ни на 12. задан 14 Янв '14 15:24 
ivan145 |
|
В таких случаях применяется формула включений и исключений. Можно ввести обозначения для множеств чисел (из указанного отрезка), делящихся на 2, делящихся на 3, на 7 и так далее. Число элементов каждого такого множества легко подсчитывается. Далее надо посмотреть на попарные пересечения. Для чисел 2 и 3 получится множество чисел, кратных 6. Сколько их имеется в отрезке, также легко выясняется. Таким же образом исследуются тройные пересечения, и так далее. Везде надо брать наименьшее общее кратное в том смысле, что пересечением множеств, относящихся к числам 4 и 6, будет множество чисел, кратных 12. После применения формулы (она есть в книжках по комбинаторике) получается подсчёт тех чисел, которые на что-то из указанного делятся, а нам нужно то, что осталось. Поэтому в конце надо взять общее количество (равное 1566-232) и вычесть из него то, что нашли по формуле. В Вашем примере про 9 и 12 можно не говорить, так как если число не делится ни на 2, ни на 3, то оно не будет кратно ни 9, ни 12. отвечен 14 Янв '14 15:57 
falcao Насчет пересечений,можно ли все находить не используя формулу,других способов нет?
(14 Янв '14 16:06)
ivan145
@ivan145: тот способ, который я назвал -- самый прямой, естественный и лёгкий. Такие задачи являются "типовыми", и решаются именно этим способом. Там можно разве что вывести прямые формулы с участием целых частей вида $%[n/2]$%, $%[n/3]$%, $%[n/6]$% с суммами и разностями. Но основой всё равно будет идея формулы включений и исключений. Можно, конечно, для отрезка длиной 42 всё сосчитать вручную, а потом поделить числа на секции по 42 числа в каждой и умножить на число секций, а потом так же подсчитать количество чисел в неполной секции, но это как бы не проще.
(14 Янв '14 16:12)
falcao
Можно, конечно, для отрезка длиной 42 всё сосчитать вручную, а потом поделить числа на секции по 42 числа в каждой и умножить на число секций, а потом так же подсчитать количество чисел в неполной секции, но это как бы не проще Можно про вот этот вариант поподробнее
(14 Янв '14 19:51)
ivan145
Для чисел от 0 до 41 все считается просто. Их можно выписать, а потом вычеркнуть все чётные, все делящиеся на 3, все делящееся на 7. Подсчитать то, что осталось. Столько же чисел будет в каждой полной секции длиной 42. То есть среди Ваших чисел первая полная секция начинается числом 252, кратным 42, а последняя полная оканчивается числом 1553. Полных секций там помещается вроде бы 31, и про них всё известно. А небольшие участки слева и справа (от начала до 251 и от 1554 до конца) "прочёсываются" вручную.
(14 Янв '14 22:49)
falcao
Далее надо посмотреть на попарные пересечения. Для чисел 2 и 3 получится множество чисел, кратных 6.Не совсем понял как искать пересечения,можно этот процесс поподробнее
(14 Янв '14 23:53)
ivan145
@ivan145: речь здесь идёт об очевидном факте. Если число делится и на 2, и на 3, то оно делится на 6. То есть само пересечение двух множеств этим уже найдено. Количество же его элементов, то есть чисел списка, делящихся на 6, находится по такому же принципу, как и количество чисел, делящихся на 2 и прочие числа.
(14 Янв '14 23:59)
falcao
показано 5 из 6
показать еще 1
|