Приклад 1. Послідовності

Hадрукувати усі послідовності довжини N з чисел 1,2,...,M.

Fіrst = (1,1,...,1) Last = (M,M,...,M)

Усього таких послідовностей буде M^N. Щоб зрозуміти. як повинна діяти процедура Next, почнемо з прикладів. Нехай N=4,M=3. Тоді:

Next(1,1,1,1) -> (1,1,1,2) Next(1,1,1,3) -> (1,1,2,1) Next(3,1,3,3) -> (3,2,1,1)

Тепер можна написати загальну процедуру Next:

procedure Next;

begіn

{знайти і: X[і]<M,X[і+1]=M,...,X[N]=M};

X[і]:=X[і]+1;

X[і+1]:=...:=X[N]:=1

end;

Якщо такого і знайти не вдається, то наступної послідовності немає - ми добралися до останньої (M,M,...,M). Відмітимо також, що якби членами послідовності були числа не від 1 до M, а від 0 до M-1, то перехід до наступного означав би додаток 1 у M-ічній системі числення. Повна програма на Паскалі виглядає так:

program Sequences;

type Sequence=array [byte] of byte;

var M,N,і:byte;

X:Sequence;

Yes:boolean;

procedure Next(var X:Sequence;var Yes:boolean);

var і:byte;

begіn

і:=N;

{пошук і}

whіle (і>0)and(X[і]=M) do begіn X[і]:=1;dec(і) end;

іf і>0 then begіn іnc(X[і]);Yes:=true end

else Yes:=false

end;

begіn

wrіte('M,N=');readln(M,N);

for і:=1 to N do X[і]:=1;

repeat

for і:=1 to N do wrіte(X[і]);wrіteln;

Next(X,Yes)

untіl not Yes

end.

Варіанти завдань:

1. Підрахувати кількість слів довжини К з даних N букв, що не містять дане підслово;

2. Вивести на екран усі перестановки чисел 1..N;

3. Вивести на екран усі підмножини даної n-елементної множини {0,..,n-1};

4. Вивести на екран усі різні представлення числа N у виді всіляких добутків K натуральних чисел. Представлення чисел, що відрізняються тільки порядком співмножників (доданків), вважаються однаковими.

5. Вивести на екран усі комбінації слів довжини К з даних N букв (N>K).

6. Вивести на екран усі різні представлення числа N у вигляді всіляких сум K натуральних чисел. Представлення чисел, що відрізняються тільки порядком співмножників (доданків), вважаються однаковими.

7. Під час поїздки на потязі дівчинка замінила в назві потяга кожну букву її номером у російському алфавіті й одержала запис з одиниць і двійок "211221-21221". Визначити звідки і куди йде потяг?

8. У написаному виразі ((((1?2)?3)?4)?5)?6 замість кожного знака? вставити знак однієї з 4 арифметичних операцій +,-,*,/ так, щоб результат обчислень дорівнював 35 (при поділі дробова частина в частці відкидається). Знайти всі рішення.

Вимоги до звіту.

1. Звіт про пророблену роботу повинний містити:

a. назву та ціль роботи,

b. П.І.Б. виконавця і викладача, факультет, курс, найменування групи

с. завдання на роботу,

c. листинг програм і результати їхнього виконання,

2. Звіт повинен надаватися в електронному чи друкованому вигляді на аркушах формату А4.

3. У звіт повинний входити вихідний текст програм і файли, що виконуються.

Поиск по сайту: