←  Комбинаторика

олимпиадники-информатики

»

Сочетание с повторением (нестандартный алг...

Я. Илья фотография Я. Илья 15 янв 2012

Нестандартный алгоритм сочетания с повторением. В состав обычного алгоритма входит сочетание ноликов ( перегородок ) и единичек. Этот алгоритм несколько иной.
Вот как его можно составить:
Само название "сочетание с повторением" говорит само за себя - это тоже самое, что и сочетание, но элементы могут повторяться. Таким образом, если взять сочетание 2 места по 3 элемента получим:
12
13
23
А если взять сочетание с повторением с таким параметром, то получим:
11
12
13
22
23
33
Вот сам код:
var n,m,i,j:longint;a,t:array[0..1000]of longint;
Begin
 
        read(n,m);
        {ввод массива элементов в t}
        for i:=1 to m do //заполняем начальный уровень
        a[i]:=1;
        while a[0]=0 do //повторяем, пока укладываемся в м элементов
        begin
        for i:=1 to m do //выводим результат
        write(t[a[i]]);
        writeln;
        j:=m; 
        while (j>0)and(a[j]=n) do //ищем с конца позицию меньше н
        j:=j-1;
        a[j]:=a[j]+1; //делаем её больше
        for i:=j+1 to m do //заполняем до конца лучшим случаем, которым можно заполнить
        a[i]:=a[j];
        end;
End.
Ответить