C - Задача из комбинаторики

[decantnik]

Доброе время суток.
Получил по лабе вот такую задачу:

Определить количество чисел состоящих из n десятичных разрядов (N - натуральное число, вводится пользователем, N <= 10) у которых в двоичном представлении количество разрядов, установленных в «1», равняется числу K (натуральное число, вводится пользователем, K < log2N + 1). Учитывать, что число может начинаться с нулей: 0042342.

Препод сказал только пару слов "ищи информацию по комбинаторики"

Помогите кто-нибудь разобраться с условием

[Lasur]

1) Определить сколько двоичных разрядов у такого числа. Их примерно (int)log2(N)+1. Обозначим M.
2) Тогда кол-во всех возможных чисел с K единицами из такого кол-ва разрядов с учетом порядка равно A(M, k) = M!/(M-k)!
Где x! - факториал числа x.

[decantnik]

Спасибо большое!!

[Lasur]

Вот детали, если интересно.

[decantnik]

Вот решение, так сказать для истории:

#include <stdio.h>
#include <math.h>


double fact (int chislo);

int main(int argc, char *argv[])
{   
	int n,k;
    printf ("N = ");
	scanf ("%d", &n);
    printf ("K = ");
    scanf ("%d", &k);
	int m,a;
    m  = log2(n)+1;  //находим кол. двоичных разрядов
    a = fact(m)/(fact(m-k)); //кол-во всех возможных чисел с K единицами из такого кол-ва разрядов с учетом порядка
    printf("%d\n", m);
    return 0;
}

double fact (int chislo)
	{
double z=1;
for (int i=1;i<=chislo;i++)
	z*=i;
				
return(z);	
	}

[Lasur]

Не обязательно писать факториал, это несколько замедлит код, так как и в произведении знаменателя, и в произведении числителя вы считаете некоторые числа по несколько раз. Достаточно в цикле for посчитать a=(m)*(m-1)*(m-2)*......*(m-k+1), тогда лишних произведений не будет.