Комбинаторные задачи на программирование
статья по информатике и икт по теме

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

(автор статьи Курилов Игорь Анатольевич)

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

…

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=nm (формула получена путем убывающего факториала см. Википедия)

Пример: составим комбинации (размещения) из 2 цифр длиной 8 цифр – 28=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 вида комбинаций

program kombin;

  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 i<>j 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.

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

Литература:

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