Я задал вопрос. Вы взялись отвечать. Я же вас силком не тянул :-) Но на полпути вы закрыли тему, потому что а) всем якобы всё очевидно б) раз мне не очевидно, то проблема во мне. Отлично. Эту вашу точку зрения я понял. У вас есть ещё что-то новое мне сообщить?
Рост числа комбинаций чего в зависимости от чего? Ещё раз: "чего в зависимости от чего" Вы правда, когда формулируете — формулируете настолько расплывчато, а когда вам предлагают уточнить, говорите что уточнения нужны для нубов, а всем и так всё понятно. Ну да, ну да.
Согласно факториалу — это количество комбинаций из n предметов.
Кроме того, факториал растёт значительно быстрее экспоненциальной функции. Формула Стирлинга, вот это всё.
Фраза, «я не собираюсь Вам ничего доказывать, т.к. это уже давно доказано» — тут следует либо привести ссылку, на место где разбиралась ровно такая задача, а не на «учебник комбинаторики».
Ну и наконец. Википедия говорит, что экспоненциальный рост и геометрический рост — это одно и то же. А то, что вы попутали его с логарифмическим, ну это наверное я, нуб, виноват :-)
Кстати, если я недостоин вашего внимания, то мне можно просто не отвечать в этом треде. Боюсь, вы правда не удержитесь ещё рас сказать мне, какое я ничтожество :-)
Т.е. поясню. У вас есть число комбинаций, которое растёт экспоненциально, но есть и число оставшихся билетов которые мы должны будем заполнить чтобы было без перекрытия. Даже если число растёт экспоненциально, совсем не факт что число оставшихся билетов не будет расти быстрее, чем этот рост. Это требуется до-ка-зать.
1. Не приведена оценка, как такая рекурсия будет работать, непонятно что такое «комбинация» в применении к данному вопросу. В данном случае нужно перебрать все возможные способы выбрать все билеты, и это число астрономическое. Но непонятно даже, как написать этот алгоритм. Если вы хотите — используйте псевдокод.
2. Как провести эту проверку? Вот есть список чисел билетов A, и B, и что?
3. Это утверждение не является точно математически сформулированным. "количество комбинаций увеличивается в геометрической прогрессии" — каких комбинаций и в зависимости от чего? Как это поможет в применении к нашей задаче? Строго математически, чтобы доказать теорему, вы должны сравнить две зависимости между собой, и доказать что одна больше. А не просто «видно, что одна очень большая и растёт быстро».
1. Не приведён алгоритм получения комбинаций без повторений. Это можно, очевидно, сделать несколькими способами. Возможно, одни из них окажутся более оптимальными для будущих «добитий», чем другие.
2. Нет алгоритма этого внутреннего цикла без повторений, оценки сложности этого алгоритма (будет ли он работать полиномиальное от входа время или экспоненциальное).
3. Пока нет строгого доказательства, что начинать всегда нужно с максимума и «добивать» им до упора. Да, число комбинаций растёт быстро, ну и что? Есть функции, которые растут быстрее факториала. Возможно, взяв «большой кирпичик слишком неправильной формы» в начале, потом придётся добивать слишком большим числом мелких.
Вы, конечно, обвиняли меня в недостаточном уровне знаний. В таком случае, вы наверняка знаете, что "Задача о Рюкзаке", например, при всей своей простоте формулировки не имеет полиномиального точного решения, и простого приблеженного решения тоже не имеет.
1. Что значит без единого повторения? Я уже писал случай, когда повторения явно выгодны. habrahabr.ru/qa/36335/#comment_173837
2. Как сделать по (P-1) заведомо без пересечений с предыдущими?
И да, задачу нужно решать для произвольных чисел (в этом и смысл решения задачи). Это как вы бы теорему ферма доказывали не для произвольных чисел, а для трёх конкретных. Смешно.
Вы хотите сказать, что данная задача разбиралась — в том виде, котором я её поставил — где-то в учебнике? Если да, то просто дайте ссылку. А если нет, то и всё.
Я уже написал, что вы формулируете свои мысли не строго. Да, общая идея, видимо, «сначала крупными, потом мелкикими», но это вовсе не даёт нам строго алгоритма, как мне нужно.
«взять сначала билеты с максимально возможным числом крестиков, без повторения комбинаций». Что это значит, как минимум, уже непонятно (это не строгое объяснение). Я, повторюсь, вы же не пишите АЛГОРИТМ, ПРОГРАММУ, а просто выражаетесь на русском языке — а он не строгий.
Я уже написал случай, когда ваше «без повторения» не оптимально, но вы как-будто этого не заметили. Вот простая задача: угадать 2 из 6. Разрешено зачеркивать до трёх цифр. Какой оптимальный набор билетов?
