Любой экспонентальный рост — это геометрический рост. Любой геометрический рост — это не обязательно экпонентальный рост. Ещё один прокол с вашей стороны. Если читаете Википедию, то читайте внимательнее.
Во-первых, я не собираюсь расписывать алгоритмы для Вас, т.к. задача элементариная. Если Вы нуб в программировании, то это ваши проблемы.
Во-вторых, я не собираюсь Вам ничего доказывать, т.к. это уже давно доказано. Если Вы нуб в комбинаторике, то это ваши проблемы.
В-третьих, количество сочетаний вычисляется через факториал, а не через логарифм, поэтому число комбинаций будет рости геометрически, а не эксонентально. Доказывать Вам это не буду (см. пункт 2).
1. Самый простой алгоритм приведён в моём втором комментарии — перебор всех комбинаций в лоб при помощи рекурсии. Проще просто не придумаете, т.к. число проходов равно числу возможных комбинаций.
2. Внутрений алгоритм представляет собой цикл с сравнением комбинаций. Самым простым способом будет проверка чисел комбинации на принадлеженость разным «большим билетам». Количество переборов будет увеличено на 6 — число цифр в комбинации.
3. Я уже вам его приводил — количество комбинаций увеличивается в геометрической прогрессии, поэтому самым выгодным будет взятие сначала самых «больших» билетов.
Задача о рюкзаке не в тему, т.к. условия другие — у нас комбинации все равновероятностны.
1. Без единого повторения комбинации. Числа в «больших» (с максимальным числом крестиков) билетах могут перекрываться меньше, чем комбинация.
2. Внутрениий цикл с проверкой предыдущих комбинаций.
У вас условия задачи постепенны неправильно чтобы по ним делать алгоритм — нет ограничения на количество «крестиков». При вашей подаче самым оптимальным вариантом будет покупка билета с n «крестиками».
Если ограничение, есть то алгоритм также простой — в цикле перебираем все крупные варианты по числу крестиков, с не повторяющимися цифрами, за исключением крайних.
А что там доказывать?
Количество комбинаций увеличивается геометрически (по факториалу), соответственно, нам, чтобы уменьшить количество билетов нужно взять сначала билеты с максимально возможным числом крестиков, без повторения комбинаций.
Почему число комбинаций увеличивается геометрически Вы можете прочитать в учебнике по комбинаторике.
Загнули. Вы мне предлагаете Вам на пальцах доказать половину теорем комбинаторики, начиная с бинома Ньютона?
Я уже понял, что у Вас большие пробелы в этой области.
Просто назовите число чисел в вашей лотерее, а я посчитаю сколько билетов Вам понадобиться.
Единственный случай, когда удобно (но не выгодно — по деньгам тоже самое), это когда мы покупаем билеты с полностью разными цифрами, а остальное добиваем билетами с 6 крестиками.
Вы что не можете допереть, что чтобы обеспечить 100% выигрыш нужно ещё обеспечить 0% проигрыш.
В вашем последнем примере, кроме того, что нет ни одной общей комбинации и, соответственно, самое большое число возможных комбинаций для двух билетов, для этих же двух билетов самое большое количество не покрытых комбинаций.
Повторения комбинаций появляются в случаях, если мы ставим больше крестиков, чем 6. Таким образом самым экономным способом будет покупка билетов с 6 крестиками.
Какое ещё КПД в комбинаторике? В данной сфере используется понятие «вероятность».
Чтобы получить 100% вероятность мы должны перебрать абсолютно все комбинации, даже есть придётся платить большие деньги за малые проценты вероятности выигрыша. Мы можем съэкономить деньги только понижая вероятность выигрыша, но тогда появляется вероятность проигрыша.
