Приближалась зима, и Хома с Сусликом решили запастись горохом. Весь день они бегали в амбар и таскали по несколько стручков: Хома по четыре, а Суслик по два. К вечеру они пересчитали все стручки, что они натаскали, и задумались, как теперь этот горох делить. Хома утверждал, что если он за раз тащил в два раза больше, чем Суслик, то и гороха ему должно достаться в два раза больше. Суслик на это резонно возражал, что, во-первых, скорость у Хомы заметно меньше, чем у Суслика, а, во-вторых, кто его знает, может Хома всего раз-два сбегал, а остальное время бездельничал…
Помогите друзьям хоть немного разобраться в этой сложной ситуации. Определите все возможные варианты того, сколько стручков притащил Суслик, а сколько Хома.
Входные данные
В первой строке натуральное четное число M – количество украденных стручков, 2 ≤ M ≤ 1000.
Выходные данные
Все возможные сочетания количеств стручков, принесенных Сусликом и Хомой по одному сочетанию в строке. Каждое сочетание представляет собой два целых неотрицательных числа через пробел: первое число – количество стручков, принесенных Сусликом, второе – принесенных Хомой. Сочетания упорядочить по убыванию первого числа.
Тесты
| Входные данные | Выходные данные | |
| 6 | \\ 6 \; 0 \\ 2 \; 4 | |
| 11 | \\ 11\;0 \\ 7\;4 \\ 3\;8 | |
| 18 | \\ 18\;0 \\ 14\;4 \\ 10\;8 \\ 6\;12 \\ 2\;16 | |
Код программы
#include using namespace std ; int main () { int a , b = 0 ; cin >> a ; while (a >= 0 ) { cout << a << " " << b << "\n" ; a -= 4 ; b += 4 ; return 0 ; |
Решение задачи
Пусть a — количество стручков, принесенных Хомой и b — количество стручков, принесенных Сусликом. Так как по условию задачи Хома таскал только по четыре стручка, мы будем считать a = a-4 и b = b + 4, чтобы таким образом перебрать все возможные сочетания количеств стручков, принесенных Сусликом и Хомой. Также воспользуемся циклом while , который будет повторять действие, описанное выше, до тех пор, пока a \geq 0. В ответе выводим все возможные сочетания количеств стручков, принесенных друзьями по одному в строке, упорядоченные по убыванию первого числа.
Рассмотрим задачу подсчета числа выборок из данного множества в общем виде. Пусть имеется некоторое множество N , состоящее из n элементов. Любое подмножество, состоящее из m элементов можно рассматривать без учета их порядка, так и с его учетом, т.е. при изменении порядка переходим к другой m – выборке.
Сформулируем следующие определения:
Размещения без повторения
Размещением без повторения из n элементов по m N , содержащее m различных элементов .
Из определения следует, что два размещения отличаются друг от друга, как элементами, так и их порядком, даже если элементы одинаковы.
Теорема 3 . Число размещений без повторения равно произведению m сомножителей, наибольшим из которых является число n . Записывают:
Перестановки без повторений
Перестановками из n элементов называются различные упорядочения множества N .
Из этого определения следует, что две перестановки отличаются только порядком элементов и их можно рассматривать как частный случай размещений.
Теорема 4 . Число различных перестановок без повторений вычисляется по формуле
Сочетания без повторений
Сочетанием без повторения из n элементов по m называется любое неупорядоченное подмножество множества N , содержащее m различных элементов.
Из определения следует, что два сочетания различаются только элементами, порядок не важен.
Теорема 5 . Число сочетаний без повторений вычисляют по одной из следующих формул:
Пример 1 . В комнате 5 стульев. Сколькими способами можно разместить на них
а) 7 человек; б) 5 человек; в) 3 человека?
Решение:
а) Прежде всего надо выбрать 5 человек
из 7 для посадки на стулья. Это можно
сделать
способом. С каждым выбором конкретной
пятерки можно произвести
перестановок местами. Согласно теореме
умножения искомое число способов посадки
равно.
Замечание: Задачу можно решать, используя только теорему произведения, рассуждая следующим образом: для посадки на 1-й стул имеется 7 вариантов, на 2-й стул-6 вариантов, на 3-й -5, на 4-й -4 и на 5-й -3. Тогда число способов посадки 7 человек на 5 стульев равно . Решения обоими способами согласуются, так как
б) Решение очевидно
-
в)
- число выборов занимаемых стульев.
- число размещений
трех человек на трех выбранных стульях.
Общее число выборов равно .
Не трудно проверить
формулы
;
;
Число всех подмножеств множества, состоящего из n элементов.
Размещения с повторением
Размещением с повторением из n элементов по m называется всякое упорядоченное подмножество множества N , состоящее из m элементов так, что любой элемент ожжет входить в это подмножество от 1 до m раз, либо вообще в нем отсутствовать .
Число
размещений с повторением обозначают
и вычисляют по формуле, представляющей
собой следствие из теоремы умножения:
Пример 2
.
Пусть дано множество из трех букв N
= {a,
b,
c}.
Назовем словом любой набор из букв,
входящих в это множество. Найдем
количество слов длиной 2, которые можно
составить из этих букв:
.
Замечание:
Очевидно, размещения с повторением
можно рассматривать и при
.
Пример 3 . Требуется из букв {a, b}, составить всевозможные слова длиной 3. Сколькими способами это можно сделать?
Ответ
:
Все N элементов, и ни один не повторяется, то это задача о количестве перестановок. Решение можно найти простым . На первом месте в ряду может стоять любой из N элементов, следовательно, получается N вариантов. На втором месте - любой, кроме того, который уже был использован для первого места. Следовательно, для каждого из N уже найденных вариантов есть (N - 1) вариантов второго места, и общее количество комбинаций становится N*(N - 1).
Это же можно повторить для остальных элементов ряда. Для самого последнего места остается только один вариант - последний оставшийся элемент. Для предпоследнего - два варианта, и так далее.
Следовательно, для ряда из N неповторяющихся элементов возможных перестановок равно произведению всех целых от 1 до N. Это произведение называется факториалом числа N и обозначается N! (читается «эн факториал»).
В предыдущем случае количество возможных элементов и количество мест ряда совпадали, и их число было равно N. Но возможна ситуация, когда в ряду меньше мест, чем имеется возможных элементов. Иными словами, количество элементов в выборке равно некоторому числу M, причем M < N. В этом случае задача определения количества возможных комбинаций может иметь два различных варианта.
Во-первых, может потребоваться сосчитать общее количество возможных способов, которыми можно выстроить в ряд M элементов из N. Такие способы называются размещениями.
Во-вторых, исследователя может интересовать число способов, которыми можно выбрать M элементов из N. При этом порядок расположения элементов уже не важен, но любые два варианта должны различаться между собой хотя бы одним элементом. Такие способы называются сочетаниями.
Чтобы найти количество размещений по M элементов из N, можно прибегнуть к такому же способу рассуждений, как и в случае с перестановками. На первом месте здесь по-прежнему может стоять N элементов, на втором (N - 1), и так далее. Но для последнего места количество возможных вариантов равняется не единице, а (N - M + 1), поскольку, когда размещение будет закончено, останется еще (N - M) неиспользованных элементов.
Таким образом, число размещений по M элементов из N равняется произведению всех целых чисел от (N - M + 1) до N, или, что то же самое, частному N!/(N - M)!.
Очевидно, что количество сочетаний по M элементов из N будет меньше количества размещений. Для каждого возможного сочетания есть M! возможных размещений, зависящих от порядка элементов этого сочетания. Следовательно, чтобы найти это количество, нужно разделить число размещений по M элементов из N на N!. Иными словами, количество сочетаний по M элементов из N равно N!/(M!*(N - M)!).