Теорія чисел в програмуванні

Скачати 435.43 Kb.

Назва	Теорія чисел в програмуванні
Сторінка	5/10
Дата	24.10.2013
Розмір	435.43 Kb.
Тип	Документи

bibl.com.ua > Інформатика > Документи

1 2 3 4 5 6 7 8 9 10

Генерація всіх можливих переставлень. Задача2.

Отримати всі можливі переставлення з N заданих чисел.

Ідея розв’язання. У цьому розв’язанні ntemp – кількість елементів у масиві, що підлягають перестановці. Рекурсивна процедура запускається, починаючи з першого елемента масиву. При вході у процедуру вважається, що частина перестановки від першого елемента до (к-1)-го вже згенерована. Відповідно, на к-те місце можна поставити один з елементів, що залишилися у хвості перестановки. Для кожного з варіантів значення цього елемента виконується рекурсивне заглиблення. Воно припиняється при досягненні останього елементу масиву. Перестановку виконує процедура заміни двох елементів місцями swap.

Розв’язання. До вашої уваги третій варіант генерації переставлень

Program Perturbation;

Const Nmax=100;

Var i,NTemp:integer;

a:array [1..Nmax] of byte;

Procedure Swap(a,c:integer);

Var r:byte;

Begin

R:=a;a:=c;c:=r;

End;

Procrdure Perturb(k:byte);

Var j:integer;

begin

If k=Ntemp then

For j:=1 to ntemp do write(a[j]:5);

Else

For j:=k to ntemp do

begin

Swap(a[k],a[j]);

Perturb(k+1);

Swap(a[k],a[j]);

End;

End;

Begin

Read(Ntemp);

For i:=1 to Ntemp do read(a[i]);

Perturb(1); {A- масив переставлень}

End.

Зробіть програми для цієї задачі на основі варіантів розв’язування задачі 1.

Генерація всіх можливих розміщень

Отримати всі можливі розміщення по M з N перших натуральних чисел.

Ідея розв’язання. Внесемо зміни до розв’язку попередніх задач: треба генерувати переставлення, але рахувати кількість чисел, що вже задієно

Розв’язання.

Program Razm;

Type ij=set of byte;

Const n=4; m1=3

Var f,k:integer;

M:array [1..n] of byte;

Procedure Chang1(w:ij; ind:integer);

Var i,j:byte;

Begin

If ind>m1 then

Begin

Inc(f);

For k:=1 to m1 do write(m[k]);

Writeln;

End

Else

For j:=1 to n do

If not(j in w) then

Begin

M[ind]:=j;

Chang1(w+[j],ind+1);

End;

End;

Begin

F:=0; {кількість розміщень}

Chang1([],1); {М- масив розміщень}

End.

Внесіть зміни в інші варіанти генерації переставлень з тим, щоб отримати генерацію розміщень.

Генерація всіх можливих розміщень. Задача2.

Отримати всі можливі розміщення по M з N заданих натуральних чисел.

Ідея розв’язання. Будемо генерувати розміщення індексів елементів масиву. Тоді зміни потрібно буде внести тільки у вивід результатів:

For k:=1 to m1 do write(a[m[k]]);

Генерація всіх можливих сполучень

Отримати всі можливі сполучення по M з N перших натуральних чисел.

Ідея розв’язання. Внесемо зміни до розв’язку попередніх задач: треба генерувати переставлення, але рахувати кількість чисел, що вже задієно та слідкувати затим, щоб не було однакових варіантів

Розв’язання.

Program Soch;

Type ij=set of byte;

Const n=4; m1=3

Var f,k:integer;

M:array [0..n] of byte;

Procedure Chang2(w:ij; ind:integer);

Var i,j:byte;

Begin

If ind>m1 then

Begin

Inc(f);

For k:=1 to m1 do write(m[k]);

Writeln;

End

Else

For j:=m[ind-1]+1 to n do

If not(j in w) then

Begin

M[ind]:=j;

Chang2(w+[j],ind+1);

End;

End;

Begin

F:=0; {кількість сполучень}

Chang2([],1); {М- масив сполучень}

End.

Внесіть зміни в інші варіанти генерації переставлень з тим, щоб отримати генерацію сполучень.

1 2 3 4 5 6 7 8 9 10

Схожі:

Відомі українські математики Діапазон наукової творчості Остроградського надзвичайно широкий: диференціальне та інтегральне числення, алгебра, теорія чисел, диференціальна...	Сума та перетин пiдпросторiв, розклад в пряму суму, фактор-простори” Алгебра і теорія чисел” I курсу, проведене 03. 03. 2008 студентом-практикантом VI курсу
Урок в 6 класі Тема. Найбільший спільний дільник кількох чисел ( НСД) Мета: сформулювати поняття спільного дільника кількох чисел, найбільшого спільного дільника, взаємно простих чисел; домогтися засвоєння...	МІНІСТЕРСТВО ОСВІТИ І НАУКИ, МОЛОДІ ТА СПОРТУ УКРАЇНИ МІЖНАРОДНИЙГУМАНІТАРНИЙУНІВЕРСИТЕТ... Україні, а також виходячи з необхідності закріплення ідеї пріоритету права в юридичній діяльності вивчення навчальної дисципліни...
Порівняння чисел у межах Порівняння чисел у межах Послідовність чисел у межах Складання і розв'язування прикладів	Відгук на дипломну роботу студента ОКР «бакалавр» Солодюка Олега... Солодюк О. В. виконав досить великий обсяг роботи, опрацював серйозну монографічну і журнальну літературу, що стосувалось досліджень...
Урок №6 Тема. Найменше спільне кратне кількох натуральних чисел Мета: на основі знань про кратне число сформувати уявлення учнів про поняття спільного кратного кількох натуральних чисел, НСК, а...	ПРОГРАМА ДИСЦИПЛІНИ “Математика ” Натуральні числа і нуль. Читання та запис натуральних чисел. Порівняння натуральних чисел. Дії над натуральними числами
Міністерство освіти і науки, молоді та спорту України Державний вищий навчальний заклад Натуральні числа і нуль. Читання і запис натуральних чисел. Порівняння натуральних чисел. Дії над натуральними числами	Задача № 1 групи «А» Назвімо число m особливим, якщо можна дібрати такі цілі a та b, що. Скільки існує натуральних чисел, менших від 123 456 789, які...

Додайте кнопку на своєму сайті:
Портал навчання