Const N = 10; Var A:array[1..N] of integer; i,j,M,B,C,p,s:integer; Begin Randomize; {Заполнение и вывод} Write('Исходный массив:'); For i:= 1 to N do Begin A[i]:=random(N); Write(' ',A[i]); End; WriteLn; {Сортировка} p:=0; For i:= 1 to N do Begin M:=i; For j:= i+1 to N do if A[j]<A[M] then M:=j; if M<>i then Begin B:=A[M]; A[M]:=A[i]; A[i]:=B; p:=p+1; {Вывод каждого шага сортировки} Write('Перестановка №',p,':'); For j:= 1 to N do Write(' ',A[j]); WriteLn; End; End; WriteLn; Write('Отсортированный массив:'); For i:= 1 to N do Write(' ',A[i]); {Бинарный поиск} WriteLn; Write('Введите число: ');ReadLn(C); m:=N div 2; i:=1; j:=N; s:=0; While (A[m]<>C)and(i<=j) do Begin if C > A[m] then i:=m+1 else j:=m-1; s:=s+1; m:=(i+j) div 2; End; WriteLn; if A[m]=C then WriteLn('В массиве есть данное число') else WriteLn('В массиве нет данного числа'); WriteLn('Кол-во перестановок за сортировку: ',p); WriteLn('Кол-во сравнений за поиск: ',s); End.
#include "stdafx.h" #include "malloc.h" #include <iostream> using namespace std;
int _tmain(int argc, _TCHAR* argv[]) { // Вводим исходные данные. int m; int n; printf ("Введите количество столбцов? m = "); cin >> m; printf ("Введите количество строк? n = "); cin >> n;
// Инициализируем другие переменные. int xMin = 0, // левая граница спирали xMax = m, // правая граница спирали (не включая ее, поэтому ниже будет использоваться xMax - 1) yMin = 0, // верхняя граница спирали yMax = n, // нижняя граница спирали (не включая ее, поэтому ниже будет использоваться yMax - 1) i = 0, // текущее число x, y; // расходный материал.
// Бесконечный цикл, пока не заполним матрицу. while (1) { // Заполняем верхний ряд слева направо. for (x = xMin; x < xMax; x++) pMatrix[x + yMin * m] = i++; // Заполнили весь верхний ряд. Подвигаем вниз верхнюю границу. yMin ++; // Если верхняя граница совпала с нижней, то заканчиваем цикл. if (yMin == yMax) break;
// Заполняем правый ряд сверху вниз. for (y = yMin; y < yMax; y++) pMatrix[xMax - 1 + y * m] = i++; // Заполнили весь правый ряд. Подвигаем налево правую границу. xMax --; // Если правая граница совпала с левой, то заканчиваем цикл. if (xMax == xMin) break;
// Заполняем нижний ряд справа налево. for (x = xMax - 1; x >= xMin; x--) pMatrix[x + (yMax - 1) * m] = i++; // Заполнили весь нижний ряд. Подвигаем вверх нижнюю границу. yMax --; // Если верхняя граница совпала с нижней, то заканчиваем цикл. if (yMin == yMax) break;
// Заполняем левый ряд снизу вверх. for (y = yMax - 1; y >= yMin; y--) pMatrix[xMin + y * m] = i++; // Заполнили весь левый ряд. Подвигаем направо левую границу. xMin ++; // Если правая граница совпала с левой, то заканчиваем цикл. if (xMax == xMin) break; // если мы все еще здесь, значит идем на очередной виток спирали.. . }
// Есть предположение, что спираль заполнена. Напечатаем ее, посмотреть.. . for (y = 0; y < n; y++) { // Печатаем строку. for (x = 0; x < m; x++) printf ("i, ", pMatrix[x + y * m]); // Переходим на другую строку. printf ("\r\n"); }
// Освобождаем память и выходим. free (pMatrix); pMatrix = 0; }
N = 10;
Var
A:array[1..N] of integer;
i,j,M,B,C,p,s:integer;
Begin
Randomize;
{Заполнение и вывод}
Write('Исходный массив:');
For i:= 1 to N do
Begin
A[i]:=random(N);
Write(' ',A[i]);
End;
WriteLn;
{Сортировка}
p:=0;
For i:= 1 to N do
Begin
M:=i;
For j:= i+1 to N do
if A[j]<A[M] then M:=j;
if M<>i then
Begin
B:=A[M];
A[M]:=A[i];
A[i]:=B;
p:=p+1;
{Вывод каждого шага сортировки}
Write('Перестановка №',p,':');
For j:= 1 to N do
Write(' ',A[j]);
WriteLn;
End;
End;
WriteLn;
Write('Отсортированный массив:');
For i:= 1 to N do
Write(' ',A[i]);
{Бинарный поиск}
WriteLn;
Write('Введите число: ');ReadLn(C);
m:=N div 2;
i:=1;
j:=N;
s:=0;
While (A[m]<>C)and(i<=j) do
Begin
if C > A[m] then i:=m+1
else j:=m-1;
s:=s+1;
m:=(i+j) div 2;
End;
WriteLn;
if A[m]=C then WriteLn('В массиве есть данное число')
else WriteLn('В массиве нет данного числа');
WriteLn('Кол-во перестановок за сортировку: ',p);
WriteLn('Кол-во сравнений за поиск: ',s);
End.
Примеры:
Исходный массив: 0 4 5 4 1 2 6 7 0 7
Перестановка №1: 0 0 5 4 1 2 6 7 4 7
Перестановка №2: 0 0 1 4 5 2 6 7 4 7
Перестановка №3: 0 0 1 2 5 4 6 7 4 7
Перестановка №4: 0 0 1 2 4 5 6 7 4 7
Перестановка №5: 0 0 1 2 4 4 6 7 5 7
Перестановка №6: 0 0 1 2 4 4 5 7 6 7
Перестановка №7: 0 0 1 2 4 4 5 6 7 7
Отсортированный массив: 0 0 1 2 4 4 5 6 7 7
Введите число: 3
В массиве нет данного числа
Кол-во перестановок за сортировку: 7
Кол-во сравнений за поиск: 4
Исходный массив: 4 4 1 3 4 4 5 0 7 2
Перестановка №1: 0 4 1 3 4 4 5 4 7 2
Перестановка №2: 0 1 4 3 4 4 5 4 7 2
Перестановка №3: 0 1 2 3 4 4 5 4 7 4
Перестановка №4: 0 1 2 3 4 4 4 5 7 4
Перестановка №5: 0 1 2 3 4 4 4 4 7 5
Перестановка №6: 0 1 2 3 4 4 4 4 5 7
Отсортированный массив: 0 1 2 3 4 4 4 4 5 7
Введите число: 5
В массиве есть данное число
Кол-во перестановок за сортировку: 6
Кол-во сравнений за поиск: 2