1

Тема: Задача з комбінаторики в Pascal

Умова:
Задано натуральні числа n i r. Навести в лексикографічному порядку (в порядку зростання) всі r-сполучення з повтореннями з елементів множини {1, 2,..., n} та визначити їх кількість.

В режимі діалогу вводяться числа n i r (n i r не більше 10). Моя програма кількість сполучень рахує. Питання у виведенні кортежів.
Наприклад, при значеннях n=3, r=2 має вивести:
11
12
13
22
23
33
Отож, допоможіть, будь ласка, з виведенням елементів. Поясніть хоча б принцип

2

Re: Задача з комбінаторики в Pascal

1. Покажіть наявний у вас код, якщо згадали про його наявність. ;)
2. Телепатично: там, де ви збільшуєте лічильник сполучень, можна й одразу вивести це сполучення або зберегти його кудись і вивести потім.

3 Востаннє редагувалося studentKA (16.03.2014 23:51:08)

Re: Задача з комбінаторики в Pascal

Ось мій код (можливо трохи неграмотний та я тільки вчуся):

program math;
uses crt;
var n,r,fr,fch,fzn,i: integer;
    c: real;
begin
     writeln('Vvedit n ta r');
     readln(n,r);
     fch:=1;
     for i:=2 to (n+r-1) do
        fch:=fch*i;
     fr:=1;
     for i:=2 to r do
        fr:=fr*i;
     fzn:=1;
     for i:=2 to (n-1) do
        fzn:=fzn*i;
     c:=fch/(fr*fzn);
     writeln('Kilkist spoluchen - ',c);
end.

Кількість сполучень я знаходжу по формулі, тому й немає лічильника сполучень

4 Востаннє редагувалося koala (17.03.2014 11:07:57)

Re: Задача з комбінаторики в Pascal

1. Формуєте перше сполучення (наприклад, масивом): (1, 1, 1, ..., 1).
2. Шукаєте, де закінчується рядок з n-ок наприкінці поточного сполучення.

Наприклад

(1, 1, 1, ..., 1) - рядок закічнується за межами сполучення
(2, 3, 3, 4, 4) при n=4 - рядок містить 2 числа

3. Збільшуєте на 1 перше число не з цього рядка, рядок міняєте на ті самі числа

Наприклад

(1, 1, 1, ..., 1) стає (1, 1, 1, ..., 2)
(2, 3, 3, 4, 4) стає (2, 3, 4, 4, 4)
(1, 2, 2, 4, 4) стає (2, 2, 3, 3, 3)

4. Якщо весь масив не n, перехід на п. 2.
ОК?

5

Re: Задача з комбінаторики в Pascal

За допомогою вищих сил, вдалося роздобути, зрозуміти та відредагувати код. Та все ж виводить сполучення в порядку спадання.

program z1;
const
  m = 10;
var
  a: array [1..m] of integer; 
  b: array [1..100] of byte;
  n, NN, r, i, j, k,fr,fch,fzn: integer;
  c: real;
Procedure Swapb(i, k: byte);
var
  x : byte;
begin
  x    := b[i];
  b[i] := b[k];
  b[k] := x;
end;
Procedure Writeb;
var
  i, j : byte;
begin
  j := 1;
  for i := 1 to NN do
    if b[i] = 0 then
      Inc(j)
    else
      write(a[j]);
  writeln;
end;
begin
  repeat
    write('n = ');
    readln(n);
    if (n < 2) or (n > m) then writeln('n за межами 2..', m, ', повторити.')
  until (n >= 2) and (n <= m);
  repeat
    write('r = ');
    readln(r);
    if (r < 1) then writeln('r має бути натуральним числом, повторити.')
  until (r >= 1);
       fch:=1;
     for i:=2 to (n+r-1) do
        fch:=fch*i;
     fr:=1;
     for i:=2 to r do
        fr:=fr*i;
     fzn:=1;
     for i:=2 to (n-1) do
        fzn:=fzn*i;
     c:=fch/(fr*fzn);
     writeln('Кількість сполучень - ',c);
  NN := n-1+r; 
  for i:=1 to n do a[i]:=i; 
  for i:=1 to n-1 do b[i]:=0; 
  for i:=n to n+r-1 do b[i]:=1;
  WriteB;
  while (true) do
  begin
    i:=NN;
    while (i>0) and (b[i] >= b[i+1]) do i:=i-1;
    if i=0 then exit;
    for j:=i+1 to NN do
      if (b[j]>b[i]) then k:=j;
    SwapB(i,k);
    for j:=i+1 to (i+ ((NN+1-i) div 2)) do
      SwapB(j,NN+i+1-j);
    WriteB;
  end;
  readln
end.

Змінювала в процедурі значення 0 на 1. В деяких випадках виводить в порядку зростання, в інших - взагалі не вірні сполучення...

Procedure Writeb;
var
  i, j : byte;
begin
  j := 1;
  for i := 1 to NN do
    if b[i] = 1 then
      Inc(j)
    else
      write(a[j]);
  writeln;
end;

Можливо знаєте як вивести в порядку зростання? Буду вельми вдячна)

6

Re: Задача з комбінаторики в Pascal

Ну, оскільки ціна заплачена...

var
  comb: array [1..m] of integer; {поточна комбінація}
  change: integer;{номер елементу, який треба змінити}
...
  { Формуємо перше сполучення }
  for i := 1 to r do 
    comb[ i ] := 1;
  change := r;
  { Якщо весь масив не n, повторюємо}
  while change > 0 do begin
    for i := 1 to r do
      write( comb[ i ] );
    writeln;
    change := r;
    { Шукаємо, де закінчується рядок з n-ок наприкінці поточного сполучення }
    while ( change > 0 ) and ( comb[ change ] = n ) do 
      dec( change );
    if change > 0 then begin
      { Збільшуємо на 1 перше число не з цього рядка }
      inc( comb[ change ] );
      { рядок міняємо на ті самі числа }
      for i:= change + 1 to r do
        comb[ i ] := comb[ change ];
    end;
  end;

Але більше так не робіть, добре?

Подякували: studentKA1

7

Re: Задача з комбінаторики в Pascal

Я Вам щиро вдячна! :-*

koala написав:

Але більше так не робіть, добре?

І що саме не робити? *SCRATCH*

8

Re: Задача з комбінаторики в Pascal

Не допомагайте тим, хто сам нічого не робить.

9

Re: Задача з комбінаторики в Pascal

Окей, а підсказувати ж можна?)

10

Re: Задача з комбінаторики в Pascal

Ну я ж вам раніше підказав :)
Втім, справа ваша - допомагати чи ні; просто часто люди - невдячне бидло, і на допомогу вирішують, що це ваш обов'язок...

11

Re: Задача з комбінаторики в Pascal

Я згодна, так воно в житті. Та все ж треба вірити, що добро обов'язково повернеться ще більшим добром)

Подякували: Replace1