Определение

Полный перебор - метод решения задач, при котором перебираются все возможные исходы. Такой метод гарантированно находит правильный ответ, однако время выполнения зависит от количества исходов. Если их количество очень велико, то полный перебор может высчитывать ответ несколько дней или больше.

Примеры задач

Задача №1

Сколько различных двузначных чисел можно составить из цифр $1, 3, 4, 5$ ?

Решение

Для решения задачи просто перебираем все цифры между собой.

Псевдокод

Функция найти_двузначные_числа(цифры):  
    результат = список()  
  
    Для первой_цифры в цифры:  
        Для второй_цифры в цифры:  
            число = первая_цифра * 10 + вторая_цифра  
            добавить число в результат  
  
    вернуть результат

Реализация на Python

Аннотация:  
generate_two_digit_numbers - функция для генерации всех возможных двузначных чисел  
digits - массив цифр, из которых нам надо составить двухзначное число  
result - итоговый список двухзначных чисел  
first_digit - число, которое будет стоять на первой позиции  
second_digit - число, которое будет стоять на второй позиции 

def generate_two_digit_numbers(digits):  
    result = []  
    for first_digit in digits:  
        for second_digit in digits:  
            data = first_digit * 10 + second_digit  
            result.append(data)   
    return result

Олимпиадная реализация на C++

Аннотация:  
typedef - переопределение имени типа данных  
generate_two_digit_numbers - функция для генерации всех возможных двузначных чисел  
digits - массив цифр, из которых надо составить двухзначное число  
res - итоговый список двухзначных чисел  
d1 - число, которое будет стоять на первой позиции  
d2 - число, которое будет стоять на второй позиции 

typedef vector<int> vi;  
  
vi generate_two_digit_numbers(const vi& digits) {  
    vi res;  
    for (int d1 : digits) {  
        for (int d2 : digits) {  
            int data = d1 * 10 + d2;  
            res.push_back(data);  
        }  
    }  
    return res;  
}

Продуктовая реализация на C++

Аннотация:  
generate_two_digit_numbers - функция для генерации всех возможных двузначных чисел  
digits - массив цифр, из которых надо составить двухзначное число  
result - итоговый список двухзначных чисел  
first_digit - число, которое будет стоять на первой позиции  
second_digit - число, которое будет стоять на второй позиции 

using namespace std;  
  
vector<int> generate_two_digit_numbers(const vector<int>& digits) {  
    vector<int> result;  
    for (int first_digit : digits) {  
        for (int second_digit : digits) {  
            int data = first_digit * 10 + second_digit;  
            result.push_back(data);  
        }  
    }  
    return result;  
}

Задача №2

Сколько различных трёхзначных чисел можно составить из цифр $2, 4, 0$, если цифры в записи числа не повторяются.

Решение

Аналогично перебираем все цифры между собой, однако помним, что числа не могут начинаться с нуля. Также проверяем, что все три числа разные.

Псевдокод

Функция найти_трехзначные_числа(изначальные_цифры, цифры_первой_позиции):  
    результат = список()  
  
    Для первого_числа в цифрах_первой_позиции:  
        Для второго_числа в изначальных_цифрах:  
            Для третьего_числа в изначальных_цифрах:  
                если первое_число не равно второму_числу и первое_число не равно третьему_числу и второе_число не равно третьему числу:  
                    число = первое_число * 100 + второе_число * 10 + третье_число  
                    добавить число в результат  
  
    вернуть результат

Реализация на Python

Аннотация:  
generate_unique_three_digit_numbers - функция для генерации всех возможных уникальных трёхзначных чисел  
digits - массив цифр, которые можно поставить на первую позицию  
digits_0 - массив цифр, из которых надо составить трёхзначное число  
result - итоговый список трёхзначных чисел  
first_digit - число, которое будет стоять на первой позиции  
second_digit - число, которое будет стоять на второй позиции   
third_digit - число, которое будет стоять на третьей позиции 

def generate_unique_three_digit_numbers(digits, digits_0):  
    result = []  
    for first_digit in digits:  
        for second_digit in digits_0:  
            for third_digit in digits_0:  
                if first_digit != second_digit and first_digit != third_digit and second_digit != third_digit:  
                    data = first_digit * 100 + second_digit * 10 + third_digit  
                    result.append(data)   
    return result

Олимпиадная реализация на C++

Аннотация:  
typedef - переопределение имени типа данных  
generate_unique_three_digit_numbers - функция для генерации всех возможных уникальных трёхзначных чисел  
digits - массив цифр, которые можно поставить на первую позицию  
digits_0 - массив цифр, из которых надо составить трёхзначное число  
result - итоговый список трёхзначных чисел  
d1 - число, которое будет стоять на первой позиции  
d2 - число, которое будет стоять на второй позиции   
d3 - число, которое будет стоять на третьей позиции 

typedef vector<int> vi;  
  
vi generate_unique_three_digit_numbers(  
    const vi& digits, const vi& digits_0) {  
  vector<int> res;  
  for (int d1 : digits) {  
    for (int d2 : digits_0) {  
      for (int d3 : digits_0) {  
        if (d1 != d2 and d1 != d3 and d2 != d3) {  
          int data = d1 * 100 + d2 * 10 + d3;  
          result.push_back(data);  
        }  
      }  
    }  
  }  
  return res;  
}

Продуктовая реализация на C++

Аннотация:  
generate_unique_three_digit_numbers - функция для генерации всех возможных уникальных трёхзначных чисел  
digits - массив цифр, которые можно поставить на первую позицию  
digits_0 - массив цифр, из которых надо составить трёхзначное число  
result - итоговый список трёхзначных чисел  
first_digit - число, которое будет стоять на первой позиции  
second_digit - число, которое будет стоять на второй позиции   
third_digit - число, которое будет стоять на третьей позиции 

using namespace std;  
  
vector<int> generate_unique_three_digit_numbers(  
    const vector<int>& digits, const vector<int>& digits_0) {  
  vector<int> result;  
  for (int first_digit : digits) {  
    for (int second_digit : digits_0) {  
      for (int third_digit : digits_0) {  
        if (first_digit != second_digit and first_digit != third_digit and second_digit != third_digit) {  
        int data = first_digit * 100 + second_digit * 10 + third_digit;  
        result.push_back(data);  
        }  
      }  
    }  
  }  
  return result;  
}