Комбинаторика

[Гост]

Колко шестцифрени числа с различни цифри се образуват с цифрите 0,1,2,3,5,8и9?

[Jack]

Колко шестцифрени числа с различни цифри се образуват с цифрите 0,1,2,3,5,8и9?

Математически метод:

$$
\begin{array}{| c| c| c| c| c| c| }
\hline \\
Dig 1 & Dig 2 & Dig 3 & Dig 4 & Dig 5 & Dig 6 \\
\hline \\
6 & 6 & 5 & 4 & 3 & 2 \\
\hline
\end{array}
$$

Обяснение:
За първата цифра имаме $6$ възможности - $1, 2, 3, 5, 8, 9$.
За втората цифра имаме $6$ възможности - $0$ и другите $5$ неизползвани цифри.
За третата цифра имаме $5$ възможности - $5$ неизползвани цифри.
За четвъртатата цифра имаме $4$ възможности - $4$ неизползвани цифри.
За петата цифра имаме $3$ възможности - $3$ неизползвани цифри.
За шестата цифра имаме $2$ възможности - $2$ неизползвани цифри.

Има общо $6 \times 6 \times 5 \times 4 \times 3 \times 2 = 4320$

Симулация:
За да съм сигурен в отговора ще направя симулация с програма на $c++$:

Който го интересува кода на програмата:

Скрит текст: покажи

Код: Избери целия код

#include <iostream>

using namespace std;

int main()
{
    int ans = 0;

    for (int i = 102358; i <= 985321; i++)
    {
        int dig[10] = {0};
        int copie = i;

        while (copie)
        {
            dig[copie % 10]++;
            copie /= 10;
        }

        bool f1 = 0, f2 = 0;

        for (int q = 0; q < 10; q++)
        {
            if (dig[q] > 1)
            {
                f1 = 1;

                break;
            }
        }

        for (int q = 0; q < 10; q++)
        {
            if (q != 0 && q != 1 && q != 2 && q != 3 && q != 5 && q != 8 && q != 9 && dig[q] > 0)
            {
                f2 = 1;

                break;
            }
        }

        if (!f1 && !f2)
        {
            ans++;
        }
    }

    cout << ans << endl;

    return 0;
}


Получавам $4320$. [tex]\Rightarrow[/tex]

Отг. Всички шестцифрени числа отговарящи на условията са $4320$.

[peyo]

...

Има общо $6 \times 6 \times 5 \times 4 \times 3 \times 2 = 4320$

Симулация:
За да съм сигурен в отговора ще направя симулация с програма на $c++$:

Който го интересува кода на програмата:
...

Аз се интересувам, защото и аз когато изчисля нещо свързано с комбинации или вероятности, обикновено не вярвам на отговора докато не направя симулация.

Но С++ обикновено е много неудобен език за симулации. Аз лично препоръчвам Python за подобни цели:

In [160]: from itertools import permutations

In [164]: sum([1 for p in permutations([0,1,2,3,5,8,9], 6) if p[0] !=0])
Out[164]: 4320

[Jack]

...

Има общо $6 \times 6 \times 5 \times 4 \times 3 \times 2 = 4320$

Симулация:
За да съм сигурен в отговора ще направя симулация с програма на $c++$:

Който го интересува кода на програмата:
...

Аз се интересувам, защото и аз когато изчисля нещо свързано с комбинации или вероятности, обикновено не вярвам на отговора докато не направя симулация.

Но С++ обикновено е много неудобен език за симулации. Аз лично препоръчвам Python за подобни цели:

In [160]: from itertools import permutations

In [164]: sum([1 for p in permutations([0,1,2,3,5,8,9], 6) if p[0] !=0])
Out[164]: 4320

Аз го направих на С++, защото знам само него като език как да имплементирам нещо.

Като видях това permutations, ми хрумна идея с готовата функция next_permutation в $c++$ да симулирам числата вместо да проверявам всички шестцифрени числа:

Код: Избери целия код

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int arr[7] = {0, 1, 2, 3, 5, 8, 9};
    int ans = 0;

    do
    {
        if (arr[0] != 0)
        {
            ans++;
        }
    }
    while (next_permutation(arr, arr + 7));

    cout << ans << endl;

    return 0;
}


[peyo]

Аз го направих на С++, защото знам само него като език как да имплементирам нещо.

Като видях това permutations, ми хрумна идея с готовата функция next_permutation в $c++$ да симулирам числата вместо да проверявам всички шестцифрени числа:

Код: Избери целия код

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int arr[7] = {0, 1, 2, 3, 5, 8, 9};
    int ans = 0;

    do
    {
        if (arr[0] != 0)
        {
            ans++;
        }
    }
    while (next_permutation(arr, arr + 7));

    cout << ans << endl;

    return 0;
}


Това вече е доста по-добре, но пак не съвсем. С++ next_permutation генерира N! с дължина N, докато в нашия случай ние имаме 7 различни цифри, но искаме да генерираме всички редици с дължина само 6. По случайност в нашия случай резултат за 6 и 7 съвпада и без да искаш получи верния отговор:

In [165]: sum([1 for p in permutations([0,1,2,3,5,8,9], 6) if p[0] !=0])
Out[165]: 4320

In [166]: sum([1 for p in permutations([0,1,2,3,5,8,9], 7) if p[0] !=0])
Out[166]: 4320

Но ако търсихме 5:

In [167]: sum([1 for p in permutations([0,1,2,3,5,8,9], 5) if p[0] !=0])
Out[167]: 2160


Изглежда няма хубава фунция за пермутации за С++ която приема параметър лимит, но изглежда има workaround дискутиран в stackoverflow.

Щом имаш интерес към програмирането препоръчвам ученето на повече езици. Всеки език е подходящ за различни цели и много често ученето на нов език помага за по-доброто разбиране на други езици, както кода на Python ти даде идея за C++.

[Jack]

Аз го направих на С++, защото знам само него като език как да имплементирам нещо.

Като видях това permutations, ми хрумна идея с готовата функция next_permutation в $c++$ да симулирам числата вместо да проверявам всички шестцифрени числа:

Код: Избери целия код

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int arr[7] = {0, 1, 2, 3, 5, 8, 9};
    int ans = 0;

    do
    {
        if (arr[0] != 0)
        {
            ans++;
        }
    }
    while (next_permutation(arr, arr + 7));

    cout << ans << endl;

    return 0;
}


Това вече е доста по-добре, но пак не съвсем. С++ next_permutation генерира N! с дължина N, докато в нашия случай ние имаме 7 различни цифри, но искаме да генерираме всички редици с дължина само 6. По случайност в нашия случай резултат за 6 и 7 съвпада и без да искаш получи верния отговор:

In [165]: sum([1 for p in permutations([0,1,2,3,5,8,9], 6) if p[0] !=0])
Out[165]: 4320

In [166]: sum([1 for p in permutations([0,1,2,3,5,8,9], 7) if p[0] !=0])
Out[166]: 4320

Но ако търсихме 5:

In [167]: sum([1 for p in permutations([0,1,2,3,5,8,9], 5) if p[0] !=0])
Out[167]: 2160


Изглежда няма хубава фунция за пермутации за С++ която приема параметър лимит, но изглежда има workaround дискутиран в stackoverflow.

Щом имаш интерес към програмирането препоръчвам ученето на повече езици. Всеки език е подходящ за различни цели и много често ученето на нов език помага за по-доброто разбиране на други езици, както кода на Python ти даде идея за C++.

Получил съм същият отговор, защото накрая все едно за последната цифра е останала само една цифра и броят на възможностите не се променя.