.: Учебник по практическому программированию ( Бейсик, Си, Паскаль ) :.

Глава 4. Работа с массивами Объявление массивов Инициализация массивов Статические и динамические массивы Массивы в качестве параметров процедур и функций Сортировка больших массивов Поиск Задачи, советы и ответы

Глава 4.

Работа с массивами

Как правило, массив представляет собой набор однотипных данных, расположенных в оперативной памяти таким образом, чтобы по индексам элементов можно было легко вычислить адрес соответствующего значения. Например, пусть одномерный массив А состоит из элементов, расположенных в памяти подряд по возрастанию индексов и каждый элемент занимает по k байт. Тогда адрес 1-го элемента вычисляется по формуле:

адрес(A[i]) = адрес(А[0]) + i * k

Если мы имеем дело с двумерным массивом в размерности MXN, расположенным в памяти по строкам, то адрес элемента в [i, j ] вычисляется по формуле:

адрес(В[i,j]) = адрес(В[0,0]) + (i * N + j) * k

Приведенные выше формулы незначительно усложняются в тех случаях, когда начальные индексы отсчитываются не от нуля, что характерно для Паскаля.

Использование массивов позволяет заменить большое количество индивидуальных имен каждого объекта одним групповым именем набора данных, вслед за которым в круглых (QBasic) или квадратных (Си, Паскаль) скобках задаются один или несколько индексов, определяющих местоположение требуемого значения. Естественно, что такая возможность упрощает и массовую обработку данных в соответствующих циклах программы.

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

Объявление массивов

В QBasic для объявления массивов и одновременного отведения памяти под хранение их элементов используется оператор DIM:

DIM А(10),В(2 ТО 8,3 ТО 5),С(3,2,6)

В простом объявлении указывается максимальный индекс и, поскольку минимальный индекс по умолчанию равен 0, то в массиве А, например, содержится не 10, а 11 элементов. Конструкция "qq то kk" позволяет одновременно задать и минимальный, и максимальный индексы.

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

INPUT "Введите размерность массива F", N DIM F(N)

После работы с этим массивом в программе может встретиться следующая пара операторов:

INPUT "Введите новую размерность массива F",M REDIM F(M)

И новое значение верхней границы может быть как меньше предыдущего, так и больше. Массивы подобного рода в QBasic принято называть динамическими. В отличие от этого оператор DIM с конкретными числовыми границами формирует статические массивы, значения элементов которых сохраняются и после завершения работы программы.

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

Объявление массивов в Си чем-то особым не отличается от других алгоритмических языков. Разве что в задании многомерных массивов каждый индекс записывается в отдельных квадратных скобках:

#define N_max 50

char a1[20], a2[5][80];

int b1[25],b2[N_max];

Индексы в Си всегда отсчитываются от 0, так что, например, в массиве b1 можно манипулировать с элементами b1[0], b1[1], ..., b1[24]. Элемент b1[25] массиву ы уже не принадлежит и попытка записи в него может привести к непредсказуемым последствиям.

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

type

mat_q_k=array [l..q,l..k] of integer;

var

f :mat_q__k;

ИЛИ

var

f:array [l..q,l..k] of integer;

ИЛИ

var

f:array [l..q][l..k] of integer;

ИЛИ

var

f:array [l..q] of array [l..k] of integer;

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

var

ch:array ['A'..'Z'] of integer;

str:string;

begin

.....................

inc(ch[str[j]]) ;

....................

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

Инициализация массивов

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

Средства такого рода имеются только в Си и Паскале. Здесь одновременно с объявлением массива можно задать начальные значения всех элементов массива или только нескольких первых его компонент:

char а[7]="Привет";

char b[7]={'П','р','и','в','е','т',0x00};

char с[]="Привет";

int d[10] = {1,2,3,4};

int f[2][3]={{1,2,3}, {4,5,6}};

В символьном массиве а формируются значения семи компонент, первые шесть из которых соответствуют кодам отображаемых символов заданной строки. Признак конца строки — байт с нулевым кодом — заносится в элемент а [6] автоматически. В отличие от этого в массиве ь, где значения элементов формируются посимвольно, такой признак конца программист должен задавать сам. Обратите внимание на третью строку, в которой отсутствует указание о размере массива. Компилятор Си сам сформирует нужное значение по количеству инициализирующих данных. В нашем случае под массив с будет отведено 7 байт, включая последний байт с нулевым кодом, завершающий каждую строку.

В Паскале инициализация производится в разделе const: const

a:string[7]='Привет';

d:array [1..10] of integer=(1,2,3,4);

f:array [1..2,1..3] of integer=((1,2,3),(4,5,6));

Инициализация глобальных и статических массивов в Си производится один раз при загрузке программы. Локальные массивы в функциях языка Си инициализируются при каждом обращении к функции.

Статические и динамические массивы

Статическим массивом называют набор данных, для хранения которого перед началом функционирования программы выделяется фиксированное место в памяти, освобождаемое после завершения работы программы.

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

В системе QBasic по умолчанию массивы с конкретными числовыми границами считаются статическими, а с переменными границами —динамическими. Однако, если первой строкой программы задана метакоманда вида КЕМ $STATIC или REM $DYNAMIC, то все массивы в программе будут заводиться либо как статические, либо как динамические. По оператору ERASE v1,v2, ... статические массивы "чистятся", а динамические массивы освобождают занимаемую память. Чистка массивов подразумевает засылку нулевых значений во все элементы числовых массивов и засылку "пустых" (нулевых) строк в элементы массива символьного типа. Оператор REDIM позволяет переопределить размеры ранее объявленных динамических массивов, не изменяя количество приписанных им индексов. Одновременно с этим происходит чистка переобъявляемых массивов.

В Си для запроса и освобождения памяти используются следующие системные функции:

q=(тип_q *)calloc(n_el,s_el); //запрос памяти с очисткой;

q=(тип q *)farcalloc(n_el,s_el); //запрос памяти с очисткой;

q=(тип_q *)malloc(n_byte); //запрос памяти в ближней "куче"

q=(тип_q *)farmalloc(n_byte); //запрос памяти в дальней "куче"

q new=realloc(q_old,n_byte); //изменение размера блока

q_new=farrealloc(q_old,n_byte); //изменение размера блока

free(q); //освобождение памяти

farfree(q); //освобождение памяти

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

Максимальный размер сегмента памяти, предоставляемого в ближней "куче", равен 65 521 байт. Добавка far означает, что программа использует дальние указатели типа far или huge, которые позволяют адресоваться к дальней "куче" и использовать сегменты размером более 64 Кбайт. Любая функция выделения памяти возвращает начальный адрес или "нулевой" указатель (NULL) в случае отсутствия свободной памяти запрашиваемого размера. Для того чтобы нормально работать с предоставленным фрагментом памяти, возвращаемый адрес обязательно должен быть приведен к типу указателя q.

Функция realloc (farreallioc) позволяет перераспределить ранее выделенную память. При этом новый размер массива может быть как меньше предыдущего, так и больше. Если система выделит память в новом месте, то все предыдущие значения, к которым программа обращалась по указателю q_old, будут переписаны на новое место автоматически.

В новых версиях Borland C++ появились две более удобные процедуры для запроса и освобождения памяти, не нуждающиеся в дополнительном указании о приведении типа возвращаемого адреса:

q=new тип[n_е1]; //запрос памяти под массив из n_e1 элементов;

q=new тип; //запрос памяти под скалярную переменную;

delete q[n_e1]; //освобождение памяти, занятой массивом;

delete q; //освобождение памяти, занятой массивом или

//скалярной переменной;.

Для формирования в Паскале динамического массива с элементами определенного типа с таким массивом надо связать соответствующий указатель и обратиться к процедуре New:

type

mas=array [1..200] of integer;

point^{=^}mas; var

p:point;

j:integer;

..................

begin New(p);

for j :=1 to 200 do

readln(p^[j]);

...................

Запрошенная таким образом память освобождается процедурой Dispose (р). Для запроса и освобождения памяти под разнородные данные в Паскале можно использовать процедуры GetMem(q,n_byte) и FreeMem(q,n_byte). Указатель я, которому присваивается начальный адрес выделенного сегмента, в данном случае представлен нетипизированным указателем (q:pointer;).

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

q=NULL; //так это делается в Си

p:=nil; //так это делается на Паскале

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

Массивы в качестве параметров процедур и функций

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

SUBROUTINE MATMULT(A,B,C,N)

REAL A(N,N),B(N,N),C(N,N),D

DO 1 J=1,N

DO 1 K=1,N D=0

DO 2 L=1,N

2 D=D+A(J,L)*B(L,K)

1 C(J,K)=D

END

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

Массивы-параметры в подпрограммах и функциях QBasic

Ближе всего к идеологии Фортрана оказался QBasic. В нем довольно похожим образом можно передать массив в подпрограмму или функцию. Продемонстрируем эту возможность на примере подпрограммы сложения целочисленных квадратных матриц:

Программа 4_01.bas

DECLARE SUB ADDMAT(A%(),B%(),C%(),N%) DEFINT A-Z CLS

DIM A1(2,2), A2(2,2),A3{2,2)

DIM Bl(3,3),B2(3,3),B3(3,3)

FOR J=0 TO 2 : FOR K=0 TO 2

A1(J,K)=J+K : A2(J,K)=J*K

NEXT К : NEXT J

CALL ADDMAT(Al(),A2(),A3() ,2) 'Так можно обратиться к подпрограмме

FOR J=0 TO 3 : FOR K=0 TO 3 B1(J,K)=J+K :

B2(J,K)=J*K

NEXT К : NEXT J

ADDMAT Bl(),B2(),B3(),3 'И так можно обратиться к подпрограмме END

SUB ADDMAT (A%(),В%(),С%(),N%)

DEFINT A-Z

FOR Q=0 TO N : FOR S=0 ТО N

C(Q,S)=A(Q,S)+B(Q,S)

NEXT S : NEXT Q

END SUB

Как в заголовке подпрограммы, так и в операторах обращения к ней массив-параметр сопровождается пустыми круглыми скобками, независимо от числа индексов, приписанных фактически передаваемым массивам. Никаких переобъявлений типа DIM A(N,N) в теле подпрограммы не нужно. Более того, попытка вставить такой оператор приведет к фиксации ошибки, сопровождаемой сообщением о повторном объявлении массива. Обратите внимание на то, что в заголовке подпрограммы использованы имена А%, B%, C%, N%, а в тексте подпрограммы вместо них выступают имена А, в, с, N. Своей эквивалентностью они обязаны оператору DEFINT A-Z, объявляющему все переменные внутри подпрограммы целочисленными.

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

Массивы-параметры в процедурах и функциях Паскаля

Первое ограничение, с которым сталкиваются программисты в Паскале, звучит следующим образом — если формальным параметром является массив, то его нельзя описать явным образом. Например, ошибочным является заголовок:

function Max(a:array [1..100] of integer):integer;

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

type

mas100=array [1..100] of integer;

function Max(a:mas100):integer;

Однако такая функция обрекает нас на определение максимального элемента только в массиве типа masioo. А если в нашей программе понадобится обрабатывать массивы и с другим количеством элементов? Конечно, можно добавить еще один параметр — количество обрабатываемых элементов:

function Max(a:mas100; n:integer):integer;

Это позволит ограничиться первыми n элементами массива, но размерность фактического параметра может быть только mas100.

Первый выход из столь неприятного положения заключается в том, чтобы передать массив как адрес параметра без типа:

function Max(var a; n:integer):integer;

type

b=array [1.. Maxlnt] of integer;

var

m,k:integer;

begin

m:=b(a}[1];

for k:=2 to n do

if m<b(a)[k] then m:=b(a)[k] ;

Max:=m;

end;

Несколько необычная запись b(а) означает, что нетипизированный параметр а приводится к типу целочисленного массива, каковым он на самом деле и является. Только функция мах об этом "не знает". Может показаться немного странным выбор верхней границы индекса в типе "b". Однако он позволяет избежать неприятностей, когда фактическое значение параметра n достаточно велико (при этом может возникнуть аварийная ситуация, вызванная выходом индекса за границы диапазона). Каким бы большим не было значение п, оно не может превысить величину Maxint, ибо массивы в Паскале не могут быть более 64 Кбайт.

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

function Max(var a; n:integer):integer;

var

c:array[l.. Maxlnt] of integer absolute a;

m,k:integer;

begin

m:=c[l];

for k:=2 to n do

if m<c[k] then m:=c[k];

Max:=m;

end;

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

Третья идея заключается в том, чтобы передать нетипизированный указатель на массив а:

function Max(pa:pointer; n:integer):integer;

var

m,k:integer;

pb:^integer;

begin

pb:=ptr(зед(ра^) , ofs(ра^) ) ;

m:=рb^;

for k:=2 to n do

begin

pb:=ptr(seg(ра^),ofs(ра^)+k*2);

if m < рb^ then m:=рb^;

end;

Max:=m;

end;

Для вызова такой функции при определении максимального элемента в массиве q необходимо задавать адрес аргумента:

max_q:=Max(&q,100);

Этот пример демонстрирует работу с адресами и указателями в Паскале. В нем использована функция ptr, вычисляющая адрес элемента данных по сегменту (seg) и смещению (ofs). Адрес сегмента, задающий начало массива, у локачьного указателя ь совпадает с адресом массива a (seg(pb^)=seg(pa^)), а смещение очередного элемента вычисляется в цикле путем прибавления к смещению начального элемента ofs (ра^) приращения 2*k.

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

function Max(a:array of integer):integer;

var

m,k:integer;

begin

m:=a[0];

for k:=l to High(a) do

if m < a[k] then m:=a[k];

Max:=m; end;

Для открытых массивов появилась системная функция High, позволяющая узнать максимальный индекс. При использовании открытых массивов вы должны включить соответствующее указание компилятору — {$P+}.

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

Распространим некоторые идеи передачи параметров на двумерные массивы в задаче суммирования квадратных матриц. Первый пример использует нетипизированные переменные:

procedure sum+mat(var a,b,c; n:integer);

var

x:array [0..0] of integer absolute a;

y:array [0..0] of integer absolute b;

z:array [0..0] of integer absolute c;

j,k:integer;

begin {$R-}

for j :=0 to n-1 do

for k:=0 to n-1 do

z[j*n+k]:=x[j*n+k]+y[j*n+k];

{$R+} end;

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

Второй пример использует вариант с указателями:

procedure sum_mat(pa, pb, pc:pointer; n:integer);

var

a,b,с:^integer;

j,k:integer;

begin

for j:=0 to n-1 do

for k:=0 to n-1 do

begin

a:=ptr(seg(ра^),ofs(ра^)+(j*n+k)*2) ;

b:=ptr(seg(pb^),ofs(рb^)+(j*n+k)*2);

c:=ptr(seg(рс^),ofs(рс^)+(j*n+k)*2);

с^:=а^+b^;

end;

end;

Массивы-параметры в функциях Си

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

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

int Max(int *a, int n) {

int m, k;

m=a[0];

for(k=l; k<n; k++)

if (m < a[k]) m=a[k];

return m; }

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

Абсолютно эквивалентным является вариант с использованием арифметики указателей:

int Max(int *a, int n) {

int m,k;

m=*a;

for(k=l; k<n; k++)

if (m < *(a+k) m=*(a+k);

return m; }

Следующий пример демонстрирует сложение квадратных матриц с приведением адресов элементов двумерного массива к их одномерным аналогам:

void sum_mat(int *a, int *b, int *c, int n) {

int j,k,m;

for(j=0; j < n; j++)

for(k=0; k < n; k++) {

m=j*n+k;

* (c+m)=* (a+m) + *(b+m) ; } }

Сортировка больших массивов

Говорят, и это подтверждается многочисленными примерами, что 90% времени работы программы.приходится на так называемые узкие места, занимающие в общем объеме программы не более 10% команд. Поиск таких мест и улучшение их временных характеристик — один из основных методов совершенствования программ.

К числу таких узких мест относятся фрагменты программ, занимающиеся упорядочением достаточно объемной информации, поиском данных в больших массивах и т. п. Ниже приводится описание нескольких довольно популярных методов упорядочения числовых массивов и тексты реализующих их процедур. Схемы программ на Си заимствованы из [12], однако в их тексты внесены небольшие изменения. Желающим познакомиться более подробно с другими методами сортировки и возникающими при этом серьезными математическими проблемами мы рекомендуем книгу Д. Кнута "Искусство программирования для ЭВМ", т. 3.

Пузырьковая сортировка (bubble)

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

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

С целью повышения быстродействия программ на Си наиболее активно используемые переменные i и j распределяются в регистровой памяти.

Подпрограмма bubble.bas

SUB BUBBLE(X(),N)

FOR 1=1 TO N-l

FOR J=N-1 TO I STEP -1

IF X(J-l) > X(J) THEN

TMP=X(J-1): X(J-l) =X(J): X(J)=TMP

END IF

NEXT J

NEXT I

END SUB

Подпрограмма bubbiei.bas

SUB BUBBLE1(X(),N) M:Q=0

FOR 1=1 TO N-l

IF X(I-l) > X(I) THEN

TMP=X(I-1): X(I-1)=X(I): X(I)=TMP: Q=l

END IF

NEXT I

IF Q=l THEN GOTO *M

END SUB

Функция bubble.с

void bubble(int *x, int n) {

register int i,j;

int tmp;

for(i=l; i<n; i++)

for(j=n-l; j>=i; j—)

if<x[j-l] > x[j])

{

tmp=x[j-1] ;

x[j-l] = x[j];

x[j ] = tmp; } }

Функция bubblel.c

void bubblel(int *x, int n) {

register int i,j;

int tmp,q; m:q=0;

for(i=0; i<n-l; i++)

if(x[i] > x[i+l]) {

tmp=x[i];

x[i]=x[i+l];

x[i+l]=tmp;

q=l; }

if(q!=0) goto m; }

Процедура bubble.pas

procedure bubble(var x:array of integer;n:integer);

var

i,j,tmp:integer;

begin

for i:=l to n-1 do

for j:=n-l downto i do

if x[j]<x[j-l] then begin

tmp:=x[j-l]; x[j-l]:=x[j];

x[j]:=tmp;

end;

end;

Процедура bubblel.pas

procedure bubblel(var x:array of integer;n:integer);

label m;

var

i,tmp,q:integer;

begin m:q:=0

for i:=0 to n-2 do

if x[i] > x[i+l] then begin

tmp:=x[i];

x[i]:=x[i+l];

x [i+1] :=tmp;

q:=l; end;

if q=l then goto m;

end;

Сортировка методом отбора (select)

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

Подпрограмма select.bas

SUB SELECT(X(),N)

FOR I=0 TO N-2

Q=0: K=I: TMP=X(I)

FOR J=I+1 TO N-l

IF X(J)<TMP THEN K=J: TMP=X(J): Q=l NEXT J

IF Q=l THEN X(K)=X(I): X(I)=TMP NEXT I

END SUB

Функция select.с

void select(int *x, int n) {

register int i,j,k;

int q,tmp;

for(i=0; i<n-l; i++) {

q=0;

k=i;

tmp=x[ i ] ;

for(j=i+l; j<n; j++) {

if(x[j] < tmp) {

k=j;

tmp=x[ j ] ;

q=l; } } if (q)

{x[k]=x[i];

x[i]=tmp;} } }

Процедура select.pas

procedure select(var x:array of integer;n:integer);

var

i,j,k,q,tmp:integer;

begin

for i:=0 to n-2 do begin

q:=0;

k:=i;

tmp:=x[i];

for j:=i+l to n-1 do

if x[j]<tmp then begin

k:=j;

tmp:=x[j];

q:=l;

end;

if q=l then begin

x[k]:=x[i];

x[i]:=tmp;

end;

end;

end;

Сортировка методом вставки (insert)

Идея этого метода базируется на последовательном пополнении ранее упорядоченных элементов. На первом шаге сортируются первые два элемента. Затем на свое место среди них вставляется третий элемент. К трем упорядоченным элементам добавляется четвертый, который занимает свое место в новой четверке. И так продолжается до тех пор, пока к n-1 ранее упорядоченным элементам не присоединится последний. Примерно таким способом игроки упорядочивают свои карты при сдаче их по одной.

Подпрограмма insert.bas

SUB INSERT(X%(),N%) DIM I,J,TMP

FOR I=1 TO N-l TMP=X(I)

FOR J=I-1 TO 0 STEP -1

IF TMP > X(J) THEN EXIT FOR

X(J+1)=X(J)

NEXT В X(J+1)=TMP

NEXT I

END SUB

Функция insert.c

void insert(int *x,int n) {

register int i,j; int trnp;

for(i=l; i<n; i++) {

tmp=x[ i ] ;

for(j=i-l;j>=0 && tmp < x[j]; j--)

x[j+l]=x[j];

x[j+l]=tmp;

} }

Процедура insert.pas

procedure insert(var x:array of integer;n:integer);

var

i,j,tmp:integer;

begin

for i:=l to n-1 do

begin

tmp:=x[i];

j:=i-l;

while (j>=0) and (tmp<x[j]> do

begin .

x[j+l]:=x[j]; j:=j-l;

end;

x [ j+1] :=tmp;

end;

end;

Сортировка методом Шелла (shell)

Метод Д. Л. Шелла, опубликованный в 1959 г., предлагает сортировать массив в несколько этапов. На первом этапе в сортировке участвуют достаточно далекие элементы, например, отстоящие друг от друга на восемь позиций. На втором проходе сортируются элементы, расстояние между которыми уменьшено, например до четырех. Затем упорядочиваются каждые вторые элементы и, наконец, на последнем этапе сравниваются смежные элементы. Выбор последовательно уменьшающихся шагов в методе Шелла представляет довольно сложную математическую задачу. На практике чаще всего применяют пятизвенную схему 9—>5—>3—>2—>1.

Подпрограмма shell.bas

SUB SHELLSORT (X%"() , N% )

DIM I, J,GAP,K,XX,A(5) A(0)=9: A(l)=5: A(2)=3: A(3)=2: A(4)=l

FOR K=0 TO 4 GAP=A(K)

FOR I=GAP TO N-1 XX=X(I)

FOR J=I-GAP TO 0 STEP -GAP

IF XX >= X(J) THEN EXIT FOR

X(J+GAP)=X(J)

NEXT J X(J+GAP)=XX

NEXT I

NEXT К

END SUB

Функция shell.с

void shell(int *x,int n) {

register int i,j,gap,k; int xx;

char a[5]={9,5,3,2,l};

for(k=0; k<5; k++) {

gap=a[k];

for(i=gap; i<n; ++i) {

xx=x[i];

for(j=i-gap; xx < x[j] && j >= 0; j=j-gap)

x[j+gap]=x[j); x[j+gap]=xx; } } }

Процедура shell.pas

procedure shell(var x:array of integer;n:integer) ;

var

i,j,k,gap,xx:integer;

const

a:array [0..4] of byte=(9,5,3,2,1};

begin

for k:=0 to 4 do

begin

gap:=a[k];

for i:=gap to n-1 do begin

xx:=x[i];

j:=i-gap;

while (j >= 0) and (xx < x[j]) do

begin

x[j+gap]:=x[j];

j:=j-gap;

end;

x[j+gap]:=xx;

end;

end;

end;

Сортировка методом Хоара (quicksort)

Метод Ч. Э. Р. Хоара, опубликованный в 1962 г., издалека напоминает способ ловли льва в пустыне "методом Вейерштрасса". Сначала пустыню делят пополам и выбирают ту половину, в которой находится лев. Затем эту половину снова делят пополам и так продолжают до тех пор, пока область, содержащая льва, не помещается в клетку. В математике подобный метод применяют для нахождения корня функции, принимающей на концах отрезка разные знаки. Это и есть метод Вейерштрасса, более известный под названием "метода деления пополам".

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

Затем аналогичный прием применяют к каждой из полученных половин. В каждой из них выбирается свой средний элемент и относительно него осуществляются необходимые перестановки. Как следует из описания, алгоритм Хоара очень хорошо укладывается в понятие рекурсивной процедуры. Для единообразия в обращении процедура быстрой сортировки представлена в виде двух процедур — внешней hoar, к которой обращается пользователь, и внутренней — quick. Последняя выполняет рекурсивную обработку подмассива, заданного граничными значениями индексов — left и right.

Подпрограмма hoare.bas

SUB HOARE(X% (),N%)

QUICK X%(),0,N%-1

END SUB

SUB QUICK(X%(),LEFT%,RIGHT%)

DIM I,J,XX,YY

I=LEFT%: J=RIGHT%

XX=X((LEFT%+RIGHT%)\2)

DO

WHILE X%(I) < XX AND I < RIGHT%: I=I+1: WEND

WHILE XX < X%(J) AND J > LEFT%: J=J-1: WEND

IF I <= J THEN

YY=X%(I): X%(I)=X%(J): X%(J)=YY: 1=1+1: J=J-1

END IF

LOOP WHILE I <= J

IF LEFT% < J THEN QUICK X%(),LEFT%,J

IF I < RIGHT% THEN QUICK X%(),I,RIGHT%

END SUB

Функция hoare.c

void hoare(int *x,int n) {

quick(x,0,n-1);

return;

}

/*--------------------------------*/

void quick(int *x, int left, int right) {

register int i,j;

int xx,tmp;

i=left;

j=right;

xx=x[(left+right)/2];

do

{

while (x[i] < xx && i < right) i++;

while (xx < x[j] && j > left) j--;

if (i<=j)

{

tmp=x[ i ] ;

x[i]=x[j];

x[j]=tmp;

i++; j-- ;

}

}

while(i<=j);

if(left < j) quick(x,left,j);

if(i < right) quick(x,i,right);

}

Процедура hoare.pas

procedure quick(var x:array of integer;left,right:integer);

var

i,j,xx,tmp:integer;

begin

i:=left; j:=right;

xx:=x[(left+right) div 2];

repeat

while (x[i] < xx) and (i < right) do i:=i+l;

while (xx < x[j]) and (j > left) do j:=j-l;

if i<=j then

begin

tmp:=x[i];

x[i]:=x [j];

x[j]:=tmp;

i:=i+l;

j:=j-i;

end;

until i>j;

if left < j then quick(x,left,j);

if i < right then quick(x,i,right);

end;

procedure hoare(var x:array of integer;n:integer);

begin

quick(x,0,n-l);

end;

Поиск

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

В достаточно общих чертах задача поиска формулируется следующим образом. Имеется массив а, содержащий п однородных объектов (чисел, строк, записей), и нужно установить, содержится ли в нем заданный объект q. При положительном ответе следует дополнительно сообщить порядковый номер (индекс) j найденного объекта (a[j] = q).

Последовательный поиск

Если исходный массив а не упорядочен, то единственно разумным способом является последовательный перебор всех элементов массива и сравнение их с заданным значением. В лучшем случае мы можем получить ответ на первом же шаге, если q = а [ 1 ]. В худшем случае придется перебрать все п элементов и только после этого дать положительный или отрицательный ответ. В среднем количество проверок может оказаться порядка п/2.

Классический алгоритм последовательного поиска включает следующие шаги:

• S1 Остановить начальный индекс равным 1 (j = 1).
  
• S2:Проверить условие q = a[j]. Если оно выполняется, то сообщить, что искомое значение находится в массиве а на j-ом месте и прервать работу. В противном случае продолжить работу.
  
• S3:Увеличить индекс j на 1.
  
• S4:Проверить условие j < n + 1. Если оно выполняется, то вернуться к шагу S2. В противном случае сообщить, что значение q в массиве а не содержится.
  

Большинству программистов кажется, что приведенный алгоритм является оптимальным и ничего сократить в нем нельзя. Однако это — очень распространенное заблуждение. Д. Кнут приводит модификацию алгоритма последовательного поиска, в которой цикл содержит не две логические проверки (шаги S2 и S4), а всего одну. В нашем случае это довольно существенно, т. к. описанный выше цикл реализуется пятью-шестью машинными командами и исключение из него даже одной команды эквивалентно повышению производительности на 15—20%.

Модификация состоит в том, что к массиву а добавляется еще один элемент, в который до начала цикла заносится q. Теперь цикл повторяется до тех пор, пока не будет встречен элемент а [ j ], равный q, и необходимость в проверке j < n + 1 отпадает. Конечно, перед возвратом из процедуры надо удостовериться в том, что найденный индекс j не равен n + l. Но такая проверка выполняется за пределами цикла.

Для программистов, имеющих дело с языком ассемблера, известен и более простой прием, не требующий расширения исходного массива. Очевидно, цикл поиска можно организовать как в прямом (j меняется от 1 до n), так и в обратном (j меняется от n до i) направлении. Обратный цикл на ассемблере реализуется с помощью команды LOOP, организующей возврат в начало цикла с одновременным вычитанием 1 из счетчика сх. Цикл повторяется до тех пор, пока содержимое регистра сх не станет равным 0. Таким образом, дополнительного сравнения (j < n + 1) здесь не требуется.

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

Функция ssearch.bas

FUNCTION SSEARCH(Q,A(),N)

FOR J=0 TO N-l

IF Q=A(J) THEN SSEARCH=J: EXIT FUNCTION

NEXT J

SSEARCH=-1

END FUNCTION

Функция ssearch.c

int ssearch(int q, int *a, int n)

}

register int j;

for(j=0; j<n; j++)

if(q==a[j]) return j;

return -1;

}

Функция ssearch.pas

function ssearch(q:integer;a:array of integer;n:integer):integer;

var

j:integer; begin

for j:=0 to n-1 do

if q=a[j] then

begin

ssearch:=j;

exit;

end;

ssearch:=-l;

end;

Бинарный поиск

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

Исключим тривиальный случай, когда искомое значение g выходит за пределы интервала [а[1],а[n]]. Обозначим через left и right индексы элементов массива, определяющие текущий диапазон поиска. В начальный момент left = 1 и right = n. Сравним значение q с величиной среднего элемента a [mid] в диапазоне поиска (mid = (left + right)/2). Если значение q строго меньше a [mid], то заменим правую границу диапазона поиска на mid - 1. Если значение q строго больше a [mid], то заменим левую границу диапазона поиска на mid + 1. Если оба строгие неравенства не выполнены, то имеет место равенство q = a [mid], и в этом случае процедура поиска завершена успешно.

Поиск следует продолжать до тех пор, пока значение индекса left не превосходит значения индекса right. А нарушиться это условие может только в случае, когда диапазон поиска сведен к минимальному (right = left + l) и имеют место неравенства:

a[left] < q < a[right]

Это означает, что значение q в массиве а не содержится.

Функция bsearch.bas

FUNCTION BSEARCH(Q,A() ,N) LEFT=0: RIGHT=N-1

WHILE LEFT <= RIGHT

MIDDLE=(LEFT+RIGHT)\2

IF Q < A(MIDDLE) THEN RIGHT=MIDDLE-1: GOTO M

IF Q > A(MIDDLE) THEN LEFT=MIDDLE+1: GOTO M

BSERACH=MIDDLE : EXIT FUNCTION M:WEND

BSEARCH=-1 END FUNCTION

Функция bsearch.c

int bsearch(int q,int *a,int n)

{

register int left,right,mid;

left=0; right=n-l;

for(;left <= right;)

{

mid=(left+right)12;

if(q < a[mid]) right=mid-l;

else if(q > a[mid]) left=mid+l;

else

return mid; }

return -1; }

Функция bsearch.pas

function bsearch(q:integer;a:array of integer;n:integer):integer;

var

left,right,mid:integer;

begin

left:=0; right:=n-l;

until left <= right do

begin

mid:=(left+right) div 2;

if q < a[mid] then right=mid-l

else if q > a[mid] then left=mid+l

else

begin

bsearch:=mid;

exit;

end;

end;

bsearch:=-l;

end;

Идея бинарного поиска может быть с успехом реализована в игре с отгадыванием задуманного целого числа из заранее установленного диапазона [O,N]. В ответ на число, предложенное угадывающим, его партнер может дать один из трех ответов:

• это число меньше загаданного;
• это число больше загаданного;
• это число равно загаданному.
  

Оптимальное поведение отгадывающего в точности повторяет схему бинарного поиска. Сначала надо предложить число, расположенное в середине интервала, т. е. N/2. Затем, сузив интервал поиска вдвое, повторить аналогичный маневр. Попадание в цель произойдет не более чем через log₂N шагов.

Приведенные ниже тексты программ реализуют оптимальную тактику отгадывания чисел из диапазона [0,100], затрачивая на это не более 7 шагов. На вопросы программы загадавший должен нажимать клавишу Y или у (в случае положительного ответа) или любую другую клавишу, если вопрос программы не соответствует загаданному числу.

Программа 4_02.bas

'Программа угадывания задуманного числа в интервале [0,100]

DEFINT A-Z

CLS

LEFT=0: RIGHT=100:

DO

MIDDLE=(LEFT+RIGHT)\2

PRINT "Задуманное Вами число больше, чем"; MIDDLE; " (Y/N) - ";

INPUT "",A$

IF RIGHT-LEFT <= 1 THEN

IF A$="Y" OR A$="y" THEN

PRINT "Вы задумали ";RIGHT: END

ELSE

PRINT "Вы задумали ";LEFT: END

END IF

END IF

IF A$="Y" OR A$="y" THEN LEFT=MIDDLE+1 ELSE RIGHT=MIDDLE

LOOP

END

Программа 4_02.с

/* Программа угадывания задуманного числа в интервале [0,100] */

#include <stdio.h>

#include <conio.h>

main ()

{

int left=0, right=100, middle, ok;

char ch;

clrscr();

for (;;)

{

middle={left+right)/2;

printf("\n Задуманное Вами число больше, чем % d (Y/N) - ", middle);

ch=getche();

if(right-left <= 1)

if (ch=='Y' || ch == 'y') { ok=right; break; }

else { ok=left; break;}

if(ch=='Y' II ch== 'y') left=middle+l;

else right=middle; }

printf("\пВы задумали %d",ok); getch(); }

Программа 4_02.pas

{ Программа угадывания задуманного числа в интервале [0,100] }

uses Crt;

var

ch: char;

left, right, middle, ok: byte;

begin

left:=0;

right:=100;

clrscr;

repeat

middle := (left + right) div 2;

write('Задуманное Вами число больше, чем ',middle,' (Y/N) - ');

ch:=readkey;

writeln(ch);

if (right-left <= 1) then

if (ch='Y') or (ch = 'y') then begin ok:=right;

break;

end else begin ok:=left;

break;

end; if(ch='Y') or (ch='y') then left := middle + 1

else right := middle;

until false;

writeln('Вы задумали ',ok);

readln;

end.

Задачи, советы и ответы

Задание 4.03. Перестановка элементов одномерного массива в обратном порядке

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

Совет 1 (общий)

В этой задаче особых проблем не возникает, и она включена как подготовительный этап к выполнению последующего задания. Цикл по перестановке элементов следует продолжать до целой части п/2 (n — число элементов в массиве), не обращая внимания на четность или нечетность п. Возможно, что при этом средний элемент, который должен оставаться на месте, переставится сам с собой.

Программа 4_03.bas

DECLARE SUB INVERT (A%(), N%)

DEFINT A-Z

CLS

N = 20

DIM A(N)

PRINT "Массив до перестановки :"

FOR I=0 ТО N-l: A(I)=I+1: PRINT A(I); : NEXT I

PRINT

INVERT A(), N

PRINT "Массив после перестановки :"

FOR I=0 ТО N-l: PRINT A(I); : NEXT I

END

SUB INVERT (A%(), N%)

DEFINT A-Z

FOR I = 0 TO (N-l)\2

TMP = A(I): A(I) = A(N-I-l): A(N-I-1) = TMP

NEXT I

END SUB

Программа 4_03.с

#include <stdio.h>

#include <conio.h>

void invert(int *a, int n) ;

void main(void)

{

#define N 20

int i,a[N];

clrscr ();

printf("Массив до перестановки :\n");

for(i=0; i < N; i++)

fa[i]=i+l; printf("%3d",a[i]); }

invert(a,N);

printf("\n Массив после перестановки :\n");

for(i=0; i < N; i++)

printf("%3d",a[i]);

getch(); } void invert(int *a, int n)

int j,tmp;

for(j=0; j < n/2; j++)

{ tmp=a[j];

a[j]=a[n-j-1];

a[n-j-l]=tmp; } }

головной и хвостовой частях. Основным препятствием для реализации процедуры является запрет на использование вспомогательного массива.

Совет 1 (общий)

Это довольно известная в мире задача из набора программистских "жемчужин" (Бентли Д. Жемчужины творчества программистов / Пер. с англ. М.: Радио и связь, 1990). Она имеет изящное трехшаговое решение. На первом шаге производится обратная перестановка элементов только головной части массива. На втором шаге такой же перестановке подвергаются элементы хвостовой части. И заключительный этап — еще одна перестановка, но уже всех элементов массива.

Конечно, можно принять предложенный алгоритм на веру и убедиться на нескольких примерах, что он работает правильно. Но это не может дать абсолютной уверенности в том, что также произойдет на любых сочетаниях исходных данных. Поэтому можно попытаться доказать правильность алгоритма, проследив за местоположением (индексом) каждого элемента после указанных перестановок.

Если элемент с исходным индексом i принадлежал голове массива (i < i < k), то инвертирование головы перемещает:

1-й элемент в позицию с индексом k, 2-й элемент в позицию с индексом k-l,

k-й элемент в позицию с индексом 1.

Сумма индексов элементов, меняющихся своими местами, при этом равна k+l. Поэтому 1-й элемент из головной части после инвертирования головы массива окажется на месте с индексом k-i+1. При последующем инвертировании всего массива сумма индексов взаимных пар меняющихся элементов равна п+1. Следовательно, элемент с первоначальным индексом i из головной части окажется на месте элемента с индексом (n+l) - (k-i+l)=n-k+i. Таким образом:

1-й элемент окончательно окажется в позиции n-k+l, 2-й элемент окончательно окажется в позиции n-k+2,

k-й элемент окончательно окажется в позиции n-k+k.

Это означает, что прежняя голова массива переместится в его хвост, сохранив взаимное расположение элементов.

Теперь рассмотрим поведение 1-го элемента из хвостовой части (k + i < i < n). После инвертирования хвоста:

элемент с индексом k+l окажется в позиции п, элемент с индексом k+2 окажется в позиции n-1,

элемент с индексом п окажется в позиции k+l.

Сумма индексов пар, меняющихся при этом местами, равна n+k+i. Поэтому 1-й элемент из хвостовой части после инвертирования хвоста перемещается в по-

зицию n+k+l-i. При последующем инвертировании полного массива, когда сумма индексов соответствующих пар равна n+1, произойдет следующее:

элемент с индексом k+l, предварительно перемещенный в позицию n, займет место элемента с номером (n+l)-n=l;

элемент с индексом k+2, предварительно перемещенный в позицию п-1, займет место элемента с номером (n+1)-(n-1)=2;

элемент с индексом п, предварительно перемещенный в позицию k+l, займет место элемента с номером (n+l)-(k+l)=n-k.

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

Совет 2 (общий)

Процедуру invert, приведенную в предыдущем задании, целесообразно модифицировать, задавая в ней дополнительные параметры. Например — индекс j, начиная с которого производится инвертирование, и количество len элементов, участвующих в перестановке.

Программа 4_04.bas

DECLARE SUB INVERT1 (A%(), J%, N%)

DEFINT A-Z

CLS

N=20: K=15

DIM A(N)

PRINT "Массив до перестановки :"

FOR I=0 TO N-l: A(I)=I+1: PRINT A(I); : NEXT I

PRINT

INVERT1 A(),0,K

PRINT "После перестановки в головной части :"

FOR I=0 ТО N-l: PRINT A(I); : NEXT I: PRINT

INVERT1 A(),K,N-K

PRINT "После перестановки в хвостовой части :"

FOR I=0 ТО N-l: PRINT A(I); : NEXT I: PRINT

INVERT1 A(),0,N

PRINT "После полной перестановки :"

FOR I=0 TO N-l: PRINT A(I); : NEXT I

END

SUB INVERT1 (A%(), J%, N%)

DEFINT A-Z

FOR I = J TO J+(N-1)\2

TMP=A(I): A(I)=A(2*J+N-1-I): A(2*J+N-l-I)=TMP

NEXT I

END SUB

Программа 4_04.с

#include <stdio.h>

#include <conio.h>

void invertl(int *a, int j , int k) ;

void main(void) {

#define N 20

#define К 15

int i,a[N];

clrscr () ;

printf("Массив до перестановки :\n");

for(i=0; i < N; 1++)

{

a[i] = 1 + 1;

printf("%3d",a[i]); }

invertl(a,0,K);

printf("\n После перестановки в головной части :\n");

for(i=0; i < N; i++)

printf("%3d",a[i]);

invertl(a,K,N-K);

printf("\n После перестановки в хвостовой части :\n");

for(i=0; i < N; i++)

printf("%3d",a[i]);

invertl(a,0,K);

printf("\n После полной перестановки :\n");

for(i=0; i < N; i++)

printf("%3d",a[i]);

getch(); }

void invertl(int *a, int j, int k) {

int m,tmp;

for(m=j; m < j+k/2; m++)

{

tmp=a[m]; a[m] = a[2*j+k-m-1];

a[2*j+k-m-l]=tmp; }

}

Программа 4_04,pas

program pearl; uses crt; const

N=20; K=15; var

a:array [1..N] of integer;

i:integer;

procedure invertl(var a; j,k:integer);

var

m,tmp:integer;

aa:array [1..1] of integer absolute a;

begin {$R-}

for m:=j to j + k div 2 do begin

tmp:=aa[m];

aa[m]:=aa[2*j+k-m-1];

aa[2*j+k-m-l]:=tmp;

end;

{$R+} end;

begin clrscr;

writeln('Массив до перестановки : ') ;

for i:=l to N do

begin a[i]:=i;

write(a[i]:3);

end;

writeln;

invertl(a,1,K);

writeln('После перестановки в головной части :');

for i:=l to N do

write(a[i]:3);

writeln;

invertl(a,K+l,N-K);

writeln('После перестановки в хвостовой части :');

for i:=l to N do write(a[i]:3);

writeln; invertl(a,l,N);

writeln('После полной перестановки :');

for i:=l to N do

write(a[i]:3);

readln;

end.

Задание 4.05. Вывод массивов

Составить процедуру (функцию) вывода небольших целочисленных матриц размерности m x n с управлением по ширине колонок (w) и по местоположению на экране (row — строка, col — столбец, определяющие левый верхний угол матрицы). Предполагается, что матрица целиком помещается на экране и что ширина ее колонок не превосходит девяти позиций.

Совет 1 (общий)

В каждом алгоритмическом языке предусмотрена процедура типа window, позволяющая определить прямоугольную область вывода на экране. Однако пользоваться ей в данном случае нецелесообразно, т. к. придется запоминать параметры окна, существовавшие до обращения к процедуре вывода, затем устанавливать новые, а перед выходом из процедуры восстанавливать запомненные. В Си и Паскале, в принципе, такая возможность имеется (см. функцию gettextinf о), а в QBasic такие действия перекладываются на программиста. Все это сильно усложнит организацию процедуры. Будем считать, что в нашем распоряжении находится полный экран и никаких дополнительных окон вызывающая программа не создавала. Поэтому можно воспользоваться прямыми средствами управления позицией курсора на экране — LOCATE (QBasic) или gotoxy (Си, Паскаль).

Совет 2 (QBasic)

Для вывода числа, прижатого к правой границе поля фиксированной ширины, целесообразно использовать оператор PRINT USING. Так как ширина поля в нашем случае — величина переменная, то шаблон вывода придется сформировать в виде значения строки, содержащей w символов "I".

Совет 3 (Си)

Так же, как и в Бейсике, здесь придется сформировать символьную строку вида "%wd". Чтобы вписать в нее символьное представление ширины поля w, можно воспользоваться суммой вида w+48, где добавка 48 соответствует коду символа "0".

Совет 4 (Паскаль)

Оператор write позволяет задавать ширину поля вывода не только в виде конкретного числа, но и как значение арифметического выражения (в данном случае простейшего — w).

Программа 4_05.bas

DECLARE SUB PRINTA (ROW%, COL%, W%, C% (-) , N%, M%)

DEFINT A-Z

CLS

DIM A(2, 3) , B(3, 3)

FOR J = 0 ТО 2: FOR К = 0 TO 3

A(J, K) = J + К * К NEXT К: NEXT J PRINTA 5, 5, 3, A() , 3, 4

FOR J = 0 TO 3: FOR К = 0 ТО 3

B(J, K) = J * 10 + К * 25 NEXT K: NEXT J PRINTA 5, 40, 5, B() , 4, 4

END

SUB PRINTA (ROW%, COL%, W%, C%(), N%, M%) DEFINT A-Z

F$ = LEFT$("##########", W)

FOR J = 0 TO N - 1: FOR К = 0 TO M - 1

LOCATE ROW + J, COL + K*W

PRINT USING F$; C(J, K) NEXT K: NEXT J

END SUB

Программа 4_05.с

#include <stdio.h>

#include <conio.h>

void printa(int row,int col,int w,int *c,int n,int m) ;

void main(void) {

int a[3] [4] = {{!,2,3,4),{10,20,30,40},{100,200, 300, 400}};

int b[4][4]={{l,2,3,4},{5,6,7,8},{9,10,ll,12},{13,14,15,16}};

clrscr();

printa (5,5,4, (int *)a,3,4);

printa(5,40,5,(int *)b,4,4);

getch(); }

void printa(int row,int col,int w,int *c,int n,int m) {

int j,k;

char f[4]="%0d";

f[1] += w;

for(j=0; j<n; j++)

for(k=0; k<m; k++)

{

gotoxy(col+k*w,row+j);

printf(f,c[k+j*m]); }

}

Программа 4_05.pas

program mat_print;

uses crt;

const

a:array [1..3,1..4] of integer = ((1,2,3,4), (10,20,30,40), (100,200,300,400));

b:array [1..4,1..4] of integer = ((1,2,3,4), (5,6,7,8), (9,10,11,12), (13,14,15,16));

procedure printa(row,col,w:integer,-var с;n,m:integer);

var

j,k:integer;

d:array [0..MaxInt-l] of integer absolute c;

begin

for j:=0 to n-1 do

for k:=0 to m-1 do

begin

gotoxy(col+k*w,row+j); write(d[k+m*j]:w);

end;

end;

begin clrscr;

printa(5, 5, 4, a, 3, 4);

printa(5, 40, 5, b, 4, 4);

readln;

end.

Задание 4.06. Ход конем

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

Говорят, что конь ходит буквой "Г". Это не совсем точно, т. к. допустимые ходы этой фигуры образуются перемещениями на две клетки по горизонтали (вертикали) с последующим поворотом на 90 градусов по или против часовой стрелки и сдвигом по вертикали (горизонтали) еще на одну клетку. Если сопоставить с шахматной доской матрицу 8x8, то из позиции a[i,j] возможны максимум 8 ходов в клетки со следующими индексами:

1. a[i-2,j-1] 5. a[i+l,j-2]

2. a[i-2,j+l] 6. a[i+l,j+2]

3. a[i-l,j-2] 7. a[i+2,j-1]

4. a [i-1,j+2] 8. a[i + 2,j + 1]

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

Для определения минимального количества ходов, соединяющих клетки a[i1,j1] и a[i2,j2], предлагается следующий алгоритм. Сначала все элементы массива расписываются каким-то кодом, например числом — 1, означающим, что все клетки шахматного поля свободны. Затем в начальную позицию a[i1,j1] заносится 0 и делаются попытки определить все клетки, достижимые за один ход. В каждую из них заносим 1. Для каждой клетки, достигаемой после первого хода, делается попытка совершить следующий ход, и все вновь достигаемые позиции метятся кодом 2. Естественно, что среди них исключаются ходы, возвращающие нас в начальную позицию, т. е. ходить надо только по свободным клеткам. Из каждой клетки, достигаемой за два хода, делается попытка совершить следующий ход в еще не занятые позиции и пометить все допустимые элементы массива числом 3. Числовую метку, которую мы заносим на очередном шаге охвата клеток шахматного поля, можно назвать уровнем досягаемости.

Расстановка уровней досягаемости продолжается до тех пор, пока мы не попадем в конечную позицию а [12, j2]. А еще лучше — до тех пор, пока не будет заполнена вся матрица, и тогда мы получим ответ, за сколько ходов можно переместиться из позиции a [i1, j1] в любую другую клетку шахматного поля.

Наряду с матрицей а можно ввести еще один массив ь и заполнять его аналогичным образом, начиная из конечной позиции b[i2,j2]. Если n-минимальное число ходов, переводящих коня из клетки a[i1, j1] в клетку а [i2, j2], то обратное путешествие по минимальной траектории займет тоже п шагов. Кроме того, можно заметить, что в каждой клетке любой минимальной траектории имеет место равенство

a[i,j] + b[i,j] = n.

Оно означает, что число промежуточных ходов из начальной позиции в клетку a [i, j ] и число встречных ходов по этой же траектории из конечной точки в сумме составляют длину минимальной траектории. Этот факт позволяет отсечь все недопустимые позиции и, тем самым, выделить клетки, принадлежащие только минимальным траекториям.

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

Совет 1 (общий)

Целесообразно выделить в отдельную процедуру поиск и заполнение клеток, достигаемых за один ход из каждой клетки k-ro уровня. Назовем эту процедуру newlevel и условимся, что, помимо маркировки клеток (k+l)-ro уровня, она сообщает, удалось ли сделать хотя бы один ход.

Программа 4_06.bas

DIM A(8,8)

FOR I=0 ТО 7 : FOR J=0 TO 7

A(I,J)=-l NEXT J: NEXT I

CLS : INPUT "Задайте начальную позицию :",I,J A(I,J)=0 : K=0 M:NEWLEVEL

IF XOD = 1 THEN GOTO M

FOR I=0 TO 7 : FOR J=0 TO 7

PRINT A(I,J) NEXT J: PRINT : NEXT I END

SUB NEWLEVEL XOD=0

FOR I=0 TO 7 : FOR J=0 TO 7

IF A(I,J)=K THEN

TRY(I-2,J-l): TRY(I-2,J+1)

TRY(I-1,J-2): TRY(I-l,J+2)

TRY(I+1,J-2): TRY(I+1,J+2)

TRY(I+2,J-l): TRY(I+2,J+1)

END IF NEXT J: NEXT I

K=K+1

END SUB

SUB TRY(P,Q)

IF P>=0 AND P<8 AND Q>=0 AND Q<8 AND A(P,Q)<0 THEN A(P,Q)=K+1 : XOD=1

END IF

END SUB

Программа 4_06.с

#include <stdio.h>

#include <conio.h>

char newlevel(void);

void try(int p,int q);

char a[8][8],i,j,k=0,xod;

void main(void) {

clrscr();

for(i=0; i<8; i++)

for(j=0; j<8; j++)

a[i][j]=-l;

puts("Задайте начальную позицию :");

scanf("%d %d",&i,&j);

a[i][j]=0; m:newlevel();

if(xod==l) goto m;

for(i=0; i<8; i++) {

for(j=0; j<8; j++)

printf("%3d",a[i] [j]) = —1;

printf("\n");

}

getch(); )

char newlevel(void) {

char di[8]={-2,-2,-l,-l, 1,1, 2,2};

char dj[8]={-l, l,-2, 2,-2,2,-1,1};

char f;

xod=0;

for(i=0; i<8; i++)

for(j=0; j<8; j++)

if (a[i] [j]==k)

for(f=0; f<8; f++)

try(i+di[f],j+dj[f]);

k++;

return xod; }

void tryfint p,int q) {

if(p>=0 && p<8 && q>=0 && q<8 && a[p][q]<0)

{ a[p][q]=k+l;

xod=l;} }

Программа 4_06.pas

program horst;

{=======================================

Построение полей досягаемости ходом коня из заданной позиции.

Индексы позиций задаются от 0 до 7. Поле, из которого конь начинает, помечается уровнем 0. Поля, достигаемые после первого хода, помечаются уровнем 1, после второго хода - уровнем 2 и т. д.

=====================================}

uses Crt;

label m;

var

i,j,k,xod:byte;

a:array [0..7,0..7] of shortint;

procedure try(p,q:integer);

{=================================

Попытка совершить ход уровня k+1 в позицию (p,q). При возможности хода в а[р,q] заносится номер уровня, а в переменную xod - значение 1. В противном случае переменная xod остается равной 0.

==================================}

begin

if (p>=0) and (p<8) and (q>=0) and (q<8) and (a[p,q]<0) then

begin a[p,q]:=k+l; xod:=l; end; end;

procedure newlevel;

{================================

Поиск всех ходов уровня k+1 из клеток, достигнутых за k ходов

================================}

const

{смещения по индексам i,j для 8 возможных ходов коня}

di:array [0..7] of integer = (-2,-2,-1,-1, 1,1, 2,2);

dj:array [0..7] of integer = (-1, l,-2, 2,-2,2,-1,1); var

f:byte; begin

xod:=0; {Гашение признака возможности совершить ход}

{Поиск полей, достигаемых на k-том уровне)

for i:=0 to 7 do

for j:=0 to 7 do

if a[i,j]=k then

{Если поле найдено, из него делаются попытки сходить по 8 возможным направлениям}

for f:=0 to 7 do try(i+di[f],j+dj[f]);

k:=k+l;

{Повышение уровня хода}

end;

begin

k:=0; {Уровень хода} clrscr;

for i:=0 to 7 do

for j:=0 to 7 do

a[i,j]:=-1; {Начальная роспись матрицы позиций}

write('Задайте начальную позицию : '};

readln(i,j);

a[i,j]:=0; (Отметка начальной позиции)

m: newlevel;

{На поиск ходов следующего уровня}

if xod=l then goto m; {Если поиск был завершен успешно} {Цикл вывода заполненной матрицы с уровнями ходов}

for i:=0 to 7 do

begin

for j:=0 to 7 do

write (a[i,j]:3);

writeln;

end;

readln;

end.

Задание 4.07. Сравнение методов сортировки

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

Совет 1 (общий)

Программу тестирования целесообразно написать в двух вариантах — в укороченном (МАХ = 20) и в полном (МАХ = 15 000, для интерпретатора QBasic достаточно МАХ = 5000). Их можно объединить, закомментировав ту или иную группу операторов. В укороченном варианте следует предусмотреть вывод элементов массива до и после упорядочения с целью проверки работоспособности программы. В полном варианте вывод массива следует закомментировать, чтобы это время не включалось в хронометраж алгоритма.

Совет 2 (общий)

Можно собрать в рамках одной программы все алгоритмы сортировки, но оставить незакомментированным вызов только одного из них. А затем по очереди подключать тот или иной алгоритм.

Программа 4_07.bas

DECLARE SUB BUBBLE(X%(),N%)

DECLARE SUB INSERT(X%(),N%)

DECLARE SUB SELECT1(X%(},N%)

DECLARE SUB SHELLSORT(X%(),N%)

DECLARE SUB HOARE(X%(),N%)

DECLARE SUB QUICK(X%(),LEFT%,RIGHT%)

DEFINT A-Z

CLS

CONST N=5000

DIM A(N)

FOR J=0 TO N

A(J)=INT(N*RND) 'PRINT USING "#### "; A(J); NEXT J

PRINT T1#=TIMER BUBBLE A() , N ' INSERT A (),N 'SELECT1 A(),N 'SHELLSORT A(),N 'HOARE A{},N T2#=TIMER

PRINT T2#-T1#; "сек"

'FOR J=0 TO N: PRINT USING "#### ";A(J); : NEXT J END

REM Тексты подпрограмм сортировки

Программа 4_07.с

#include <iostream.h>

#include <stdlib.h>

#include <conio.h>

#include <dos.h>

#define MAX 15000

void bubble(int *x, int n) ;

void select(int *x, int n) ;

void insert(int *x, int n);

void shell(int *x, int n);

void hoare(int *x, int n);

void quick(int *x, int left, int right);

main( ) {

int num[MAX];

int i ;

struct time w;

clrscr();

//cout << "До сортировки" << endl;

for(i=0; i < MAX; i++) // {

num[i]=random(MAX);

// cout << num[i] << " ";}

// cout << endl; // getch();

// cout << "После сортировки" « endl;

gettime (&w);

cout << (unsigned int)w.ti_sec <<".";

cout << (unsigned int)w.ti_hund << endl;

bubble(num,MAX);

//select(num,MAX);

//insert(num,MAX);

//shell(num,MAX);

//hoare(num,MAX);

gettime(&w);

cout << (unsigned int)w.ti_sec <<".";

cout << (unsigned int)w.ti_hund << endl;

//cout << "Кончили";

getch();

//for(i=0; i<MAX; i++)

//cout << num[i] << " ";

//getch();

return 0; }

/*==== тестируемые процедуры ========*/

Программа 4_07.pas

program all_sort; uses crt,WinDos; const

MAX=15000; type

xarr=array [0..MAX-1] of integer; var

x:xarr;

i:integer;

hour,minute,second,sec100:word;

{===== тестируемые процедуры ======}

begin

clrscr;

for i:=0 to MAX-1 do

begin

x[i]:=random(MAX); {write(x[i],' ');}

end;

writeln;

write('До сортировки - ');

gettime(hour,minute,second,sec100);

write(minute:2,' мин ',second:2,'.',sec100:2, ' сек');

writeln;

{Вызов метода}

{ bubble(x,MAX);}

{ select(x,MAX);}

{ insert(x,MAX);}

shell(x,MAX);

{ hoare(x,MAX);}

gettime(hour,minute,second,sec100};

write('После сортировки - ');

write(minute:2,' мин ',second:2,'.',seclOO:2,' сек');

writeln;

{ for i:=0 to MAX-1 do write(x[i],' ');}

readln; end.

Задание 4.08. Счастливый билет

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

Совет 1 (общий)

Алгоритм "в лоб" заключается в том, чтобы организовать шесть вложенных циклов, в каждом из которых перебирается очередная цифра номера. В самом внутреннем цикле организуется проверка суммы старших и младших цифр номера и подсчет счастливых билетов. Однако эту проверку придется повторять миллион раз, и даже достаточно мощные процессоры затратят на такой алгоритм заметное время. Решение задачи можно найти примерно в 1000 раз быстрее, если вместо лобового перебора подсчитать, сколько раз сумма трех цифр равна 0, 1, 2.....27. Очевидно, что нулевую сумму дает единственная комбинация цифр 000, представляющая единственный счастливый билет с номером 000000. Сумму, равную 1, дают три комбинации — 001, 010 и 100. Соответственно, счастливых билетов с такой суммой уже 9 (каждая из перечисленных выше комбинаций в старших цифрах с тремя аналогичными сочетаниями в младших разрядах). Таким образом, если обозначить через s [0], s [1].....S [27] количество комбинаций цифр, сумма которых равна индексу элемента в массиве S, то общее количество счастливых билетов N будет равно сумме:

N = S[0] * S[0] + S[l] * S[l] + ... + S[27] * S[27].

Программа 4_08.bas

DIM S(28)

FOR Al=0 TO 9: FOR A2=0 TO 9: FOR A3=0 TO 9

S(A1+A2+A3)=S(A1+A2+A3)+1 NEXT A3: NEXT A2: NEXT A1

FOR K=0 TO 27: N=N+S(K)*S(K) : NEXT К

PRINT "Количество счастливых билетов = ";N

END

Программа 4_08.с

#include <stdio.h>

#include <conio.h>

main()

{

int s[28],al,a2,a3,k;

long N;

clrscr();

for(k=0; k<28; k++)

s[k]=0;

for(al=0; al<10; al++)

for(a2=0; a2<10; a2++)

for(a3=0; аЗ<10; а3++)

s[al+a2+a3]++;

for(k=0,N=0; k<28; k++)

N += s[k] *s [k] ;

printf("\n Количество счастливых билетов = %ld",N);

getch(); }

Программа 4_08.pas

program lucky_ticket;

var

al,a2,a3,k:integer;

N:longint;

s:array [0..27] of integer;

begin

for al:=0 to 9 do

for a2:=0 to 9 do

for a3:=0 to 9 do

inc(s[al+a2+a3]);

for k:=0 to 27

N:=N+s [k] *s["k] ;

writeln('Количество счастливых билетов = ',N);

readln;

end.

Задание 4.09. Количество разных элементов в целочисленном массиве

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

Совет 1 (общий)

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

Совет 2 (общий)

Второй алгоритм состоит из трех шагов. На первом из них выясняется, содержится ли в исходном массиве хотя бы один элемент с нулевым значением. Если таковой не обнаружен, то признак k0 = 0, в противном случае k0 = 1. На втором шаге организуются два вложенных цикла, в которых каждый ненулевой 1-й элемент сравнивается со всеми последующими. Если при этом будет обнаружен двойник, то i-му элементу присваивается нулевое значение. На третьем шаге подсчитывается количество оставшихся ненулевых значений, которое корректируется на величину k0.

Совет 3 (общий)

Третий алгоритм базируется на использовании массива индикаторов. Так как значения элементов исходного массива принадлежат интервалу [0,32767], то заводится 32 768 битовых индикаторов (4096 байт). В начале все индикаторы сбрасываются в нуль, а затем выполняется цикл одноразового просмотра элементов исходного массива. Для значения каждого элемента a[i] проверяется соответствующий бит в массиве индикаторов и, если он равен 0, в него заносится 1 и к счетчику разных чисел добавляется единица. Если проверяемый бит индикаторов отличен от нуля, то соответствующее значение уже встречалось.

Совет 4 (Си)

Массив индикаторов (b) можно явным образом запрашивать при входе в подпрограмму и освобождать при выходе, хотя локальные данные в процедурах и функциях все равно выделяются и освобождаются автоматически. Но в библиотеке Си есть полезная функция calloc, которая одновременно выделяет память и чистит ее. Переменные byte и bit использованы для определения байта и бита в массиве индикаторов, соответствующих анализируемому значению a [i].

Программа 4_09a.bas

DECLARE SUB SORT (A() AS INTEGER, N%)

DECLARE FUNCTION DIFFERENCE% (A() AS INTEGER, N%)

DEFINT A-Z

DIM A(5)

DATA 0,0,0,0,0

DATA 1,1,1,1,1

DATA 0,1,1,1,1

DATA 0,0,1,1,2

DATA 0,1,2,3,4

DATA 1,2,3,4,5

CLS

FOR k=1 TO 5

FOR I=0 TO 4: READ A(I): NEXT I

PRINT "Количество разных чисел в массиве ";k;" = ";

PRINT DIFFERENCE(A(), 5} NEXT k END

FUNCTION DIFFERENCE (A() AS INTEGER, N%)

SORT A(),N%

M=l

FOR I=0 TO N%-2

IF A(I)<>A(I+1) THEN M=M+1

NEXT I

DIFFERENCE=M

END FUNCTION

SUB SORT(A() AS INTEGER,N%)

REM тело любой процедуры сортировки

END SUB

Программа 4_09b.bas

DECLARE SUB SORT (A() AS INTEGER, N%)

DECLARE FUNCTION DIFFERENCE% (A() AS INTEGER, N%)

DEFINT A-Z

DIM A0(5),A1{5),A2(5),A3(5},A4(5),A5(5)

DATA 0,0,0,0,0

FOR I=0 TO 4: READ А0(I): NEXT I

DATA 1,1,1,1,1

FOR I=0 TO 4: READ A1(I): NEXT I

DATA 0, 1,1, 1, 1

FOR I=0 TO 4: READ A2(I): NEXT I

DATA 0,0, 1, 1,2

FOR I=0 TO 4: READ A3(I): NEXT I

DATA 0,1,2,3,4

FOR I=0 TO 4: READ A4(I): NEXT I

DATA 1,2,3,4,5

FOR I=0 TO 4: READ A5(I): NEXT I

PRINT "Количество разных чисел в массиве А0 = ";

PRINT DIFFERENCE(А0(),5)

PRINT "Количество разных чисел в массиве А1 = ";

PRINT DIFFERENCE(A1(),5)

PRINT "Количество разных чисел в массиве А2 = ";

PRINT DIFFERENCE(A2(),5)

PRINT "Количество разных чисел в массиве A3 = ";

PRINT DIFFERENCE(A3() ,5)

PRINT "Количество разных чисел в массиве А4 = ";

PRINT DIFFERENCE(A4(),5)

PRINT "Количество разных чисел в массиве А5 = ";

PRINT DIFFERENCE(A5(), 5)

END

FUNCTION DIFFERENCE (АО AS INTEGER-,N%) DEFINT A-Z

FOR I=0 TO N%-1

IF A(I)=0 THEN K0=l: EXIT FOR NEXT I

FOR I=0 TO N%-1 IF A(I)<>0 THEN

FOR J=I+1 TO N%-1

IF A(I)=A(J) THEN A(I)=0: EXIT FOR NEXT J END IF NEXT I

FOR I=0 TO N%-1

IF A(I)<>0 THEN M=M+1 NEXT I

DIFFERENCE=M+K0

END FUNCTION

Программа 4_09а.с

#include <stdio.h>

#include <conio.h>

void sort(int *a,int n);

int difference(int *a,int n);

main() {

int a0[5]={0,0,0,0,0};

int a1[5]={l,l,l,l,l};

int a2[5]={0,l,l,l,l);

int a3[5]={0,0,l,l,2};

int a4[5]={0,l,2,3,4};

int a5[5]={l,2,3,4,5};

printf("\n Количество разных чисел в этом массиве равно ");

printf("%d",difference(a0,5));

getch(); }

void sort(int *a,int n) {

/* тело любой процедуры сортировки */

return; }

int difference(int *a, int n) {

int i,m;

sort(a,n);

for(i=0,m=l; i<n-l; i++)

if(a[i] != a[i+l]) m++;

return m; }

Программа 4_09b.c

#include <stdio.h>

#include <conio.h>

int difference(int *a,int n);

main() {

int a0[5]={0,0,0,0,0};

int al[5] = {l,l,l,l,1};

int а2[5]={0,1,1,1,1};

int a3[5]={0,0,l,l,2};

int a4[5]={0,l,2,3,4};

int a5[5]={l,2,3,4,5};

printf("\n Количество разных чисел в этом массиве равно ");

printf("%d",difference(a0,5));

getch (); }

int difference(int *a,int n) {

int i,j,k0,m;

for(i=k0=0; i<n; i++)

if(a[i] == 0) { k0=1; break; }

for(i=0; i<n-l; i++)

{ if(a[i]==0) continue;

for(j=i+l; j<n; j++)

if(a[i]==a[j]) { a[i]=0; break; } }

for(i=m=0; i<n; i++)

if(a[i] !=0)m++;

return m+k0; }

Программа 4_09с.с

#include <stdio.h>

#include <conio.h>

#include <alloc.h>

int difference(int *a,int n);

main() {

int a0[5]={0,0,0,0,0};

int a1[5]={l,l,l,l,l};

int a2[5]={0,l,l,l,l};

int a3[5]={0,0,l,l,2);

int a4[5]={0,l,2,3,4);

int a5[5]={l,2,3,4,5};

printf("\n Количество разных чисел в этом массиве равно ");

printf("%d",difference(a5, 5)) ;

getch(); }

int difference(int *a, int n) {

char *b;

char mask[8]={128,64,32,16,8,4,2,1};

int bit,byte,i,m;

b=calloc(4096,1);

for(i=m=0; i<n; i++) {

byte = a[i]/8; bit = a[i]%8;

if ((b [byte] & mask [bit] )=0)

{ m++; b[byte] | = mask[bit]; } }

free(b); return m; }

Программа 4_09a.pas

program dif;

const

a0:array [0..4] of integer=(0,0,0,0, 0)

al:array [0..4] of integer=(l,1,1,1,1)

a2:array [0..4] of integer=(0,1,1,1,1)

a3:array [0..4] of integer=(0,0,1,1, 2)

a4:array [0..4] of integer=(0,1,2,3,4)

a5:array [0..4] of integer=(1,2, 3, 4, 5)

procedure sort(var a:array of integer);

begin end;

function difference(a:array of integer):integer;

var i,m: integer;

begin

sort(a);

m:=l;

for i:=0 to High(a)-1 do

if a[i] <> a[i+l] then inc(m);

difference:=m;

end;

begin

write('Количество разных чисел в этом массиве равно ');

write(difference(a5));

readln; end.

Программа 4_09b.pas

program difl; const

a0:array [0..4J of integer=(0,0,0,0,0)

a1:array [0..4] of integer= (1,1,1,1,1)

a2:array [0..4] of integer=(0,1,1,1,1)

a3:array [0..4] of integer=(0,0,1,1,2)

a4:array [0..4] of integer=(0,1,2,3,4)

a5:array [0..4] of integer=(1,2,3,4,5)

function difference(a:array of integer):integer;

var

i,j,k0,m,n:integer;

begin

k0:=0; n:=High(a);

for i:=0 to n do

if a[i]=0 then begin k0:=l;

break;

end;

for i:=0 to n-1 do begin

if a[i]=0 then continue; for j:=i+l to n do

if a[i]=a[j] then begin a[i]:=0;

break; end; end ;

m:=0; for i:=0 to n do

if a[i]<>0 then inc(m);

difference:= m+k0;

end;

begin

write(' Количество разных чисел в этом массиве равно ');

write(difference(a5)};

readln;

end.

Задание 4.10. Перемешивание "колоды карт"

Практически все карточные игры нуждаются в процедуре тасования колоды карт.

Совет 1 (общий)

Для кодировки колоды карт в памяти ЭВМ можно предложить, как минимум, два варианта. Например, можно связать с каждой картой числовой номер из диапазона [0,35] (или [0,51]). Предварительно надо договориться о порядке следования мастей (например, пики, трефы, бубны, черви) и карт внутри каждой масти (например, по силе карты: 6, 7, 8, 9, 10, валет, дама, король, туз). Вместо числового массива можно использовать строковый массив, в котором каждая карта представлена двух-, трехсимвольным обозначением (например, "6Т" — шестерка треф, "104" — десятка червей, "ТП" — туз пик).

Совет 2 (общий)

Одна из наиболее простых идей перемешивания элементов массива заключается в использовании датчика случайных чисел. .По двум очередным случайным числам (i, j) i-й и j-й элементы массива меняются местами. Если эту процедуру повторять достаточно долго, например 10 000 раз, то "колода карт" окажется хорошо перетасованной.

Совет 3 (общий)

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

Совет 4 (общий)

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

Программа 4_10.bas

DECLARE SUB MIXER(В() AS INTEGER)

DEFINT A-Z

DIM A(36)

CLS

PRINT "Упорядоченная колода:"

FOR K=0 TO 35: A(K)=K: PRINT USING "####";A(K); : NEXT К

FOR J=0 TO 4

MIXER A()

PRINT "Перетасованная колода:"

FOR K=0 TO 35: PRINT USING "####";A(K); : NEXT К NEXT J END

SUB MIXER(B() AS INTEGER) DEFINT A-Z

RANDOMIZE INT(32767*RND)

FOR J=0 TO 10000

I=INT(35*RND+.5)

TMP=B(0)

B(0)=B(I)

B(I)=TMP

NEXT J

END SUB

Программа 4_10.с

#include <stdlib.h>

#include <conio.h>

void mixer(char *b);

main()

{

char j,k, a[36];

clrscr();

printf("\n Упорядоченная колода:\n");

for (k=0; k<36; k++) {

a[k]=k;

printf("%4d",a[k]); }

for(j=0; j<5; j++) {

mixer(a);

printf("\n Перетасованная колода:\n");

for(k=0; k<36; k++)

printf("%4d",a[k]);

begin clrscr;

writeln('Упорядоченная колода:') ;

for k:=0 to 35 do begin

a[k]:=k; write(a[k]:4);

end;

writeln;

for j:=0 to 4 do begin

mixer(a);

writeln('Перетасованная колода:');

for k:=0 to 35 do

write(a[k]:4);

writeln;

end;

readln;

end.

Задание 4.11. Игра в НИМ

Правила игры:

• в начале игры в каждой из п кучек находится отличное от 0 количество каких-то предметов (например, спичек);
  
• два игрока ходят по очереди. За один ход разрешается взять любое, отличное от 0, количество предметов из любой кучки;
  
• выигрывает тот, кто заберет содержимое последней оставшейся кучки.
  

Совет 1 (общий)

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

Совет 2 (общий)

Программу игры целесообразно разбить на четыре процедуры:

• start, осуществляющую выбор количества кучек и начальный расклад;
  
• user, обеспечивающую диалоговое взаимодействие с пользователем и ввод его хода;
  
• computer, реализующую ход программы (для подсчета поразрядной суммы использовать операцию хог);
  
• print_xod, выводящую текущее состояние предметов в кучках.
  

Совет 3 (общий)

В игровых программах очень важно оформление, но мы ограничимся самыми скромными средствами протоколирования игры. Количество кучек будем выбирать случайным образом в диапазоне от 3 до 5, число предметов в каждой кучке тоже ограничим интервалом [1,12]. Каждый ход будем фиксировать в виде строки красного (после хода компьютера) или зеленого (после хода игрока) цвета, отражающей текущее содержимое каждой кучки.

Программа 4_11.bas

DECLARE SUB USER()

DECLARE SUB START{)

DECLARE SUB COMPUTER()

DECLARE SUB PRINTXOD(col%,msg$)

DEFINT A-Z

DIM SHARED N

DIM SHARED В AS INTEGER,S AS INTEGER,M AS INTEGER,Q AS INTEGER

N=5: Q=12

DIM SHARED A(N) AS INTEGER,I AS INTEGER,J AS INTEGER,К AS INTEGER

M=l

START m1:

USER

COMPUTER

GOTO ml END

SUB COMPUTER S=0

FOR I=0 TO K-1: S=S XOR A(I): NEXT I

IF s=o THEN

J=0: S=A(0)

FOR I=1 TO K-1

IF S<A(I) THEN S=A(I): J=I

B=l

NEXT I ELSE

FOR J=0 TO K-1

B=A(J)-(A(J) XOR S)

IF B>=0 THEN EXIT FOR NEXT J END IF

A(J)=A(J)-B

PRINTXOD 4, "Победил компьютер"

END SUB

SUB PRINTXOD(col%,msg$) COLOR col%, 0 FOR I=0 TO K-1

LOCATE M+l,3*I+1: PRINT USING "###";A(I)

NEXT I

M=M+1: IF M>23 THEN M=2: CLS: PRINTXOD col%, msg$'

S=0

FOR J=0 TO K-l: S=S+A(J): NEXT J

IF S<>0 THEN EXIT SUB LOCATE M,2: PRINT msg$ SLEEP STOP

END SUB

SUB START

CLS : RANDOMIZE (VAL(RIGHTS(TIME$, 2)))

K=INT(RND*(N-3))+3: ' число кучек

FOR I=0 TO K-l

A(I)=INT(RND*Q)+1

NEXT I

LOCATE 1,2 : PRINT "Начало игры"

PRINTXOD 4,"" END SUB

SUB USER COLOR 2,0

LOCATE M, 20

PRINT "Ваш ход (кучка - сколько берем):"

М2:

LOCATE M, 33: PRINT ""

LOCATE M,33: INPUT J

IF (J<1) OR (J>K) OR (A(J-1)=0) THEN GOTO M2

m3:

LOCATE M, 35: PRINT "-"

LOCATE M, 37: INPUT В

IF (B<1) OR (B>A(J-1J) THEN GOTO m3

A(J-1)=A(J-1)-B SLEEP

PRINTXOD 2, "Вы победили"

END SUB

Программа 4_11.c

#include <stdio.h>

#include <stdlib.h>

#include <conio.h>

void print_xod(int color,char *msg);

void start(void);

void user(void);

void computer(void);

#define N 5

#define Q 12

int i,j,k,b,s,m=l;

int a[N];

main() {

start(); ml:

user () ;

computer() ;

goto ml; }

void start(void) {

clrscr();

randomize();

k=random(N-3)+3; /* число кучек */

for(i=0; i<k; i++)

a[i]=random(Q)+1;

print_xod(RED,"Начало игры"); }

void user(void) {

textcolor(GREEN);

gotoxy(20,m-l); cprintf("Ваш ход (кучка - сколько берем):");

m2:

gotoxy(33,m);

cprintf(" ") ;

gotoxy(33,m);

scanf("%d",&j);

if((j<l) || (j>k) || (a[j-l]=0)) goto ra2;

m3:

gotoxy(35,m); cprintf("- ") ;

gotoxy(37,m); scanf("%d",&b);

if((b<l) || (b>a[j-l])) goto m3;

a[j-l]-=b;

print_xod(GREEN,"Вы победили");

return; }

void computer(void) {

for(s=0, i=0; i<k; i++)

s ^= a[i];

if(s==0) {

for(i=l,j=0,s=a[0]; i<k; i++)

if(s<a[i]) {s=a[i]; j=i;} b=l; }

else

for(j=0; j<k; j++)

(b=a[j]-(a[j]"s);

if(b>=0) break;}

a[j]-=b;

print_xod(RED,"Победил компьютер");

return; }

void print_xod(int color,char *msg) (

textcolor(color);

for(i=0; i<k; i++)

gotoxy(3*i+l,m) ;

cprintf("%3d",a[i]);}

m++;

if(m>23)

{

m=2;

clrscr();

print_xod( color, msg) ;

}

for(j=0,s=0; j<k; j++)

s+=a[j];

if(s!=0) return;

gotoxy(l,m);

cprintf("%s",msg);

getch();

exit(0); }

Программа 4_11.pas

program nim; uses Crt; const

n=5; q=12; var

i,j,k,b,s,m:integer; a:array [l..n] of byte; label ml;

procedure print_xod(color:integer);

begin textcolor(color);

for i:=l to k do begin

gotoxy(3*i,m);

write(a[i]:2);

end;

m:=m+l;

if m > 23 then begin clrscr;

m:= 2;

print_xod(color);

end;

end;

procedure start;

begin

clrscr; randomize;

k:=random(n-3)+3; {число кучек}

m:=1;

if m>23 then begin clrscr;

m:=2;

print_xod(color);

end;

for i:=l to k do

a[i]:=random(q)+1;

print_xod(RED);

end;

procedure user;

label m2,m3;

begin

textcolor (GREEN) ;

gotoxy(20,m-1);

write('Ваш ход (кучка - сколько берем):');

m2:

gotoxy(33,m); write(' ');

gotoxy(33,m) ; read(j);

if(j<l) or (j>k) or (a[j]=0) then goto m2;

m3:

gotoxy(35,m);

write('- ');

gotoxy(37,m);

read(b);

if(b<l) or (b>a[j]) then goto m3;

a[j]:=a[j]-b;

print_xod(GREEN);

end;

procedure computer;

begin s:=0;

for i:=l to k do s:=s xor a[i];

if s=0 then begin s:=a[l];

j:=l;

for i:=2 to k do

if s<a[i] then begin

s:=a[i];

j:=i;

end;

b:=l;

end

else

for j:=l to k do begin b:=a[j]-(a[j] xor s) ;

if b>=0 then break; end;

a[j]:=a[j]-b;

print_xod(RED);

end;

begin

start;

ml : user;

s:=0;

for j:=l to k do s:=s+a[j];

if s=0 then begin

gotoxy(1,m);

write('Вы победили');

readln; readln;

exit; end;

computer; s:=0;

for j:=l to k do s:=s+a[j];

if s<>0 then goto ml;

gotoxy(l,m);

write('Победил компьютер');

readln;

readln;

end.

Задание 4.12. Игра "крестики-нолики"

Составить программу для игры в крестики-нолики на поле размером 3x3. Правила игры: играют двое, делая последовательные ходы в клетках игрового поля. Первый игрок ставит крестики, второй — нолики. Выигрывает тот, кому первому удастся разместить три своих символа на одной из восьми игровых линий (три горизонтали, три вертикали, две диагонали). Если на поле после девятого хода выигрышная ситуация не выстроена, то считается, что игра закончилась вничью. Многими докомпьютерными поколениями подтверждено, что при "правильном" поведении обоих игроков, каждому из них обеспечена, как минимум, ничья. И только при явной ошибке партнера создается выигрышная ситуация для его оппонента.

Беспроигрышная тактика для первого игрока заключается в соблюдении трех следующих правил:

• первым ходом захватить центр, т. к. центральная клетка контролирует максимальное число линий (4 из 8);
  
• вторым ходом поставить крестик в один из углов, расположенных на вертикальной или горизонтальной линии, занятой первым ходом противника (этот ход контролирует 3 линии и создает возможность выигрыша по диагонали);
  
• третий и дальнейшие ходы делаются по следующей схеме:
  

  a) если обнаружена линия, на которой расположены два крестика и есть свободное поле (выигрышная ситуация), заполните его;
  

  b) если ситуация а) не обнаружена, но имеет место выигрышная позиция для противника, воспрепятствуйте этому;
  

  c) если не обнаружена ни ситуация а), ни ситуация Ь), то поставьте крестик на любое свободное поле.
  

Для второго игрока беспроигрышная тактика заключается в соблюдении следующих правил:

• если центр не был занят первым ходом, то займите его;
  
• если центр занят, то нужно поставить нолик в любую из четырех угловых клеток (другой ход приведет к проигрышу);
  
• второй и последующие ходы выполняются в точном соответствии с приведенной ранее схемой:
  

  a) если обнаружена линия, ведущая к победе, сделайте решающий ход;
  

  b) если своего выигрышного хода нет, воспрепятствуйте выигрышу первого игрока;
  

  c) если не обнаружена ни ситуация а), ни ситуация b), то ставьте нолик на любое свободное поле.
  

Совет 1 (общий)

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

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

Нумерация позиций игрового поля, привязка к экрану и хранение информации о ходах. Пронумеруем клетки рабочего поля слева направо и сверху вниз от 1 до 9 и сопоставим содержимое центра каждой клетки с элементом целочисленного массива а:

• a[i] = 0, если клетка свободна;
  
• a[i] = 2, если клетка занята "крестиком";
  
• а [i] =-2, если клетка занята "ноликом".
  

Центры клеток в относительных номерах столбцов (х) и строк (у) имеют следующие координаты:

• клетка 1 (х=3, у=2) клетка 4 (х=3, у=4) клетка 7 (х=3, у=6)
  
• клетка 2 (х=7, у=2) клетка 5 (х=7, у=4) клетка 8 (х=7, у=6)
  
• клетка 3 (х=11 ,у=2) клетка 6 (х=11, у=4) клетка 7 (х=11, у=6)
  

В программе массив роз заполнен элементами, соответствующими экранным координатам позиций игрового поля.

Нумерация игровых линий.

Пронумеруем линии числами от 1 до 8 следующим образом:

• линия 1 (верхняя горизонталь) проходит через клетки (1,2,3);
  
• линия 2 (средняя горизонталь) проходит через клетки (4,5,6);
  
• линия 3 (нижняя горизонталь) проходит через клетки (7,8,9);
  
• линия 4 (левая вертикаль) проходит через клетки (1,4,7);
  
• линия 5 (средняя вертикаль) проходит через клетки (2,5,8);
  
• линия 6 (правая вертикаль) проходит через клетки (3,6,9);
  
• линия 7 (1-я диагональ) проходит через клетки (1,5,9);
  
• линия 8 (2-я диагональ) проходит через клетки (3,5,7).
  

Обратите внимание на массив lines, каждая тройка элементов которого соответствует одной из игровых линий.

Отображение игрового поля. Воспроизведение контуров игрового поля осуществляется выводом семи строковых констант, состоящих из нужной цепочки символов псевдографики. Для отображения сделанных ходов организуем цикл перебора элементов массива а и выводим в центрах каждой клетки символ, соответствующий значению элемента a[j]. В программе для этой цели использована процедура show(j, k), которая совмещает описанные выше действия с предварительной засылкой числа k в элемент а [ j ] (параметр k может принимать значения +2 или -2, в зависимости от того, кем был сделан текущий ход). После отображения игрового поля курсор переводится в центр, т. к. из него можно добраться до любой игровой клетки самым быстрым способом.

Ввод хода игрока. Для индикации хода человека используется процедура input (в программе на QBasic—USER, т. к. слово INPUT является служебным). Она предоставляет возможность перемещать курсор по центральным позициям игрового поля с помощью стрелок на клавиатуре. В выбранной позиции человек должен нажать клавишу <Enter>. Перемещение за пределы игрового поля пресекается соответствующими проверками. Нажатие непредусмотренных клавиш игнорируется с выдачей звукового сигнала (вывод символа beep с кодом 7).

Выполнение первого хода программы (в приводимых ниже программах первый ход делает компьютер, реализация второго варианта вносит очень небольшие изменения в текст головной программы). Реализуется непосредственным обращением к процедуре show (5, 2).

Выполнение второго хода компьютера. На любой из возможных восьми ходов человека предусмотрен фиксированный ответ — если человек выбрал клетку с номером j (j = l, 2, 3, 4, б, 7, 8 или 9), то второй ход программы определяется значением элемента массива b [ j ].

Выполнение последующих ходов компьютера. Осуществляется процедурой step345, действия которой сводятся к следующим акциям:

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

Определение выигрышной ситуации. Организуем цикл перебора игровых линий с суммированием элементов a[j], соответствующих клеткам, через которые проходит линия. Если полученная сумма равна 4, то на данной линии находятся два крестика и имеется свободное поле. В него и надо поставить очередной крестик, чтобы победить. Этот анализ выполняется с помощью функции xod(k1 = 2, k2 = 2). Она пытается найти линию, в которой сумма элементов а [ j ] равна 2*k1, и, если таковая находится, заносит в "свободный" элемент линии число k2. Функция xod принимает значение "истина", если победный ход был сделан.

Определение угрожающей ситуации со стороны второго игрока. Организуем аналогичный цикл и, если получена сумма, равная -4, то найдена линия, в которой находится два нолика и имеется свободная позиция. В нее и нужно поставить очередной крестик, чтобы воспрепятствовать выигрышу соперника. Этот анализ тоже выполняет функция xod, но теперь ее аргументы k1 = -2 и k2 = 2. Если угрожающую линию удалось закрыть, то функция xod принимает значение "истина".

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

Определение результата игры. В случае обнаружения выигрышной позиции надо зафиксировать победный ход и сообщить о победе компьютера. Для обнаружения ничейной ситуации можно ограничиться подсчетом абсолютных значений элементов а [ j ]. После девятого хода, заполняющего рабочее поле, там находится пять величин, соответствующих ходам программы (+2), и четыре величины, фиксировавших ходы человека (-2). Так что общая сумма элементов (по модулю) будет равна 18. Конечно, о ничейном результате можно было бы догадаться и раньше, но такой анализ несколько утяжелил бы программу.

Совет 2 (QBasic)

Обратите внимание на оператор LOCATE. Во-первых, в нем, в отличие от процедуры gotoxy, координаты х и у переставлены местами (у — строка, х — столбец). Во-вторых, кроме местоположения курсора, здесь добавлен третий параметр, определяющий видимость курсора. Если этого не сделать, то игрок не будет видеть позицию, в которой он намеревается поставить нолик.

Совет 3 (Си, Паскаль)

Некоторая экономия в объеме программы отображения игрового поля достигнута за счет использования окна вывода (window). Задавая нужные значения констант (х0, у0), можно переместить игровое поле в другое место экрана.

Программа 4_12.bas

DECLARE SUB STEP345()

DECLARE SUB RESULT(s$)

DECLARE SUB CURIND(cur%,porog%,dcur%,dind%)

DECLARE SUB SHOW(k%,c%)

DECLARE SUB USER()

• линия 3 (нижняя горизонталь) проходит через клетки (7,8,9);
  
• линия 4 (левая вертикаль) проходит через клетки (1,4,7);
  
• линия 5 (средняя вертикаль) проходит через клетки (2,5,8);
  
• линия 6 (правая вертикаль) проходит через клетки (3,6,9);
  
• линия 7 (1-я диагональ) проходит через клетки (1,5,9);
  
• линия 8 (2-я диагональ) проходит через клетки (3,5,7).
  

Обратите внимание на массив lines, каждая тройка элементов которого соответствует одной из игровых линий.

Отображение игрового поля. Воспроизведение контуров игрового поля осуществляется выводом семи строковых констант, состоящих из нужной цепочки символов псевдографики. Для отображения сделанных ходов организуем цикл перебора элементов массива а и выводим в центрах каждой клетки символ, соответствующий значению элемента a[j]. В программе для этой цели использована процедура show(j, k), которая совмещает описанные выше действия с предварительной засылкой числа k в элемент а [ j ] (параметр k может принимать значения +2 или -2, в зависимости от того, кем был сделан текущий ход). После отображения игрового поля курсор переводится в центр, т. к. из него можно добраться до любой игровой клетки самым быстрым способом.

Ввод хода игрока. Для индикации хода человека используется процедура input (в программе на QBasic — USER, т. к. слово INPUT является служебным). Она предоставляет возможность перемещать курсор по центральным позициям игрового поля с помощью стрелок на клавиатуре. В выбранной позиции человек должен нажать клавишу <Enter>. Перемещение за пределы игрового поля пресекается соответствующими проверками. Нажатие непредусмотренных клавиш игнорируется с выдачей звукового сигнала (вывод символа beep с кодом 7).

Выполнение первого хода программы (в приводимых ниже программах первый ход делает компьютер, реализация второго варианта вносит очень небольшие изменения в текст головной программы). Реализуется непосредственным обращением к процедуре show(5, 2).

Выполнение второго хода компьютера. На любой из возможных восьми ходов человека предусмотрен фиксированный ответ — если человек выбрал клетку с номером j (j =l, 2, 3, 4, б, 7, 8 или 9), то второй ход программы определяется значением элемента массива b [ j ].

Выполнение последующих ходов компьютера. Осуществляется процедурой step345, действия которой сводятся к следующим акциям:

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

Определение выигрышной ситуации. Организуем цикл перебора игровых линий с суммированием элементов a[j], соответствующих клеткам, через которые проходит линия. Если полученная сумма равна 4, то на данной линии находятся два крестика и имеется свободное поле. В него и надо поставить очередной крестик, чтобы победить. Этот анализ выполняется с помощью функции xod(k1 = 2, k2 = 2). Она пытается найти линию, в которой сумма элементов а [ j ] равна 2*k1, и, если таковая находится, заносит в "свободный" элемент линии число k2. Функция xod принимает значение "истина", если победный ход был сделан.

Определение угрожающей ситуации со стороны второго игрока. Организуем аналогичный цикл и, если получена сумма, равная -4, то найдена линия, в которой находится два нолика и имеется свободная позиция. В нее и нужно поставить очередной крестик, чтобы воспрепятствовать выигрышу соперника. Этот анализ тоже выполняет функция xod, но теперь ее аргументы kl = -2 и k2 = 2. Если угрожающую линию удалось закрыть, то функция xod принимает значение "истина".

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

Определение результата игры. В случае обнаружения выигрышной позиции надо зафиксировать победный ход и сообщить о победе компьютера. Для обнаружения ничейной ситуации можно ограничиться подсчетом абсолютных значений элементов а [ j ]. После девятого хода, заполняющего рабочее поле, там находится пять величин, соответствующих ходам программы (+2), и четыре величины, фиксировавших ходы человека (-2). Так что общая сумма элементов (по модулю) будет равна 18. Конечно, о ничейном результате можно было бы догадаться и.раньше, но такой анализ несколько утяжелил бы программу.

Совет 2 (QBasic)

Обратите внимание на оператор LOCATE. Во-первых, в нем, в отличие от процедуры gotoxy, координаты х и у переставлены местами (у — строка, х — столбец). Во-вторых, кроме местоположения курсора, здесь добавлен третий параметр, определяющий видимость курсора. Если этого не сделать, то игрок не будет видеть позицию, в которой он намеревается поставить нолик.

Совет 3 (Си, Паскаль)

Некоторая экономия в объеме программы отображения игрового поля достигнута за счет использования окна вывода (window). Задавая нужные значения констант (хО, уО), можно переместить игровое поле в другое место экрана.

Программа 4_12.bas

DECLARE SUB STEP3450

DECLARE SUB RESULT(s$)

DECLARE SUB CURIND(cur%,porog%,dcur%,dind%)

DECLARE SUB SHOW(k%,c%)

DECLARE SUB USER()

DECLARE FUNCTION XOD!(k%,kl%)

DEFINT A-Z

DIM SHARED POS1(1 TO 18) AS INTEGER,lines(0 TO 23) AS INTEGER

DIM SHARED A(l TO 9) AS INTEGER,b(l TO 9) AS INTEGER

DIM SHARED x0 AS INTEGER,у0 AS INTEGER

DIM SHARED Ind AS INTEGER,CurX AS INTEGER,CurY AS INTEGER

FOR k=l TO 9: A(k)=0: NEXT k

DATA 3,1,1,1,5,3,1,7,3

FOR k=l TO 9: READ b(k): NEXT k x0=l: y0=l

DATA 3,2, 7, 2, 11, 2, 3,4,

7, 4, 11, 4,3, 6, 7, 6, 11, 6

FOR k=l TO 18: READ POSl(k): NEXT k

DATA 1,2,3,4,5,6,7,8,9,1,4,7,

2,5,8,3,6,9,1,5,9,3,5,7

FOR k=0 TO 23: READ lines(k): NEXT k

CLS

SHOW 5,2 ' Первый ход программы

USER ' Ввод 1-го хода игрока

FOR J=l TO 9 ' Второй ход программы

IF A(J)=-2 THEN SHOW b(J),2: EXIT FOR NEXT J

m2: USER ' Ввод последующих ходов игрока

STEP345 ' Последующие ходы программы

GOTO m2 END

DEFSNG A-Z

SUB CURIND(cur%,porog%,dcur%,dind%)

IF curoporog THEN cur=cur+dcur: Ind=Ind+dind END SUB

DEFSNG A-Z SUB RESULT(s$)

LOCATE 1,40: PRINT s$: END END SUB

DEFINT A-Z

SUB SHOW(k%,C%) DEFINT A-Z CLS

LOCATE x0,y0: PRINT "+-------------------+"

LOCATE x0+l,y0: PRINT "| | | |"

LOCATE x0+2, y0: PRINT " |-----|-----|-----| "

LOCATE x0+3,y0: PRINT "| | | |"

LOCATE x0+4,y0: PRINT "|-----|-----|-----|"

LOCATE x0+5,y0: PRINT "| | | |"

LOCATE x0+6,y0: PRINT "+-----+-----+-----+"

A(k%)=c% FOR J=l TO 9

LOCATE y0-l+POSl(J*2),x0-1+POSl(J*2-l)

IF A(J)=2 THEN PRINT "X"

IF A(J)=-2 THEN PRINT "0" NEXT J

CurX=xO+6: CurY=y0+3: Ind=5 LOCATE CurY,CurX,l END SUB

SUB STEPS45 DEFINT A-Z

IF XOD(2,2)=1 THEN RESULT "Победа компьютера": END

IF XOD(-2,2)=1 THEN EXIT SUB

FOR J=l TO 9

IF A(J)=0 THEN SHOW J,2: EXIT FOR

NEXT J END SUB

DEFSNG A-Z

SUB USER

DEFINT A-Z

Left=75: Right=77: Up=72: Down=80: Enter=13 k=0:

FOR J=l TO 9: k=k+ABS(A(J)): NEXT J IF k=18 THEN RESULT "Боевая ничья": END

m: ch$=INKEY$:

IF LEN(ch$)=0 THEN GOTO m

SELECT CASE ASC(RIGHTS(ch$,1))

CASE Left: CURIND CurX,3,-4,-l

CASE Right: CURIND CurX,ll,4/l

CASE Up: CURIND CurY,2,-2,-3

CASE Down: CURIND CurY,6,2,3

CASE Enter:

IF A(Ind)=0 THEN SHOW Ind,-2:

EXIT SUB

CASE ELSE: BEEP END SELECT

LOCATE y0-l+CurY,x0-l+CurX,l USER END SUB

DEFINT A-Z FUNCTION XOD(k%,kl%)

DIM J AS INTEGER,m AS INTEGER,p AS INTEGER XOD=0

FOR J=0 TO 7 m=J*3

IF A(lines(m))+A(lines(m+1))+A(lines(m+2))=2*k% THEN XOD=1

FOR p=m TO m+2

IF A(lines(p))=0 THEN SHOW lines(p),kl% EXIT FUNCTION END IF NEXT p

END IF NEXT J END FUNCTION

Программа 4_12.с

#include <stdio.h>

#include <conio.h>

void input(void);

void cur_ind(int *cur,int porog,int dcur,int dind);

void step345(void);

int xod(int k, int kl);

void showfint k, int c);

void result(char *s);

int a[9]={0,0,0,0,0,0,0,0,0}, b[9]={3,l,l,l,5,3,l,7,3},

х0=1, у0=1, j, CurX, CurY, Ind; main()

{

clrscr();

window(x0,y0,x0+13,y0+7);

show(5,2); /* Первый ход программы */

input(); /* Ввод 1-го хода игрока */

for(j=0; j<9; j++) /* Второй ход программы */

if (a[j]==-2) { show(b[j],2); break; }

m2:

input(); . /* Ввод последующих ходов игрока */

step345(); /* Последующие ходы программы */

goto m2;

}

/*--------------------------------*/

void result(char *s) {

window(40,l,60,2);

puts(s);

getch () ;

exit(0);

}

/*-------------------------------*/

void show(int k,int c) {

char pos[18]=(3,2,7,2,11,2,3,4,7,4,11,4,3,6,7,6,11,6};

char j;

clrscr ();

printf("+-----------+\n");

printf("| | | |\n");

printf ( "|----|----|----| \n") ;

printf("| | | |\n");

printf (" |----|----|----| \n"} ;

printf("| | | |\n");

printf ("+----------------+") ;

a[k-l]=c;

for(j=0; j<9; j++) {

gotoxy(x0-l+pos[j*2],y0-l+pos[j*2+l]);

if(a[j]==+2) printf("X");

if(a[j]==-2) printf("0"); }

CurX=x0+6; CurY=y0+3; Ind=5; gotoxy(CurX,CurY);

}

/*-------------------------------*/

int xod(int k, int k1) {

char line[24]={1,2,3,4,5,6,7,8,9,1,

4,7,2,5,8,3,6,9,1,5,9,3,5,7},

j,m,p;

for(j=0; j<8; j++)

{

m=j*3;

if(a[line[m]-1)+a[line[m+1]-1]+a[line[m+2]-1]==2*k)

{

printf ("\nm=%d",m) ; for(p=m; p<m+3; p++)

if(a[line[p]-l]==0) {

show(line[p],kl); return 1; } } } return 0;

}

/*-------------------------------------* /

void step345(void)

{

if(xod( 2,2)) result("Победа компьютера");

if(xod(-2,2)) return;

for(j=0; j<9; j++)

if(a[j]==0) {

show(j+l,2); break;

} }

/*----------------------------*/

void cur_ind(int *cur, int porog, int dcur, int dind) {

if( *cur != porog) {

*cur += dcur;

Ind += dind; }

}

/*----------------------------*/

void input(void) {

int ch, j, k;

for(k=0, j=0; j<9; j++) k+=abs(a[j]);

if(k==18) result("Боевая ничья");

ch=getch(); if(ch==0) ch=getch();

switch (ch)

{

case 75: cur_ind(&CurX, 3,-4,-l);break; /*Left*/

case 77: cur_ind(&CurX,11, 4, 1); break; /*Right*/

case 72: cur_ind(&CurY, 2,-2,-3); break; /*Up*/

case 80: cur_ind(&CurY, 6, 2, 3); break; /*Down*/ case 13:

printf("\nInd=%d",Ind); /*Enter*/

if(a[Ind-l]==0)

{ show(Ind,-2); return;}

else

printf("%c",0x7);

break;

default: printf("%c",0x7); }

gotoxy(x0-l+CurX,y0-l+CurY);

input(); }

Программа 4_12.pas

program krestiki;

uses Crt;

label m2;

const

a-.array [1..9] of integer = (0,0,0,0,0,0,0,0,0);

b:array [1..9] of byte = (3,1,1,1,5,3,1,7,3);

x0=5; y0=5;

var

j, CurX, CurY, Ind : word; procedure result(s:string);

begin

window(40,1,60,2);

write(s);

readln; halt; end;

procedure show(k,с:integer) ;

const

pos:array [1..18] of byte = (3,2,7,2,11,2,3,4,7,4,11,4,3,6,7,6,11,6);

var

j:byte;

x,у:word;

begin

clrscr;

writeln (' +----+----+----+')

writeln('| | | |')

writeln (' |----|----|----| ')

writeln('| | | |')

writeln(' |----|-----|-----|')

writeln('| | | |')

write (' +----+----+----+')

a[k]:=c;

for j:=1 to 9 do begin

x:=pos[(j-l)*2+l]; y:=pos[(j-1)*2+2];

gotoxy(x,y);

if a[j]=+2 then write('X');

if a[j]=-2 then write('0');

end;

CurX:=7; CurY:=4; Ind:=5;

gotoxy(CurX,CurY); end;

function xod(k,kl:integer):boolean;

const

line:array [0..23] of byte=

(1, 2, 3,4, 5, б, 7, 8, 9,1,4, 7, 2, 5, 8, 3,6, 9,1,5, 9, 3,5,7) ;

var

j,m,p:byte; begin

xod:=false; for j:=0 to 7 do begin m:=j*3;

if a[line[m]]+a[line[m+1]]+a[line[m+2]]=2*k then begin

xod:=true;

for p:=m to m+2 do

if a[line[p]]=0 then

begin

show(line[p],kl);

exit;

end;

end;

end;

end;

procedure step345; begin

if xod( 2,2) then result('Победа компьютера');

if xod(-2,2) then exit;

for j :=1 to 9 do if a[j]=0 then begin

show(j,2);

break;

end;

end;

procedure input; const

Left=#75;

Right=#77;

Up=#72;

Down=#80;

Enter=#13; var

ch:char;

j,k:byte;

procedure cur_ind(var cur:word;porog,dcur,dind:integer) ;

begin

if cur <> porog then begin

cur:=cur+dcur;

Ind:=Ind+dind; end;

end; begin

k:=0;

for j:=l to 9 do

k:=k+abs(a[j]);

if k=18 then result('Боевая ничья');

ch:=readkey;

if ch=#0 then ch:=readkey;

case ch of

Left: cur_ind(CurX, 3,-4,-l);

Right: cur_ind(CurX,11, 4, 1);

Up: cur_ind(CurY, 2,-2,-3);

Down: cur_ind(CurY, 6, 2, 3);

Enter: if a[Ind]=0 then begin

show(Ind,-2);

exit;

end

else write(tt7);

else write(#7); end;

gotoxy(CurX,Cury);

input; end; begin

clrscr;

window(x0,y0,x0+13,y0+7);

show(5,2);

{ Первый ход программы }

input; { Ввод 1-го хода игрока }

for j:=1 to 9 do { Второй ход программы }

if a[j]=-2 then

begin show(b[j],2);

break;

end;

m2: input; { Ввод последующих ходов игрока }

step345; { Последующие ходы программы }

goto m2;

end.

Задание 4.13. Слияние массивов

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

Совет 1 (общий)

Если в объединяемых массивах находится соответственно тип элементов, то процедура слияния потребует m+n шагов. На первом шаге сравниваются первые элементы сливаемых массивов и меньший из них переписывается в результирующий массив. Перед очередным сравнением необходимо переместить

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

Программа 4_13.bas

DECLARE SUB MERGE (A%(),NA%,B%(),NB%,C%())

DEFINT A-Z

CLS

NA=3:

DIM A(NA)

DATA 0,2,4

FOR K=0 TO NA-1: READ A(K): PRINT A(K); : NEXT K: PRINT

NB=4

DIM B(NB)

DATA 1,3,5,7

FOR K=0 TO NB-1: READ B(K): PRINT B(K); : NEXT K: PRINT

DIM C(NA+NB)

MERGE A(),NA,B(),NB,C()

FOR K=0 TO NA+NB-1: PRINT C(K); : NEXT К

END

SUB MERGE(A(),NA,В(),NB,С())

JA=0: JB=0

FOR JC=0 TO NA+NB-1

IF JA=NA THEN GOTO MB

IF JB=NB THEN GOTO MA

IF A(JA)<B(JB) THEN GOTO MA MB: C(JC)=B(JB): JB=JB+1: GOTO M1 MA: C(JC)=A(JA): JA=JA+1: Ml:

NEXT JC

END SUB

Программа 4_13.с

#include <stdio.h>

#include <conio.h>

void merge(int *a,int ka,int *b,int kb,int *c);

main() {

#define na 3

#define nb 4

int j,a[na]={0,2,4},b[nb]={l,3,5,7},c[na+nb]_;

clrscr();

for(j=0; j<na; j++)

printf("%4d",a[j]);

printf("\n");

for(j=0; j<nb; j++)

printf("%4d",b[j]);

printf("\n");

merge(a,na,b,nb,c);

for(j=0; j<na+nb; j++)

printf("%4d",с[j]);

getch(); }

void merge(int *a,int ka,int *b,int kb,int *c) {

int ja=0,jb=0,jc;

for(jc=0; jc<ka+kb; jc++) {

if (ja==ka) goto mb;

if (jb==kb) goto ma;

if (a[ja]<b[jb])goto ma;

mb:

c[jc]=b[jb];

jb++;

continue;

ma:

c[jc]=a[ja];

ja++;

} }

Программа 4_13.pas

program merge2;

uses Crt;

const

na=3 ;

nb=2 ;

a:array [0..na] of integer = (0,2,4,6);

b:array [0..nb] of integer = (1,3,5);

var

c:array [0..na+nb+l] of integer;

j:integer;

procedure merge(a,b:array of integer;var c:array of integer);

var

ja,jb,jc,na,nb,nc:integer;

label ma, mb;

begin

na:=High(a); ja:=0;

nb:=High(b);

jb:=0;

nc:=High(c);

if nc < na+nb+1 then begin

writeln('Массив с слишком мал');

exit;

end;

for jc:=0 to na+nb+1 do begin

if ja > na then goto mb;

if jb > nb then goto ma;

if a[ja] < b[jb] then goto ma;

mb:

с[jc]:=b[jb]; inc(jb);

continue;

ma:

с[j с]:=a[j a];

inc(j a};

end;

end;

begin clrscr;

for j:=0 to na do

write(a[j]:4);

writeln;

for j:=0 to nb do

write(b[j]:4) ;

writeln; merge(a,b,c);

for j:=0 to na+nb+1 do

write(c[j]:4) ;

readln; end.