Комбинаторика. 6-ти значное число.
От: Багер  
Дата: 25.12.02 12:53
Оценка:
Сколько шестизначных чисел можно составить из 3-х чётных и 3-х нечётных цифр.
Нужно как математическое решение, так и программа, проверяющая методом перебора математику.

16.01.03 23:48: Перенесено из 'Алгоритмы'
Ваша программа работает корректно? Один звонок и я всё исправлю!

Делаю потенциальные фичи :))
Re: Комбинаторика. 6-ти значное число.
От: Pushkin Россия www.linkbit.com
Дата: 25.12.02 13:01
Оценка:
Здравствуйте, Багер, Вы писали:

Б>Сколько шестизначных чисел можно составить из 3-х чётных и 3-х нечётных цифр.

Б>Нужно как математическое решение, так и программа, проверяющая методом перебора математику.

Если числа, начинающиеся с нуля допускаются, то

N= C(10,3)*C(10,3)*6!/3!/3! = 10*9*8/3/2 * 10*9*8/3/2 * 6*5*4*3*2/3/2/3/2 = 288000
Re[2]: Комбинаторика. 6-ти значное число.
От: Pushkin Россия www.linkbit.com
Дата: 25.12.02 13:13
Оценка:
Пардон, соврал , вот так, пожалуй

N= 5^3 * 5^3 * 6! / 3! /3! = 312500
Re[3]: Комбинаторика. 6-ти значное число.
От: Багер  
Дата: 25.12.02 13:16
Оценка:
C нуля числа — _не_ __шестизначные__.
Ваша программа работает корректно? Один звонок и я всё исправлю!

Делаю потенциальные фичи :))
Re[2]: Комбинаторика. 6-ти значное число.
От: Lexey Россия  
Дата: 25.12.02 13:26
Оценка:
Здравствуйте, Pushkin, Вы писали:

P>Здравствуйте, Багер, Вы писали:


Б>>Сколько шестизначных чисел можно составить из 3-х чётных и 3-х нечётных цифр.

Б>>Нужно как математическое решение, так и программа, проверяющая методом перебора математику.

P>Если числа, начинающиеся с нуля допускаются, то


P>N= C(10,3)*C(10,3)*6!/3!/3! = 10*9*8/3/2 * 10*9*8/3/2 * 6*5*4*3*2/3/2/3/2 = 288000


Хм, а C(10,3) откуда? По-моему:
N = (P(5,3) — 5*C(3,2)*5 + 5)^2*A(6,3) = 363000
"Будь достоин победы" (c) 8th Wizard's rule.
Re: Комбинаторика. 6-ти значное число.
От: Atilla Россия  
Дата: 25.12.02 13:32
Оценка:
Здравствуйте, Багер, Вы писали:

Б>Сколько шестизначных чисел можно составить из 3-х чётных и 3-х нечётных цифр.

Б>Нужно как математическое решение, так и программа, проверяющая методом перебора математику.

Цифры могут повторяться или нет?? типа "111000"?
http://forum.buhpravda.ru/images/smilies/umnik.gifКр-ть — с.т.
Re[4]: Комбинаторика. 6-ти значное число.
От: Chorkov Россия  
Дата: 25.12.02 13:33
Оценка: 18 (2)
Здравствуйте, Багер, Вы писали:

Б>C нуля числа — _не_ __шестизначные__.

тодга:
5^3*5^3*6!/3!/3!-5^3*5^2*5!/2!/3!
=281250
Re[3]: Комбинаторика. 6-ти значное число.
От: Lexey Россия  
Дата: 25.12.02 13:34
Оценка:
Здравствуйте, Lexey, Вы писали:

L>Хм, а C(10,3) откуда? По-моему:

L>N = (P(5,3) — 5*C(3,2)*5 + 5)^2*A(6,3) = 363000

Для чисел начинающихся не с 0:
N = 9*[(P(5,3) — 5*C(3,2)*5 + 5) * (P(5,2) — 5)]*A(5,3) = 198000
"Будь достоин победы" (c) 8th Wizard's rule.
Re[5]: Комбинаторика. 6-ти значное число.
От: Pushkin Россия www.linkbit.com
Дата: 25.12.02 13:40
Оценка:
Здравствуйте, Chorkov, Вы писали:

Б>>C нуля числа — _не_ __шестизначные__.

C>тодга: 5^3*5^3*6!/3!/3!-5^3*5^2*5!/2!/3!=281250

Факт!
Re[3]: Комбинаторика. 6-ти значное число.
От: Pushkin Россия www.linkbit.com
Дата: 25.12.02 13:43
Оценка:
Здравствуйте, Lexey, Вы писали:

P>>N= C(10,3)*C(10,3)*6!/3!/3! = 10*9*8/3/2 * 10*9*8/3/2 * 6*5*4*3*2/3/2/3/2 = 288000


L>Хм, а C(10,3) откуда?


от лукавого я уже поправился

По-моему:
L>N = (P(5,3) — 5*C(3,2)*5 + 5)^2*A(6,3) = 363000

нет, любые С() здесь не нужны — цифры могут повторяться
Re[6]: Комбинаторика. 6-ти значное число.
От: Lexey Россия  
Дата: 25.12.02 13:45
Оценка:
Здравствуйте, Pushkin, Вы писали:

Б>>>C нуля числа — _не_ __шестизначные__.

C>>тодга: 5^3*5^3*6!/3!/3!-5^3*5^2*5!/2!/3!=281250

P>Факт!


Логику в студию, pls. Мне интересно, как вы учитываете перестановки дублирующихся цифр без формулы включений/исключений.
"Будь достоин победы" (c) 8th Wizard's rule.
Re: Комбинаторика. 6-ти значное число.
От: Кодт Россия  
Дата: 25.12.02 13:46
Оценка: 12 (1)
Здравствуйте, Багер, Вы писали:

Б>Сколько шестизначных чисел можно составить из 3-х чётных и 3-х нечётных цифр.

Б>Нужно как математическое решение, так и программа, проверяющая методом перебора математику.

Числа вида OOOEEE -- 5^6 вариантов.
Перестановки OOEOEE, OOEEOE и т.д. -- C(3,6) = (6*5*4)/(1*2*3) = 20.
Итого: 20 * 5^6 = 312500.

Пятизначные числа 0{OOEEE} -- 5^5 * C(3,5) = 5^5 * (5*4)/(2*1) = 5^3*2 = 250

Итого, подлинно 6-значных — 312250.

Программа, которая выводит отсортированный список, не совершая неудачных попыток
int count = 0;

int digit[6]; // 0..10
int parity[2] = {0, 0}; // 0..3

void run(int d)
{
  if(i == 6)
  {
    count++;
    printf("[ %6d ] %d %d %d %d %d %d\n",
           count, digit[0],digit[1],digit[2],digit[3],digit[4],digit[5],digit[6]
          );
    return;
  }

  if(parity[0] < 3 && parity[1] < 3) // сплошной бег
  {
    for(digit[d] = (d == 0) ? 1 : 0; digit[d] < 10; digit[d]++) // первая цифра 1..10.
    {
      parity[digit[d] % 2] ++;
      run(d+1);
      parity[digit[d] % 2] --;
    }
  }
  else
  {
    int p = (parity[0] < 3) ? 0 : 1; // четность, которая осталась вакантной
    parity[p]++;
    for(digit[d] = p; digit[d] < 10; digit[d] += 2)
      run(d+1);
    parity[p]--;
  }
}

main()
{
  run(0);
}
http://files.rsdn.org/4783/catsmiley.gif Перекуём баги на фичи!
Re[7]: Комбинаторика. 6-ти значное число.
От: Pushkin Россия www.linkbit.com
Дата: 25.12.02 13:58
Оценка: 12 (1)
Здравствуйте, Lexey, Вы писали:

Б>>>>C нуля числа — _не_ __шестизначные__.

C>>>тодга: 5^3*5^3*6!/3!/3!-5^3*5^2*5!/2!/3!=281250

P>>Факт!


L>Логику в студию, pls. Мне интересно, как вы учитываете перестановки дублирующихся цифр без формулы включений/исключений.


Пусть первый ноль разрешён.

Первую чётную цифру можно выбрать пятью способами. Вторую тоже. И третью.
Та же байда с нечётными — отсюда шесть пятёрок множителями.

Цифры мы выбрали, теперь нодо решить, как их расставить промеж друг друга.
Иными словами, сколько всего различных на вид расстановок трёх одинаковых белых шаров и трёх одинаковых чёрных.
Всего перестановок 6!, но там полно одинаковых на вид — там где только два белых поменялись или только два чёрных. Чтобы их убить, делим на число перестановок самих белых и самих чёрных (два делителя по 3!).

Если первый ноль запрещён, то вычитаем все начинающиеся с нуля — та же формула, но для 2 чётных + 3 нечётных.
Re[2]: Комбинаторика. 6-ти значное число.
От: Pushkin Россия www.linkbit.com
Дата: 25.12.02 14:07
Оценка:
Здравствуйте, Кодт, Вы писали:

К>Пятизначные числа 0{OOEEE} -- 5^5 * C(3,5) = 5^5 * (5*4)/(2*1) = 5^3*2 = 250

К>Итого, подлинно 6-значных — 312250.

В центральном знаке равенства потерял три пятёрки
Верный ответ для пятизначных 5^5*10=31250
а для подлинно шестизначных 281250 (by Chorkov)
Re: Комбинаторика. 6-ти значное число.
От: Аноним  
Дата: 25.12.02 14:13
Оценка:
Здравствуйте, Багер, Вы писали:

Б>Сколько шестизначных чисел можно составить из 3-х чётных и 3-х нечётных цифр.

Б>Нужно как математическое решение, так и программа, проверяющая методом перебора математику.

Ответ: 19*5^6-10*5^5=265625
Re[2]: Комбинаторика. 6-ти значное число.
От: Аноним  
Дата: 25.12.02 14:15
Оценка:
Здравствуйте, Аноним, Вы писали:

А>Здравствуйте, Багер, Вы писали:


Б>>Сколько шестизначных чисел можно составить из 3-х чётных и 3-х нечётных цифр.

Б>>Нужно как математическое решение, так и программа, проверяющая методом перебора математику.

А>Ответ: 19*5^6-10*5^5=265625


Ошибся : 20 вместо 19
те 281250
Re[2]: Комбинаторика. 6-ти значное число.
От: Багер  
Дата: 25.12.02 14:26
Оценка:
Уууу-х, просветили, однако!
Скоро обрадую брательника моего знакомого, что мы всё-таки правильно в Экселе написали программу, а вот решение было неправильным ))
Спасибо!
Ваша программа работает корректно? Один звонок и я всё исправлю!

Делаю потенциальные фичи :))
Re[8]: Комбинаторика. 6-ти значное число.
От: Lexey Россия  
Дата: 25.12.02 14:48
Оценка:
Здравствуйте, Pushkin, Вы писали:

L>>Логику в студию, pls. Мне интересно, как вы учитываете перестановки дублирующихся цифр без формулы включений/исключений.


P>Пусть первый ноль разрешён.


P>Первую чётную цифру можно выбрать пятью способами. Вторую тоже. И третью.

P>Та же байда с нечётными — отсюда шесть пятёрок множителями.

Это я понимаю.

P>Цифры мы выбрали, теперь нодо решить, как их расставить промеж друг друга.

P>Иными словами, сколько всего различных на вид расстановок трёх одинаковых белых шаров и трёх одинаковых чёрных.

Неа, такая логика тут не работает. Сначала ты считаешь число РАЗЛИЧНЫХ упорядоченных выборок из отдельно четных и отдельно нечетных цифр. Далее ты хочешь это умножить на число перестановок ОДНОЙ конкретной выборки. В этой выбоке у тебя присутствуют КОНКРЕТНЫЕ цифры. Их никак нельзя считать шарами одного цвета.

P>Всего перестановок 6!, но там полно одинаковых на вид — там где только два белых поменялись или только два чёрных. Чтобы их убить, делим на число перестановок самих белых и самих чёрных (два делителя по 3!).


Впрочем, ответ действительно правильный.
"Будь достоин победы" (c) 8th Wizard's rule.
Re[9]: Комбинаторика. 6-ти значное число.
От: Pushkin Россия www.linkbit.com
Дата: 25.12.02 15:41
Оценка:
Здравствуйте, Lexey, Вы писали:

P>>Первую чётную цифру можно выбрать пятью способами. Вторую тоже. И третью.

P>>Та же байда с нечётными — отсюда шесть пятёрок множителями.

L>Это я понимаю.


P>>Цифры мы выбрали, теперь нодо решить, как их расставить промеж друг друга.

P>>Иными словами, сколько всего различных на вид расстановок трёх одинаковых белых шаров и трёх одинаковых чёрных.

L>Неа, такая логика тут не работает. Сначала ты считаешь число РАЗЛИЧНЫХ упорядоченных выборок из отдельно четных и отдельно нечетных цифр. Далее ты хочешь это умножить на число перестановок ОДНОЙ конкретной выборки. В этой выбоке у тебя присутствуют КОНКРЕТНЫЕ цифры. Их никак нельзя считать шарами одного цвета.


Ну почему? В числе всегда есть первая, вторая и третья чётная цифра.

Ну хорошо, давай так: чисел вида чччннн 5^6 — да?
Теперь из каждого такого числа перестановками можно получить 6!/3!/3! различных чисел.
Например ччннчн, чнннчч, нннччч — всего 20 вариантов, посчитай.
Типичная задача о трёх чёрных (ч) и трёх белых (н) шарах.

L>Впрочем, ответ действительно правильный.


И это всё доказывает, таких совпадений не бывает
Re[10]: Комбинаторика. 6-ти значное число.
От: Pushkin Россия www.linkbit.com
Дата: 25.12.02 15:46
Оценка:
Здравствуйте, Pushkin, Вы писали:

P>Ну хорошо, давай так: чисел вида чччннн 5^6 — да?

P>Теперь из каждого такого числа перестановками можно получить 6!/3!/3! различных чисел.
P>Например ччннчн, чнннчч, нннччч

У, блин. Это просто дословно сдуто у Кодта
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.