Question

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

Answer 1

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.

Примеры:
Исходный массив: 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

Answer 2

Конечно, вот пример программы на Pascal ABC, которая выполняет описанные вами действия:

pascalCopy code
program ArraySortAndSearch;

const
  SIZE = 10;

var
  arr: array[1..SIZE] of integer;
  i, j, temp, comparisons, swaps, searchValue: integer;
  found: boolean;

procedure SimpleSelectionSort(var arrayToSort: array of integer; size: integer; var comparisons, swaps: integer);
var
  i, j, minIndex, temp: integer;
begin
  for i := 0 to size - 2 do
  begin
    minIndex := i;
    for j := i + 1 to size - 1 do
    begin
      comparisons := comparisons + 1;
      if arrayToSort[j] < arrayToSort[minIndex] then
        minIndex := j;
    end;

    if minIndex <> i then
    begin
      temp := arrayToSort[i];
      arrayToSort[i] := arrayToSort[minIndex];
      arrayToSort[minIndex] := temp;
      swaps := swaps + 1;
    end;
  end;
end;

function BinarySearch(arrayToSearch: array of integer; size, value: integer; var comparisons: integer): boolean;
var
  left, right, mid: integer;
begin
  left := 0;
  right := size - 1;
  while left <= right do
  begin
    mid := (left + right) div 2;
    comparisons := comparisons + 1;
    if arrayToSearch[mid] = value then
      Exit(true)
    else if arrayToSearch[mid] < value then
      left := mid + 1
    else
      right := mid - 1;
  end;
  Exit(false);
end;

begin
  writeln('Введите ', SIZE, ' целых чисел для массива:');
  for i := 1 to SIZE do
    readln(arr[i]);

  comparisons := 0;
  swaps := 0;
  SimpleSelectionSort(arr, SIZE, comparisons, swaps);

  writeln('Массив после сортировки:');
  for i := 1 to SIZE do
    write(arr[i], ' ');
  writeln;
  writeln('Количество перестановок: ', swaps);
  writeln('Количество сравнений: ', comparisons);

  writeln('Введите целое значение для поиска:');
  readln(searchValue);

  comparisons := 0;
  found := BinarySearch(arr, SIZE, searchValue, comparisons);

  if found then
    writeln('Значение найдено в массиве.')
  else
    writeln('Значение не найдено в массиве.');
  
  readln; // Чтобы консоль не закрывалась сразу
end.

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