nextupprevious

Next:6.2 Построение программ с процедурами и функциями
Up:6.1 Подпрограммы: процедуры и функции
Previous:6.1.9 Метод структурной индукции
 

6.1.10 Упражнения

1. Укажите, какие из приведенных описаний функций и процедур не содержат ошибок:

(1) procedure ВВОД; begin read(X) end ВВОД;

(2) procedure ВЫВОД (X:array[1..100] of real);
var I : integer;
begin for I := 1 to 100 do write X[I] end ВЫВОД;

(3) procedure ВВОД (Х:ВЕКТОР); var I : ИНДЕКС;
begin for I := 1 to N do read(X) end ВВОД;

(4) procedure ЗАМЕНА (var X,Y :ВЕКТОР); var Z : ВЕКТОР;
begin if Сумма(Х) $>$ Сумма(Y) then
begin Z := X; X := Y; Y := Z end
end ЗАМЕНА;

(5) procedure Сумма (var X;Y;Z : real); begin X := Y + Z end Сумма;

(6) procedure Сумма (Y,Z : real, var X : real); X := Y + Z ;

(7) procedure Сумма (Y,Z : real; var X : real); begin X := Y+Z end Сумма;

(8) Real function МАКС (X,Y : integer);
begin if X $>$ Y then write(X) else write(Y) end;
(9) function МАКС (X,Y : integer) : integer;
begin if X $>$ Y then write(X) else write(Y) end;

(10) function ФАКТ (N:Integer):Integer;
var I : Integer;
begin ФАКТ := 1; for I := 2 to N do ФАКТ := ФАКТ $\ast$ I end;

(11) function ПОИСК (X:Real; A:ВЕКТОР) : Boolean;
var I : ИНДЕКС;
begin for I := 1 to N do if A[I] = X then ПОИСК := True end ПОИСК;

(12) procedure SUM (X,Y : ВЕКТОР) : ВЕКТОР;
var I : ИНДЕКС; Z : ВЕКТОР;
begin for I := 1 to N do Z[I] := X[I] + Y[I]; SUM := Z end;

(13) procedure ПЯТЬ : Integer; begin ПЯТЬ := 5 end;

(14) procedure MULT (K,N : Integer):Integer;
begin if N $>$ 0 then MULT := K + MULT(K,N-1)
else MULT := -MULT(K,-N)
end;

(15) procedure MULT (K,N : Integer):Integer;
begin if N = 0 then MULT := 0
else if N $>$ 0 then MULT := K + MULT(K,N-1)
else MULT := -MULT(K,-N)
end;

(16) procedure Сумма (X:Real; N:Integer):Real;
var I : Integer; S:Real;
procedure POWER (X:Real; N:Integer):Real;
begin if N = 0 then POWER := 1
else POWER := X $\ast$ POWER(X,N-1)
end;
procedure ФАКТ (N:Integer):Integer;
begin if N = 0 then ФАКТ := 1 else ФАКТ := N $\ast$ ФАКТ(N-1) end;
begin S := 0; for I := 1 to N do S := S + POWER(X,I) / ФАКТ(I);
Сумма := S
end;

2. Укажите, для решения каких задач написаны приведенные ниже программы и какие из них не содержат ошибок (если ошибки есть, то исправьте их):

(1)
module ЧислоДнейДоРождества;
    type МЕСЯЦЫ = (ЯНВАРЬ, ФЕВРАЛЬ, МАРТ, АПРЕЛЬ, МАЙ, ИЮНЬ, ИЮЛЬ, АВГУСТ,СЕНТЯБРЬ,
            ОКТЯБРЬ,НОЯБРЬ,ДЕКАБРЬ);
    var ДЕНЬ,ГОД,Сумма : integer;МЕСЯЦ,СЛЕДМЕСЯЦ:МЕСЯЦЫ;
    procedure ЧТЕНИЕДАТЫ (var ДЕНЬ :Integer;
                                                   var МЕСЯЦ : МЕСЯЦЫ; var ГОД : Integer);
        function ПРЕОБРАЗОВАНИЕ (НОМЕРМЕСЯЦА :Integer;
                       МЕСЯЦЫ;
        begin case НОМЕРМЕСЯЦА of

1:return ЯНВАРЬ;
2:return ФЕВРАЛЬ;
3:return МАРТ;
4:return АПРЕЛЬ;
5:return МАЙ;
6:return ИЮНЬ;
7:return ИЮЛЬ;
8:return АВГУСТ;
9:return СЕНТЯБРЬ;
10:return ОКТЯБРЬ;
11:return НОЯБРЬ;
12:return ДЕКАБРЬ
        end
    end;
    begin read (ГОД, НОМЕРМЕСЯЦА,ДЕНЬ);
            if (ГОД$<$1800) or (ГОД$>=$2100) or (НОМЕРМЕСЯЦА $<$1)
                or (НОМЕРМЕСЯЦА $>$ 12) or (ДЕНЬ$<$1) or (ДЕНЬ$>$
                ДЛИНАМЕСЯЦА(МЕСЯЦ,ГОД)
            then write ('ОШИБКА ВО ВХОДНЫХ ДАННЫХ!')
            end
    end;
    procedure ДЛИНАМЕСЯЦА (МЕСЯЦ:МЕСЯЦЫ;ГОД:integer)integer;
        var ВИСОКОСНЫЙГОД : Boolean;
    begin if МЕСЯЦ = ФЕВРАЛЬ
              then ВИСОКОСНЫЙГОД := (ГОД mod = 4) &
                       (not (ГОД mod 100 = 0) or (ГОД mod 400 = 0));
                        if ВИСОКОСНЫЙГОД then ДЛИНАМЕСЯЦА := 29
                        else ДЛИНАМЕСЯЦА := 28
                        end
              elsif (МЕСЯЦ = СЕНТЯБРЬ) or (МЕСЯЦ = ИЮНЬ) or
                       (МЕСЯЦ = АПРЕЛЬ) or (МЕСЯЦ = НОЯБРЬ)
              then ДЛИНАМЕСЯЦА := 30
              else ДЛИНАМЕСЯЦА := 31
              end
   end;
begin ЧТЕНИЕДАТЫ (ДЕНЬ,МЕСЯЦ,ГОД);
          if (МЕСЯЦ = ДЕКАБРЬ) & (ДЕНЬ = 25) then Сумма := 25 - ДЕНЬ
          else Сумма := ДЛИНАМЕСЯЦА (МЕСЯЦ,ГОД) - ДЕНЬ;
                 if МЕСЯЦ = ДЕКАБРЬ then СЛЕДМЕСЯЦ := ЯНВАРЬ; ГОД := ГОД + 1
                else СЛЕДМЕСЯЦ := Succ(МЕСЯЦ)
                end;
                for МЕСЯЦ := СЛЕДМЕСЯЦ to НОЯБРЬ do
                      Сумма := Сумма + ДЛИНАМЕСЯЦА (МЕСЯЦ,ГОД)
                end;
                Сумма := Сумма + 25
          end;
          WriteLn ('Число ДНЕЙ ДО РОЖДЕСТВА =', Сумма)
end ЧислоДнейДоРождества.

(2)
module ПоискМиниМакс;
        const N = 20;
        type ВЕКТОР = array N of integer;
        var A : ВЕКТОР; I,M : integer;
        procedure МИНИМАКС (var B : ВЕКТОР);
               var I : integer; MIN,MAX : integer;
               procedure ЗАМЕНА (X,Y : integer);
                    begin if X $>$ MAX then MAX := X  end;
                              if Y $<$ MIN then MIN := Y end
                    end;
       begin MIN := B[1]; MAX := MIN; I := 2;
                while I $<$ N do
                       if B [I] $>$ B [I+1] then ЗАМЕНА(В[I], B[I+1])
                       else ЗАМЕНА (B[I+1], B[I])
                       end;
                       if I = N then
                            if B[N] $>$ MAX then MAX := B[N]
                            elsif B[N] $<$ MIN then MIN := B[N]
                            end;
                            writeln ('MIN=', MIN, 'MAX=', MAX)
                       end
               end
       end;
       procedure ВВОД (В:ВЕКТОР);
            var I : integer;
        begin write ('ИСХОДНЫЙ ВЕКТОР:');
                  for I := 1 to N do read(B[I]); write(B[I]:5) end;
                  writeln
        end;
begin ВВОД(А); МИНМАКС(А); writeln('ИСХОДНЫЙ ВЕКТОР:');
    for I := 1 to N do Read(M); A[I] := A[I] + M;Write(A[I]:5) end;
    МИНМАКС(А)
end ПоискМиниМакс.

(3) module УстойчивыеБраки;
    const N = 10;
    type МУЖЧИНЫ = integer; ЖЕНЩИНЫ = integer, РАНГ = integer;
    var M:МУЖЧИНЫ; W:ЖЕНЩИНЫ; R:РАНГ;
    WMR : array N, N of ЖЕНЩИНЫ;
    MWR : array  N, N of МУЖЧИНЫ;
    RMW : array N, N of РАНГ;
    RWM : arrayN, N of РАНГ;
    X : array N of ЖЕНЩИНЫ;
    Y : array N of МУЖЧИНЫ;
    ОДНА : array N of boolean;
    procedure ПЕЧАТЬ;
        var M: МУЖЧИНЫ; RM,RW : Integer;
    begin RM := 0; RW := 0;
            for M := 1 to N do
                   write (X[M]:4);
                    RM := RM + RMW[M,X[M]]; RW := RW + RWM[X[M],M];
            end;
            writeln (RM:8, RW:4)
    end;
    procedure ПОПЫТКА (M:МУЖЧИНЫ);
        var R:РАНГ; W:ЖЕНЩИНЫ;
        procedure УСТОЙЧИВЫЙ:Boolean;
            var RM:МУЖЧИНЫ; RW:ЖЕНЩИНЫ; I,K : РАНГ; F:Boolean;
        begin F := True; I := 1;
               while (I $<$ R) & F do
                    RW := WMR[M,I]; I := I+1;
                    if not ОДНА [RW] then F := RWM[RW,M]$>$RWM[RW,Y[RW]] end
               end;
               I := 1; K := RWM[W,M];
               while (I $<$ K) & F do
                       RM := MWR[W,I]; I := I+1;
                       if RM $<$ M then S := RMW[RM,W] $>$ RMW[RM,X[RM]]
               end;
               return F
        end;
    begin for R := 1 to N do
                   W := WMR [M,R];
                   if ОДНА [W] then
                            if УСТОЙЧИВЫЙ then
                                  X[M] := W; Y[W] := M; ОДНА [W] := False;
                                  if M $<$ N then ПОПЫТКА (Succ(M)) else ПЕЧАТЬ end;
                                  ОДНА [W] := True
                            end
                   end
             end
    end
begin
    for M := 1 to N do for R := 1 to N do read(WMR[M,R]); RMW[M,WMR[M,R]] := R end end;
    for W := 1 to N do for R := 1 to N do read(MWR[M,R]); RWM[W,MWR[W,R]] := R end end;
    for W := 1 to N do ОДНА[W] := true end;
    ПОПЫТКА(1)
end УстойчивыеБраки.

3. Рассмотрим следующее доказательство того, что для любого положительного числа $n$: $\frac{1}{1\cdot2} + \frac{1}{2\cdot3} + \ldots + \frac{1}{(n-1)n} =\frac{3n-2}{2n}.$

Доказательство проводится методом математической индукции.

Базис. Для $n = 1$ утверждение справедливо, ибо $\frac {1}{1\cdot2} = \frac{3\cdot1-2}{2\cdot1} = \frac{3-2}{2} =\frac{1}{2}.$

Индуктивный переход. Предположим, что формула справедлива для любого $n$, т.е.

$\frac{1}{1\cdot2} + \frac{1}{2\cdot3} + \ldots + \frac{1}{(n-1)n} =\frac{3n-2}{2n},$

и рассмотрим формулу для $n + 1$:

$\frac{1}{1\cdot2} + \frac{1}{2\cdot3} + \ldots + \frac{1}{(n-1)n} +\frac{1}{n(n+1)}$= (по индуктивному предположению) =
$\frac{3n-2}{2n}+ \frac{1}{n(n+1)}$ = $\frac{(3n-2)(n+1)+2}{2n(n+1)}$ = $\frac{3n^2+n-2+2}{2n(n+1)}$ = $\frac{3n^2+n}{2n(n+1)}$ = $\frac{n(3n+1)}{2n(n+1)}$ = $\frac {3n+1}{2(n+1)}$ = $\frac{3(n+1)-2}{2(n+1)}$

Таким образом, утверждение справедливо и для $n + 1$.

Хотя доказательство выглядит как будто правильно, оно неверно, поскольку при $n = 4$ имеем

$\frac{1}{1\cdot2} + \frac{1}{2\cdot3} + \frac{1}{3\cdot4}$ = $\frac{1}{2} + \frac{1}{6} + \frac{1}{12}$ = $\frac{9}{12}$ = $\frac{3}{4}$$\ne \frac{10}{8}$ = $\frac{3\cdot4-2}{2\cdot4}$ = $\frac{3n-2}{2n}.$

Найдите ошибку в приведенных выше рассуждениях.

4. Найдите ошибку в следующем доказательстве методом математической индукции (по $n$ -- числу людей в группе) того, что в любой группе людей все люди одного роста.

Базис. Для $n = 1$ это высказывание очевидно.

Индуктивный переход. Предположим, что высказывание справедливо для любой группы из $n$ человек, и рассмотрим произвольную группу, состоящую из $n + 1$ человека. Произвольным образом занумеруем людей в группе и проведем следующие рассуждения. Если мы удалим ($n + 1$)-го человека из группы, то останется группа из $n$ человек; по индуктивному предположению все люди в такой группе одного роста. Представим себе, что вместо последнего мы удаляем первого человека из исходной группы; здесь то же число людей $n$ и, следовательно, все они одного роста. Отсюда следует, что все $n + 1$ человек исходной группы будут одного роста, так как известно, что люди с номерами от 1 до $n$ одного роста, а ($n + 1$)-й человек того же роста, что и $n$-й (даже больше, его рост совпадает с ростом второго, третьего и т.д.). Таким образом, мы показали справедливость индуктивного перехода.

5. Рассмотрим следующую функцию

procedure S (M,N : Integer):Integer;
begin
if M = 1 then if N = 1 then S := 5 else return S(1,N-1)+2
elsif N = 1 then S := S(M-1,N)+2 else return S(M,N-1)+2
end.

Покажите, что для любых A и B вычисление S(A,B) заканчивается и $S(A,B) = 2 \cdot (A+B)+1$.

6. Рассмотрим следующую функцию

procedure F (M,N : INTGER):Integer;
begin if N = 0 then if M = 0 then return 0 else return F(M - 1,N)+1 else return F(M,N - 1) - N
end.

Докажите, что для любых неотрицательных целых чисел $A$ и $B$ вычисление $F(A,B)$ заканчивается с результатом, равным значению $\frac{A(A+1)}{2} + B$.

7. Для функции

procedure T (M,N : integer):integer;
begin
if N = 0 then if M = 0 then return 1 else return T(M-1,N)+M else return T(M, N-1)+N end
end

напишите общую формулу для $T(A,B)$, где $A$ и $B$ -- произвольные неотрицательные целые числа, и докажите ее справедливость.

8. Приведенные ниже три рекурсивных определения функции $F$ были запрограммированы таким образом, чтобы для любых двух неотрицательных чисел $X1$ и X$Х2$

$F(X1,X2) = \left \{ \begin{array}{l}X1, \mbox{ если } X2 = 0 \\1,\mbox{ иначе },\end{array} \right.$

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

(1) procedure F (X1,X2 : integer):integer;
begin if X2 = 0 then return X1 elsif X1 = 0 then return F(X1-1,1) else return F(F(X1-1,X2), X2-1) endend F;

(2) procedure F (X1, X2 : integer):integer;
begin if X2 = 0 then return 1 elsif X1 = 0 then return F(X2-1,1) else return F(F(X1-1,X2) X2-1) endend F;

(3) procedure F (X1,X2 : integer):integer;
begin if X2 = 0 then return X1 elsif X1 = 0 then return F(1,X2-1) else return F(F(X1-1,X2),X2) end end F.
 

Next:6.2 Построение программ с процедурами и функциями
Up:6.1 Подпрограммы: процедуры и функции
Previous:6.1.9 Метод структурной индукции

© В.Н. Касьянов, Е.В.Касьянова, 2004