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

Разделы: Информатика


Цель урока - по заданному условию задачи выбрать оптимальный вариант решения поставленной задачи, с использованием алгоритмов ветвления.

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

Для каждого варианта составляется алгоритм, пишется программа на языке программирования Pascal, проводится отладка и тестирование на компьютере. Выбирается оптимальный вариант.

I. ФОРМУЛИРОВКА ЗАДАЧИ:

  1. Заданы стороны 1 прямоугольника A1,B1 и стороны 2 подобного прямоугольника A2,B2 с одним центром координат, параллельными  сторонами и одинаковым поворотом относительно центра координат.
  2. Определить поместится ли первый прямоугольник во второй.

II. ПОСТАНОВКА ЗАДАЧИ:

При решении этой задачи возможны три варианта ответов:

  1. Если стороны первого прямоугольника, меньше сторон второго прямоугольника, то поместится.
  2. Если стороны первого прямоугольника, больше сторон второго прямоугольника, то не поместится.
  3. Если стороны первого прямоугольника, равны сторонам второго прямоугольника, то прямоугольники впишутся друг в друга.

Чтобы получить три варианта ответов необходимо при любом алгоритме для этой задачи  три раза тестировать программу.

ОПТИМИЗАЦИЯ РЕШЕНИЯ ЗАДАЧИ

ВЫБОР ПЕРВОГО РЕШЕНИЯ: ДВА ПРОСТЫХ УСЛОВИЯ

Составим алгоритм ветвления с простыми условиями:

Если (A1<= A2), то

       Если  (B1<=B2),

       то вывод (‘Поместится’)

       Иначе вывод(‘НЕ поместится’);

Недостаток этого метода: используется два алгоритма ветвления. (Отдельно сравниваются стороны каждого прямоугольника).

ПРОГРАММА ДЛЯ ПЕРВОГО РЕШЕНИЯ:

PROGRAM  VETV_1;
var A1,B1,A2,B2:INTEGER;
BEGIN
     READLN(A1,B1,A2,B2);
IF A1<=A2 THEN
     BEGIN
          IF B1<=B2 THEN  BEGIN
               WRITELN('POMESTITSA');
                                         END
END
ELSE
BEGIN
           WRITELN('NE POMESTITSA');
    END;
    WRITELN(' A1=',A1:3,' B1=',B1:3,' A2=',A2:3,' B2=',B2:3);
END.

АЛГОРИТМ  ПЕРВОГО РЕШЕНИЯ: ДВА ПРОСТЫХ УСЛОВИЯ

ВЫБОР ВТОРОГО РЕШЕНИЯ: СЛОЖНОЕ УСЛОВИЕ

Чтобы уменьшить количество  операторов, составим сложное условие.

Если (A1<= A2) и  (B1<=B2), то вывод (‘Поместится’)
                                                      Иначе вывод(‘НЕ поместится’);

Недостаток этого метода: необходимо  два раза тестировать одну  Ветвь «ДА»: 

  1. Стороны первого прямоугольника, меньше  сторон второго прямоугольника. Вывод (‘Поместится’).
  2. Стороны первого прямоугольника, равны  сторонам второго прямоугольника. Вывод (‘Поместится’).
  3. Хотя для второго  варианта более корректный ответ:
  4.  Вывод (‘Прямоугольники впишутся друг в друга ‘).

ПРОГРАММА ДЛЯ ВТОРОГО РЕШЕНИЯ

Сложное условие.

PROGRAM VETV_2;
var A1,B1,A2,B2:INTEGER;
BEGIN
     READLN(A1,B1,A2,B2);
     IF (A1<=A2) AND (B1<=B2)
     THEN
     BEGIN
          WRITELN('POMESTITSA');
     END
     ELSE
     BEGIN
          WRITELN('NE POMESTITSA');
     END;
     WRITELN(' A1=',A1:3,' B1=',B1:3,' A2=',A2:3,' B2=',B2:3);
END.

АЛГОРИТМ ВТОРОГО РЕШЕНИЯ: СЛОЖНОЕ УСЛОВИЕ

ВЫБОР ТРЕТЬЕГО РЕШЕНИЯ
Вложенное ветвление и сложное условие.

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

Чтобы уменьшить число операторов, составим сложное условие.

Если (A1<A2) и  (B1<B2),
то вывод (‘Поместится’)
          иначе если (A1>A2) и  (B1>B2),
то вывод(‘НЕ поместится’)
           иначе вывод (‘Прямоугольники впишутся друг в друга ‘);

Достигнут более корректный результат, когда каждая ветвь отвечает за один из трех вариантов.

ПРОГРАММА ДЛЯ ТРЕТЬЕГО РЕШЕНИЯ

var A1,B1,A2,B2:INTEGER;
BEGIN
     READLN(A1,B1,A2,B2);
     IF (A1<A2) AND (B1<B2)
     THEN BEGIN
          WRITELN('POMESTITSA');
          END
     ELSE
         IF (A1>A2) AND (B1>B2)
         THEN
         BEGIN
              WRITELN('NE POMESTITSA');
         END
         ELSE
         BEGIN
              WRITELN('VPISHETSA');
         END;
         WRITELN(' A1=',A1:3,' B1=',B1:3,' A2=',A2:3,' B2=',B2:3);
END.

Достигнут более корректный результат, когда каждая ветвь отвечает за один из трех вариантов.

ВЫВОД: Выбираем третье решение из трех вариантов алгоритмов для этой задачи.

АЛГОРИТМ ТРЕТЬЕГО РЕШЕНИЯ

Вложенное ветвление и сложное условие.