Сформировать массив в пределах крайних значений заданного массива, но из других чисел

Задача

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

Решение

Описание переменных: 

  • M, N - количество элементов первого и второго массивов;
  • A - заданный массив (первый);
  • arr - формируемый массив (второй);
  • qty - номер последнего полученного на данный момент элемента в формируемом массиве;
  • num - сгенерированное число;
  • i - счетчик;
  • flag - флаговая переменная.

Алгоритм решения задачи: 

Второй массив изначально пуст. Поэтому переменной qty присвоим 0. Перед тем как добавлять элемент в массив, будем увеличивать qty на 1. Генерацию чисел и добавление элементов следует продолжать пока qty меньше размерности формируемого массива (N).

Добавление сгенерированного числа в массив и увеличение qty на 1 будет происходить лишь тогда, когда число уникально, т.е. не встречается в первом массиве. Чтобы проверить это, надо сравнить сгенерированное число со всеми элементами заданного массива. Если произойдет совпадение, то присвоить флаговой переменной false (изначально ей присвоено true) и прервать цикл проверки. Если флаг остался в состоянии true, значит число уникально, и его можно добавлять в массив.

Генерируемые числа должны лежать в крайних пределах заданного массива. Поскольку этот массив упорядочен по возрастанию, то минимальный его элемент - первый, максимальный - последний (с индексом M). Чтобы сгенерировать число, лежащее между двумя заданными, надо 1) найди диапазон (количество возможных значений), 2) сгенерировать случайное число от 0 до границы этого диапазона, 3) увеличить полученное число на заданный минимум.

Например, в программе ниже минимум заданного массива равен 1, максимум равен 85. Значит, числа формируемого массива могут быть от 2 до 84 включительно. Сначала генерируется случайное число от 0 до 82 включительно. Далее к нему прибавляется единица, получаем диапазон от 1 до 83. После этого прибавляется минимум первого массива. Так если random() сгенерирует 0, то мы получим 2, если же random() сгенерирует свой максимум (82), то мы получим 84.

Программа на языке Паскаль:

const 
    M = 10;
    A: array[1..M] of byte = (1,5,9,16,22,44,48,52,70,85);
    N = 15;
var
    arr: array[1..N] of byte;
    i, qty, num: byte;
    flag: boolean;
begin
    randomize;
    qty := 0;
    while qty < N do begin
        num := random(A[M] - A[1] - 1) + 1 + A[1];
        flag := True;
        for i:=1 to M do
            if A[i] = num then begin
                flag := False;
                break;
            end;
        if flag = True then begin
            qty := qty + 1;
            arr[qty] := num;
        end;
    end;
 
    write('Исходный: ');
    for i:=1 to M do
        write(A[i],' ');
    writeln;
    write('Полученный: ');
    for i:=1 to N do
        write(arr[i],' ');
    writeln;
end.

Пример выполнения кода:

Исходный: 1 5 9 16 22 44 48 52 70 85 
Полученный: 66 65 18 2 40 31 63 20 68 66 20 25 23 49 4

Тема

Одномерные массивы

Уровень

Комбинированные задачи

Теги

Комментарии

program Сформировать_массив_в_пределах_крайних_значений_заданного_массива_но_из_других_чисел;
const
  n = 5;
type
  intmas = array [1..n] of integer;
var
a,b : intmas;
i, j: byte;
begin
  randomize;
  a[1] := random(5);
  write(a[1], ' ');
  for i:=2 to n do
    begin
      a[i] := a[i-1] + random(5);
      write(a[i], ' ');
    end;
 
  for i:=1 to n do 
    begin
    b[i] := random(a[1],a[n]);
                  j := 1;      
                  while j<=n do
                  if a[j]=b[i] then 
                                  begin
                                  b[i] := random(a[1],a[n]);
                                  j := 1;
                                  end
                                else
                                inc(j);
    end;
 
 writeln;
 for i:=1 to n do
      write(b[i], ' ');
 
end.  

Добавить комментарий