end.
В
6 Сполучення з повтореннями
Для безлічі символів від A до C і розміру M = 3 поєднання з повтореннями будуть наступними:
CCC BCC BBC BBB ACC ABC ABB AAC AAB AAA
Загальна кількість поєднань = (N + M-1)! /(M! * (N-1)!) p> де N - кількість символів
M - по скільки символів в поєднанні
Основна ідея генерації таких сполучень з повтореннями полягає в наступному:
Сполучення записуємо у вигляді (N-1)-го нуля і M одиниць, де одиниці замінюють символи, а нулі виступають в ролі pазделітелей.
Напpимеp:
ABB - 1 0 1 1 AAC - 1 1 0 0 1 CCC - 0 0 1 1 січня
A B B A A C C C C
При такому підході для вирішення завдання досить згенерувати всі перестановки з M одиниць і N-1-го нуля.
Нижче наводиться програма, яка вирішує поставлену задачу.
const
alphabet: string [26] = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ';
var
b: array [1 .. 100] of byte;
N, i, j, k, M, N1: byte;
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 N do
if b [i] = 0
then Inc (j)
else write (alphabet [j]);
writeln;
end;
begin
readln (N1, M); N: = N1-1 + M;
for i: = 1 to n1-1 do b [i]: = 0;
for i: = n1 to n1 + m-1 do b [i]: = 1;
WriteB;
while (true) do
begin
i: = N;
while (i> 0) and (B [i]> = B [i +1]) do i: = i-1;
if i = 0 then exit;
for j: = i +1 to N do
if (B [j]> B [i]) then K: = j;
SwapB (i, k);
for j: = i +1 to (i + ((N +1- i) div 2)) do
SwapB (j, N + i +1- j);
WriteB;
end;
end.
Пояснення до програми:
1. Початкова перестановка формується послідовно з N1-1 нулів і M одиниць. p> 2. У програмі виведення перестановки WriteB здійснені зміни, відповідні задуму (нулі - роздільники, одиниці - символи). Якщо поточний елемент масиву B дорівнює 0, то "стає активним" наступний символ. Якщо поточний символ масиву B дорівнює 1, то поточний активний символ виводиться на екран.
Висновок
Всі програми для більшої наочності в якості ілюстрації оперують з масивом символів від A до Z. Очевидно, що пропоновані алгоритми та програми практично не змінюються при роботі з масивами елементів будь-якого типу, необхідного за умовами завдання (наприклад, масивами чисел, слів, геометричних фігур і т.д.)
Література
1. Абдеев Р.Ф. Філософія інформаційної цивілізації. - М.: Владос, 1994. p> 2. Адамар Ж. Дослідження психології процесу винаходи в галузі математики. - М.: Сов. радіо, 1970.
3. Болтянский В.Г. Інформатика та викладання математики// Математика в школі. 1989. № 4.-С.86-90
4. Вейценбаум Дж. Можливості обчислювальних машин і людський розум. - М.: Радіо і зв'язок, 1982. p> 5. Вірт Н. Алгоритми + Структури даних = Програма. - М.: Мир, 1989
6. Вірт Н. Систематичне програмування: Введення. - М.: Мир, 1977. p> 7. Громов Г.Р. Нариси інформаційної технології. - М.: ІнфоАрт, 1993. p> 8. Дейкстра Е. Дисципліна програмування. - М.: Мир, 1978. p> 9. Ільєнко Е. В. Філософія і культура. - М.: Політ. літ., 1991.
10. Йодан Е. Структурний проектування і конструювання програм. - М.: Мир, 1979. p> 11. Майерс Г. Надійність програмного забезпечення. - М.: Мир, 1980. p> 12. Махмутов М.І. Організація проблемного навчання в школі. - М., 1986. br/>
