• Вступление
• Программ's
• Голосование
• Послесловие

Здравствуйте!
Хочу порадовать всех. На сайте http://www.ibp7.narod.ru появился раздел, посвященный решению заданий. Мои решения вы всегда можете прочитать в номерах, а вот теперь вы можете прочитать решения других подписчиков.
Сегодняшний выпуск целиком и полностью посвящен решению задач. Мы расмотрим задачи о полиндроме, о переводе заглавных букв в строчные, о подсчёте некоторых тригонометрических функций, а так же задачу о Ханойских башнях.

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

Итак в прошлый раз я не объяснил про полиндром. Вообщем это довольно простая програмка. Хотя, когда сталкиваешься с этим в первый раз, всё таки задумываешься. Вообщем основная мысль такая: мы пробегаем строку с начала и с конца одновременно, пока не встретимся. Если при этом символы, отстояшщие на равном растоянии от концов, не будут равны , значит слово не полиндром:

К сожалению в оригинальном выпуске в программе была допущенна ошибка. Правильный вариант программы приведён ниже:

Program Polindrom;

var
  str : string;
  i, j : integer;
  flag : boolean;
begin
     i := 1;
     flag := true;

     readLn (str);
     j := ord (str[0]);

     while i < j do
     begin
          if str[i] <> str[j] then
          begin
               flag := false;
               break
          end;
		  { ВОТ ЭТО БЫЛО ПРОПУЩЕННО !! }
		  i := i + 1;
		  j := j - 1
	end;
		  
     if flag  then
        writeLn ('ДА !')
     else
        writeLn ('НЕТ !')
end.

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

Биты	76543210
Буква А:	01000001
Баква а:	01100001

значит нам для преобразования A в а нам нужно поменять 5 бит с 0 на 1. Остальные биты нужно не трогать. Давайте вспомним логические операции. Например OR - 0 or 1 = 1 или xor - 0 xor 1 = 1. Обе операции подходят. Теперь давайте придумаем число. Очевидно, что оно будет выглядеть как-то так:

Биты	76543210
	**1*****

При этом биты, обозначенные *, не должны поменятся. Давайте подберём число, что бы * or 1 = 1 и * or 0 = 0. Очевидно, что это число 0. Кстати эти рассуждения подойдут и для операции xor. Поэтому число у нас превращается 00100000b. Ну и соответственно текст программы:

program down;

var
 i : integer;
 str : string;
begin
     str := 'i''M WORLD-BEST pASCAL PROGRAMMER :)';
     writeLn (str);

     for i := 1 to ord (str[0]) do
     begin
          if (str[i] >= 'A') and (str[i] <= 'Z') then
             str[i] := chr ( ord(str[i]) or 32)
     end;

     writeLn (str)
end.

function Sin(X: Real): Real; - возвращает sin угла х (в радианах).
function Cos(X: Real): Real; - возвращает cos угла х (в радианах).
function ArcTan(X: Real): Real; - возвращает arctg числа Х.

С sin и cos я предпологаю знакомы все. Итак тангенсом угла А называется выражение tg A = sin A / cos A

Котангенсом называется выражение: ctg A = 1 / tg A = cos A / sin A

Соответственно существуют обратные функции, которые по значению дадут нам угол. Эти функции имеют те же имена, но с приставкой arc (arccos, arcsin, arctg, arcctg).

Многие ошибочно пологают, что раз называется обратная функция, то она равна 1 / функцию. Это не так. Давайте рассмотрим пример: пусть у нас есть два множества А и В:

множество А

множество В

пускай у нас есть функция B = F (A) т.е. некое правило, которое ставит в соответствие любому элементу множества А некий элемент множества В.

множество А

-> F (A) ->

множество В

Обратная функция (правило) должно нас возвращать из В в А. т.е. нужно придумать такую функцию (A = G (B)), что бы каждому элементу множества В ставился элемент А

множество А

-> F (A) -> <- G (B) <-

множество В

Поэтому arcsin не равен 1 / sin. Надеюсь, что это понятно.

Теперь посмотрим на наш скудный арсенал функций - всего 3 штуки.... мда. не густо. Но ведь язык Паскаль и был создан для обучения программированию. Вот сейчас мы и научимся считать любые тригонометрические функции.

Думаю вы уже догадались, как можно сосчитать tg и ctg, если не догадались, то посмотрите ещё раз сюда.

arcctg так же получается просто из arctg. Всё дело в том, что они связаны такой формулой: arctg A + arcctg A = П /2 (где П - число Пи = 3.141592653589). Поэтому получить из arctg arcctg несложно. Сложнее с arcsin и arccos. Они связаны между собой таким соотношением: arcsin A + arccos A = П / 2. Однако, как выразить arccos или arcsin через arctg я не знаю. Возможно такая формула и есть, возможно её нет. Мы будем исходить из другого.

Конечно, то что будет написанно ниже будет понятно не всем, однако это математика (высшая, а не элементарная) и тут ничего не поделать. Итак ряд Тейлора.

Если функция f (x) допускает в некоторой окрестности точки а разложение в степенной ряд по степеням х-а, то этот ряд имеет вид:

f (x) = f (a) + f^' (a) (x - a) + f^'' (a) (x - a) ² / 2! + ... + f⁽ⁿ⁾ (a) (x - a) ⁿ / n! + ...

при a = 0 получается ряд Маклорена, которым мы и будем пользоваться.

Давайте напишем такой ряд для arcsin:

x + 1/2 * x ³ / 3 + 1 / 2 * 1 / 3 * x⁵ / 5 + ... + (1 * 3 * 5* .... *(2n - 1) / (2 * 4 * 6 *....*2n) * x ^{2n + 1} / (2n + 1)

function arcsin (x : real) : real;
var
  i, j : integer;
  result, rs : real;

  function ipow (a : real; b : integer) : real;
  var
    res : real;
  begin
       res := 1;
       for j := 1 to b do
         res := res * a;
       ipow := res
  end;

begin
   result := 0;

   for i := 0 to 25 do
   begin
      rs := 1;

      for j := 1 to i do
           rs := rs * (2 * j - 1) / (2 * j);

      result := result + rs * ipow (x, 2 * i + 1) / (2 * i + 1)
   end;
   arcsin := result
end;

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

Следующая задача, называется задачей о Ханойских башнях.

Пусть у нас имеется 3 стержня (назовём их X, Y, Z) и N дисков. Наденем все диски на стержень Х в порядке возрастания: в самом низу окажется самый большой диск, в верху самый маленький. Задача состоит в том, что бы перенести эти диски со стержня Х на стержень Y (в том же порядке). Использовать при этом можно только стержень Z. За один раз можно переносить только один диск. Любой диск можно разместить либо на пустом стержне, либо поверх диска большего размера (соответственно вверху всегда должны быть маленькие диски).

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

1. в цикле: пока число ступенек не равно 0
2. через рекурсию: спускаемся на одну ступеньку, проверяем не на земле ли мы? да - выход, нет - вызовем себя ещё раз

var i : integer;

procedure demo;
begin
   i := i + 1;
   writeLn ('Произошёл ', i,'-ый вызов процедуры');
   demo
end;

begin
  i := 0;
  demo
end.

Можете убедится, что мы не освобождаем эту память, т.к. не доходим до слова end (жмите F7, если забыли.

Глубиной рекурсии называется количество вызовов процедуры(функции) саму себя. В предыдущем примере, мы превысили допустимо возможную глубину и были наказаны ошибкой 202.

Так вот для решения задачи о ханойских башнях нам понадобится рекурсия. Лучшим вариантом будет, если вы возьмёте ручку и бумагу и нарисуете 3 палки (это X, Y, Z :) и на Х поставите 3 чёрточки разных размеров. Это башни :) Так вот я сейчас буду объяснять, как решить такую задачу, а вы для наглядности рисуйте. Диски нумеруем так: самый верхний - 1, самый средний 2, самый нижний - 3.

Сначала перенесём диск 1 с Х на Y.
потом перенесём диск 2 с Х на Z.
теперь перенесём диск 1 (не забыли где он у нас :) с Y на Z.
Теперь подходим ко второму этапу: переносим диск 3 с Х на Y
переносим диск 1 с Z на Х.
перемещаем диск 2 с Z на Y.
... и заключительный штрих - перемещаем диск 1 с Х на Y.
Всё!

поупражнявшись с несколькими башнями можно прийдти к такому алгоритму:

• переместить N-1 дисков с X на Z, используя при этом Y для временного хранения.
• перемещаем N-ый диск с Х на Y.
• перемещаем N-1 дисков с Z на Y, используя X для временного хранения.

Вот пример реализации этой задачи:

Program Tower_of_hanoi;

uses CRT;

procedure Hanoi (n : integer; x, y, z : char);
begin
     if n <> 0 then
     begin
          Hanoi (n - 1, x, z, y);
          writeLn ('Перемещаем диск ', n, ' c  ',  x,  ' на ', y);
          Hanoi (n - 1, z, y, x)
     end
end;

var
   disk : integer;
begin
     ClrScr;
     write ('Сколько дисков ?');
     readLn (disk);
     Hanoi (disk, 'X', 'Y', 'Z')
end.

• переместить N-1 дисков с X на Z, используя при этом Y для временного хранения. - Hanoi (n - 1, x, z, y);
• перемещаем N-1 дисков с Z на Y, используя X для временного хранения. - Hanoi (n - 1, z, y, x)

Сколько дисков ?3
Перемещаем диск 1 c  X на Y
Перемещаем диск 2 c  X на Z
Перемещаем диск 1 c  Y на Z
Перемещаем диск 3 c  X на Y
Перемещаем диск 1 c  Z на X
Перемещаем диск 2 c  Z на Y
Перемещаем диск 1 c  X на Y

Отвлечёмся ещё на теорию: рекурсия может быть неявной. Например такой:

procedure A;
begin
 .....
	B;
........
end;

procedure B;
begin
.........
   A;
 ......
 end;

procedure Flip(N: Integer); forward;

procedure Flop(N: Integer);
begin
  WriteLn('Flop');
  if N > 0 then
      Flip(N - 1)
end;

procedure Flip;
begin
  WriteLn('Flip');
  if N > 0 then
      Flop(N - 1)
end;

begin
  Flop (5)
end.

• procedure Flip(N: Integer); forward;
• procedure Flip;

Ну вот практика и кончилась. Конечно рассмотреть большое множество задач нам не удасться. Поупражняйтесь в рекурсии. Это пригодится. Вот кстати и очередное задание, для тех кто его делает, - написать функцию для вычисления факториала с помощью рекурсии. На этом всё. На следующей неделе увидимся чаще!