Комбинаторные задачи на программирование

Категория: Информатика.

Комбинаторные задачи на программирование

С учениками на уроках информатики мы сталкиваемся с задачами, где нужно найти количество комбинаций чего-либо. Начинаем всегда с самой простой задачи, когда надо найти и вывести на экран все комбинации произведений однозначных чисел, то есть таблицу умножения (для этого достаточно хорошо понимать вложенные циклы):

…

for i:=2 to 9 do

for j:=2 to 9 do

writeln(i,’ * ‘,j,’ = ‘,i*j);

…

или изменим параметр вложенного цикла и получим вывод комбинаций без повторений:

…

for i:=2 to 9 do

for j:=i to 9 do

writeln(i,’ * ‘,j,’ = ‘,i*j);

…

Уже из первого примера понятно, что найти количество комбинаций и вывести их на экран – это не одно и тоже.

К моменту изучения вложенных циклов и перебора с таблицей умножения мои ученики уже знают, стандартный алгоритм и программу нахождения факториала:

…

read(n);

p:=1;

for i:=1 to n do

p:=p*i;

writeln(’n! = ‘,p);

…

Поэтому найти количество перестановок, размещений, сочетаний найти не сложно, надо только знать формулы из комбинаторики, которые рассмотрим ниже и немного подумать какую формулу в данной задаче применить.

а) перестановки без повторений – комбинаторные соединения, которые могут отличаться друг от друга лишь порядком входящих в них элементов p=n!

Пример: из цифр 1,2,3 можно составить p=3!=1*2*3=6 комбинаций

123, 132, 213, 231, 312, 321.

б) перестановки с повторениями комбинаторные соединения, в которых среди образующих элементов имеются одинаковые p=n!/(m1!*m2!*…)

Пример: из 3 цифр 1,1,2 – две единицы p=3!/(2!*1!)=6/2=3

11, 12, 22

в) Размещения без повторений – комбинаторные соединения, составленные из n элементов по m. При этом два соединения считаются различными, если они либо отличаются друг от друга хотя бы одним элементом, либо состоят из одних и тех же элементов, но расположенных в разном порядке. . p=m!/(m-n)!

Пример: из 4 цифр 0,1,2,3 составим размещения без повторений из 2-х цифр p=4!/(4-2)!=24/2=12

01, 02, 03, 10, 12, 13, 20, 21, 23, 30, 31, 32

Примером из жизни может быть количество игр проводимых футболистами в группе на чемпионате страны (в 2 круга).

г) Размещения с повторениями – комбинаторные соединения, составленные из n элементов по m. При этом каждый из n элементов может содержаться сколько угодно раз или вообще отсутствовать. p=n^m (формула получена путем убывающего факториала см. Википедия)

Пример: составим комбинации (размещения) из 2 цифр длиной 8 цифр – 2⁸=256,

00000000, 00000001, …, 11111110, 11111111 (наверное, вспомнили ребята, где применяется эта формула в информатике)

Примером из жизни может быть количество символов в алфавите или палитра изображения при кодировании текстовой или графической информации определенных количеством бит (длина кода).

д) Сочетания без повторений – комбинаторные соединения из n элементов по m, составленные из этих элементов и отличающиеся друг от друга только составом. p=m!/(m-n)!n!

Пример: из 4 цифр 0,1,2,3 составим сочетания без повторений из 2-х цифр p=4!/(4-2)!2!=24/4=6

01, 02, 03, 12, 13, 23

Примером из жизни может быть количество игр проводимых футболистами в группе на чемпионате мира.

е) Сочетания с повторениями – комбинаторные соединения из n элементов по m, составленные из этих элементов без учета порядка с возможностью многократного повторения предметов. p=(n+m-1)!/m!(n-1)!

Пример: из 4 цифр 0,1,2,3 составим сочетания с повторениями из 2-х цифр p=(4+2-1)!/4!(2-1)!=120/12=10

00, 01, 02, 03, 11, 12, 13, 22, 23, 33

Примером из жизни может быть количество молекул составленных из 2-х атомов, причем имеются атомы 4-х видов.

А как сделать вывод всех комбинаций (в вышеописанных ситуациях)? Здесь формулы не нужны, а всё можно сделать вложенными циклами (по крайней мере, для простых школьных задач). Мы меняем параметр и получаем все вышеописанные ситуации (ниже рассмотрим несколько примеров):

Задача 1. ДЕМО-программа показывает 4 вида комбинаций

programkombin;

const n=4;

var a:array[1. . n] of integer; b:array[1. . n] of string;

i,j:integer; q,w:byte;

begin

for i:=1 to n do a[i]:=i-1; w:=64; for i:=1 to n do b[i]:=chr(w+i);

writeln('Выберите, что хотите получить:');

writeln('1:размещения с повторениями');

writeln('2:размещения без повторений');

writeln('3:сочетания с повторениями');

writeln('4:сочетания без повторений');

readln(q);

case q of

1:for i:=1 to n do

for j:=1 to n do begin write(a[i],a[j],' '); writeln(b[i],b[j]); end;

2:for i:=1 to n do

for j:=1 to n do if ij then begin write(a[i],a[j],' '); writeln(b[i],b[j]); end;

3:for i:=1 to n do

for j:=i to n do begin write(a[i],a[j],' '); writeln(b[i],b[j]); end;

4:for i:=1 to n-1 do

for j:=i+1 to n do begin write(a[i],a[j],' '); writeln(b[i],b[j]); end;

end;

readln;

end.

Задача 2. Сколькими способами можно набрать n рублей, если существуют монеты 1, 2, 5, 10 и 50 рублей.

var n,i,j,k,l,m,s:byte;

begin

readln(n);

for i:=0 to n do

for j:=0 to n div 2 do

for k:=0 to n div 5 do

for l:=0 to n div 10 do

for m:=0 to n div 50 do

if i+j*2+k*5+l*10+m*50=n then begin

writeln('1*',i,'+2*',j,'+5*',k,'+10*',l,'+50*',m,'=',n);

s:=s+1; end;

writeln('Комбинаций ',s);

readln;

end.

Задача 3. Сколько можно составить слов из 4 букв, при этом алфавит состоит из 20 букв

const n=20;

a:array[1. . n] of string=('а','б','в','г','д','е','ж','з','и','к',

'л','м','н','о','п','р','с','т','у','ф');

var i,j,k,l:integer; s:real;

begin

for i:=1 to n-3 do

for j:=i+1 to n-2 do

for k:=j+1 to n-1 do

for l:=k+1 to n do begin

writeln(a[i]:2,a[j]:2,a[k]:2,a[l]:2);

s:=s+1;

end;

writeln(s*s*s*s:20:0);

readln;

end.

Вывод: Знания основ комбинаторики и умение их применять в программировании позволяет решить множество задач из математики, информатики и просто задач из повседневной жизни, с которыми мы сталкиваемся.

Литература:

l Лисичкин В. Т. , Соловейчик И. Л. Математика – Москва: Высшая школа, 1991. – 480 c.

l Википедия

И. А. Курилов, МБОУ СОШ №9, г. Нерчинск, Забайкальский край

Метки: Информатика

• Назад
• Вперед