Составить процедуру инвертирования целочисленного массива,
Задание 4.03. Перестановка элементов одномерного массива в обратном порядке
Составить процедуру инвертирования целочисленного массива, которая меняет местами первый элемент с последним, второй — с предпоследним и т. д. Процедура должна обрабатывать массивы любой длины.
Совет 1 (общий)
Программа 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
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 (общий)
Конечно, можно принять предложенный алгоритм на веру и убедиться на нескольких примерах, что он работает правильно. Но это не может дать абсолютной уверенности в том, что также произойдет на любых сочетаниях исходных данных. Поэтому можно попытаться доказать правильность алгоритма, проследив за местоположением (индексом) каждого элемента после указанных перестановок.
Если элемент с исходным индексом 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 (общий)
Программа 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
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 (общий)
Совет 2 (QBasic)
Совет 3 (Си)
Совет 4 (Паскаль)
Программа 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 (общий)
Программа 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 (общий)
Совет 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 (общий)
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 (общий)
Совет 2 (общий)
Совет 3 (общий)
Совет 4 (Си)
Программа 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 (общий)
Совет 2 (общий)
Совет 3 (общий)
Совет 4 (общий)
Программа 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. Игра в НИМ
Правила игры:
Совет 1 (общий)
Совет 2 (общий)
Совет 3 (общий)
Программа 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. Правила игры: играют двое, делая последовательные ходы в клетках игрового поля. Первый игрок ставит крестики, второй — нолики. Выигрывает тот, кому первому удастся разместить три своих символа на одной из восьми игровых линий (три горизонтали, три вертикали, две диагонали). Если на поле после девятого хода выигрышная ситуация не выстроена, то считается, что игра закончилась вничью. Многими докомпьютерными поколениями подтверждено, что при "правильном" поведении обоих игроков, каждому из них обеспечена, как минимум, ничья. И только при явной ошибке партнера создается выигрышная ситуация для его оппонента.
Беспроигрышная тактика для первого игрока заключается в соблюдении трех следующих правил:
a) если обнаружена линия, на которой расположены два крестика и есть свободное поле (выигрышная ситуация), заполните его;
b) если ситуация а) не обнаружена, но имеет место выигрышная позиция для противника, воспрепятствуйте этому;
c) если не обнаружена ни ситуация а), ни ситуация Ь), то поставьте крестик на любое свободное поле.
Для второго игрока беспроигрышная тактика заключается в соблюдении следующих правил:
a) если обнаружена линия, ведущая к победе, сделайте решающий ход;
b) если своего выигрышного хода нет, воспрепятствуйте выигрышу первого игрока;
c) если не обнаружена ни ситуация а), ни ситуация b), то ставьте нолик на любое свободное поле.
Совет 1 (общий)
Выбор конфигурации рабочего поля. Не будем усложнять программу графическими процедурами, остановимся лишь на работе дисплея в текстовом режиме. Для того чтобы приблизить конфигурацию рабочего поля к квадрату, разумно выбрать соотношение сторон клетки 5 (по горизонтали) к 3 (по вертикали) и размещать символ в центральной позиции такого прямоугольника.
Нумерация позиций игрового поля, привязка к экрану и хранение информации о ходах. Пронумеруем клетки рабочего поля слева направо и сверху вниз от 1 до 9 и сопоставим содержимое центра каждой клетки с элементом целочисленного массива а:
Центры клеток в относительных номерах столбцов (х) и строк (у) имеют следующие координаты:
В программе массив роз заполнен элементами, соответствующими экранным координатам позиций игрового поля.
Нумерация игровых линий.
Пронумеруем линии числами от 1 до 8 следующим образом:
Обратите внимание на массив 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)
Совет 3 (Си, Паскаль)
Программа 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()
Обратите внимание на массив 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)
Совет 3 (Си, Паскаль)
Программа 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 (общий)
текущий указатель в массиве, из которого на предыдущем шаге был выбран минимальный элемент. Однако предварительно разумно проверить, не исчерпан ли уже один из массивов.
Программа 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.
