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

Тема в разделе "WASM.A&O", создана пользователем Panda, 5 окт 2008.

Страница 3 из 3
  1. crypto

    crypto Active Member

    Публикаций:
    0
    Регистрация:
    13 дек 2005
    Сообщения:
    2.533
    Y_Mur
    Я же специально отметил, что эти результаты для старшей цифры != 0, поэтому общее количество не 1000000000, а как раз 2*450000000.
    А если старшая цифра 0, то получается тоже половина.
     
    crypto, 7 окт 2008
    #41
  2. Panda

    Panda New Member

    Публикаций:
    0
    Регистрация:
    5 окт 2008
    Сообщения:
    11
    Y_Mur
    Да, в разных позициях могут быть одинаковые предметы (сочетания с повторениями).

    crypto
    Спасибо, буду разбираться. Пока что-то туго доходит. Надо почитать.
     
    Panda, 7 окт 2008
    #42
  3. Mikl___

    Mikl___ Супермодератор Команда форума

    Публикаций:
    14
    Регистрация:
    25 июн 2008
    Сообщения:
    3.792
    А мне кажется, что преподавателю доставит больше удовольствия, что вы "потратили несколько часов на конкретный пример" (© crypto) но разобрались, чем выдернутое готовое решение из "Искусства программирования" Кнута и при этом до вас ничего не дошло :)
     
    Mikl___, 8 окт 2008
    #43
  4. Y_Mur

    Y_Mur Active Member

    Публикаций:
    0
    Регистрация:
    6 сен 2006
    Сообщения:
    2.494
    Возвращаясь к:
    имеем 10 цифр - предметов, для них 9 позиций в числе, цифры имеют право повторяться,
    но C(n+m-1,n) не равно 1000000000, значит речь не о любых комбинациях 10 произвольных предметов в 9 позициях, есть ещё какое-то условие - напомните пожалуйста какое?
     
    Y_Mur, 8 окт 2008
    #44
  5. Velheart

    Velheart New Member

    Публикаций:
    0
    Регистрация:
    2 июн 2008
    Сообщения:
    526
    Я в конце неправильно написал, из рассуждений должно быть всего 8*10^8/2 + 10^8*2 = 450000000, как и у crypto, т.к. мы считаем 9-значные не начинающиеся с нуля и девяти в первом слагаемом
     
    Velheart, 8 окт 2008
    #45
  6. crypto

    crypto Active Member

    Публикаций:
    0
    Регистрация:
    13 дек 2005
    Сообщения:
    2.533
    Y_Mur
    Это может быть связано с числом решений уравнения
    x1 + x2 + ... + x9 = N,
    где каждое x лежит между 0 и 9.
    А упомянутая мной формула выражает число решений этого уравнения при условии, что каждое x >= 0.

    Но похоже это слишком длинный путь. Немного проще привлечь производящие функции. Скажем так. Возьмем такую функцию
    f(x1,...,x9) = (x1 + x1^2 + ... + x1^9)*(1 + x2 + x2^2 + ... + x2^9)*...*(1 + x9 + x9^2 + ... + x9^9). Если теперь взять x1=x2=...=x9=x и просумировать коэффициенты при четных степенях x, как раз получим требуемое число. А как взять сумму коэффициентов при четных степенях x, мы тоже знаем: (f(1,...1) + f(-1,...,-1))/2.
     
    crypto, 8 окт 2008
    #46
  7. Mikl___

    Mikl___ Супермодератор Команда форума

    Публикаций:
    14
    Регистрация:
    25 июн 2008
    Сообщения:
    3.792
    crypto
    Рассмотрим 1-значные числа от 0 до 9: 5 из них имеет четное число, 5 - нечетное. Теперь рассмотрим 2-значные числа, Если первая цифра четная, то к ней добавляют четную вторую цифру, таких 2-значных чисел 5*5=25, если первая цифра нечетная, то добавляют нечетную вторую цифру, таких 2-значных чисел 5*5=25. Итого 2-значных чисел с четной суммой будет 25+25=50 (в уме держим, что осталось 50 чисел с нечетной суммой) не поленитесь напишите на листочке числа от 00 до 99, обведите кружочком числа с четной суммой и убедитесь, что их 50, а не 45! далее по индукции 3-значных чисел с четной суммой цифр 5*50 + 5*50 = 500 (в уме держим, что осталось 500 чисел с нечетной суммой) и т.д. до 9-значного чисела -- вот здесь следует учесть, что 9-значное число не может начинаться с цифры 0 - получается 4*50000000 + 5*50000000=450000000
     
    Mikl___, 8 окт 2008
    #47
  8. crypto

    crypto Active Member

    Публикаций:
    0
    Регистрация:
    13 дек 2005
    Сообщения:
    2.533
    Mikl___
    Дык я это и имел в виду, может коряво высказался, что двузначных, начинающихся с 1, 45, а начинающихся с 0, 50. В отличие от меня ты изложил суть решения логически грамотно и последовательно.
     
    crypto, 8 окт 2008
    #48
  9. Mikl___

    Mikl___ Супермодератор Команда форума

    Публикаций:
    14
    Регистрация:
    25 июн 2008
    Сообщения:
    3.792
    crypto
    Учусь у вас понемногу :) интересно, устроит ли решение Pand'у?
     
    Mikl___, 8 окт 2008
    #49
  10. Vovochka

    Vovochka New Member

    Публикаций:
    0
    Регистрация:
    8 окт 2008
    Сообщения:
    1
    Дароф всем! Люди помогите упростить выражение( я это не понимаю....)
    (C\/B)/\(неА\/неВ)/\А/\(В\/неА)\/А
     
    Vovochka, 8 окт 2008
    #50
  11. crypto

    crypto Active Member

    Публикаций:
    0
    Регистрация:
    13 дек 2005
    Сообщения:
    2.533
    Mikl___
    М-да, девушка что-то замолчала...
     
    crypto, 8 окт 2008
    #51
  12. Mikl___

    Mikl___ Супермодератор Команда форума

    Публикаций:
    14
    Регистрация:
    25 июн 2008
    Сообщения:
    3.792
    Vovochka не понимаешь -- это твои проблемы, они тут никого не волнуют, читай здесь. Провожу бесплатную экскурсию по форуму -- самое главное -- внимательно читай название разделов WASM.A&O-->Обсуждение алгоритмов и техник оптимизации кода. т.е. твой вопрос здесь явно не в тему. Судя по вопросу -- тебе вот сюда WASM.BEGINNERS-->Раздел для новичков. Если вы чувствуете себя неопытным - задавайте свои вопросы здесь. в подраздел Студентам с вопросами о лабораторных работах сюда здесь будешь долго ждать ответа и нудить, чтобы ответили и помогли. Хочешь быстро -- тогда тебе сюда WASM.COMMERCE-->Здесь следует размещать коммерческие объявления, связанные с тематикой форума. Незнание Правил форума WASM не освобождает от бана [​IMG]
    Меняем значки \/ (логическое сложение) и /\ (логическое умножение) на более привычные "+" и "*" используем свойство дистрибутивности X*Y+X*Z=X*(Y+Z) и две аксиомы 1+X=1 и 1*X=X в итоге получаем
    (C+B)*(неА+неВ)*А*(В+неА)+А=((C+B)*(неА+неВ)*(В+неА)+1)*А=А
     
    Mikl___, 9 окт 2008
    #52
Страница 3 из 3