А.Г.Баханский © Программирование – вторая грамотность. А.П.Ершов Комбинаторные алгоритмы

Оглавление Генерация всех подмножеств заданного множества Генерация разбиения заданного множества на k непересекающихся подмножеств Генерация перестановок из n различных элементов Генерация всевозможных сочетаний из n элементов по к

Генерация всех подмножеств заданного множества Задано множество, содержащее n элементов (например, m[1..n]). Сгенерировать всевозможные его подмножества.

Утверждение Множество, содержащее n элементов имеет 2 n подмножеств, включая пустот подмножество и само множество. Обоснование Каждый элемент множества может входить в подмножество (флаг – 1), либо не входить (флаг - 0). Всего флагов n. Имеем 2 n разных вариантов набора флагов – т.е. вариантов подмножеств.

Переменные алгоритма n – число элементов множества m[1..n] – элементы множества a[1..n+1] – таблица флагов i, j – вспомогательные переменные для организации циклов

program podmnojestva; uses crt; const nmax=32; var a:array[1..nmax+1] of byte; n,i:integer; procedure print; var i:integer; begin for i:=1 to n do write(a[i]); writeln; end; begin clrscr; write('Число элементов множества '); readln(n); writeln('Коды подмножеств' ); i:=1; while i<=n do begin print; i:=1; while a[i]=1 do begin a[i]:=0; inc(i); end; inc(a[i]); end; readkey; end.

program podmn2f; uses crt; const nmax=32; var a:array[1..nmax+1] of byte; m:array[1..nmax] of string; n,i:integer; procedure print; var i:integer; p:boolean; begin p:=false; write('{'); for i:=1 to n do if a[i]=1 then if p then write(', ',m[i]) else begin p:=true; write(m[i]) end; writeln('}'); end; begin clrscr; write('Число элементов множества '); readln(n); writeln('Вводите элементы множества'); for i:=1 to n do readln(m[i]); writeln('========================'); i:=1; while i<=n do begin print; i:=1; while a[i]=1 do begin dec(a[i]); inc(i); end; a[i]:=1; end; readkey; end.

Задача Имеется куча из k камней, масса каждого из которых выражается натуральным числом. Разбить эту кучу на две так, чтобы их массы отличались друг от друга как можно меньше.

program dvekuhi; uses crt; const nmax=32; var m:array[1..nmax] of integer; a,la:array[1..nmax] of byte; mm,mm1,n,i,j,tr,lr:integer; begin clrscr; write('Число камней ');readln(n); mm:=0; writeln('Вводите массы камней'); for i:=1 to n do begin read(m[i]);inc(mm,m[i]); end; lr:=abs(mm-2*m[n]); a[n]:=1;la[n]:=1; mm1:=m[n]; i:=1; while i<n do begin i:=1; while a[i]=1 do begin dec(a[i]); dec(mm1,m[i]); inc(i); end; a[i]:=1; inc(mm1,m[i]); tr:=abs(mm-2*mm1); if tr<lr then begin lr:=tr; for j:=1 to n do la[j]:=a[j]; end; writeln('Лучшая разность ',lr); for i:=1 to 2 do begin write(i,' куча '); for j:=1 to n do if la[j]=i-1 then write(m[j],' '); writeln; end; readkey; end.

Задача Товар стоит N рублей (Nнатуральнот число). Покупатель и кассир имеют неограниченнот количество монет (купюр) различного достоинства (1, 2, 5, 10, 20, 50, 100, 200, 500, 1000, 5000, 10000, 50000, рублей). Предложить варианты расчета, в котором участвует минимальнот количество монет (купюр). На входе программы: число N. На выходе программы: варианты расчета. Пример Вход Выход 29124= – – =50000–10000–10000– – =50000–10000–10000– = –

program dengi; uses crt; var k:array[1..14] of longint=(100000,50000,10000,5000,1000,500,200,100,50,20,10,5,2,1); a:array[1..15] of shortint; n,nn,p,tkk,lkk:longint; i,j:integer; procedure print; var i,j:integer; f:boolean; znak:char; begin nn:=n;f:=false;znak:='+;write(n,'='); for i:=1 to 14 do begin p:=nn div k[i]+a[i]; nn:=abs(nn-p*k[i]); for j:=1 to p do begin if f then write(znak); write(k[i]);f:=true; end; if a[i]=1 then if znak='+' then znak:='-' else znak:='+'; end; writeln; end;

begin clrscr; write('Стоимость покупки ');readln(n); lkk:=n+1;i:=1; while i<14 do begin tkk:=0; nn:=n; for j:=1 to 13 do begin p:=nn div k[j]+a[j]; tkk:=tkk+p; nn:=abs(nn-p*k[j]); end; tkk:=tkk+nn; if tkk<lkk then lkk:=tkk; i:=1; while a[i]=1 do begin dec(a[i]); inc(i); end; inc(a[i]); end; writeln('Меньшее число купюр ',lkk);

for i:=1 to 14 do a[i]:=0; i:=1; while i<14 do begin tkk:=0; nn:=n; for j:=1 to 13 do begin p:=nn div k[j]+a[j]; tkk:=tkk+p; nn:=abs(nn-p*k[j]); end; tkk:=tkk+nn; if tkk=lkk then print; i:=1; while a[i]=1 do begin dec(a[i]); inc(i); end; inc(a[i]); end; readkey; end.

Генерация разбиения заданного множества на k непересекающихся подмножеств Задано множество, содержащее n элементов (например, m[1..n]). Сгенерировать всевозможные его разбиения на k непересекающихся подмножеств.

Утверждение Множество, содержащее n элементов разбивается на k непересекающихся подмножеств k n способами. Обоснование Каждый элемент множества может входить в первот подмножество (флаг – 0), либо во второт (флаг - 1),..., либо в последнее (k-от) (флаг – k-1). Всего флагов n. Имеем k n разных вариантов набора флагов – т.е. вариантов разбиения.

Переменные алгоритма n – число элементов множества k – число подмножеств m[1..n] – элементы множества a[1..n+1] – таблица флагов i, j – вспомогательные переменные для организации циклов

program podmnk; uses crt; const nmax=32; var a:array[1..nmax+1] of byte; n,k,i:integer; procedure print; var i:integer; begin for i:=1 to n do write(a[i]); writeln; end; begin clrscr; write('Число элементов множества '); readln(n); write('Число подмножеств '); readln(k); writeln('Коды подмножеств '); i:=1; while i<=n do begin print; i:=1; while a[i]=k-1 do begin a[i]:=0; inc(i); end; inc(a[i]); end; readkey; end.

Задача Задача Имеется 8 гирь в 1, 2, 4, 8, 16, 32, 64, 128 грамм. Требуется взвесить груз N граммов (N – натуральнот число), используя минимальнот количество гирь. Гири разрешается класть на обе чашки. Например, груз 60 грамм можно взвесить, положив его на одну чашку весов вместе с гирей в 4 грамма, а на другую чашку – гирю 64 грамма (60 = 64 – 4).

program gruz; uses crt; var m:array[1..8] of integer=(1,2,4,8,16,32,64,128); a,la:array[1..9] of integer; n,nn,lk,tk,i,j:integer; begin clrscr; write('Сколько взвешиваем '); readln(n);

lk:=9; i:=1; while i 1 then inc(tk); if tk<lk then begin lk:=tk; for j:=1 to 8 do la[j]:=a[j]; end; end; end;

if lk<9 then begin write(n,'='); for i:=1 to 8 do begin if la[i]=0 then write('-',m[i]); if la[i]=2 then write('+',m[i]); end; writeln; end else writeln('Груз ',n,' взвесить невозможно!'); readkey; end.

Задача (районная олимпиада года, задание 3) Задача (районная олимпиада года, задание 3) Вася Пупкин стал выписывать в порядке возрастания натуральные числа, в записи которых используются только цифры 1, 3, 7: 1, 3, 7, 11,13, 17, 31, 33, 37, …, стремясь узнать, какот число будет записано 10-м. Вероятно, его заинтересуют потом и числа стоящие на других местах. Помогите ему. Составьте программу, которая по номеру места (целот) находит нужнот число. Например: Место 10 Число 71 Ваша программа должна * запросить номер места (целот); * найти и сообщить число, записаннот с помощью цифр 1, 3, 7, стоящее на этом месте.

program chislo; uses crt; var i,n,k:integer; s:string; begin clrscr; writeln('Какот место Вас интересует '); readln(n); k:=1; s:='1'; while (k<n) do begin s:='0'+s; i:=length(s); while (s[i]='7') do begin s[i]:='1'; i:=i-1 end; case (s[i]) of '0': s[i]:='1'; '1': s[i]:='3'; '3': s[i]:='7'; end; if (s[1]='0') then delete(s,1,1); k:=k+1; end; writeln('Искомот число ',s); readkey; end.

program chislo; uses crt; var n,nn:longint; c:integer; s:string; begin clrscr; writeln('Какот место Вас интересует '); readln(n); nn:=n; s:=''; while (nn>0) do begin c:=nn mod 3; if (c=0) then c:=3; case (c) of 1: s:='1'+s; 2: s:='3'+s; 3: s:='7'+s; end; nn:=(nn-c) div 3; end; writeln('Искомот число ',s); readkey; end.

Генерация перестановок из n различных элементов Задано множество, содержащее n элементов (например, m[1..n]). Сгенерировать всевозможные перестановки этих элементов.

Утверждение Число перестановок из n элементов равно n!. Обоснование Первый элемент перестановки может быть иметь n разных значений. Второй после того как выбран первый (n-1) значение, третий – (n-2), …, последний одно. Всего всевозможных перестановок n × (n-1) × (n-2) × … × 1 = n!.

Переменные алгоритма n – число элементов m[1..n] – элементы a[1..n] – указатель – номер элемента в массиве i, j, r, j0 – вспомогательные переменные

program perest; uses crt; const nmax=32; var n,i,j,j0:integer; a:array[1..nmax] of integer; procedure print; var i:integer; begin for i:=1 to n do write(a[i],' '); writeln; end; procedure obmen(var a,b:integer); var r:integer; begin r:=a;a:=b;b:=r; end;

begin clrscr; write('Число элементов '); readln(n); writeln('Перестановки '); for i:=1 to n do a[i]:=i; print; repeat if a[i]<a[i+1] then begin j:=n; while a[j]<a[i] do dec(j); obmen(a[i],a[j]); j0:=(n+i) div 2; for j:=i+1 to j0 do obmen(a[j],a[n+i+1-j]); print; i:=n-1; end else dec(i); until i=0; readkey; end.

Генерация всевозможных сочетаний из n элементов по к Задано множество, содержащее n элементов (например, m[1..n]) и число k. Сгенерировать всевозможные сочетания из n элементов по k.

Утверждение Число всевозможных сочетаний из n элементов по k равно C k n. Обоснование Всего первый элемент может быть иметь n разных значений. второй после того как выбран первый (n-1) значение, третий – (n-2), …, последний (n-k+1). Всего всевозможных размещений n × (n-1) × (n-2) × … × (n-k+1)! = n!/k!= C k n.

Переменные алгоритма n – число элементов K – число элементов в сочетании m[1..n] – элементы a[1..n] – указатель – номер элемента в массиве i, j – вспомогательные переменные

program sohetan; uses crt; const nmax=32; var a:array[1..nmax] of integer; n,k,i,j:integer; procedure print; var i:integer; begin for i:=1 to k do write(a[i],' '); writeln; end; begin clrscr; write('Сочетания из скольких элементов '); readln(n); write('По скольку '); readln(k); writeln(Сочетания '); for i:=1 to k do a[i]:=i; print;

i:=k; repeat if a[i]<n-k+i then begin inc(a[i]); for j:=i+1 to k do a[j]:=a[j-1]+1; print; i:=k; end else dec(i); until i=0; readkey; end.

И это еще не все, но... КОНЕЦКОНЕЦ