Data «Сидоров», «Алеша», 5, 3, 3

Data «», «», 0, 0, 0

 

Рассмотренная задача имеет чисто квалификационный характер проверки знаний информатики по школьной программе и умения самостоятельно составлять алгоритмы и программы решения на ЭВМ простейших информационных задач. С этой задачей справилось большинство участников олимпиады. Однако далеко не все преду­смотрели исключительные ситуации и в результате многие из них потеряли определенную часть баллов на указанных тестах.

Вторая олимпиадная задача также относится к классу информа­ционно-логических задач. Ее содержание заключается в переработке символьных данных.

 

Задача 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: 'маршруты:

Data 1, 2, 3, 4

Data 1, 2, 4, 3

Data 1, 3, 2, 4

Data 1, 2, 4, 3

Data 1, 4, 2, 3

Data 1, 4, 3, 2

tchks: 'координаты точек

Data 0, 0

Data 0, 3

Data 4, 0

Data 4, 3

 

Результаты выполнения на ЭВМ приведенной программы:

координаты точек:

0 0

4 0

4 3

 

маршруты: длина:

1 2 3 4 16

1 2 4 3 14

1 3 2 4 18

1 2 4 3 14

1 4 2 3 18

1 4 3 2 16

максимальный маршрут:

1 3 2 4

длина =18

минимальный маршрут:

1 2 4 3

длина = 14

 

Четвертую задачу можно отнести к геометрическим задачам, ре­шение которых опирается на некоторые геометрические законы и свойства. Эта задача наиболее сложная среди рассмотренных задач из-за необходимости привлечения определенных математических знаний для организации ее решения.

Задача 4. «Ломаная».

Найти все точки самопересечения разноцветной замкнутой линии, заданной на плоскости координатами своих вершин в порядке обхода ломаной. Данные о ломаной представляются таблицей:

 

х	у

 

Особенность этой задачи - большое число частных случаев, свя­занных с возможным вырождением или наложением отрезков ло­манной линии. Именно эти ситуации и составляют содержание те­стов, на которых большинство программ дают неправильные резуль­таты.

Приведем проверочные тесты:

Tecт₁. (Основной случай)

 

 

Правильные результаты:

точки пересечения

0.5 0.5

 

Тест ₂. (Основной случай)

 

 

Правильные результаты:

точки пересечения:

отсутствуют

 

Тест₃. (Наложение вершины)

 

0.5

 

Правильные результаты:

точки пересечения

0.5 0

 

Тест₄. (Наложение ребра)

 

0.2
0.8

 

Правильные результаты:

отрезок пересечения:

[0.2, 0] - [0.8, 0]

Для систематического конструирования алгоритмов и программы необходима разработка сценария диалога и описание метода решения поставленной геометрической задачи.

Сценарий

точек: <n>

координаты точек:

<k>: <x> <у>

……..

точки пересечения:

отрезок: <k> - <k+l> *

отрезок: <1> - <1+1>

точка: <х> <у>

………

отсутствуют

 

Метод решения данной задачи может быть основан на вычислении точек пересечения отрезков (х₁, у₁) - (x₂, у₂) и (х₃, y₃) - (х₄, y₄) как точек пересечения линий, проходящих через заданные отрезки, с помощью системы уравнений:

 

(y₂ – y₁)×(x – x₁) - (x₂ – x₁)×(y – у₁) = 0;

(у₄ – у₃)×(x – x₃) - (x₄ – x₃)×(у – y₃) = 0.

 

Решение этих уравнений может быть проведено вычислением определителей D, D_x, D_y приведенной системы уравнений:

 

(у₂ – у₁)×х - (х₂ – х₁)×у = (у₂ – y₁)×х₁ - (x₂ – x₁)×y₁;

(у₄ – y₃)×х - (х₄ – х₃) ×у = (у₄ – у₃)×х₃- (x₄ – x₃)×y₃,

 

для которой будет справедлив следующий набор расчетных формул:

 

х = D_x/D;

у = D_y/D;

D = (у₂ - у₁)×(х₄ - x₃) - (x₂ - x₁)×(y₄ - y₃);

D_x = [(y₂ - y_l)×x_l - (х₂ – x₁)×y₁] - (x₄ – х₃) - (x₂ – x₁)×[(y₄ – y₃)×x₃ - (х₄ – х₃)×y₃];

D_y = (у₂ - у₁)×[(у₄ – у₃)×х₃ - (x₄ - x₃)×у₃] - [(у₂ – y₁)×x₁ - (х₂ – x₁)×y₁]×(y₄ – y₃).

 

Факт пересечения пар отрезков может быть установлен из этих же уравнений подстановкой в правые части координат точек альтерна­тивного отрезка и сравнением значений этих выражений. А именно, отрезок [(х₃, у₃) - (х₄, у₄)] пересекает линию, проходящую через отрезок [(x₁, y₁) - (х₂, у₂)], если эти выражения имеют разные знаки:

 

(у₂ - у₁)×(х₃ – x₁) - (х₂ – х₁)×(y₃ – у₁) ´ (у₂ - у₁)×(х₄ – x₁) - (х₂ – x₁)×(y₄ – y₁) £ 0.

 

Соответственно, отрезок [(х₁, у₁) - (х₂, у₂)] пересекает линию, проходящую через отрезок [(х₃, у₃) - (х₄, у₄)], если аналогичные выражения имеют разные знаки:

 

(у₄ – у₃)×(х₁ – х₃) - (х₄ – х₃)×(у₁ – у₃)´(у₄ – у₃)×(х₂ – х₃) - (х₄ – х₃)×(у₂ – у₃) £ 0.

 

И наконец, самый тонкий момент - это частные случаи, когда отрезки ломаной оказываются на одной прямой линии. В этом случае отрезки либо вообще не пересекаются, либо имеют общую часть, которую можно определить из взаимного расположения отрезков на прямой.

В последнем случае общая часть отрезков находится из взаимо­расположения отрезков [(х₁, у₁) - (х₂, у₂)] и [(х₃, у₃) - (х₄, у₄)] на прямой. В данной ситуации взаиморасположение вершин отрезков можно выяснить, вычислив взаиморасположение между ними на прямой относительно отрезка [(х₁, у₁) - (х₂, у₂)] по следующим фор­мулам:

 

d₁ = 0;

d₂ = (х₂ – х₁)×(х₂ – х₁) + (у₂ – у₁)×(у₂ - 1);

d₃ = (х₃ – х₁)×(x₂ – х₁) + (у₃ - у₁)×(у₂ - 1);

d₄ = (х₄ – х₁)×(х₂ – х₁) + (у₄ – y₁)×(y₂ - 1).

 

Если d₂ < min (d₃, d₄) или max (d₃, d₄) < 0, то отрезки не пересе­каются. В противном случае необходимо выделить и отбросить две крайние точки, и тогда оставшиеся две точки зададут общую часть этих отрезков.

Опираясь на эти математические факты можно приступить к составлению алгоритмов и программы. Приведем программу, в которой установлено максимальное число точек nt = 200. Реальное число точек устанавливается при вводе исходных данных из перечня операторов data, записанных в конце текста программы.

¢ самопересечение ломаной

nt = 200

Dim x(nt), y(nt)

Gosub wod 'ввод данных

? «точки пересечения:»

np = 0 'число пересечении

for k = 1 to nt - 1

xl = x(k): yl = y(k)

x2 = x(k + I): y2 = y(k + 1)

for 1 = k + 1 to nt - 1

x3 = x(I): y3 = y(I)

х4 = x(I + 1): y4 = y(I + 1)

Gosub pint 'пересечение

Next 1

Next k

if np = 0 then? «отсутствуют»

End

 

pint: ¢ точка пересечения:

d213 = (у2 - yl)*(x3 - х1) - (х2 - х1)*(у3 - у1)

d214 = (у2 - у1)*(х4 - х1) - (х2 - х1)*(у4 - у1)

d431 = (у4 - у3)*(х1 - хЗ) - (х4 - х3)*(у1 - уЗ)

d432 = (у4 - у3)*(х2 - хЗ) - (х4 - х3)*(у2 - уЗ)

if d213*d2l4 > 0 or d431*d432 > 0 then

' нет пересечения

elseifd213*d214 < 0 or d431*d432 < 0 then

Gosub tchki ' расчет точки