Задача тижня 09.04.12 – 15.04.12

2 Грудня, 2011 kaf-informatics@hnpu.edu.ua

Код

Агенту 256 необхідно відкрити сейф з кодовим замком. З таємного повідомлення він дізнався, що в якості коду вибрано паліндром найбільшої довжини, який міститься у рядку символів, накресленому на дверцятах сейфу.

Пояснення: паліндром – це послідовність поряд розташованих символів, що однаково читається зліва направо і справа наліво.

1. Створіть програму, яка допоможе агентові знайти код.

Вхідні дані

R – рядок символів на дверцятах сейфу, довжина рядка не перевищує 255 символів.

Вихідні дані

K – кількість знайдених паліндромів найбільшої довжини, ціле число від 1 до 255;

Z [i] (i = 1, 2, …, К) – знайдені варіанти коду (паліндроми найбільшої довжини), рядки, довжина яких не перевищує 255 символів.

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

№	R	K	Z [i]
1	kvetnjtgtjntivkvitnznztstriciutrssrtuz	2	tnjtgtjnt, ntivkvitn
2	itnntivvitzztirritzyyztuzzut
3	kvetnjtgtjntevkzutrsrtytrsrtuz
4	kvetnjtgzutrsrtytrsrtuzgtjntevk
5	kvetnjtgtjntevkvetnjtgzutrsrtytrsrtuzutrsrty
6	kvetnjtgkvetnjtgkvetnjtgkvetnjtgkvetnjtg

Аналіз розв’язку задачі «Код»

Одним із варіантів розв’язку даної задачі є перевірка частин рядка символів на «паліндромність» і пошуку серед знайдених паліндромів найдовшого.

Рішення матиме вигляд:

Введемо змінні:

R – заданий рядок:

n – ціле число, довжина рядка R;

i, j – цілі числа, допоміжні змінні;

p – змінна рядкового типу, підрядок рядка R довжиною у m символів, починаючи з j-го;

m – ціле число, довжина підрядка p;

b – ціле число («прапорець»), що набуває значення 1, якщо підрядок p є паліндромом, або 0 у протилежному випадку;

мах – змінна рядкового типу, паліндром максимальної довжини;

s – змінна рядкового типу, що містить паліндром (паліндроми) максимальної довжини;

K – ціле число, кількість знайдених паліндромів найбільшої довжини.

початок

вводимо рядок R;

n: = довжина рядка R;

мах:= ”; { мах – порожній рядок, відповідно і довжина рядка мах рівна 0}

s: = ”; { s – порожній рядок}

К: = 0;

для j від 1 до (n – 1)

початок циклу

для m від (n – j + 1) до 2

початок циклу

p: = підрядок рядка R довжиною у m символів, починаючи з j-го;

b: = 1; {«піднімаємо прапорець»}

i: = 1;

поки (b = 1) and (i <= m div 2) { перевіряємо, чи є підрядок p паліндромом}

початок циклу

якщо p[і] <> р[ m – і + 1]

то b: = 0 («опускаємо прапорець»)

інакше i: = i + 1;

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

{якщо p – паліндром,порівнюємо його довжину з довжиною рядка мах }

якщо(b = 1) and (m = довжина (мах))

то

початок

К: = К + 1;

s:= s + ‘ ‘+ p;

кінець;

якщо(b = 1) and (m > довжина (мах))

то

початок

мах: = p;

К: = 1;

s: = p;

кінець;

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

виводимо на екран значення змінної К і рядок s;

кінець.

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

№	R	K	Z [i]
1	kvetnjtgtjntivkvitnznztstriciutrssrtuz	2	tnjtgtjnt, ntivkvitn
2	itnntivvitzztirritzyyztuzzut	1	Ztirritz
3	kvetnjtgtjntevkzutrsrtytrsrtuz	2	kvetnjtgtjntevk, zutrsrtytrsrtuz
4	kvetnjtgzutrsrtytrsrtuzgtjntevk	1	kvetnjtgzutrsrtytrsrtuzgtjntevk
5	kvetnjtgtjntevkvetnjtgzutrsrtytrsrtuzutrsrty	4	kvetnjtgtjntevk, gtjntevkvetnjtg, zutrsrtytrsrtuz, ytrsrtuzutrsrty
6	kvetnjtgkvetnjtgkvetnjtgkvetnjtgkvetnjtg	0

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

№	Учасник	Кількість балів
1	SERGEY	4
2	Kolgatin Andrey	4

Кафедра інформатики

Кафедра інформатики

Задача тижня 09.04.12 – 15.04.12

Вам також може сподобатися

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

Задача тижня 06.02.12 – 12.02.12

Задача тижня 23.04.12 – 29.04.12