Как сделать перебор чисел c
Добавил пользователь Дмитрий К. Обновлено: 05.10.2024
В данной статье будет рассмотрено два алгоритма перебора всех возможных вариантов. Для начала придумаем задачу, на примере которой будем рассматривать алгоритмы. Пусть у нас имеется множество S, состоящее из 4-х элементов: * - + /, и наша задача - перебрать все возможные комбинации из 3-х элементов, используя элементы множества S. Причем, выбираемые элементы могут повторяться. Например: "+*+". Первый алгоритм Сопоставим каждому элементу число, начиная с 0. * - 0 - - 1 + - 2 / - 3 Можно догадаться, что нужно перебрать элементы от 0 0 0 до 3 3 3: 0 0 0 0 0 1 0 0 2 0 0 3 0 1 0 0 0 1 . . 3 2 3 3 3 0 3 3 1 3 3 2 3 3 3 Всего получится 64 варианта (4 * 4 * 4 = 64) Далее нужно провести обратную операцию, сопоставив числу элемент множества S. Например, набору 2 0 2 соответствует +*+ В алгоритме мы будем имитировать сложение в столбик, каждый раз прибавляя единицу, чтобы получить новый вариант. Реализация:
Здравствуйте!
F как сделать так чтобы прогонял не все варианты, а по одному разу только осмысленные используя только по одному уникальному слову в одной строке со словами Мама Мыла Раму, например:
МамаМылаРаму
РамуМылаМама
МамаРамуМыла
РамуМамаМыла
и т.д всего 6
В комбинаторике сочетанием из N различных элементов по M называется набор M элементов, выбранных из множества N элементов. Такие наборы отличаются только вхождением в них M определенных элементов, порядок следования элементов в таком наборе не важен. Наборы, отличающиеся только порядком следования элементов (но не составом), считаются одинаковыми, и этим сочетания отличаются от размещений.
Сочетания без повторений
Задача : Найти все возможные сочетания без повторений из множества элементов по 2.
Существуют следующие сочетания:
1: 1 2
2: 1 3
3: 2 3
Количество возможных сочетаний без повторений из N элементов по M можно определить по формуле (N≥M):
что в M! раз меньше соответствующего количества размещений без повторений (поскольку сочетания без повторений не зависят от порядка следования элементов).
Рассмотрим задачу получения всех сочетаний для чисел 1…N по M.
Реализация на С++
Сочетания с повторениями
Сочетаниями с повторениями называются наборы по M элементов, в которых каждый элемент множества N может участвовать несколько раз. При этом на соотношение значений M и N не накладывается никаких ограничений, а общее количество сочетаний с повторениями составляет
Примером такой задачи может служить выбор M открыток из N всеми возможными способами.
Для генерации сочетаний с повторениями воспользуемся решением для генерации размещений с повторениями, рассмотренным в этой статье.
Реализация на С++
При решении задачи возникает несколько ситуаций, в которых нам нужно перебирать все возможные комбинации массива. В этой статье мы обсудим метод использования битов для этого.
Для пояснения рассмотрим следующий вопрос:
Given an array b[] = . The tasks is to check if there exists any combination of elements of this array whose sum of elements is equal to k = 6.
Решение с использованием битовых операций :
Поскольку в этом массиве есть 3 элемента, следовательно, нам нужно 3 бита для представления каждого из чисел. Бит, установленный как 1, соответствующий элементу, означает, что он включен при вычислении суммы, а не если он равен 0.
Следовательно, диапазон, необходимый для доступа ко всем этим битам, равен 0 — 7. Мы перебираем каждый бит каждой из возможных комбинаций и проверяем для каждой комбинации, равна ли сумма выбранных элементов требуемой сумме или нет.
Примеры:
Ниже приведена реализация вышеуказанного подхода:
// C ++ программа для перебора всех возможных
// комбинации элементов массива
using namespace std;
// Функция для проверки, если любая комбинация
// элементы массива суммируются в k
- Простейшие задачи на перебор – это задачи на поиск решения в одномерном массиве (например, найти элемент с заданным свойством). Сложность таких задач пропорциональна количеству элементов в массиве $N$.
- Следующие задачи на перебор – поиск пар элементов либо из одного массива, либо из двух разных массивов. При решении таких задач, как правило, используется вложенный цикл, то есть их сложность пропорциональна $N^2$.
- Далее идет перебор троек элементов. Рассмотрим, например, следующую задачу.
Пример 6.1 . На плоскости разбросаны $N$ точек с координатами ($x^1$, $y^1$), ($x^2$, $y^2$), …,
($x^N$, $y^N$). Найти тройку точек, которые образуют треугольник с максимальной площадью.
Ясно, что при решении этой задачи необходимо использовать три вложенных цикла, таким образом, задача решается за $N^3$ шагов.
Для задания координат точек используем датчик случайных чисел.
INPUT "введите количество точек $N$>2 ", $N$
DIM x(1 TO n), y(1 TO n)
FOR i = 1 TO $N$ 'Задание экранных координат точек случайным образом
x(i) = INT(RND * 640)
y(i) = INT(RND * 480)
CIRCLE (x(i), y(i)), 2 ' Рисуем “ точки ”
a = SQR((x(i) -x(j)) ^ 2 + (y(i) - y(j)) ^ 2) ' Длины сторон
b = SQR((x(i) -x(k)) ^ 2 + (y(i) - y(k)) ^ 2)
c = SQR((x(k) - x(j)) ^ 2 + (y(k) - y(j)) ^ 2)
p = (a + b + c) / 2 ' Полупериметр
s = SQR(p * (p - a) * (p - b) * (p - c)) ' Формула Герона
IF s > smax THEN smax = s: im = i: jm = j: km = k
'Рисуем треугольник с максимальной площадью
LINE (x(im), y(im))-(x(jm), y(jm)), 2
LINE (x(im), y(im))-(x(km), y(km)), 2
LINE (x(km), y(km))-(x(jm), y(jm)), 2
PRINT " Площадь Номера точек "; im; jm; km
Однако этот перебор можно существенно сократить, если не повторять лишних проходов по циклам.
В последующих задачах будет показано, как ограничить число вариантов перебора, используя условия задачи, различные приемы и методы программирования.
2.3.1. Перебор с отсечениями
Пример 6.2 . Решить уравнение в целых числах: $x^1$ 4 + $x^2$ 4 + … + x15 4 = 2000
DIM SHARED p 4(1 TO 6) ‘массив четвертых степеней
DIM SHARED x (1 TO 15) ‘значения переменных $x^1$, …, $x^15$
DIM SHARED $N$‘номер переменной, значения которой перебираются в процедуре Find
FOR i = 1 TO 6: p 4( i ) = i ^ 4: NEXT ‘высчитываем один раз четвертые степени
PRINT "Поиск решения:" ‘запускаем поиск решения
CALL Find (2000, 6) ‘набираем сумму 2000, начиная с x 1=6
SUB Find ( sum , start ) ‘основная процедура поиска решения
‘ sum – сумма, которую осталось набрать
‘ start – значение, с которого начинать перебор
IF $N$ = 15 THEN ‘если значения всех 15 переменных заданы, то
IF sum = 0 THEN ‘если набрана нужная сумма,
FOR i = 1 TO 15: PRINT x(i); : NEXT ‘ печатаем решение
EXIT SUB ‘иначе возвращаемся к предыдущему шагу
IF sum > 0 THEN ‘ если сумма 4x степеней предыдущих
‘переменных не превосходит 2000,
FOR i = start TO 1 STEP –1 ‘перебираем значения очередной переменной
x ($N$) = I ‘фиксируем значение $N$-ой переменной и
CALL Find ( sum - p 4( i ), i ) ‘переходим к перебору значений $N$+1-ой
Приведенная программа ищет решения уравнения $x^1$ 4 + $x^2$ 4 + … + $x^15$ 4 = 2000 в натуральных числах методом перебора. Перебор является, пожалуй, одним из самых простых (по реализации), но, вместе с тем, самым трудоемким (по времени выполнения) из всех алгоритмов, поэтому при решении каждой конкретной задачи перебором возникает другая задача – сократить и оптимизировать перебор, иными словами, максимально уменьшить время, затрачиваемое компьютером на поиск решения.
Познакомимся с некоторыми возможными приемами сокращения перебора на данной конкретной задаче.
1) В первую очередь, надо правильно выбрать границы значений перебираемых величин. По условию задачи все переменные принимают натуральные значения, но ведь натуральных чисел бесконечно много! Однако, в данном примере совершенно очевидно, что, если решение уравнения существует, то все $x^1$, …, x 15 лежат в промежутке от 1 до 6, поскольку натуральные числа, большие 6, в четвертой степени дают значение уже превосходящее 2000 (7 4 = 2401 > 2000). Итак, в алгоритме все переменные перебираются в пределах от 1 до 6, что видно из вызова процедуры Find (2000, 6).
2) Далее, важным моментом при оптимизации является отсечение заведомо неверных ветвей перебора. Например, в данном примере, не имеет смысла продолжать поиск, если на некотором шаге сумма $x^1$ 4 + … + xn 4 уже превысила 2000. В приведенной программе это условие проверяется в строке if sum >0 then , т.е. дальнейший перебор осуществляется лишь в том случае, когда разность 2000 и ранее полученной суммы $x^1$ 4 + … + xn 4 положительна.
3) Следует избегать многократного выполнения одних и тех же операций в циклах и рекурсивных процедурах, если данные, используемые в этих циклах, могут быть подготовлены заранее. Так, в приведенном примере значения четвертых степеней чисел 1, 2, …, 6 вычислены один раз и занесены в массив констант: p 4 = (1, 16, 81, 256, 625, 1296). Подобный прием часто помогает избавиться от лишних вычислений, например, в алгоритмах, работающих с простыми числами, полезно бывает включить заранее найденные простые числа в текст программы, так же, в виде массива констант.
4) Кроме того, можно существенно ускорить перебор, если не рассматривать варианты, аналогичные (либо похожие) ранее рассмотренным. Так, в данной задаче решения уравнения определены с точностью до перестановки слагаемых, т.е., если найдено одно решение, то любая перестановка переменных в нем тоже будет являться решением. Поэтому, чтобы сократить поиск, не перебирая варианты, отличающиеся только перестановкой слагаемых, в процедуру Find был введен дополнительный параметр start – максимальное значение, которое может принимать очередная ($N$-ая) переменная. Благодаря этому гарантируется, что алгоритм будет рассматривать только те значения переменных, при которых $x^1$ ³ $x^2$ ³ … ³ $x^15$.
Пример 6.3 . Найти все решения уравнения в целых числах
МУХА+МУХА+МУХА=СЛОН
Используем факт, что C £ 9 и число не начинается с 0, тогда 1 £ M £ 3. Если М = 3, то У £ 2 (иначе имели бы справа от знака равенства четырехзначное число). Следовательно, число МУХА возможно из диапазона [1023, 3210]. Начинаем перебор.
DIM SHARED $N$ (1 TO 4) 'цифры для слова "МУХА"
$N$ (1) = 1: $N$ (2) = 0: $N$ (3) = 2: $N$ (4) = 3 'начальный набор цифр слова "МУХА"
Читайте также: