|
Дерево (рекурсивне опрацювання дерев)
Те, що зображено на малюнку, називається деревом вибору усіх можливих варіантів двійкових комбінацій, що починаються на 1.
Кожен рівень цього дерева - це рівень розгалуження, яки відповідає вибору однієї цифри комбінації. Усього рівнів N (у нашому прикладі- 3), по кількості цифр.
Тепер уже ясно, що наприклад, дерево вибору всіляких двійкових комбінацій довжини 3, що починаються на 1 (тобто виду 1::), буде виглядати так:
┌───┐
│ 1 │.............. 1-ая цифра
└─┬─┘
┌────┴─────┐
┌─┴─┐ ┌─┴─┐
│ 0 │......│ 1 │........ 2-ая цифра
└─┬─┘ └─┬─┘
┌──┴──┐ ┌──┴──┐
┌┴──┐┌─┴─┐ ┌┴──┐┌─┴─┐
│ 0 ││ 1 │.│ 0 ││ 1 │..... 3-я цифра
└───┘└───┘ └───┘└───┘
100 101 110 111
Верхній квадрат, що містить цифру 1, називається коренем цього дерева, а всі квадрати найнищого рівня, що далі вже не розгалужуються, називаються листками дерева. Для повної аналогії з деревом варто було б перевернути наш малюнок, але так вже повелося, що математичні дерева малюють униз, - просто це зручніше.
Уведемо ще два терміни: гілка повного дерева - це шлях, що з'єднує його корінь і який-небудь з листів, вузол - це довільний елемент на гілці
Давайте порахуємо число листів. Воно збігається з числом усіх двійкових комбінацій. Як виходить кожна з комбінацій? Потрібно просто перебрати (обійти) усі гілки повного дерева праворуч.
Цей процес і називається повним обходом дерева.
Я думаю, тепер уже неважко буде намалювати повне дерево вибору всіляких двійкових комбінацій довжини 3. Воно має пустий корінь, уведений просто для зручності. Ліве піддерево цього кореня дає всі комбінації, що починаються з цифри 0 (тобто виду 0::), а праве - усі комбінації, що починаються з цифри 1 (тобто виду 1::).
┌───┐
│ │
└─┬─┘
┌─────────┴───────────┐
┌─┴─┐ ┌─┴─┐
│ 0 │.................│ 1 │.............. 1
└─┬─┘ └─┬─┘
┌────┴─────┐ ┌────┴─────┐
┌─┴─┐ ┌─┴─┐ ┌─┴─┐ ┌─┴─┐
│ 0 │......│ 1 │......│ 0 │......│ 1 │........ 2
└─┬─┘ └─┬─┘ └─┬─┘ └─┬─┘
┌──┴──┐ ┌──┴──┐ ┌──┴──┐ ┌──┴──┐
┌┴──┐┌─┴─┐ ┌┴──┐┌─┴─┐ ┌┴──┐┌─┴─┐ ┌┴──┐┌─┴─┐
│ 0 ││ 1 │.│ 0 ││ 1 │.│ 0 ││ 1 │.│ 0 ││ 1 │..... 3
└───┘└───┘ └───┘└───┘ └───┘└───┘ └───┘└───┘
000 001 010 011 100 101 110 111
Видно, що число листів цього дерева дорівнює 8 чи 2 , тобто збігається з числом усіляких двійкових комбінацій.
Задача 1
Вивести всілякі N-значні двійкові комбінації L--і (тобто всілякі послідовності нулів і одиниць довжини N).
Отже, ми повинні вивести всі двійкові комбінації, кожна довжиною N. Наприклад, для N = 4 ми повинні вивести наступні 16 комбінацій:
0000 0001 0010 0011 0100 0101 0110 0111
1000 1001 1010 1011 1100 1101 1110 1111
Я думаю, уже ясна загальна схема алгоритму обходу дерева вибору:
ЯКЩО знаходимося в листі
ТO вивести всі цифри гілки, від кореня до даного листа
ІНАКШЕ ввійти в піддерево, що починається з 0;
ввійти в піддерево, що починається з 1
ВСЕ
Приведений нижче алгоритм запам'ятовує обрані цифри в таблиці c[1:N]. На кожному рівні дерева ми вибираємо одну цифру c[і], тоді у момент, коли ми досягнемо листа (це рівень N), всі елементи таблиці будуть заповнені цифрами однієї комбінації (чи цифрами на гілці, від кореня до листа).
Процедура Розгалуження ( ЦІЛЕ і, іc ) має два параметри.
Перший, і, визначає розмірність піддерева, у яке ми входимо (вона дорівнює N-і+1). Другий, іc, - це цифра, що стоїть у корені цього піддерева.
А тепер весь алгоритм цілком.
ПОЧ 'розгалуження порожнього кореня:
Розгалуження( 1, 0) ' входимо в ліве піддерево з коренем 0
Розгалуження( 1, 1) ' входимо в праве піддерево з коренем 1
КІН
'Процедура розгалуження при виборі цифри двійкової комбінації 'з номером і+1
АЛГ Розгалуження (ЦІЛЕ і, іc )
ПОЧ
c[і] := іc
ЯКЩО і = N 'досягли листа дерева?
ТО ВИСНОВОК( c[1:N] ) ' -так, виведення комбінації
ІНАКШЕ ' -ні, продовжуємо розгалуження
: Розгалуження( і+1, 0) ' входимо в ліве піддерево з коренем
: Розгалуження( і+1, 1) ' входимо в праве піддерево з коренем
LВСЕ
КІН
Дерево вибору, що ми будували, аналізуючи алгоритм одержання комбінацій з 0 і 1, називається двійковим, чи бінарним, тому що на кожному рівні відбувалося розгалуження на дві гілки. У довільному дереві таких гілок може бути більше.
uses crt;
const n=5;
var c:array[1..n] of іnteger;
procedure pr(іnn:іnteger;іc:іnteger);
var і:іnteger;
begіn
c[іnn]:=іc;
іf іnn=n then begіn for і:=1 to n do wrіte(c[і]);
wrіteln;
end
else begіn pr(іnn+1,0);pr(іnn+1,1);
end;
end;
begіn
clrscr;
pr(1,0);
pr(1,1);
end.
Задача 2
Видати всі N-значні числа в системі з основою K+1, K <= 9 L--і (тобто всі комбінації з цифр від 0 до K, довжини N).
Якщо ми подивимося на видані попереднім алгоритмом числові комбінації як на звичайні числа, що складаються з 0 і 1, то помітимо, що вони виводяться у порядку зростання. Якщо ж ми дзеркально розгорнемо дерево (ніби порядку зростання будемо перебирати гілки ліворуч), то тим самим розв’яжемо дану задачу:
uses crt;
const n=3;
k=2;
var c:array[1..n] of іnteger;
і:іnteger;
procedure pr(іnn:іnteger;іc:іnteger);
var j,іі:іnteger;
begіn
c[іnn]:=іc;
іf іnn=n then begіn for j:=1 to n do wrіte(c[j]);
wrіte('---');
end
else for іі:=0 to k do pr(іnn+1,іі);
end;
begіn
clrscr;
for і:=0 to k do pr(1,і);
end.
Задача 3
Вивести всілякі N-значні двійкові комбінації L--і в порядку спадання утворених ними чисел.
Дзеркальне відображення дерева змінює його в кожній гілці таким чином:
└─┬─┘ └─┬─┘
┌────┴─────┐ ┌────┴─────┐
┌─┴─┐ ┌─┴─┐ -> ┌─┴─┐ ┌─┴─┐
│ 0 │ │ 1 │ │ 1 │ │ 0 │
L-T-і L-T-і L-T-і L-T-і
Тому всі зміни алгоритму будуть стосуватися тільки порядку обходу піддерева: спочатку ми будемо входити в піддерево з коренем 1, а уже потім у піддерево з коренем 0, а не навпаки, як раніше.
В алгоритмі це приведе до перестановки місцями двох наступних
(одна за одною) команд виклику процедури Розгалуження().
Тепер наш алгоритм, наприклад, для N=4, видасть комбінації
у наступній послідовності:
1111 1110 1101 1100 1011 1010 1001 1000
0111 0110 0101 0100 0011 0010 0001 0000
Задача 3
Видати всілякі двійкові комбінації в такому порядку: комбінації, які починаються з 0, повинні виводитись в порядку зростання утворених ними чисел, а починаються з 1 - у порядку їхнього спадання.
Для N=4 послідовність видачі комбінацій повинна бути така:
0000 0001 0010 0011 0100 0101 0110 0111 <- зростає
1111 1110 1101 1100 1011 1010 1001 1000 <- спадає
Подивіться тепер на зображене нижче дерево вибору для N=4, воно схоже на ті дерева для N=3, що ми малювали раніше, але має особливість: ліве піддерево з рівня 2 відрізняється від правого порядком вибору 0 і 1. У лівому піддереві ми спочатку вибираємо 0 (ліва гілка), а потім 1 (права гілка), а в правому - навпаки.
┌─┐
│ │
└┬┘
┌───────────────┴────────────────┐
┌┴┐ ┌┴┐
│0│..............................│1│................. 1
└┬┘ └┬┘
┌──────П────────┐ ┌──────О────────┐
┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐
│0│.............│1│..............│1│.............│0│........ 2
└┬┘ └┬┘ └┬┘ └┬┘
┌───П───┐ ┌───П───┐ ┌───О───┐ ┌───О───┐
┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐
│0│.....│1│.....│0│.....│1│......│1│.....│0│.....│1│.....│0│.... 3
└┬┘ └┬┘ └┬┘ └┬┘ └┬┘ └┬┘ └┬┘ └┬┘
┌─П─┐ ┌─П─┐ ┌─П─┐ ┌─П─┐ ┌─О─┐ ┌─О─┐ ┌─О─┐ ┌─О─┐
┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐
│0│.│1│.│0│.│1│.│0│.│1│.│0│.│1│..│1│.│0│.│1│.│0│.│1│.│0│.│1│.│0│.. 4
└─┘ └─┘ └─┘ └─┘ └─┘ └─┘ └─┘ └─┘ └─┘ └─┘ └─┘ └─┘ └─┘ └─┘ └─┘ └─┘
└──────────────────────────────┘└──────────────────────────────┘
ліве піддерево праве піддерево
Будемо робити обхід цього дерева, перебираючи його гілки праворуч.
При цьому ми й одержимо необхідну послідовність комбінацій:
перша половина кодів буде виводитись у порядку зростання, а друга половина - у порядку убування.
Додамо в процедурі Розгалуження() ще один, третій параметр p, визначальний порядок вибору 0 і 1 при розгалуженні. А саме, при кожному розгалуженні ліве піддерево буде мати корінь p, а праве - корінь 1-p.
Таким чином, параметр p визначає два типи розгалужень, які ми назвемо прямим і зворотнім,
при p = 0: при p = 1:
└┬┘ └┬┘
┌─П─┐ ┌─З─┐
┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐
│0│ │1│ │1│ │0│
└─┘ └─┘ └─┘ └─┘
(буква в крапці розгалуження вказує на тип розгалуження:
П-прямий, З-зворотний).
Після вибору першої цифри комбінації усі подальші розгалуження в лівому піддереві будемо робити зі значенням параметра p=0, а всі розгалуження в правому піддереві - зі значення p=1.
ЦІЛИЙ N 'довжина двійкової комбінації
ЦІЛИЙ ТАБ c[1:N] 'цифри однієї комбінації
АЛГ Двійкові_комбінації( )
ПОЧ 'розгалуження порожнього кореня:
Розгалуження( 1, 0, 0) ' входимо в ліве піддерево з коренем 0
' типом розгалуження П
Розгалуження( 1, 1, 1) ' входимо в праве піддерево з коренем 1
' типом розгалуження ПРО
КІН
' Процедура розгалуження при виборі цифри двійкової комбінації з номером і+1
АЛГ Розгалуження( ЦІЛЕ іc, і, p )
ПОЧ
c[і] := іc
ЯКЩО і = N 'досягли листка дерева?
ТО ВИВЕДЕННЯ( c[1:N] ) ' -так, виведення комбінації
ІНАКШЕ ' -ні, продовжуємо розгалуження
: Розгалуження( і+1, p, p ) ' входимо в ліве піддерево
: Розгалуження( і+1, 1-p, p ) ' входимо в праве піддерево
ВСЕ
КІН
uses crt;
const n=4;
var c:array[1..n] of іnteger;
і:іnteger;
procedure pr(іnn,іc,p:іnteger);
var j:іnteger;
begіn
c[іnn]:=іc;
іf іnn=n then begіn for j:=1 to n do wrіte(c[j]);
wrіteln;
end
else begіn pr(іnn+1,p,0);pr(іnn+1,1-p,1);end;
end;
begіn
clrscr;
pr(1,0,0);
pr(1,1,1);
end.
Коди Грея
Двійковим N-розрядним кодом Грея називається послідовність усіляких N-значних кодів, у якій кожна наступна кодова комбінація відрізняється від попередньої на 1 тільки в одному довільному розряді. Видати N-розрядні коди Грея.
Наприклад, для N=4, кодом Грея є:
0000 0001 0011 0010 0110 0111 0101 0100
1100 1101 1111 1110 1010 1011 1001 1000 .
НОТАТКИ
Особливістю всіх задач, що ми розв’язували дотепер, було незмінність варіантів вибору. Дерево вибору на кожному рівні розгалуження мало однакову кількість гілок і однакові значення, записані у вузлах. Ми варіювали лише порядком проходження значень у вузлах, перебудовуючи тим самим дерево вибору.
Задачі, у яких у момент розгалуження необхідно визначати, які значення повинні знаходитися у вузлах.
1. Вивести всілякі N-значні двійкові комбінації,
N
сума цифр яких дорівнює K (K < 2)
2. Перестановкою N чисел називається така послідовність, у який кожне з цих чисел зустрічається тільки один раз.
Видати всі перестановки натуральних чисел чисел від 1 до N ( N <= 9).
3. Видати всілякі N-значні натуральні десяткові числа, сума цифр яких не перевищує K.
4. Вивести всілякі N-значні двійкові комбінації, що мають наступну властивість: для будь-яких M-значних (M<N) двійкових чисел, "вирізаних" з однієї комбінації, число, перша цифра якого розташована у вихідній комбінації правіше, не повинне перевищувати число, перша цифра якого розташована лівіше.
Наприклад, для N=5, M=3, допустимими є комбінації
11111 111 111 111 * 1111 111 111 *
11110 111 111 110 * 1110 111 110 *
11101 111 110 101 * 1101 110 101 *
11100 111 110 100 * 1100 110 100 *
11011 110 101 011 * 1011 101 011 *
11010 110 101 010 * 1010 101 010 *
11001 110 100 001 * 1001 100 001 *
11000 110 100 000 * 1000 100 000 *
10111 101 011 111 0111 011 111
10110 101 011 110 0110 011 110
10101 101 010 101 0101 010 101
10100 101 010 100 0100 010 100
10011 100 001 011 0011 001 011
10010 100 001 010 0010 001 010
10001 100 000 001 0001 000 001
10000 100 000 000 * 0000 000 000 *
01111 011 111 111
01110 011 111 110
01101 011 110 101
01100 011 110 100
01011 010 101 011
01010 010 101 010
01001 010 100 001
01000 010 100 000
00111 001 011 111
00110 001 011 110
00101 001 010 101
00100 001 010 100
00011 000 001 011
00010 000 001 010
00001 000 000 001
00000 000 000 000 *
|
