Как перемешать массив таким образом, чтобы модуль разности любых соседних чисел был не меньше чем 5?

118
11 июля 2021, 07:20

Заполнить одномерный массив размером 200 элементов случайными и неповторяющимися числами в диапазоне 1 – 200.

Перемешать данные в массиве таким образом, чтобы модуль разности любых соседних чисел был не меньше чем 5.

#include <iostream>
#include <ctime> 
#include <iomanip>
#include <cmath>
using namespace std;
int main() {
    srand(time(NULL));  
    int const n = 20;   
    int a[n];   
    int b;  
    int c = 1;
    for (int i = 0; i < n; i++) {
        a[i] = 0;
    }
    for (int i = 1; i <= n; i++) {
        b = rand() % n;
        if (a[b] != 0) {
            for (int k = b + 1; k <= n; k++) {
                if (k == n) {
                    k = 0;
                }
                if (a[k] == 0) {
                    a[k] = i; break;
                }
            }
        }
        else {
            a[b] = i;
        }
    }
    for (int i = 0; i < n; i++) {
        cout << setw(3) << a[i];
    }
// Непосредственно перемешка массива таким образом, чтобы модуль разности любых соседних чисел был не меньше чем 5  
    cout << endl;
    for (int i = 0; i < n; i++) {
        cout << setw(3) << a[i];
    }
    system("pause>null");
}
Answer 1

Я бы попробовал отсортировать массив, а потом проходить по нему многократно - сначала выбираем первый символ, потом идем дальше, пока не встретим первый же, который на 5 или больше больше первого, и так дальше - пока не дойдем до конца массива. Все выбранные переносятся в новый массив. Как дошли до конца - начинаем заново, сначала.

1 1 2 8 10 15 22

первый проход:

1  8  15  22              1 2 10

второй:

1  8  15  22  1  10       2

третий:

1  8  15  22  1  10  2

Как-то так. Могут быть массивы, которые неполучится так "отсортировать", как надо - скажем, когда все элементы одинаковы.

Answer 2

Я бы делал так:

  1. Заполнить массив последовательными числами от 1 до 200.
  2. Пробежать циклом i от 1-го до последнего элемента, для каждого выполняя следующую проерку
    1. Если элемент не удовлетворяет условию, то выбрать случайное j из диапазона массива.
    2. Если i не равно j и перестановка этих элементов местами сделает условие выполненным для обоих, то переставить, иначе увеличивать j на единицу (обнуляя при выходе за массив), пока условие не выполнится.

Таким образом не более чем за 40000 операций массив будет перемешан нужным образом.

READ ALSO
Чтение сокета средствами C++

Чтение сокета средствами C++

Пишу сервер на С++, отправляю ему данные вида dhw6558d5fjf48dnbp5fps5tkze5f83n{\"gl\":\"123\"} а получаю это и еще 5 непонятных символов

116
Возвращаемый тип main должен быть int, а не void [дубликат]

Возвращаемый тип main должен быть int, а не void [дубликат]

Конечно, согласно стандарту - cмраздел 6

145
Почему json приходит не весь?

Почему json приходит не весь?

Отправляю в ответ на запрос json

106