Главные вкладки

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

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

    Скачать:


    Предварительный просмотр:

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

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

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

    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. Википедия


    По теме: методические разработки, презентации и конспекты

    Практико-ориентированный проект на тему "Роль комбинаторных задач в обучении математики"

    Рассматривается роль комбинаторики в школьной теории вероятностей. Приведены примеры решения задач по комбинаторики...

    Практико-ориентированный проект на тему "Роль комбинаторных задач в обучении математики"

    Рассматривается роль комбинаторики в школьной теории вероятностей. Приведены примеры решения задач по комбинаторики...

    Практико-ориентированный проект на тему "Роль комбинаторных задач в обучении математики"

    Рассматривается роль комбинаторики в школьной теории вероятностей. Приведены примеры решения задач по комбинаторики...

    Обобщение опыта "Развитие логического мышления у учащихся 6 класса через решение комбинаторных задач на уроках математики"

    Данный материал представляет обобщение опыта  по решению комбинаторных задач в 6 классе. Также представлены разработки уроков по теме "Решение комбинаторных задач"...

    Комбинаторные задачи на нахождение числа перестановок из n элементов, сочетаний и размещений из n элементов по k (k ≤ n). 9 класс

    В настоящее время элементы статистики и теории вероятностей включены в государственный стандарт основной школы. Решение комбинаторных задач способствует развитию логического мышления, расширению круго...

    Комбинаторные задачи на нахождение числа размещений из n элементов по k (k ≤ n). 9 класс

    В настоящее время элементы статистики и теории вероятностей включены в государственный стандарт основной школы. Решение комбинаторных задач способствует развитию логического мышления, расширению круго...

    Комбинаторные задачи на нахождение числа перестановок из n элементов. 9 класс

    В настоящее время элементы статистики и теории вероятностей включены в государственный стандарт основной школы. Решение комбинаторных задач способствует развитию логического мышления, расширению круго...