Задача 195.195. Скільки різних “слів” можна утворити з слова “ПЕОМ”. Літери дозволяється використовувати стільки разів, скільки вони є у даному слові. Вивести всі слова на екран.

Розв’язання: Якби в умові задачі не ставилась вимога вивести всі слова на екран, то це була б чисто комбінаторна задача, яка розв’язувалась би досить просто: оскільки всі літери в слові різні, то нам просто потрібно знайти кількість розміщень у множині, що складається з чотирьох елементів. З іншими способами розв’язання задач з використанням множин ми познайомимось трохи пізніше у відповідному розділі. Зараз лише нагадаємо, що якщо дано множину А з n елементів а ₁, а ₂,..., а _n-1, a _n, то розміщенням з n елементів по m (m Ј n) називається будь–яка впорядкована підмножина В множини А, така, що вона містить m елементів із даних а ₁, а ₂,..., а _n–1, а _n. Причому дві такі підмножини вважаються різними, якщо вони відрізняються порядком або складом елементів.

Будемо поки що розглядати не множину літер слова «ПЕОМ», а множину порядкових номерів літер у цьому слові. Оскільки слово «ПЕОМ» складається з чотирьох літер, то ми маємо множину з чотирьох елементів: 1, 2, 3, 4. Розміщень по одному буде 4: (1); (2); (3); (4); Розміщень по два – дванадцять: (1, 2); (2, 1); (1, 3); (3, 1); (1, 4); (4, 1); (2, 3); (3, 2); (2, 4); (4, 2); (3, 4); (4, 3). Згадаймо, що у нас числа моделюють літери слова, а у слові всі літери різні (бо мають різний порядковий номер!) і не можуть повторюватись. У загальному випадку кількість розміщень з n елементів по m – знаходиться за формулою:

але з точки зору інформатики нам зручніше використовувати ту ж формулу, але записану у вигляді: = n ' (n-1) ' (n-2) '... ' (n-(m-2)) ' (n-(m-1)). Зручність використання полягає в тому, що у циклах нам зручніше працювати з цілочисельними змінними, а операція ділення вимагає використання дійсних типів. Використавши формулу, маємо: =4, = 12, = 24, = 24. Всього ми можемо утворити + + + = 64. Тобто з точки зору інформатики задача поки що мало цікава, але ось вирішення питання виведення всіх варіантів новоутворених слів на екран робить подальший розв’язок цієї задачі самостійним методом для розв’язання великої групи завдань.

Нам потрібно навчитись утворювати нові слова з заданого набору літер. Розіб’ємо це завдання на дві підзадачі.

Підзадача 1: Спочатку навчимось утворювати слова з набору з n літер, причому кількість літер у слові повинна становити також n (у термінах інформатики задачу можна сформулювати так: скласти програму для отримання всіх перестановок з n літер). Утворювати слова нам допоможуть їх порядкові номера. Оскільки множина порядкових номерів літерів слова на початку є впорядкованою за зростанням: 1, 2, 3, 4, то будемо діяти згідно алгоритму генерації перестановок лексикографічним методом наступним чином:

n вивести на друк введено слово;

n починаючи з кінця слова шукаємо перший елемент, який менший за попередній (рахуючи з кінця) і відмічаємо його;

n знову починаємо з кінця і шукаємо ще один елемент, але вже більший за відмічений, причому він повинен бути розміщеним до відміченого, рахуючи з кінця;

n якщо другий елемент знайдено, то міняємо його місцями з першим;

n “хвіст”, що утворився після обміну (після номера елемента, знайденого першим) сортуємо в порядку зростання. Оскільки до цього він був впорядкований в порядку спадання то у даному випадку операція сортування зводиться до обміну місцями відповідних елементів “хвоста”, або іншими словами – “хвіст” потрібно записати навпаки;

n все вищесказане виконуємо до тих пір, доки весь масив не буде впорядковано в порядку спадання.

Все вищесказане і являє собою алгоритм генерації всіх перестановок лексикографічним методом, але ми описали алгоритм генерації перестановок натуральних чисел. Для використання даного алгоритму стосовно до генерації всіх можливих “слів” з заданого слова поступимо досить просто. Будемо генерувати перестановки для натуральних чисел, що є номерами місцезнаходження літер у введеному слові, тобто індексами введеного масиву символів.

Тобто ми вже зараз можемо утворити всі “чотирилітерні” слова з слова ПЕОМ, більше того даний алгоритм дає нам змогу знаходити всі n–літерні слова з введеного довільного введеного n–літерного слова. На даному етапі програма утворення всіх можливих n–літерних слів матиме вигляд:

program perestanovki_leksikografika;

uses dos,crt;

var st, st1: string; { для слів }

i, k,n,t,j,m: integer; { для циклів і проміжних змінних }

n: integer; { кількість символів в рядку }

mas: array[1..10] of integer; { масив № символів в заданому слові }

begin

write(‘Введіть слово: ’);

readln(st);

{.......... формування початкового масиву з номерів символів.......... }

n:= length(st); { кількість символів в слові }

for i:=1 to n do mas[i]:=i; { заповнюємо масив номерами літер }

k:=1; { припускаємо, що існує хоча б 1 перестановка }

while k<>0 do { доки існує хоча б 1 перестановка діє }

begin { алгоритм формування нової перестановки, а пока що }

st1:=''; { приготувались до утворення нового слова }

for j:=1 to n do st1:=st1+st[mas[j]]; { утворили нове слово }

write(st1:8); { надрукували нове слово }

j:=n; { Алгоритм: починаючи з кінця масиву № літер }

k:=0; { і вважаючи, що більше перестановок нема }

while (k=0) and (j>1) do { доки не знайшли перестановку і не }

begin { досягли початку масиву }

if mas[j-1]<mas[j] then k:=j-1; { шукаємо перший елемент, }

j:=j-1; { менший за попередній, рахуючи з кінця }

end; { якщо не знайдемо, то k = 0 і все перестановки знайдено }

j:=n; { переходимо до пошук другого елементу }

t:=0; { і припускаємо, що його не існує }

while (t=0) and (j>k) do { доки не визначили положення другого і

не досягли положення першого – шукаємо другий елемент, який }

begin

if mas[j]>mas[k] then t:=j; { більший першого відміченого, }

dec(j); { причому також ідемо з кінця і до }

end; { першого відміченого. }

if t>0 then begin { Другий знайдено – міняємо його місцями з першим }

j:=mas[k];

mas[k]:=mas[t];

mas[t]:=j;

end;

m:=1; { відсортуємо «хвіст» в порядку спадання – шикуємо навпаки }

while m < (n-k+1) / 2 do

begin

i:= mas[k+m];

mas[k+m]:= mas[n+1-m];

mas[n+1-m]:= i;

m:= m+1;

end;

readln; { для візуального контролю дій алгоритму }

end; { кінець алгоритму генерації всіх перестановок }

readln; { для візуального контролю кінця алгоритму }

end.

Дана програма прекрасно утворює всі можливі n–літерні слова, але за однієї умови: всі літери в слові повинні бути різні. А як нам бути у випадку, коли у слові є однакові літери? Наприклад, «мама». Позначимо для наочності першу з однакових літер «а», а другу – «А». Тоді слова «м а м А» і «м А м а», що утворені літерами з різними порядковими номерами в дійсності записані одними й тими ж літерами і є однаковими, хоча і відповідають різним числовим перестановкам «1234» та «1432».

У цьому випадку потрібно до запропонованого алгоритму внести невеличке доповнення, яке полягає в тому, що на етапі формування початкового масиву номерів літер однаковим літерам слід присвоювати однакові номера. Подумайте, як це зручно зробити і самостійно модифікуйте дану програму.

Нам залишилось розібрати другу підзадачу, яку ми сформулювали для повного вирішення поставленої задачі: потрібно згенерувати всі можливі 1–4–літерні «слова» (ми ж поки що сформували лише всі 4–літерні слова). Розв'язання другої підзадачі ми перекладаємо на читача, оскільки вважаємо, що він вже до цього підготовлений.

 

 

Вправи та завдання

 

196. 196. Дано два слова. Скільки разів в другому слові зустрічається літера, яка в першому слові зустрічається найбільшу кількість разів. Якщо декілька літер зустрічаються однакову кількість разів, то за літеру, що зустрічається найбільшу кількість разів прийняти першу літеру.

197. 197. Підрахувати кількість різних цифр у введеному рядку.

198. 198. Знайти, в якому місці введеного речення вперше зустрілась літера “я”.

199. 199. У заданому рядку поміняти всі коми на крапки, а крапки на знаки оклику.

200. 200. У введеному рядку видалити всі розділові знаки (крапки, коми, знаки оклику і знаки питання).

201. 201. Підрахувати кількість слів у реченні.

202. 202. У введеному тексті знайти довжину найкоротшого та найдовшого слова.

203. 203. У введеному тексті знайти найдовше слово–поліндром.

204. 204. У введеному тексті замінити всі маленькі літери на великі.

205. 205. Замініть у введеному тексті всі групи літер «абв» на «абвг».

206. 206. Підрахуйте, яка з голосних літер зустрічається у тексті найбільшу кількість разів.

207. 207. Знайдіть, одно–, дво– чи трискладних слів у введеному реченні більше.

208. 208. Знайдіть у введеному реченні найдовше слово і підрахуйте, скільки у ньому різних літер.

209. 209. Ввести речення і перевірити, чи є в ньому задане слово.

210. 210. З даного тексту видалити всі фрагменти, що знаходяться у фігурних дужках.

211. 211. Підрахувати, скільки у введеному реченні слів–поліндромів.

212. 212. Підрахувати, який процент слів у реченні починається на задану літеру.

213. 213. У реченні всі фрагменти «і так далі» замінити на «і т. д.».

214. 214. Складіть програму «Словарний диктант». Програма повинна перевіряти правильність написання відомих слів. Невідомих для програми слів у тексті диктанту використовувати не слід.

215. 215. Скласти гру «Відгадай столицю». Назви країн та їх столиць занесіть у відповідні символьні масиви. Програма повинна зменшувати оцінку на 1 за кожну помилку і після трьох помилок припиняти роботу, видаючи відповідне повідомлення.

216. 216. Дано рядок, що складається зі слів і пропусків. Перевернути кожне слово, зберігши незмінним їх порядок в рядку.

217. 217. В символьному рядку є круглі дужки. Перевірити, чи вірно вони розташовані.

218. 218. В арифметичному виразі, записану в один рядок, є круглі, квадратні та фігурні дужки. Чи вірно записано вираз?

 

 

Двомірні масиви

Усі ви, мабуть, полюбляєте якийсь вид спорту. Авторам подобається футбол і шахи. У цих видах спорту, як і в багатьох інших, для виявлення переможця, наприклад чемпіонату країни з шахів, або відбіркової групи Ліги Європейських Чемпіонів з футболу, необхідно заповнити таблицю першості, яка і є прекрасною ілюстрацією двомірних масивів.

Одразу ж зауважимо, що коло використання таблиць значно ширше, адже це не тільки спортивні змагання, а й в першу чергу різноманітні економічні розрахунки, ведення статистичних даних і т.д. Практично неможливо навести приклад галузі людської діяльності, де б не використовувались таблиці. Саме тому ми і помістили розгляд двомірних масивів у окремий розгляд. Одразу ж зауважимо, що практично нічого нового у порівнянні з одномірними масивами тут немає, крім способу запису двомірних масивів. Так, для наведеного прикладу з футболу для групи у якій 4 команди для ведення обліку можна використати найпростішу таблицю 4 на 4, куди будемо заносити очки команд у зустрічах один з одним (при турнірі в одне коло). Цю таблицю на мові Паскаль можна задати у розділі опису змінних як масив 4 на 4 таким способом:

array res[1..4,1..4] of byte;

А на папері дана таблиця мала б приблизно такий вигляд:

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

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