Задача тижня 16.01.12 – 22.01.12

Синоптик

Кожного зимового дня один з трьох братів-морозів Синій Ніс, Червоний Ніс або Білий Ніс насилає на землю холоднечу. Сірий вовк щодня реєструє погоду, записуючи в рядок відповідний символ B, R або W.

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

Вхідні дані

Значення V (спостереження сірого вовка) – непустий рядок з не більш 90 символів B, R, W, що вводиться з клавіатури або з текстового файлу.

Вихідні дані

Значення F (мороз, який частіше за інших визначав погоду) – рядок, що містить від одного до трьох символів B, R або W.

Значення S (мороз, який панував найдовший термін підряд) – рядок, що містить від одного до трьох символів B, R або W.

2. Заповніть тестову таблицю за результатами роботи програми

Аналіз розв’язку задачі «Синоптик»

Розв’язок задачі робимо у два етапи:

На першому знайдемо кількість повторень і максимальну довжину ланцюжків для кожного з символів “R“, “B“, “W” у рядку V; на другому– аналізуємо знайдені значення і формуємо рядки-результати з символів, що відповідають найбільшим значенням серед знайдених кількостей і максимальних довжин.

Розглянемо докладніше:

1. Введемо цілочислові трьохелементні масиви Fr та Sr, в яких будемо накопичувати, відповідно, кількість повторень і максимальну довжину ланцюжків символів “R“, “B“, “W“. Значення Fr[k], Sr[k] для k = 1 відповідають символу “R“, для k = 2 – символу “B“, для k = 3 – символу “W”. Первісні значення елементів обох масивів мають дорівнювати нулю.

Введемо рядок-константу Ch=”RBW“, де порядок символів відповідає їх індексам у масивах Fr, Sr. Отже, якщо знаємо позицію символу  V[і] в рядку Ch, то знаємо і елементи масивів Fr, Sr, які зберігають дані про цей символ.

У мові Паскаль шукану позицію символу дає функція Pos(V[i], Ch), у мові Бейсик – InStr(Ch, mid(V, i, 1)). Ми скористаємося таким позначенням: ПОЗ(V[i], Ch). Тоді обчислення кількості повторень символів у рядку V здійснюється в циклі

для і від 1 до N

де N – довжина рядка V, у такий спосіб:

k = ПОЗ(V[i], Ch); Fr[k] = Fr[k]+1;

У тому самому циклі обчислюємо довжину неперервних ланцюжків однакових символів. Обчислення починаємо з i = 2 (тобто якщо i > 1 то), значення довжини зберігаємо в цілочисловій змінній t, до початку циклу t = 1. Якщо поточний символ співпадає з попереднім, збільшуємо значення t на 1, якщо ні – фіксуємо кінець ланцюжка і збільшуємо відповідний елемент масиву Sr, якщо це потрібно:

кінець;

Після виходу з циклу залишається додатково обробити останнє значення t, оскільки кінець рядка V автоматично є і кінцем ланцюжка символів V[N]:

то Sr[ПОЗ(V[N], Ch)] = t;

2. Формування рядків-результатів F та S здійснимо в два прийоми. Спочатку організуємо цикл перегляду значень елементів масивів Fr та Sr для знаходження найбільших значень – m серед Fr[k] та d серед Sr[k]

кінець циклу;

Потім запишемо в рядки F та S ті символи, що відповідають знайденим найбільшим значенням m та d:

кінець циклу;

Зауваження. Другий етап алгоритму можна реалізувати в рамках одного циклу:

кінець циклу;

Тестова таблиця з результатами роботи програми:

Примітка: порядок символів у рядках F та S може бути довільним відповідно до умови задачі.

Журі оцінило надіслані розв’язки наступним чином: