как ускорить перебор?

Question

условие - есть 11 пронумерованных шариков от 0 до 10, я достаю случайным образом по 1 шарику и смотрю их номера, если номер хотя бы одного шарика совпадает с номером вытягивания(считаем от нуля до 10) - комбинация считается победной(пример: 2 0 1 3 5 4 6 7 9 8 10 - победная, так как совпали числа 3 6 7 10).

есть кусок кода, он пересчитывает циклом по +1, этот код считает в 11ричной системе, и считает он где то 256 дней, собственно надо как-то ускорить. (прибавляет к последнему разряду 1 и проверяет, если проверка успешная то записывает +1 к сумме правильных вариантов, снова прибавляет 1 к последнему разряду, каждый разряд - переменная) код написан максимально просто - без массивов, всяких подпрограмм и прочего, задействованы только кейсы(это есть один из кейсов) циклы for, условия if и cin cout. ответ хотелось бы получить так же написанным максимально просто как этот отрывок.

for (int z = 0; z <= 3; z++) {
        z--;
        if (z != 3) {
            j++;
            if (j == 11) {
                j = 0;
                i++;
                if (i == 11) {
                    i = 0;
                    h++;
                    if (h == 11) {
                        h = 0;
                        g++;
                        if (g == 11) {
                            g = 0;
                            f++;
                            if (f == 11) {
                                f = 0;
                                e++;
                                if (e == 11) {
                                    e = 0;
                                    d++;
                                    if (d == 11) {
                                        d = 0;
                                        c++;
                                        if (c == 11) {
                                            c = 0;
                                            b++;
                                            if (b == 11) {
                                                b = 0;
                                                a++;
                                                if (a == 11) { 
                                                    k++;
                                                    a = 0;
                                                    if (k == 11) {
                                                        k--;
                                                        z + 100;
                                                        break;
                                                    }
                                                }
                                            }
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
        if (k == 10 or a == 9 or b == 8 or c == 7 or d == 6 or e == 5 or f == 4 or g == 3 or h == 2 or i == 1 or j == 0) {
            if (a != b and a != c and a != d and a != e and a != f and a != g and a != h and a != i and a != j and a != k) {
                if (b != c and b != d and b != e and b != f and b != g and b != h and b != i and b != j and b != k) {
                    if (c != d and c != e and c != f and c != g and c != h and c != i and c != j and c != k) {
                        if (d != e and d != f and d != g and d != h and d != i and d != j and d != k) {
                            if (e != f and e != g and e != h and e != i and e != j and e != k) {
                                if (f != g and f != h and f != i and f != j and f != k) {
                                    if (g != h and g != i and g != j and j != k) {
                                        if (h != i and h != j and h != k) {
                                            if (i != j and i != k and j != k) {
                                                summ++;
                                            }
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    cout << summ << endl;
    break;

Answer 1

Решение реализует вычисление числа порядков в соответствие с формулой включения-исключения.

Идея: допустим у нас arr[0] = 0 - это фиксированная точка, тогда мы точно знаем, что любые перестановки в остальной части массива, будут подходящим для нас решением. Теперь продолжим, пусть arr[1] = 1 - это фиксированная точка, соотвественно перестановки во всей остальной части массива будут подходящим решением, но вот беда, множества этих решений пересекаются, соответсвенно нам нужно это пересечение отнять. Идём дальше arr[2] = 2, то же самое, только теперь у нас проблема в том, что уже пересечения пересекаются и мы отнимаем это пересечение пересечений два раза, соответсвенно нам нужно его прибавить. И т.д. Вообщем, примерно как-то так можно сформулировать идею стоящую за формулой включения-исключения.

Формула включений и исключений: https://www.matburo.ru/ex_tv.php?p1=tvvi

Беспорядки (см. Задача Эйлера): https://www.matburo.ru/tvart_sub.php?p=dear_problem

#include <iostream>

int calc(int n) {
    int res = 0;
    for(int t = 1, k = n; k > 0; --k) {
        res += k & 1? t : -t;
        t *= k;
    }
    return res;
}

int main() {
    std::cout << calc(11) << '\n';
    return 0;
}

БЛОГ НА HUSL

как ускорить перебор?

Ответы (1 шт):