Функции

Как уже отмечалось ранее функции очень похожи на процедуры. Объявить функцию можно следующим образом:

function ИМЯ ( СПИСОК_ПАРАМЕТРОВ) : ТИП_ВОЗВРАЩАЕМОГО_ЗНАЧЕНЯ

function Power (a, b : real) : real;

function F : integer;
begin
	F := 3		
end;

такая функция всегда возвратит 3. Давайте теперь договоримся об обозначениях. Раньше мы писали просто имя процедуры (или функции), когда рассказывали о ней. Теперь же мы будем кроме описания помещать прототип функции (процедуры) - её заголовок. Например в рассказе об ClrScr мы бы описали её так:

procedure Clrscr;

function Round(X: Real): Longint;

function Ln(X: Real): Real;

function Exp(X: Real): Real;

function power (a, b : real) : real;
begin
     if a > 0 then
        power := exp (b * ln (a))
     else
      if a < 0 then
         power := exp (b * ln (abs (a)))
      else
          power := 0
end;

данная функция рассматривает сразу три случая: а > 0, a < 0 и a = 0. Однако сразу напрашивается четвёртый вариант: когда b=0. Ведь любое число в 0 степени - это 1. Поэтому зачем нам тратить лишнее время на вычисление логарифмов и экспаненты ? Давайте сразу проверим b и присвоим power значение 1. Добавим такой код в начало функции:

if b = 0 then 
   power := 1

Давайте посмотрим в отладчике как происходит выполнение нашей функции (при b=0) жмите F7.... и наблюдайте, что всё равно происходит проверка условий и подсчёт экспанент... м-да. Однако выход (в буквальном смысле этого слова :) есть всегда - процедура exit (англ. выход):

procedure exit;

if b = 0 then
begin 
   power := 1;
   exit
end;

Давайте посмотрим работу exit через отладчик ... вроде всё работает, НО теперь если a = 0 и b = 0, то возвращаемое значение будет 1, хотя нужно возвращать 0 (это ошибка, математики не определились про 0⁰). Так что нужно проверить и этот случай. Думаю, что довести до ума функцию для вас не составит труда.

Домашнее задание

Итак как вы помните мы решили провести эксперимент с домашним заданием: ваши мысли по поводу работы генератора случайных чисел и сортировка массива. Про сортировку мы поговорим в разделе программа. Сейчас место генератора. Всего было полученно 7 ответов. Все они были правильные. Некоторые из них содержали просто 3 слова по этому поводу, некоторые из них довольно обширные. Как же на самом деле работает генератор случайных чисел ? Итак в компьютере всё постоянно, ничего не меняется.... только если.... ага! посмотрите в правый нижний угол экрана :) правильно ЧАСЫ! Вот что меняется ! Итак ваша догадка совершенно правильна. В основе случайных чисел лежит таймер. Однако само время не случайно по своей природе. Поэтому на основе одного момента времени составляется последовательность чисел, которые потом выдаются. Поэтому мы и дожны инициализировать генератор случайных чисел с помощью процедуры randomize! Сама же теория получения случайных чисел была изложена в одном из ответов, который мы и процитируем:

цитата Ivs 10.11.2002

Для работы ЭВМ со случайными числами вначале пытались вводить эти числа из вне. Вводили в память готовые таблицы случайных чисел. Строили приборы, использующие случайные физические процессы, например радиоактивный распад, и вводящие полученные числа в машину. Все это было достаточно плохо.Таблицу случайных чисел ЭВМ быстро исчерпывала, а случайное физическое явление нельзя было повторить, чтобы проверить вычисления. Таким образом возникла пародаксальная задача - вырабатывать в самой ЭВМ случайные числа, но такие, чтобы их можно было повторить и чтобы последующее число вычислялось по предыдущим, но не зависело от них. Задача, разумеется, неразрешимая. Но Дж.Нейман придумал алгоритм, последовательно вычисляющий числа x1,x2,..., очень похожие на случайные, равномерно распределенные от 0 до 1. Их называют псевдослучайными, или просто случайными. Этот алгоритм такой: Метод середины квадрата. Будем строить 4-х значные псевдослучайные числа. Возьмем произвольное целое k из диапазона 0<k<10^4. Это будет наше первое число. Если нам уже известно k(i), то возведем его в квадрати возьмем 4 средних разряда. Если, например, k(i)=2251, то возведя в квадрат, получим k(i)^2=05067001, и поэтому k(i+1)=0670. Чтобы получить из нашей последовательности k(1),k(2),...последовательность действительных чисел x1,x2,... равномерно распределённые между 0 и 1, надо положить: x(i)=k(i)/10^4. Несмотря на очевидные возражения, вроде того, что эта последовательность непременно начнет повторяться или что она может выродиться в сплошные нули, числа x1,x2 похожи на случайные. В среднем в половине случаев x(i)<x(i+1), а в половине наоборот. Среди первой тысячи чисел x1,x2,...непременно половина будет меньше 1/2, а половина больше, и тд. Разработаны и более сложные способы получения псевдослучайных последовательностей, препятствующие обращения членов последовательности в нули и удлиняющие период её повторения. Но принцип они используют тот же, и для понимания существа дела достаточно изложенного.

Программа

Вернёмся к программе сортировки массива. Итак задача стояла следующим образом (краткое содержание предыдущих 5000 серий :) - программу, которая сортирует массив пузырьковой сортировкой. Этим делом мы сегодня и займёмся. Естественно, что мы используем полученные знания про процедуры и функции. При этом мы будем считать число сравнений и перестановок. Поэтому напишем такую простую функцию для сравнения двух чисел. При этом переменная CmpCount (число сравнений) предпологается глобальной:

function cmp (a, b : integer) : integer;
begin
     CmpCount := CmpCount + 1;
     cmp := ord (a > b)
end;

Я надеюсь вы помните, что ord преобразовывает логическое выражение к целому числу. У нас логическое выражени a > b истинно, когда а больше b, поэтому функция вернёт нам 1 в этом случае и 0 в случае, если а меньше b. Так же напишем процедуру для перестановки значений a и b. В этом случае воспользуемся адрессами переменных. Переменная SwapCount - число перестановок - глобальная:

procedure swap (var a, b : integer);
var
  c : integer;
begin
     c := a;
     a := b;
     b := c;
     SwapCount := SwapCount + 1
end;

Здесь я думаю всё прозрачно. Теперь подойдём к реализации алгоритма сортировки. Основная мысль алгоритма: сравниваются два соседних элемента, если порядок нарушен, то они меняются местами. Первая мысль, которая приходит ко мне в голову: нужно продолжать поиск по всем элементам до тех пор пока будет совершена хоть одна перестановка. Давайте введём переменную flag - когда она равна 1, то совершенна перестановка, если 0 - то перестановки не было. Поэтому напишем такое начало:

const
   Size = 10;
var 
	flag : integer;
	i      : integer;
	CmpCount : integer;
	SawpCount : integer;
	a    : array [1 .. size] of integer;

procedure PrintArray;
var
   i : integer;
begin
     for i := 1 to Size do
        write (A[i] : 4);
     writeLn
end;

begin
   randomize;
   flag := 1;
   SwapCount := 0;
   CmpCount := 0;

   for i := 1 to Size do
      A[i] := random (100);
	
   PrintArray;

   {Начало сортировки}
   while flag = 1 do 
   begin
        flag := 0;
   end;

   PrintArray;
   writeLn ('Число сравнений - ', CmpCount);
   writeLn ('Число перестановок - ', SwapCount);
   ReadLn
end.

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

while flag = 1 do 
begin
   flag := 0;
   for i := 1 to Size - 1 do
      if cmp (A[i], A[i +1]) = 1 then
      begin
	     swap (A[i], A[i + 1]) ;
  	     flag := 1
      end
end;

обратите внимание, что в цикле мы идём до Size - 1 так как сравниваем i-тый элемент с i+1 элементом. Поэтому i+1 не должно выходить за границу массива, которая у нас и равна Size (т.е. i + 1 <= Size следовательно i <= Size - 1). Мы устанавливаем flag в 1, только если произошла перестановка! Таким образом число сравнений и обменов у нас получается: (Size - 1) * Size За один проход максимальный элемент становится на свою позицию, по этому последний элемент проверять не надо. За второй проход не надо проверять предпоследний и так далее. Поэтому мы можем запомнить максимальный номер соседа, с которым происходило сравнение. И пробегать в цикле соответственно до этого номера

n := Size;

while n > 0 do
begin
      last := 0;
      for i := 1 to n - 1 do
          if cmp (B[i], B[i + 1]) = 1 then
          begin
             swap (B[i], B[i + 1]);
             last := i + 1
          end;
      n := last
end;

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