Сортировка массива по возрастанию расстояния до ближайшего

@owlbear · Регистрация: 16.08.2020

Студворк — интернет-сервис помощи студентам

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

Подскажите, пожалуйста, как строить программу для такого типа задач? так и не получилось найти ничего похожего.
(Может за одно и для этого всего тоже что-нибудь подскажете: по возрастанию расстояния до ближайшего числа Фибоначчи; по возрастанию расстояния до ближайшего числа, являющегося степенью двойки)

ФедосеевПавел · 16.08.2020, 10:01

Раз в итоге требуется вывести:
- отсортированные подходящие числа,
- расстояния до ближайших простых чисел
- эти простые числа

И нет ограничений на память.

То я бы к тому массиву создал ещё два - массив с ближайшими простыми числами (числами Фибоначчи, степенями 2) и массив расстояний.

Потом сортировал бы массив расстояний, при этом во время обмена синхронно бы обменивал соответствующие элементы всех трёх массивов.

@Puporev · 16.08.2020, 10:10

Сообщение от ФедосеевПавел

То я бы к тому массиву создал ещё два

Или объявить тип запись с полями значение, простое число, расстояние. И создать массив записей, который сортировать по полю расстояние.

@Cyborg Drone · 17.08.2020, 03:21

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

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

Степени двойки и числа Фибоначчи.

Максимальное целое число, представимое типом integer, для Pascal ABC равно 2³¹-1=2147483647. И оно ближе всего к 2³¹=2147483648. Но это число уже не влезает в integer. Получается, что нужно либо ограничить диапазон чисел в массиве, либо использовать более ёмкий тип данных. Примерно то же самое и с числами Фибоначчи:
F(46)=1836311903, F(47)=2971215073. Конечно, 2147483647 ближе к F(46), но с F(47) тоже придётся сравнивать, поскольку гарантированно точное расстояние есть минимальное расстояние до одного из ближайших чисел Фибоначчи, а априори нам не известно, до какого именно числа Фибоначчи будет минимальное расстояние от 2147483647.

Можно использовать тип real.

Предвосхищая возражения, что будут какие-то там ошибки при использовании вещественных чисел. Так как любое число типа integer помещается в мантиссу типа real полностью, то числа типа integer в машинном формате будут представлены точно (без усечения или округления). Мало того, сравнение чисел integer, преобразованных в real, даёт верный результат.

Для степеней двойки:

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
type
  num = record
          n, d: integer;
          p: real
        end;
 
const
  m = 10;
  ma = 100; //максимум 2147483647;
 
var
  a: array[1..m] of num;
  q: num;
  i, j, k, t: integer;
  df: array[1..2] of integer;
  f: array[1..2] of real;
 
begin
  //формирование массива
  randomize;
  writeln('Исходный массив:');
  for i := 1 to m do
    begin
      a[i].n := 1 + random(ma);
      writeln(a[i].n:11)
    end;
  //предварительная сортировка массива по неубыванию
  for i := 1 to m - 1 do
    begin
      k := i;
      for j := i + 1 to m do if a[k].n > a[j].n then k := j;
      if k > i then
        begin
          t := a[i].n;
          a[i].n := a[k].n;
          a[k].n := t
        end
    end;
  //ищем расстояния и степени двойки, начинаем с нулевой и первой степени двойки
  f[1] := 1;
  f[2] := 2;
  for i := 1 to m do
    begin
      while a[i].n > f[2] do
        begin
          f[1] := f[2];
          f[2] := f[2] * 2
        end;
      for j := 1 to 2 do df[j] := abs(trunc(a[i].n - f[j]));
      if df[1] <= df[2] then k := 1 else k := 2;
      a[i].d := df[k];
      a[i].p := f[k]
    end;
  //сортировка по неубыванию расстояний
  for i := 1 to m - 1 do
    begin
      k := i;
      for j := i + 1 to m do if a[k].d > a[j].d then k := j;
      if k > i then
        begin
          q := a[i];
          a[i] := a[k];
          a[k] := q
        end
    end;
  //печатаем результат
  writeln('Отсортированный массив:');
  writeln('    Элемент Расстояние Степень двойки');
  for i := 1 to m do writeln(a[i].n:11, a[i].d:11, a[i].p:11:0)
end.

Для чисел Фибоначчи поменять строки:

Pascal
35
  //ищем расстояния и числа Фибоначчи, начинаем со второго и третьего чисел

Pascal
46
47
          f[2] := f[2] + f[1];
          f[1] := f[2] - f[1]

Pascal
68
  writeln('    Элемент Расстояние Число Фибоначчи');

Простые числа.

Для последовательности простых чисел всё не так просто. Если на интервале от 1 до 2147483647 степеней двойки требуется вычислить максимум 33, чисел Фибоначчи максимум 47, то простых чисел нужно вычислить более 100000000, и вычисление последовательности простых чисел гораздо сложнее и намного медленнее, чем последовательностей степеней двойки или чисел Фибоначчи. Радует только одно: 2147483647 является простым числом (если быть точным, это восьмое простое число Мерсенна), и костыль с числами типа real не нужен.

Для отбора кандидатов в последовательность простых чисел буду использовать решето, основанное на колесе простых чисел (wheel sieving) с количеством спиц 2*3*5=30, это позволяет исключить из рассмотрения примерно 73% чисел и не требует большого объёма памяти. Для проверки отобранных чисел на простоту буду использовать то же самое колесо.

Алгоритм взят отсюда: Алгоритм, который устанавливает – является ли число простым
Ссылка на Википедию: Wikipedia - Wheel factorization

Программу придётся существенно переработать. Изменения коснутся объявления переменных и вычисления следующего числа (это строки 40..44 в программе для степеней двойки).

Получилось так:

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
type
  num = record n, d, p: integer end;
 
const
  m = 10;
  ma = 100; //максимум 2147483647;
  delta: array [0..7] of integer = (4, 2, 4, 2, 4, 6, 2, 6);
 
var
  a: array[1..m] of num;
  q: num;
  i, j, k, t, df2, dk, sqrtf: integer;
  f, df: array[1..2] of integer;
 
begin
  //формирование массива
  randomize;
  writeln('Исходный массив:');
  for i := 1 to m do
    begin
      a[i].n := 1 + random(ma);
      writeln(a[i].n:11)
    end;
  //предварительная сортировка массива по неубыванию
  for i := 1 to m - 1 do
    begin
      k := i;
      for j := i + 1 to m do if a[k].n > a[j].n then k := j;
      if k > i then
        begin
          t := a[i].n;
          a[i].n := a[k].n;
          a[k].n := t
        end
    end;
  //ищем расстояния и простые числа, начиная с 2 и 3
  f[1] := 2;
  f[2] := 3;
  df2 := 0;
  for i := 1 to m do
    begin
      while a[i].n > f[2] do
        begin
          f[1] := f[2];
          if f[2] < 7 then inc(f[2], 2)
          else
            repeat
              inc(f[2], delta[df2]);
              df2 := (df2 + 1) and 7;
              k := 7;
              dk := 0;
              sqrtf := trunc(sqrt(f[2]));
              while k <= sqrtf do
                begin
                  t := f[2] mod k;
                  if t = 0 then break;
                  inc(k, delta[dk]);
                  dk := (dk + 1) and 7
                end
            until t > 0
        end;
      for j := 1 to 2 do df[j] := abs(trunc(a[i].n - f[j]));
      if df[1] <= df[2] then k := 1 else k := 2;
      a[i].d := df[k];
      a[i].p := f[k]
    end;
  //сортировка по неубыванию расстояний
  for i := 1 to m - 1 do
    begin
      k := i;
      for j := i + 1 to m do if a[k].d > a[j].d then k := j;
      if k > i then
        begin
          q := a[i];
          a[i] := a[k];
          a[k] := q
        end
    end;
  //печатаем результат
  writeln('Отсортированный массив:');
  writeln('    Элемент Расстояние Простое число');
  for i := 1 to m do writeln(a[i].n:11, a[i].d:11, a[i].p:11)
end.

Если задать ma=10000000, считает примерно полминуты. При ma=2147483647 ждать надоело, но, полагаю, в течение часа справится.

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

Программу можно ускорить (и существенно усложнить), если применить для генерации следующего простого числа какое-нибудь другое решето. Не знаю, правда, какое. Аткина, наверное.

@bormant · 20.08.2020, 18:16

Cyborg Drone,
Для простых

Pascal
62
      for j := 1 to 2 do df[j] := abs(a[i].n - f[j]);

trunc() был лишний, остался от предыдущих вариантов с нецелыми числами.

@Cyborg Drone · 20.08.2020, 21:02

Да, действительно. Убрать забыл. Спасибо.

Новые блоги и статьи Все статьи Все блоги /
Автозаполнение реквизита при выборе элемента справочника Maks 27.03.2026 Программный код из решения ниже на примере нетипового документа "ЗаявкаНаРемонтСпецтехники" разработанного в конфигурации КА2. При выборе "Спецтехники" (Тип Справочник. Спецтехника), заполняется. . .	Сумматор с применением элементов трёх состояний. Hrethgir 26.03.2026 Тут. https:/ / fips. ru/ EGD/ ab3c85c8-836d-4866-871b-c2f0c5d77fbc Первый документ красиво выглядит, но без схемы. Это конечно не даёт никаких плюсов автору, но тем не менее. . . всё может быть. . .	Автозаполнение реквизитов при создании документа Maks 26.03.2026 Программный код из решения ниже размещается в модуле объекта документа, в процедуре "ПриСозданииНаСервере". Алгоритм проверки заполнения реализован для исключения перезаписи значения реквизита,. . .	Команды формы и диалоговое окно Maks 26.03.2026 1. Команда формы "ЗаполнитьЗапчасти". Программный код из решения ниже на примере нетипового документа "ЗаявкаНаРемонтСпецтехники" разработанного в конфигурации КА2. В качестве источника данных. . .
Кому нужен AOT? DevAlt 26.03.2026 Решил сделать простой ланчер Написал заготовку: dotnet new console --aot -o UrlHandler var items = args. Split(":"); var tag = items; var id = items; var executable = args;. . .	Отправка уведомления на почту при изменении наименования справочника Maks 24.03.2026 Программная отправка письма электронной почты на примере изменения наименования типового справочника "Склады" в конфигурации БП3. Перед реализацией необходимо выполнить настройку системной учетной. . .	модель ЗдравоСохранения 5. Меньше увольнений- больше дохода! anaschu 24.03.2026 Теперь система здравосохранения уменьшает количество увольнений. 9TO2GP2bpX4 a42b81fb172ffc12ca589c7898261ccb/ https:/ / rutube. ru/ video/ a42b81fb172ffc12ca589c7898261ccb/ Слева синяя линия -. . .	Midnight Chicago Blues kumehtar 24.03.2026 Такой Midnight Chicago Blues, знаешь?. . Когда вечерние улицы становятся ночными, а ты не можешь уснуть. Ты идёшь в любимый старый бар, и бармен наливает тебе виски. Ты смотришь на пролетающие. . .

@owlbear 0 / 0 / 0 Регистрация: 16.08.2020 Сообщений: 2

	Сортировка массива по возрастанию расстояния до ближайшего 16.08.2020, 01:40. Показов 2008. Ответов 5 Метки нет (Все метки) Дан массив натуральных чисел. Отсортируйте элементы массива по возрастанию расстояния до ближайшего простого числа. Выведете на экран отсортированные подходящие числа, расстояния до ближайших простых чисел и эти простые числа Подскажите, пожалуйста, как строить программу для такого типа задач? так и не получилось найти ничего похожего. (Может за одно и для этого всего тоже что-нибудь подскажете: по возрастанию расстояния до ближайшего числа Фибоначчи; по возрастанию расстояния до ближайшего числа, являющегося степенью двойки) 0

ФедосеевПавел Модератор 8663 / 4500 / 1670 Регистрация: 01.02.2015 Сообщений: 13,921 Записей в блоге: 13
	16.08.2020, 10:01
	Раз в итоге требуется вывести: - отсортированные подходящие числа, - расстояния до ближайших простых чисел - эти простые числа И нет ограничений на память. То я бы к тому массиву создал ещё два - массив с ближайшими простыми числами (числами Фибоначчи, степенями 2) и массив расстояний. Потом сортировал бы массив расстояний, при этом во время обмена синхронно бы обменивал соответствующие элементы всех трёх массивов. 0

@Cyborg Drone Модератор 10448 / 5739 / 3407 Регистрация: 17.08.2012 Сообщений: 17,458
	20.08.2020, 21:02
	Да, действительно. Убрать забыл. Спасибо. 0

Сортировка массива по возрастанию расстояния до ближайшего

Решение