Рассмотренная задача имеет чисто квалификационный характер проверки знаний информатики по школьной программе и умения самостоятельно составлять алгоритмы и программы решения на ЭВМ простейших информационных задач. С этой задачей справилось большинство участников олимпиады. Однако далеко не все предусмотрели исключительные ситуации и в результате многие из них потеряли определенную часть баллов на указанных тестах.
Вторая олимпиадная задача также относится к классу информационно-логических задач. Ее содержание заключается в переработке символьных данных.
Задача 2. «Слова».
Для фразы на русском языке, в которой нет знаков препинания, а слова отделяются одним единственным пробелом, организовать циклическую перестановку слов.
Исходная фраза:
ВЕЧЕРАМИ МЫ СМОТРИМ ТЕЛЕВИЗОР
Циклическая перестановка слов:
МЫ СМОТРИМ ТЕЛЕВИЗОР ВЕЧЕРАМИ
СМОТРИМ ТЕЛЕВИЗОР ВЕЧЕРАМИ МЫ
ТЕЛЕВИЗОР ВЕЧЕРАМИ МЫ СМОТРИМ
ВЕЧЕРАМИ МЫ СМОТРИМ ТЕЛЕВИЗОР
Сценарий
Исходная фраза:
<строка>
Перестановка слов:
<строка'> *
Проверочные.тесты:
Тест 1: Исходная фраза:
утром был дождь
Правильные результаты:
Перестановка слов:
был дождь утром
дождь утром был
утром был дождь
Тест 2: Исходная фраза:
правильно
Правильные результаты:
Перестановка слов:
правильно
Программа Алгоритм
¢ перестановка слов алг «перестановка слов»
cls нач
? «Исходная фраза:» вывод («Исходная фраза:»)
line input st$ ввод-строки (st$)
? st$ вывод st$
In = len(st$) in = len(st$)
? «Перестановка слов:» вывод («Перестановка слов:»)
s$ = st$ s$ = st$
do цикл
k = instr(s$,«») k = instr(s$,«»)
if k = 0 then если k = 0 то
? s$ вывод (s$)
exit do выход
end if кесли
lf$ = left$(s$,k-l) lf$ = left$(s$,k-l)
rt$ = right(s$,ln-k) rt$ = right(s$,ln-k)
ns$ = rt$ + «» + lf$ ns$ = rt$ + «» + lf$
? ns$ вывод (ns$)
if ns$ = st$ then exit do при ns$ = st$ выход
s$ = ns$ s$ = ns$
loop кцикл
end кон
Третью задачу можно отнести к числу комбинаторных задач, решение которых заключается в организации перебора различных вариантов данных.
Задача 3. «4 точки».
Для заданных четырех точек на плоскости найти длину минимального и максимального обхода их по замкнутому маршруту. Данные о координатах точек представлены в таблице:
х | у |
Составление алгоритмов и программы для решения этой задачи также полезно начать с составления сценария диалога.
Сценарий
координаты точек:
<х1> <у1>
… … …
<х4> <у4>
максимальный маршрут:
<ml> <m2> <m3> <m4>
длина = <mх>
минимальный маршрут:
<n1> <n2> <n3> <n4>
длина = <mn>
Простейший способ решения этой задачи заключается в организации перебора всех замкнутых маршрутов, проходящих через заданные точки и выбора среди минимального и максимального по длине маршрутов.
Программа Алгоритм
¢мин. и макс. маршруты алг «мин. и макс. маршруты»
cls нач
n = 4 п = 4
dim x(n),y(n),r(n,n) dim x(n),y(n),r(n,n)
? «координаты точек» вывод («координаты точек»)
gosub vvdan 'ввод данных ввод-координат-точек
restore mrshrt 'маршруты загрузка-маршрутов
? «маршруты:» вывод («маршруты:»)
mr = 1*2*3 mr =1*2*3
mx = 0 тх = 0
for l = 1 to mr от l = 1 до mr
read k1, k2, k3, k4 ввод k1, k2, k3, k4
dl = r(kl,k2) + r(k2,k3) dl = r(kl,k2) + r(k2,k3)
d3 = r(k3,k4) + r(k4,kl) d3 = r(k3,k4) + r(k4,k1)
d = dl + d3 d = d1 + d3
? kl; k2; k3; k4, d вывод (k1; k2; k3; k4, d)
if mx = 0 then если тх = 0 то
mx = d: mn = d mx = d: mn = d
ml = kl: m2 = k2 ml = k1: m2 = k2
m3 = k3: m4 = k4 m3 = k3: m4 = k4
nl = kl: n2 = k2 n1 = k1: n2 = k2
n3 = k3: n4 = k4 n3 = k3: n4 = k4
elseif d > mx then инеc d > mx то
mx = d mx = d
ml = kl: m2 = k2 m1 = k1: m2 = k2
m3 = k3: m4 = k4 m3= k3: m4 = k4
elseif d < mn then инеc d < mn то
mn = d mn = d
nl = kl: n2 = k2 n1 = k1: n2 = k2
n3 = k3: n4 = k4 n3 = k3: n4 = k4
end if кесли
next 1 кцикл
? «максимальный маршрут:» вывод («максимальный маршрут:»)
? ml; m2; m3; m4 вывод (m1; m2; m3; m4)
? «длина =»; mx вывод («длина =»; mx)
? «минимальный маршрут:» вывод («минимальный маршрут:»)
? nl; n2; n3; n4 вывод (n1; n2; n3; n4)
? «длина =»; mn вывод («длина =»; mn)
end кон
vvdan: 'ввод данных алг «ввод данных»
restore tchks загрузка-точек
for k = 1 to n от k = 1 до п
read x(k),y(k) ввод x(k),y(k)
? x(k),y(k) вывод x(k),y(k)
next k кцикл
for k = 1 to n от k = 1 до п
for l = 1 to n от l = 1 до п
dx = x(k) - x(l) dx = x(k) - x(l)
dy = y(k) - y(l) dy = y(k) - y(l)
rs = dx*dx + dy*dy rs = dx*dx + dy*dy
r(k,l) = sqr(rs) r(k,l) = sqr(rs)
next 1 кцикл
next k кцикл
return кон
mrshrt: 'маршруты: