1. Если вы только начинаете программировать на ассемблере и не знаете с чего начать, тогда попробуйте среду разработки ASM Visual IDE
    (c) на правах рекламы
    Скрыть объявление

Задача по комбинаторике

Тема в разделе "WASM.ZEN", создана пользователем Asvald, 15 янв 2010.

  1. Asvald

    Asvald New Member

    Публикаций:
    0
    Регистрация:
    18 сен 2006
    Сообщения:
    58
    Понимаю, что задача не из сложных, но что-то никак не могу въехать как к ней подступиться

    Сколько шестизначных чисел содержат ровно три различные цифры?
    Я так понял это числа типа 554422, 123122 и т.д.
    У меня получается их количество 9*9*8*3*3*3, но их больше.

    И в общем случае сколько n значных чисел содержат ровно k различных цифр.
     
  2. Ox8BFF55

    Ox8BFF55 New Member

    Публикаций:
    0
    Регистрация:
    11 июл 2009
    Сообщения:
    181
    Пошел нафик со школьными вопросами(в 5 класс там такое проходят или в 7)!
     
  3. n0name

    n0name New Member

    Публикаций:
    0
    Регистрация:
    5 июн 2004
    Сообщения:
    4.336
    Адрес:
    Russia
    ну задача фактически сводится к вычислению количества способов разложить n на k слагаемых.
     
  4. Rockphorr

    Rockphorr Well-Known Member

    Публикаций:
    0
    Регистрация:
    9 июн 2004
    Сообщения:
    2.552
    Адрес:
    Russia
    Asvald
    10*9*8 - количество трехзначных чисел с различными цифрами

    сколько способов удвоить тройку чисел ??? -
    первую цифру можно расставить 2 раза 6*5 способами
    вторую 4*3
    третью 2*1

    итак ответ

    10*9*8*6*5*4*3*2*1=10!/7
     
  5. KeSqueer

    KeSqueer Сергей

    Публикаций:
    0
    Регистрация:
    19 июл 2007
    Сообщения:
    1.183
    Адрес:
    Москва
    Rockphorr
    10!/7=518400, что-то многовато по-моему.
     
  6. Rockphorr

    Rockphorr Well-Known Member

    Публикаций:
    0
    Регистрация:
    9 июн 2004
    Сообщения:
    2.552
    Адрес:
    Russia
    KeSqueer
    ваш вариант решения ???
     
  7. Solo

    Solo New Member

    Публикаций:
    0
    Регистрация:
    11 июл 2003
    Сообщения:
    131
    Rockphorr
    а почему именно удваиваются цифры??? туда не попадает вариант "111123", к примеру...

    Ox8BFF55
    очень бы хотелось посмотреть на любого 7-миклассника, решившего эту задачу...
     
  8. Solo

    Solo New Member

    Публикаций:
    0
    Регистрация:
    11 июл 2003
    Сообщения:
    131
    Rockphorr
    а на 2 каждый случай разве не нужно разделить? ;)
     
  9. KeSqueer

    KeSqueer Сергей

    Публикаций:
    0
    Регистрация:
    19 июл 2007
    Сообщения:
    1.183
    Адрес:
    Москва
    Rockphorr
    Мой вариант решения
    Код (Text):
    1. int is_valid(unsigned val)
    2. {
    3.     int digits[10] = {0};
    4.     unsigned sum = 0;
    5.     unsigned i;
    6.     for (i = 0; i < 6; ++i)
    7.     {
    8.         digits[val%10] = 1;
    9.         val = val/10;
    10.     }
    11.     for (i = 0; i < 10; ++i)
    12.     {
    13.         sum += digits[i];
    14.     }
    15.     return sum == 3;
    16. }
    17.  
    18. int main(void)
    19. {
    20.     unsigned count = 0;
    21.     unsigned i;
    22.     for (i = 100000; i <= 999999; ++i)
    23.     {
    24.         if (is_valid(i)) count++;
    25.     }
    26.     printf("%u\n", count);
    27. }
    дает 58320.
     
  10. Solo

    Solo New Member

    Публикаций:
    0
    Регистрация:
    11 июл 2003
    Сообщения:
    131
    да, и еще, к условию задачи:
    число 001122 является шестизначным? его нужно считать?
     
  11. Solo

    Solo New Member

    Публикаций:
    0
    Регистрация:
    11 июл 2003
    Сообщения:
    131
    Блин, нашелся, все же гений, решающий комбинаторные задачи полным перебором! :)
     
  12. Asvald

    Asvald New Member

    Публикаций:
    0
    Регистрация:
    18 сен 2006
    Сообщения:
    58
    Все решил, ответ получается перебором возможных вариантов появления в числе новой цифры начиная с первой(старший разряд), которая может быть любой цифрой из 9, кроме 0, т.к. ноль не может быть первой цифрой в числе.
    Например если нам уже известна 1-я цифра, то 2-я если она не "новая" может быть только равна 1-ой и так далее до встречи следующей "новой" цифры, после которой мы можем выбирать уже из двух вариантов и так до 3-ей "новой" цифры, после которой есть уже три варианта. Тогда у нас получаются следующие комбинации:
    9*1*1*1*9*8
    9*1*1*9*2*8
    9*1*1*9*8*3
    9*1*9*2*2*8
    9*1*9*2*8*3
    9*1*9*8*3*3
    9*9*2*2*2*8
    9*9*2*2*8*3
    9*9*2*8*3*3
    9*9*8*3*3*3

    Сумма всех комбинаций дает число 58320, которое мы уже проверили, т.к. сказать заранее.
     
  13. KeSqueer

    KeSqueer Сергей

    Публикаций:
    0
    Регистрация:
    19 июл 2007
    Сообщения:
    1.183
    Адрес:
    Москва
    Asvald
    Как на счет универсальной формулы?
     
  14. valterg

    valterg Active Member

    Публикаций:
    0
    Регистрация:
    19 авг 2004
    Сообщения:
    2.105
    Чуть посложнее. Сначала надо определится с нулем - число 000111222 разрешаем или нет.
    Потом определить сколько бывает разных наборов из трех цифр. Это действительно школьная задача, хотя в наше время такое только на факультавтивах решали(давно это было).
    Так как ноль надо учитывать, то тут все просто = 10*9*8
    Теперь надо посчитать число паттернов, куда будем наши тройки бросать : aabbacbaa
    Будет что-то типа три факториала вверху и два внизу. Получим ответ или если с нулями низзя, то придется подсчитать число "запрещенных".
     
  15. KeSqueer

    KeSqueer Сергей

    Публикаций:
    0
    Регистрация:
    19 июл 2007
    Сообщения:
    1.183
    Адрес:
    Москва
    valterg
    если я нигде не ошибся, этих паттернов 90
     
  16. valterg

    valterg Active Member

    Публикаций:
    0
    Регистрация:
    19 авг 2004
    Сообщения:
    2.105
    Ну да. Тогда моя формула(без нулей в начале) меняется = 9(без нуля в начале)*9*8
    И паттернов действительно 90 - тут нули роли не играют. И кстати легко посчитать "неверные" числа =
    90*10*9*8
     
  17. Solo

    Solo New Member

    Публикаций:
    0
    Регистрация:
    11 июл 2003
    Сообщения:
    131
    кстати, чисел без нуля вначале ровно 90% от всех чисел ;)
     
  18. valterg

    valterg Active Member

    Публикаций:
    0
    Регистрация:
    19 авг 2004
    Сообщения:
    2.105
    Осталось только написать обоснованную формулу с факториалами для общего случая. Пока это было решение программистов :-)
     
  19. diamond

    diamond New Member

    Публикаций:
    0
    Регистрация:
    21 май 2004
    Сообщения:
    507
    Адрес:
    Russia
    Почитайте про числа Стирлинга второго рода - это и есть число паттернов из #14. Ну а общая формула в терминах этих чисел тут уже фактически приводилась - S(n,k)*10!/(10-k)!, если разрешаются нули в начале числа, или S(n,k)*9*9!/(10-k)!, если нет.