Комбинаторные задачи на программирование
статья по информатике и икт по теме
Комбинаторные задачи на программирование
Скачать:
Вложение | Размер |
---|---|
![]() | 44 КБ |
Предварительный просмотр:
Комбинаторные задачи на программирование
(автор статьи Курилов Игорь Анатольевич)
С учениками на уроках информатики мы сталкиваемся с задачами, где нужно найти количество комбинаций чего-либо. Начинаем всегда с самой простой задачи, когда надо найти и вывести на экран все комбинации произведений однозначных чисел, то есть таблицу умножения (для этого достаточно хорошо понимать вложенные циклы):
…
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.
Вывод: Знания основ комбинаторики и умение их применять в программировании позволяет решить множество задач из математики, информатики и просто задач из повседневной жизни, с которыми мы сталкиваемся.
Литература:
- Лисичкин В. Т., Соловейчик И. Л. Математика — Москва: Высшая школа, 1991. — 480 c.
- Википедия
По теме: методические разработки, презентации и конспекты
Презентация "Комбинаторные задачи", 9 класс
Презентация к заключительному уроку по теме "Комбинаторные задачи" в 9 классе. Имеется удобная таблица для различия задач на размещения, сочетания и перестановки и интерактивный тест....
Решение комбинаторных задач и задач по теории вероятности
Данную презентацию составил ученик 9 класса для проверки домашнего задания по изучаемой теме. Тексты задач взяты из сборника для подготовки к ГИА "Математика 9 класс" под редакцией Ф.Ф.Лысенко и С.Ю. ...
![](/sites/default/files/pictures/2012/01/07/picture-45673.jpg)
Комбинаторные задачи
Предмет: алгебра и начала анализаКласс: 11Учебник: Алгебра и начала анализа. 11 кл.: Учебник для общеобразоват. Учреждений / Ю.М. Колягин, Ю.В.Сидоров, М.В.Ткачёва, Н.Е. Фёдорова, М.И. Шабунин. ...
Решение комбинаторных задач
Данная презентация содержит задачи на применение знаний по теории вероятности. Будет полезна для работы с учащимися 9 классов....
Разработка урока по теме: "Правило умножения для комбинаторных задач"
Презентация урока, подготовка к контрольной работе....
![](/sites/default/files/pictures/2010/10/27/picture-4063.jpg)
Интерактивный задачник "Комбинаторные задачи" к учебному пособию Л.Л. Босовой "Занимательные задачи по информатике"
Данное учебное пособие можно использовать на уроках информатики, а также на дополнительных занятиях для работы с одаренными детьми....