Отправляет email-рассылки с помощью сервиса Sendsay

Всё о работе в Интернет

  Все выпуски  

Занятие 18.


И сегодня мы с вами, уважаемые подписчики, продолжаем подготовку к изучению методов и средств программирования разветвлений.

Ещё две задачи закрепят наше умение строить алгоритмы и подпрограммы с результатами логического типа.

И ЕЩЁ ПАРА АЛГОРИТМОВ С РЕЗУЛЬТАТАМИ ЛОГИЧЕСКОГО ТИПА

1. Решение задачи “Кольцо”.

Задача L.2.5. “Кольцо”. Плоское кольцо образовано двумя концентрическими окружностями радиусами R1 и R2 с центрами в начале координат. Построить алгоритм и подпрограмму для определения того, принадлежит ли кольцу заданная точка с координатами (xy). Считать, что точка, расстояние которой от начала координат совпадает с одним из радиусов, также принадлежит кольцу.

Из двух концентрических окружностей, образующих кольцо, ту, что имеет больший радиус, назовём внешней, а вторую – внутренней. Общее условие принадлежности точки кольцу будем рассматривать в виде двух составляющих:

1) точка считается принадлежащей кольцу, если она находится в пределах внешнего круга и за пределами внутреннего, то есть, если её расстояние от начала координат больше радиуса внутренней окружности и меньше радиуса внешней окружности;

2) точка считается принадлежащей кольцу, если её расстояние от начала координат совпадает с одним из радиусов.

Из условия задачи и из всего вышесказанного ясно, что необходимо знать расстояние z заданной точки от центра концентрических окружностей. Его несложно вычислить с помощью общеизвестной формулы = Sqrt ( x*+ y*).

Сначала поработаем с первым условием. Здесь нужно будет рассмотреть два варианта, существование которых связано с соотношением величин радиусов R1 и R2. Не зная, какой из них больший фактически, мы вынуждены перефразировать первое условие так:

-       предположим, что R1 < R2, тогда точка принадлежит кольцу, если она находится за пределами первого круга и в пределах второго;

-       предположим, что R1 > R2, тогда точка принадлежит кольцу, если она находится за пределами второго круга и в пределах первого.

Введём две вспомогательные логические переменные a и b, с помощью которых  обозначим результат определения того, находится ли наша точка в пределах кругов с радиусами R1 и R2 соответственно, а именно:

-       логическая переменная a, вычисляемая по формуле = z < R1, принимает истинное значение, если точка находится в пределах первого круга;

-       логическая переменная b, вычисляемая по формуле = z < R2, принимает истинное значение, если точка находится в пределах второго круга.

Таким образом, первое условие можно представить в виде следующего логического выражения: ( не a и b ) или ( не b и ).

Чисто в исследовательских целях составим для полученного логического выражения таблицу истинности:

a

b

не a

не a и b

не b

не b и a

не a и b или не b и a

НЕТ

НЕТ

ДА

НЕТ

ДА

НЕТ

НЕТ

НЕТ

ДА

ДА

ДА

НЕТ

НЕТ

ДА

ДА

НЕТ

НЕТ

НЕТ

ДА

ДА

ДА

ДА

ДА

НЕТ

НЕТ

НЕТ

НЕТ

НЕТ

И что же мы обнаружили? Мы обнаружили, что значения логического выражения, соответствующего первому условию, совпадают со значениями логического выражения xor b (см. занятие 15). Таким образом, в результате проведённого исследования к нам пришло понимание того, что значение логического выражения xor b истинно в тех случаях, когда логические переменные a и b противоположны по смыслу (точка считается принадлежащей кольцу, если она находится в пределах внешнего круга и за пределами внутреннего).  

Теперь поработаем со вторым условием. Здесь всё просто. Точка принадлежит кольцу, если её расстояние от начала координат совпадает с одним из радиусов. Логическое выражение ( z = R1 ) или ( z = R2 ) истинно именно в этих случаях.

Теперь можно построить алгоритм решения поставленной задачи в виде функции логического типа, принимающей истинное значение только в том случае, если заданная точка принадлежит заданному кольцу.

Алгоритм и его перевод на Паскаль выглядят следующим образом:

алг Кольцо ( x, y, R1, R2: вещ ): лог
   дано
 координаты точки и радиусы кольца
   надо ДА, если точка принадлежит кольцу  
нач
z: вещ; a,b: лог
   z := Sqrt ( x*x + y*y );
   
a := z < R1; b := z < R2;
   Кольцо := a xor b или (z = R1) или (z = R2)
кон

Function Ring ( x, y, R1, R2: Real ): Boolean;
   Var z: Real; a,b: Boolean;
Begin
   z := Sqrt ( x*x + y*y );
   a := z < R1; b := z < R2;
   Ring := a Xor b Or (z = R1) Or (z = R2)
End;

Естественные ограничения на исходные данные задачи: координаты точки – произвольные вещественные числа, радиусы концентрических окружностей, образующих кольцо, – произвольные положительные вещественные числа.

2. Решение задачи “Шахматная доска”.

Задача L.2.6. “Шахматная доска”. Поле шахматной доски определяется парой натуральных чисел, каждое из которых не превосходит восьми: первое число – номер вертикали (при счёте слева направо), второе – номер горизонтали (при счёте снизу вверх). Даны натуральные числа k, l, m, n, каждое из которых не превосходит восьми. Требуется выяснить, являются ли поля (k, l) и (m, n) полями одного цвета.

Эта задача – фрагмент задачи №76, которую я взял из книги “Задачи по программированию” авторов С.А. Абрамова, Г.Г. Гнездиловой, Е.Н. Капустиной и М.И. Селюн, вышедшей в главной редакции физико-математической литературы издательства “Наука” в 1988 году.

Я думаю, что все знают, как выглядит шахматная доска. Поля чёрного и белого цвета чередуются на ней как по вертикали, так и по горизонтали. При этом левое нижнее её поле с координатами (1, 1) имеет чёрный цвет.       

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

Выберем несколько полей одного и того же чёрного цвета: (1, 1), (1, 3), (2, 2), (2, 4), (3, 1), (3, 3), (4, 2), (4, 4) и т.д. Сложим между собой координаты любой пары полей:

-       (1, 1) и (1, 3); 1 + 1 + 1 + 3 = 6;

-       (1, 3) и (4, 2); 1 + 3 + 4 + 2 = 10;

-       (2, 4) и (4, 4); 2 + 4 + 4 + 4 = 14;

-       (3, 1) и (2, 2); 3 + 1 + 2 + 2 = 8 и т.д.

Замечаем, что каждый раз результатом оказывается чётное число.

Теперь выберем несколько полей одного и того же белого цвета: (1, 2), (1, 4), (2, 1), (2, 3), (3, 2), (3, 4), (4, 1), (4, 3) и т.д. И снова сложим между собой координаты любой пары полей:

-       (1, 2) и (2, 3); 1 + 2 + 2 + 3 = 8;

-       (1, 2) и (3, 4); 1 + 2 + 3 + 4 = 10;

-       (2, 3) и (3, 4); 2 + 3 + 3 + 4 = 12;

-       (3, 2) и (1, 4); 3 + 2 + 1 + 4 = 10 и т.д.

Как видим, и в этих случаях каждый раз результатом оказывается чётное число.

С другой стороны, если складывать между собой координаты любой пары разноцветных полей, то получим следующее:

-       (1, 1) и (3, 4); 1 + 1 + 3 + 4 = 9;

-       (1, 3) и (1, 4); 1 + 3 + 1 + 4 = 9;

-       (2, 4) и (2, 3); 2 + 4 + 2 + 3 = 11;

-       (3, 1) и (3, 4); 3 + 1 + 3 + 4 = 11 и т.д.

Теперь мы обнаруживаем, что найденный нами ранее признак нарушается: каждый раз результатом оказывается нечётное число.

Для работы с четными и нечётными числами можно воспользоваться стандартной логической функцией Паскаля Odd(X), где X – целочисленное выражение. Эта функция принимает значение True, если X – нечётно, и значение False – в противном случае. 

Окончательно приходим к выводу, что логическое выражение Not Odd ( k + l + m + n) будет истинным в том случае, если поля с координатами (k, l) и (m, n) – одноцветные.

Теперь можно построить алгоритм решения поставленной задачи в виде функции логического типа, принимающей истинное значение только в том случае, если заданные поля являются полями одного цвета.

Алгоритм и его перевод на Паскаль выглядят следующим образом:

алг Шахматы ( k, l, m, n: нат ): лог
   дано
 координаты двух полей
   надо ДА, если поля – одноцветные  
нач
   Шахматы := не Odd ( k + l + m + n )
кон

Function Chess ( k, l, m, n: Byte ): Boolean;
Begin
   Chess := Not Odd ( k + l + m + n )
End;

В заключение отметим, что естественное ограничение на аргументы состоит в том, что их значения должны находиться в пределах от 1 до 8.

Решение обеих задач в виде программ запишите самостоятельно.

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

Уважаемые подписчики! При необходимости задать вопрос, проконсультироваться, уточнить или обсудить что-либо обращайтесь через Гостевую книгу моего персонального сайта http://a-morgun.narod.ru

С уважением, Александр.

 


В избранное