Двенадцать программ с дублями и эпиграфами,
или
Три триады программирования,
а точнее
Третий лишний, а второй неправильный

Вот первые три дубля (на трех языка: BASIC – C – Pascal) программы с эпиграфом:

Листинг 1

"Бог любит троицу"

' Программа 1a (QBasic)

DECLARE FUNCTION F (X)

INPUT "A, B, Погрешность"; A, B, Eps

Ya = F(A) ' Расчет Y на левом конце отрезка

DO WHILE B – A >> Eps ' Начало цикла "пока"

X = (A + B) / 2 ' Делим отрезок пополам

IF Ya * F(X) >> 0 THEN ' Альтернатива

A = X ' Левое плечо альтернативы

ELSE B = X ' Правое плечо альтернативы

END IF ' Конец альтернативы

LOOP ' Конец цикла "пока"

PRINT "Y = 0 при X = "; X

END

FUNCTION F (X)

F = X ^ 2 – 3 ' Анализируемое уравнение

END FUNCTION

// Программа 1b (C)

#include <<iostream.h>>

double F (double);

void main(void) {

double A,B,Eps,YLeft,X;

cout <<<< "Введите A, B, погрешность: "; cin >>>> A >>>> B >>>> Eps;

YLeft=F(A); // Расчет Y на левом конце отрезка

while(B-A>>Eps) { // Начало цикла "пока"

X=(A+B)/2; // Делим отрезок пополам

if (YLeft*F(X)>>0) // Альтернатива

A=X; // Левое плечо альтернативы

else B=X; // Правое плечо альтернативы

} // Конец цикла "пока"

cout <<<< "Y=0 при X=" <<<< X;

}

double F(double X) {

return X*X-3; //Анализируемое уравнение

}

{Программа 1c (Pascal)}

function F(X: real): real; begin

F:=X*X-3; {Анализируемое уравнение}

end; {end function}

var A, B, Ya, X, Eps: real;

begin

write('A ? '); readln(A); write('B ? '); readln(B);

write('Погрешность ? '); read(Eps);

Y := F(A); {Расчет Y на левом конце отрезка}

while B – A >> Eps do begin {Начало цикла "пока"}

X := (A + B) / 2; {Делим отрезок пополам}

if Ya * F(X) >> 0 then {Альтернатива}

A := X {Левое плечо альтернативы}

else B := X; {Правое плечо альтернативы}

{Конец альтернативы}

end; {Конец цикла "пока"}

writeln('Y=0 при X =', X);

end.

При поиске корня алгебраического уравнения методом половинного деления используется первая триада статьи – три основные алгоритмические конструкции: следование, повторение и выбор.

В эпиграфе программы 1a следовало бы написать не "Бог", а "Э. Дейкстра", имея в виду его три алгоритмические конструкции, упоминаемые в основной структурной теореме. И дело здесь не только в триаде (следование – повторение – выбор) [1]-[5], но и в том, что на эту теорему уповают уже более 30 лет, веря в нее, как в Господа Бога.

Вспомним ее.

"Алгоритм любой сложности можно реализовать, используя только три конструкции: следование (оператор за оператором), повторение (цикл) и выбор (альтернатива)".

Алгоритмических управляющих конструкций, позволяющих исключать метки из программ, конечно, намного больше трех. К трем главным следует добавить и неполную альтернативу, и вызов процедуры (особенно рекурсивной), и множественное ветвление, и работу с функциями пользователя. Тем не менее все они объявляются вспомогательными (первое следствие теоремы Э. Дейкстры), облегчающими и ускоряющими кодирование алгоритмов, но без которых при особом желании (как будет показано в этой статье) можно обойтись. Кроме того, из всех разновидностей циклов (цикл с предпроверкой, цикл с постпроверкой, цикл с параметром и другие) в качестве основного цикла был использован цикл "пока", а остальные были объявлены вспомогательными. Это, например, отразилось на языке FRED в составе интегрированного пакета Framework [8], где есть только цикл "пока"

@@while(булево выражение, тело цикла)

и нет ни цикла "до", ни цикла с параметром.

Листинг 2

Три языка: BASIC – C – Pascal

"Старый конь борозды не испортит"

10 REM Программа 2a (GW-BASIC)

20 INPUT "A, B, C"; A, B, C

30 D = B ^ 2 – 4 * A * C

40 IF D >>= 0 THEN PRINT "X1="; (-B + SQR(D)) / 2 / A; " X2="; (-B – SQR(D)) / 2 / A ELSE PRINT "Корней нет"

50 END

// Программа 2b (C)

#include <<iostream.h>>

#include <<math.h>>

void main(void) {

double A,B,C,D;

cout <<<< "A, B, C : "; cin >>>> A >>>> B >>>> C;

D=B*B-4*A*C;

if (D>>=0)

cout <<<< "X1=" <<<< (-B+sqrt(D))/2/A <<<< "\n" \

<<<< "X2=" <<<< (-B-sqrt(D))/2/A;

else cout <<<< "Корней нет.\n";

}

{Программа 2c (Pascal)}

var A,B,C,D: real;

begin

write('A:'); readln(A); write('B:'); readln(B);

write('C:'); readln(C);

D:=B*B-4*A*C;

if D>>=0 then

begin

writeln('X1=', (-B+sqrt(D))/2/A);

writeln('X2=', (-B-sqrt(D))/2/A);

end

else writeln('Корней нет');

end.

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

Листинг 3

Три языка: BASIC – C – Pascal).

"Любопытство не порок, а ... инструмент исследователя"

' Программа 3a (QBasic)

INPUT "A, B, C"; A, B, C

D = B ^ 2 – 4 * A * C

Flag = -1

DO WHILE D >>= 0 AND Flag

PRINT "X1="; (-B + SQR(D)) / 2 / A;

PRINT " X2="; (-B – SQR(D)) / 2 / A

Flag = 0

LOOP

DO WHILE Flag

PRINT "Корней нет"

Flag = 0

LOOP

END

// Программа 3b (C)

#include <<iostream.h>>

#include <<math.h>>

void main(void) {

enum BOOL {FALSE,TRUE};

double A,B,C,D;

enum BOOL Flag=TRUE;

cout <<<< "A, B, C : "; cin >>>> A >>>> B >>>> C;

D=B*B-4*A*C;

while((D>>=0)&&Flag) {

cout <<<< "X1=" <<<< (-B+sqrt(D))/2/A <<<< "\n" \

<<<< "X2=" <<<< (-B-sqrt(D))/2/A;

Flag=FALSE;

}

while(Flag) {

cout <<<< "Корней нет.\n";

Flag=FALSE;

}

}

{Программа 3c (Pascal)}

var A,B,C,D: real; Flag: boolean;

begin

write('A:'); readln(A);

write('B:'); readln(B);

write('C:'); readln(C);

D:=B*B-4*A*C;

Flag:=TRUE;

while (D>>=0) and Flag do begin

writeln('X1=', (-B+sqrt(D))/2/A);

writeln('X2=', (-B-sqrt(D))/2/A);

Flag:=FALSE;

end;

while Flag do begin

writeln('Корней нет');

Flag:=FALSE;

end;

end.

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

Программы, приведенные в листингах 2 и 3, доказывают, что при особом желании можно обойтись без альтернативы: в программах листинга 2 она есть, а в программах листинга 3 ─ нет. Программам в листинге 3 хватило цикла "пока" и переменной Flag, заставляющей операторы тела цикла работать либо раз, либо ни разу.

Полную альтернативу можно заменить на два цикла "пока" буквально в два счета [7]. Делай раз: меняем полную альтернативу на две неполные. Такой заменой рекомендуется [1] исключать некоторые метки в Fortran программах. Делай два: меняем каждую из двух неполных альтернатив на цикл "пока", тело которого выполняется либо раз, либо ни разу.

Итак, третий (альтернатива) – лишний. Теперь программами, приведенными в листингах 4-7, поясним, что значит "а второй неправильный" в названии статьи.

Листинг 4

Два языка: BASIC – C

"Искусство – это чувство меры"

10 REM Программа 4a (GW-BASIC)

20 DEF FNY (X) = X ^ 2 – 3

30 INPUT "A, B, Погрешность"; A, B, Eps: GOSUB 100: GOSUB 110

40 : IF ABS(B – A) <<= Eps GOTO 80: REM Задача решена

50 IF Y1 << Y2 THEN B = X2: X2 = X1: Y2 = Y1: GOSUB 100: GOTO 70

60 A = X1: X1 = X2: Y1 = Y2: GOSUB 110

70 : GOTO 40: REM Новое приближение к минимуму

80 : PRINT "Y минимальный ="; FNY(X1); " при X="; X1

90 STOP: REM Конец основной программы

100 : X1 = .618 * A + .382 * B: Y1 = FNY(X1): RETURN

110 : X2 = .382 * A + .618 * B: Y2 = FNY(X2): RETURN

120 END

// Программа 4b (C)

#include <<iostream.h>>

#include <<math.h>>

double Y(double);

void Calc1(); void Calc2();

double X1,X2,Y1,Y2,A,B;

void main(void) {

double Eps;

cout <<<< "A, B, Погрешность :";cin >>>> A >>>> B >>>> Eps;

Calc1();Calc2();

Label_1: if(fabs(B-A)<<=Eps) goto Label_3; // Задача решена

if (Y1<<Y2) {

B=X2;X2=X1;Y2=Y1; Calc1(); goto Label_2; }

A=X1;X1=X2;Y1=Y2; Calc2();

Label_2: goto Label_1; // Новое приближение к минимуму

Label_3: cout <<<< "Y минимальный=" <<<< Y(X1) <<<< " при X=" <<<< X1;

}

double Y(double X) {return X*X-3;}

void Calc1() {X1=0.618*A+0.382*B; Y1=Y(X1);}

void Calc2() {X2=0.382*A+0.618*B; Y2=Y(X2);}

Попросите знакомого художника разделить отрезок на две неравные части. Можете быть уверены ─ он это сделает в золотом соотношении. Подобное чувство меры позволяет компьютеру так делить интервал неопределенности A-B, что при очередном приближении к минимуму высчитывается только одно значение анализируемой функции.

Листинг 5

Два языка: BASIC – C)

"Имя – это повесть из одного названия"

' Программа 5a (QBasic)

DEF FNY (X) = X ^ 2 – 3

INPUT "A, B, Погрешность"; A, B, Eps

GOSUB RIGHT ' "Правая" подпрограмма

GOSUB LEFT ' "Левая" подпрограмма

DO WHILE ABS(B – A) >> Eps

DO ' Альтернатива

IF Y1 << Y2 THEN B = X2: X2 = X1: Y2 = Y1: GOSUB RIGHT: EXIT DO

A = X1: X1 = X2: Y1 = Y2: GOSUB LEFT: EXIT DO

LOOP

LOOP ' Конец цикла "пока"

PRINT "Y минимальный="; FNY(X1); " при X="; X1

STOP

RIGHT: ' "Правая" метка

X1 = .618 * A + .382 * B: Y1 = FNY(X1)

RETURN

LEFT: ' "Левая" метка

X2 = .382 * A + .618 * B: Y2 = FNY(X2)

RETURN

END

// Программа 5b (C)

#include <<iostream.h>>

#include <<math.h>>

double Y(double);

void Right();

void Left();

double X1,X2,Y1,Y2,A,B;

void main(void) {

double Eps;

cout <<<< "Введите A, B, погрешность: "; cin >>>> A >>>> B >>>> Eps;

Right(); // "Правая" подпрограмма

Left(); // "Левая" подпрограмма

while(fabs(B – A)>>Eps) {

for(;;) { // Альтернатива

if (Y1<<Y2) {

B=X2;X2=X1;Y2=Y1;

Right();

break; }

A=X1;X1=X2;Y1=Y2;

Left();

break;

}

} // Конец цикла "пока"

cout <<<< "Y минимальный=" <<<< Y(X1) <<<< " при X=" <<<< X1 <<<< "\n";

}

double Y(double X) {return X*X-3;}

void Right() { // "Правая" метка

X1=0.618*A+0.382*B; Y1=Y(X1);}

void Left() { // "Левая" метка

X2=0.382*A+0.618*B; Y2=Y(X2);}

Дав метке (переменной, функции, процедуре) "звучащее" имя (LEFT – левый, RIGHT – правый), никогда не забудешь, "какая повесть ею озаглавлена", – что делается в соответствующих подпрограммах, где сужается левый (A-X1) или правый (X2-B) интервал неопределенности.

Исключить альтернативу можно и по-другому – использованием не цикла "пока", а цикла с выходом из середины. Это проиллюстрировано программами в листингах 4 и 5, осуществляющими поиск минимума одномерной унимодальной функции методом золотого сечения.

В программе 5a был использован не просто цикл, а цикл с несколькими выходами из середины и со "словами прощания". Его следует считать с одной стороны "главным" циклом, так как он легко трансформируется и в цикл "пока", и в цикл "до", а с другой – гибридом цикла и альтернативы. Во втором случае цикл становится одноразовым – для страховки в программе 5a лучше написать не LOOP, а LOOP UNTIL 1=1.

Выведенную нами новую "породу" управляющих конструкций алгоритмов с языка QBasic на языки C и Pascal так просто не переведешь: "Можно быть большим католиком, чем папа римский, и более гибким и структурированным языком, чем C и Pascal". На языках C и Pascal цикл с выходом из середины можно получить только через его "запихивание" в прокрустово ложе либо цикла for (программа 5b), либо цикла while (while 2*2=4 ...), либо цикла do (repeat .... until 1=2). Цикл же с несколькими (двумя) выходами из середины позволяет исключить полную альтернативу (листинг 5) без дополнительной переменной Flag (листинг 3). Так что цикл "пока" занял второе место в основной структурной теореме неправомерно, а альтернатива (третий), как мы уже показали, совсем лишняя.

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

Но ценность, а точнее незаменимость, цикла с выходом из середины, конечно, не в том, что за счет его можно из программы исключить полную альтернативу без ввода новых переменных (сравните листинги 4 и 5), а в том, что выходов из цикла может быть несколько. Этого не избежать, когда значение управляющего логического выражения меняется вне цикла и есть опасение пропустить в нужный момент его изменение. Такое случается, если в программе задействованы элементы параллельного программирования, когда, например, управляющее циклом логическое выражение опирается на показание встроенных часов компьютера или на опрос состояния периферии (нажата ли какая-нибудь клавиша клавиатуры, включен ли принтер, вставлена ли в него бумага, есть ли в дисководе диск, отформатирован ли он и так далее.

Цикл с выходом из середины позволяет более просто убирать из программы метки без использования второй классической триады программирования – трех методов структурирования алгоритмов [1]: дублирование, ввод признака и разбег (листинги 6 – 9).

Листинг 6

Два языка: BASIC – C

"Не откладывай на завтра то, что можно сделать сегодня"

10 REM Программа 6a (GW-BASIC)20 RANDOMIZE TIMER-32767

30 PRINT "Угадай число от 1 до 1000 за минимум попыток."

40 A=1+INT(1000*RND(1))

50 I=0:REM Обнуление счетчика попыток

60 : I=I+1

70 PRINT I;"-я попытка";

80 INPUT B

90 IF B>>A THEN PRINT "Перелет":GOTO 60

100 IF B<<A THEN PRINT "Недолет":GOTO 60

110 PRINT "Угадали"

120 END

// Программа 6b (C)

#include <<stdlib.h>>

#include <<time.h>>

#include <<iostream.h>>

inline double RND() { // функция аналогичная оператору RND(1) языка BASIC

return ((double)rand()/(double)RAND_MAX);

}

void main(void) {

int A,B,I=0;

srand((unsigned)time(NULL)); // инициализация генератора случайных чисел

RND(); // "холостой ход"

cout <<<< "Угадай число от 1 до 1000 за минимум попыток.\n";

A=1+(int)(1000*RND());

label_1: I++;

cout <<<< I <<<< "-я попытка\n";

cin >>>> B;

if (B>>A) {

cout <<<< "Перелет\n";

goto label_1;

}

if (B<<A) {cout <<<< "Недолет\n"; goto label_1; }

cout <<<< "Угадали\n";

}

Подчеркнуть "сегодня" (в момент написания программы) вторую роль разметки GW-BASIC программ можно знаками двоеточия за номерами строк, которые "притягивают" к себе операторы GOTO, GOSUB и другие (см. также программу 4a). Это поможет "завтра" при необходимости быстро избавиться от этих номеров при объединении строк или при переходе к работе с языком QBasic, C или Pascal.

Листинг 7

Два языка: BASIC – C

"Голь на выдумки хитра"

' Программа 7a (QBasic)RANDOMIZE TIMER – 32767

PRINT "Угадай число от 1 до 1000"

A = 1 + INT(1000 * RND(1))

I = 0 ' Обнуление счетчика попыток

DO ' Заголовок цикла "до"

I = I + 1

PRINT I; "-я попытка";

INPUT B

IF B >> A THEN PRINT "Перелет" ' IF A = B THEN EXIT DO

IF B << A THEN PRINT "Недолет" ' IF B >> A THEN PRINT "Перелет" ELSE PRINT "Недолет"

LOOP UNTIL A = B ' LOOP

PRINT "Угадали"

END

// Программа 7b

#include <<stdlib.h>>

#include <<time.h>>

#include <<iostream.h>>

// enum {FALSE,TRUE};

inline double RND() {

return ((double)rand()/(double)RAND_MAX);

}

void main(void) {

int A,B,I=0;

srand((unsigned)time(NULL));RND();

cout <<<< "Угадай число от 1 до 1000 за минимум попыток.\n";

A=1+(int)(1000*RND());

do { // Заголовок цикла "до"

I++;

cout <<<< I <<<< "-я попытка \n";

cin >>>> B;

if (B>>A) cout <<<< "Перелет\n"; // if (A==B) break;

if (B<<A) cout <<<< "Недолет\n"; // if (B>>A) cout <<<< "Перелет\n";

// else cout <<<< "Недолет\n";

}

while (A!=B); // while (TRUE);

cout <<<< "Угадали\n";

}

Отсутствие в наборе встроенных функций языков BASIC и C генератора истинно случайных чисел заставляет "хитрых" программистов использовать встроенные часы компьютера (TIMER) и задавать тем самым истинно случайное значение переменной A.

Программы 6 и 7 позволяют сыграть с ЭВМ в игру "Угадай число", когда машина загадывает целое число в диапазоне от 1 до 1000 (строка 40 программы 6a), которое человек должен отгадать за минимум попыток. Этой игрой часто иллюстрируют принцип бинарного (двоичного) поиска. Придерживаясь оптимальной стратегии, человек должен делить интервал неопределенности пополам, а число, оказавшееся в середине, сообщать машине в качестве очередной догадки (строка 80 программы 6a). По ответам ЭВМ "Перелет" или "Недолет" человек уменьшает интервал неопределенности вдвое. В GW-BASIC программу 6a заложена естественная последовательность действий: если догадка человека больше (строка 90) или меньше (строка 100) задуманного числа, то (THEN) машина сообщает об этом и сразу оператором безусловного перехода возвращается к запросу новой догадки. Программы в листинге 6 можно отструктурировать, продублировав некоторые действия и тем самым преобразовав в программы листинга 7. Здесь операторы безусловного перехода к меткам убраны, но появился цикл "до" с лишней, на первый взгляд, функцией. Ведь если значение B не больше значения A и значение B не меньше значения A, то незачем дополнительно проверять равенство чисел. Но эта дублирующая операция структурировала программу: теперь алгоритм игры реализуется через цикл "до", тело которого содержит две последовательные неполные (с одним плечом) альтернативы. Комментарии программ в листинге 7 показывают, что замена цикла "до" на цикл с выходом из середины намного облегчает и упрощает структурирование алгоритма, восстанавливая у него естественную последовательность действий и исключая дублирование.

Цикл "до" считается вспомогательной управляющей конструкцией и используется тогда, когда булево выражение, управляющее циклом, приобретает смысл только после первого выполнения его тела, как в программах в листинге 7. Заменяется цикл "до" на цикл "пока", если в этом есть необходимость, как при программировании на языке FRED (см. ранее), искусственным заданием логическому выражению нужного значения: B = A + 1, например, если иметь в виду программы листинга 6. Это похоже на ситуацию "вне игры" (offside) в футболе, когда защитники пробегают вперед и оставляют нападающего одного у ворот.

Второй метод структурирования (ввод признака) иллюстрируется программой, решающей известную задачу английского физика Поля Дирака (1902-1984).

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

Поль Дирак был мастер давать разным существительным приставку "анти" ─ античастица, например. И в задаче о рыбаках и рыбке он, по-видимому, не изменил своей привычке, оригинально решив ее: минус две рыбы. Выбрасываем одну антирыбу ─ получаем минус три, забираем одну (треть улова) ─ получаем минус две и так далее. Но в ответ вкралась ошибка, которую можно объяснить только тем, что у Дирака не было компьютера.

Листинг 8

Два языка: BASIC – C

"Красиво жить не запретишь"

10 REM Программа 8a (GW-BASIC)

20 INPUT "Число рыбаков";Fishers

30 INPUT "Дельта рыб";DeltaFish

40 INPUT "Начальное число рыб";StartFish

50 : P=StartFish:REM Первый рыбак насчитал StartFish рыб

60 FOR I=1 TO Fishers:REM Перебор всех рыбаков

70 P=P+DeltaFish:REM Каждый выбросил или подловил DeltaFish рыб

80 P=P-P/Fishers:REM и взял свою долю

90 IF P>>INT(P) THEN StartFish=StartFish-1:GOTO 50

100 NEXT I:REM Просыпается следующий рыбак

110 PRINT"Ответ "StartFish" рыб

120 END

// Программа 8b (C)

#include <<iostream.h>>

void main(void) {

int Fichers,DeltaFish,StartFish,I;

double P;

cout <<<< "Число рыбаков :"; cin >>>> Fichers;

cout <<<< "Дельта рыб :"; cin >>>> DeltaFish;

cout <<<< "Начальное число рыб :"; cin >>>> StartFish;

Label_1: P=StartFish; // 1-й рыбак насчитал StartFish рыб

for (I=1;I<<=Fichers;I++) { // Перебор всех рыбаков

P+=DeltaFish; // Каждый выбросил или подловил DeltaFish рыб

P-=P/Fichers; // и взял свою долю

if (P!=(int)P) { StartFish=StartFish-1; goto Label_1;}

} // Просыпается следующий рыбак

cout <<<< "Ответ " <<<< StartFish <<<< " рыб\n";

}

Даже в неструктурированной GW-BASIC программе отступами от номеров строк можно попытаться "красиво" выделить структурные управляющие конструкции алгоритма.

Листинг 9

Два языка: BASIC – C

"Timeo Danaos et dona ferentes"

' Программа 9a (QBasic)

INPUT "Число рыбаков"; Fishers

INPUT "Дельта рыб "; DeltaFish

INPUT "Начальное число рыб"; StartFish

StartFish = StartFish + 1 ' Ничего нет

DO

StartFish = StartFish – 1 ' Ничего нет

Flag = -1 ' Ничего нет

P = StartFish

FOR I = 1 TO Fishers

P = P + DeltaFish

P = P – P / Fichers ' Здесь ошибка

IF P >> INT(P) THEN Flag = 0 ' IF P >> INT(P) THEN EXIT FOR

NEXT

' IF IF P = INT(P) THEN EXIT DO

' StartFish = StartFish – 1

LOOP UNTIL Flag ' LOOP

PRINT "Ответ "; StartFish; "рыб"

END

// Программа 9b (C)

#include <<iostream.h>>

void main(void) {

enum BOOL {FALSE,TRUE};

int Fishers,StartFish,DeltaFish,I;

double P;

enum BOOL Flag;

cout <<<< "Число рыбаков :";cin >>>> Fishers;

cout <<<< "Дельта рыб : "; cin >>>>DeltaFish;

cout <<<< "Начальное число рыб :"; cin >>>> StartFish;

StartFish+=1;

do {

StartFish-=1;

Flag=FALSE;

P=StartFish;

for(I=1;I<<=Fishers;I++) {

P+=DeltaFish;

P-=P/Fishers;

if (P!=(int)P) Flag=TRUE; // if (P>>(int)P) break;

}

// if (P==(int)P) break;

// StartFish-=1

}

while(Flag); // while(TRUE);

cout <<<< "Ответ " <<<< StartFish <<<< " рыб\n";

}

"Бойтесь данайцев, дары приносящих": языки семейства BASIC не требуют объявления переменных. Такой "подарок" часто бывает причиной очень неприятной ошибки – появления в программе "троянского коня" – переменной-мутанта Fichers вместо правильного Fishers, например.

Программы в листингах 8 и 9 решают задачу о рыбаках и рыбке методом перебора, когда задается начальное число рыб (строка 40 программы 8a) и проверяется, удовлетворяет ли оно условиям честного дележа (цикл с параметром в строках 60-100 программы 8a). Если да, то ответ готов (строка 110), нет ─ начальное число рыб уменьшается на единицу (строка 90), а расчет повторяется. Рано или поздно машина ответ найдет. При этом ее, как и Поля Дирака, не будет смущать тот факт, что число рыб стало величиной отрицательной. Нормального человека такой нюанс смутил бы, конечно, но нормальный человек и до античастиц не додумался бы: талант ─ это аномалия.

В GW-BASIC программе в листинге 8a досрочное прерывание цикла с параметром "разваливает" структуру. Спасти ее можно, введя в программу переменную-признак (Flag ─ листинг 9). Перед входом в цикл "флаг" поднимается: "презумпция невиновности". Если же хоть раз остаток от дележа улова будет нецелым числом, то "флаг" опускается. Это будет сигналом к повторению счета с уменьшенным на единицу числом рыб. Алгоритм машинного решения задачи Дирака стал структурированным: в цикл "до" вложен цикл с параметром и с неполной альтернативой.

В программах листинга 9 использован и третий метод структурирования – разбег (шаг вперед – шаг назад): начальное число рыб сначала увеличивается на единицу, а потом сразу, но уже в цикле, на эту же единицу уменьшается. Такой ход в программе подобен поведению прыгуна на разбеге: шаг назад, а потом разбег. Удаление или замена в программах листинга 9 некоторых операторов на те, которые записаны в комментариях, позволяет, так же как и в программах листинга 7, структурировать программу без использования триады классических методов.

Расчеты по программам в листингах 8 и 9 дают не одно, а целый ряд решений задачи:

..., -110, -83, -56, -29, -2, 25, 52, ...

Никто не будет спорить, что минус 29, а тем более минус 110 меньше, чем минус 2. Да, жаль, что у Дирака не было компьютера.

На языках C и Pascal цикла с выходом из середины нет, и это печально. Но при необходимости он реализуется двумя способами. Во-первых, прервать цикл в любом месте можно с помощью метки и оператора условного перехода (if ... goto ...). Те же, на кого метка в программе действует, как красная тряпка на быка, поступают, как говорил Даниил Хармс, "самым остроумным способом", а именно: тело цикла записывается процедурой с вкраплениями if... then exit, т.е. с командами "если... , то прерви выполнение процедуры и вернись в основную программу или в процедуру уровнем выше к оператору, находящемуся за именем процедуры". Многие программисты к основным структурным управляющим конструкциям относят и вызов процедуры. И не рекурсивный (нет такой рекурсии, какую нельзя было бы свести к итерационному), а простой вызов процедуры, к которому прибегают в описанном случае. На языке QBasic цикл можно прервать в любом месте и не в одном (EXIT DO или EXIT FOR). Так же бесцеремонно QBasic позволяет поступать и с процедурами (EXIT SUB), и с функциями (EXIT FUNCTION). Язык C (а вслед за ним и язык Turbo Pascal 7.0) проявляет еще большую гибкость: в нем цикл можно прервать, передав управление программой либо в конец цикла (if...then break), либо в его начало (if...then Continue).

Если читатель еще не совсем запутался, то вот какую "ясность" в проблему минимального числа управляющих конструкций алгоритмов (суть основной структурной теоремы Дейкстры) внесла переведенная с английского и выпущенная в 1989 г. издательством "Мир" книга "Языки программирования Ада, Си и Паскаль. Сравнение и оценка". В ней на страницах 72 и 73 сказано: "В соответствии с генеалогией управляющих структур <<...>> циклы с использованием оператора завершения Break и оператора продолжения Continue относятся к классу DREC1. (Такую аббревиатуру европеец не мог придумать: a dreg по-английски "отбросы"; die Dreck по-немецки "грязь", "дерьмо" – примечание ред.). Теоремы, доказанные Р.Косараю (точно, не европеец – японец), показывают, что управляющие структуры, относящиеся к классу DREC1, не могут быть эмулированы с помощью управляющих структур, относящихся к классу D (название этого класса образовано от первой буквы фамилии Э. Дейкстры ─ автора основной структурной теоремы), которые составляются из произвольного числа условных операторов if, операторов цикла while и их конкатенаций. На самом деле управляющие структуры, относящиеся к классу DRECi (имеющие в своем составе оператор выхода exit(i), обеспечивающий выход на i уровней вверх, и оператор cycle(i), обеспечивающий выполнение цикла на i-м уровне вложенности, как, например, в языке Блисс), являются более мощными, чем управляющие структуры, относящиеся к классу DRECi-1. <<...>> Однако программы, содержащие циклы с использованием операторов exit и cycle, оказываются намного сложнее для понимания. Анализ показывает, что необходимость использования оператора exit возникает крайне редко. Необходимость наличия управляющих структур более высокого уровня, чем управляющие структуры класса D, до сих пор не доказана". Вот так-то. Начали "за упокой" основной структурной теоремы, а кончили ─ "за здравие".

Листинг 10

GW-BASIC

"Жадность фраера погубит"

10 REM Программа 10 (GW-BASIC)

20 DEF FNTax (a) : REM Заголовок функции Tax

30 IF a < 42000 THEN T = .12 * a: GOTO 150

40 IF a < 84000 THEN T = 5040 + .15 * (a – 42000): GOTO 150

50 REM "А то что ж: один в семи комнатах расселился, штанов у него 40 пар,

60 REM а другой шляется, в сорных ящиках питание ищет" ─ , ремарка

70 REM булгаковского Полиграфа Полиграфовича Шарикова из "Собачьего сердца".

80 IF a < 120000 THEN T = 11340 + .2 * (a – 84000): GOTO 150

90 REM Наши парламентарии спутали заработанную плату со сверхприбылью монополии.

100 IF a < 180000 THEN T = 18540 + .3 * (a – 120000): GOTO 150

110 REM Комментарий, не пропущенный в статью внутренним цензором автора.

120 IF a < 300000 THEN T = 36540 + .4 * (a – 180000): GOTO 150

130 IF a < 420000 THEN T = 84540 + .5 * (a – 300000): GOTO 150

140 T = 144540 + .6 * (a – 420000)

150 : REM Конец конструкции "Выбор"

160 FNTax = T: REM Присвоение найденной величины функции

180 END DEF: REM Конец функции Tax

190 INPUT " Чистые (рубли в год)"; Ch: REM Запрос суммы "чистых" денег

200 Tmp1 = Ch: REM Дублирование Ch во временной переменной

210 : REM Начало цикла с выходом из середины

220 Tmp2 = Ch + FNTax(Tmp1): REM Приближение к корню

230 IF ABS(Tmp1 – Tmp2) << .001 GOTO 260

240 Tmp1 = Tmp2: REM Подготовка к новому приближению

250 GOTO 210: REM Конец цикла с выходом из середины

260 : adjPay = Tmp2: REM Присвоение найденной величины функции

270 PRINT USING " Грязные = ########.## руб"; adjPay

280 PRINT USING " Налог = #######.## руб "; adjPay – Ch

290 PRINT USING " Налог = ##.## %"; 100 * (adjPay – Ch) / adjPay

300 END

Программа решает обратную налоговую задачу – по сумме "чистых" денег методом простых итераций рассчитывает сумму "грязных". Пример в оправдание эпиграфа: чтобы в год заработать "чистый" миллион, нужно отдать государству 1 231 350 рублей, т.е. 55.18 % от суммы "грязных".

Листинг 11

QBasic

"Семья – основная ячейка общества"

' Программа 11 (QBasic)

DECLARE FUNCTION TaxMarried (adjPay)

DECLARE FUNCTION TaxSingle (adjPay)

INPUT "Грязные ($ в неделю) "; adjPay

PRINT "Налог с холостого (незамужней) = "; TaxSingle(adjPay); "$"

PRINT "Налог с женатого (замужней) = "; TaxMarried(adjPay); "$"

END

FUNCTION TaxMarried (adjPay)

'Расчет федерального налога с женатого (замужней)

a = adjPay

DO ' Заголовок конструкции "Выбор"

IF a < 62 THEN T = 0: EXIT DO

IF a < 657 THEN T = .15 * (a – 62): EXIT DO

IF a < 1501 THEN T = 89.25 + .28 * (a – 657): EXIT DO

IF a < 3695 THEN T = 325.57 + .33 * (a – 1501): EXIT DO

T = 1049.59 + .28 * (a – 3695): EXIT DO

LOOP ' Конец конструкции "Выбор"

TaxMarried = T

END FUNCTION

FUNCTION TaxSingle (adjPay)

'Расчет федерального налога с холостого (незамужней)

a = adjPay

DO ' Заголовок конструкции "Выбор"

IF a < 21 THEN T = 0: EXIT DO

IF a < 378 THEN T = .15 * (a – 21): EXIT DO

IF a < 885 THEN T = 53.55 + .28 * (a – 378): EXIT DO

IF a < 2028 THEN T = 195.51 + .33 * (a – 885): EXIT DO

T = 572.7 + .28 * (a – 2028): EXIT DO

LOOP ' Конец конструкции "Выбор"

TaxSingle = T

END FUNCTION

Программа решает прямую налоговую задачу – по сумме "грязных" денег вызовом функции рассчитывает сумму "чистых". Отечественный "миллионер" (см. подпись к программе 10) в США зарабатывает 100 долларов в неделю и платит федеральный налог 11 долларов 85 центов, если он холостой, и 5 долларов 70 центов, если он женатый.

Еще одну структурную управляющую конструкцию алгоритмов "Выбор" иллюстрируют BASIC программы 10 и 11, решающие задачу о подоходном налоге. Под термином "грязные" понимается количество заработанных денег за вычетом не облагаемой налогом суммы. Конструкцию выбора (ON ... GOTO ... языка GW-BASIC и SELECT ... END SELECT языка QBasic) заменяет серия альтернатив (IF ... THEN ... GOTO ...) – листинг 10, которую в свою очередь можно заменить на цикл со многими выходами из середины – программа 11.

Сравнивая программы 10 и 11, можно проследить не только за эволюцией структурных управляющих конструкции, но и за более интересными вещами, например, за изменением технологии программирования на языке BASIC. Непрофессиональный программист, прибегающий к GW-BASIC для решения своей прикладной задачи (а профессиональные программисты GW-BASIC и за язык-то не считают), часто поступает подобно хоккеисту, вбрасывающему, недолго думая, шайбу в чужую зону в надежде на то, что потом, в свалке, удастся взять ворота противника. Так, например, в программе 10 программист первым оператором INPUT " Чистые (рубли в год)"; Ch "забросил" переменную Ch в ОЗУ машины, а затем "ринулся" за ней следом в надежде на то, что как-нибудь в "свалке" новых вводимых переменных (Tmp1, Tmp2 и других) и в коротких "передачах" GOTO и GOSUB удастся "забросить шайбу" ─ решить поставленную задачу. Среда QBasic, не отвергая описанной тактики, предоставляет программисту и другую – программа 11. Можно "в своей зоне" не спеша разыграть комбинацию ─ написать и отладить процедуры-функции: TaxMarried (adjPay) и TaxSingle (adjPay), а затем коротким броском ─ PRINT TaxSingle(adjPay) и PRINT TaxMarried(adjPay) ─ "отправить шайбу в ворота противника".

Листинг 12 (QBasic)

"Пока рак на горе не свистнет"

' Программа 12 (QBasic)

DECLARE SUB Bell (t$)

CLS

DO

LOCATE 10, 30: PRINT TIME$

IF MID$(TIME$, 4, 2) = "00" THEN IF RIGHT$(TIME$, 2) = "00" THEN Bell (TIME$)

LOOP ' LOOP UNTIL 1=2

SUB Bell (t$)

b = VAL(LEFT$(t$, 2))

IF b >> 12 THEN b = b – 12

IF b = 0 THEN b = 12

FOR i = 1 TO b ' i = 1: DO: IF i >> b THEN EXIT DO

PLAY "D P16" ' Бой часов

NEXT ' i = i + 1: LOOP

END SUB

Часы с боем имеют вечный завод, так как в программе задействован бесконечный цикл, прерывающийся, конечно, не по "свистку", а аккордом CTRL-BREAK.

Многие, решая задачу о рыбаках и рыбке (листинги 8 и 9), не получали ни дираковского (-2), ни нашего компьютерного (-29) ответов из-за того, что под числом интуитивно понимается что-то положительное и не меньше единицы. Такие "шоры" иногда мешают и гибкому использованию цикла с выходом из середины: подразумевается, что выходов из цикла может быть один или более. В программе 12 цикл имеет ноль выходов. Эта простейшая программа окажется трудным орешком для Pascal программистов, избегающих меток. Организация процедуры здесь не поможет, а выручит только "свисток рака" – конструкция REPEAT .... UNTIL 1=2 (ремарки в листинге 12 показывают, как циклом "до" заменяется бесконечный цикл, а циклом с выходом из середины – цикл с параметром).

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

P.S.

Магия цифры три не обошла стороной и автора, который в статье с тремя названиями поместил 12 (четырежды три) программ, ссылается на 9 (трижды три) литературных источников, упоминает шесть (дважды три) языков программирования (BASIC, Pascal, C, Fortran, FRED и таинственный Блисс), а в выводах оставил ровно три (одиножды три) пункта:

1. Основная структурная теорема в течение почти 30 лет давалась в неверной формулировке. Правильная редакция такая: "Алгоритм любой сложности можно реализовать, используя только две конструкции: следование и повторение".

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

3. Языки С и Pascal (включая и версию Turbo Pascal 7.0) базируются на неполном наборе структурных управляющих конструкций, что влечет за собой в некоторых случаях немотивированное использование меток или процедур.

Литература

1. Ван Тассел Д. Стиль, разработка, эффективность, отладка и испытание программ: Пер. с англ. – М.: Мир, 1985.

2. Вирт Н. Алгоритмы + структуры данных = программы: Пер. с англ. – М.: Мир, 1985.

3. Вирт Н. Систематическое программирование: Пер. с англ. – М.: Мир, 1977.

4. Дал У., Дейкстра Э., Хоор К. Структурное программирование: Пер. с англ. – М.: Мир, 1975.

5. Йодан Э. Структурное проектирование и конструирование программ: Пер. с англ. – М.: Мир, 1979.

6. Майерс Г. Отладка и тестирование программ: Пер. с англ. М.: Мир, 1979

7. Очков В.Ф., Пухначев Ю.В. 128 совета начинающему программисту. – М.: Энергоатомиздат, 1992.

8. Очков В.Ф., Пухначев Ю.В. Уроки для пользователей IBM PC. – М.: Финансы и статистика, 1992.

9. Очков В.Ф. Языки программирования GW-BASIC и QBasic: сравнительное описание.

– М.: Энергоатомиздат, 1992.

Триады информатики

Шесть упоминавшихся в статье:

1. Три структурные управляющие конструкции Э.Дейкстры.

2. Три вида цикла на языках C и Pascal.

3. Три способа структурирования алгоритмов.

4. Три способа выхода из середины цикла в C и Pascal программах.

5. Три шага при исключении из программы альтернативы.

6. Три свойства объектов в ООП.

Двенадцать не упоминавшихся в статье:

1. Три основных блока IBM PC – системный блок, дисплей, клавиатура.

2. Три вида памяти компьютера – ПЗУ, ОЗУ и магнитная.

3. Три способа записи информации – электронный, на магнитный слой и на бумагу.

4. Три попытки ввода неправильного пароля при включении компьютера.

5. Три клавиши (Ctrl-Alt-Del) перезапуска IBM PC.

6. Три способа перезапуска IBM PC – см. п. 5, Reset и Off-On.

7. Три режима работы Windows 3.0 – стандартный, реальный и защищенный.

8. Три самых популярных языка программирования – BASIC, C и Pascal.

9. Три расширения у компилируемого файла: у исходного "*.BAS"("*.C" или "*.PAS"), у объектного – "*.OBJ" и у выполнимого – "*.EXE".

10. Три главных инструмента интегрированных пакетов – текстовый процессор, табличный процессор и система управления базами данных.

11. Три главных системы счисления – двоичная, десятичная и шестнадцатиричная.

12. Три основных типа цветных видеоадаптеров – CGA, EGA и VGA.