5

Сижу, ломаю голову - и все никак не получается. Нужно создать массив из случайных чисел в диапозоне от 1 до 7 и чтобы там не было повторений. Я знаю, что есть много вариантов решения, но я выбрал следующий: при генерации числа заносить его в массив, а при генерации следующего пробегаться по массиву в поисках совпадения. Если найдено, то генерировать заново. Написал код, вроде бы все легко, но в ответе все равно проскальзывают повторения. Подскажите, где косяк?

#include "pch.h"
#include <iostream>
#include <string>
#include <locale>
#include <windows.h>
#include <conio.h>
#include <ctime>
#include <time.h>
#include<stdlib.h> 
#include <stdio.h> 

using namespace std;

int main()
{
setlocale(LC_ALL, "Russian");
SetConsoleCP(1251);
SetConsoleOutputCP(1251);

srand(time(0));

int a[7] = {0,0,0,0,0,0,0}; //создаю массив и заполняю нулями
int random; //переменная для случайных чисел

for (int i = 0; i < 7; i++) { //цикл создания случайных чисел
             random = 1 + rand() % 7; //создание случайного числа
             for (int j = 0; j < 7; j++) { //цикл проверки массива на совпадение
                 if (random == a[j]) { //условие совпадения
                     while (random == a[j]) { //цикл для создания нового случайного числа, пока оно не будет повторяться
                         random = 1 + rand() % 7;
                     }
                 }
                 else {
                     continue; //если повтора нет, переходим к следующей итерации
                 }
            }
             a[i] = random; // присваивание рандомного числа элементу массива
        } 

for (int k = 0; k < 7; k++) { //вывод массива на экран
            cout << a[k];
        }

cout << "Для выхода из консоли нажмите любую клавишу";
    _getch();
    return 0;
}
1
  • если размер случайного массива был бы заметно меньше разрешённого диапазона чисел, то можно было бы применить reservoir sampling алгоритм (линейный). Пример реализации на Питоне
    – jfs
    26 авг 2018 в 9:25

3 ответа 3

14

Для такого малого количества просто возьмите массив {1,2,3,4,5,6,7} и случайным образом его перетасуйте (например, с помощью shuffle). Будет быстрее и проще.

А ваша проблема в том, что, проверив число на равенство одному a[j] и откорректировав, вы тут же об этом забываете при проверке на следующее значение j. Т.е. ваш цикл должен выглядеть примерно как

for (int i = 0; i < 7; i++)
{
    for(;;)
    {
        bool good = true;
        random = 1 + rand() % 7;
        for (int j = 0; j < 7; j++)
        {
            if (random == a[j]) { good = false; break; }
        }
        if (good) break;
    }
    a[i] = random; // присваивание рандомного числа элементу массива
}
1
  • Это уже почти подходит на алгоритм подбора простых чисел в RSA :)
    – NewView
    26 авг 2018 в 9:27
13

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

Для решения этой задачи есть простейший алгоритм Фишера-Йетса, который сразу за один проход генерирует случайно перемешанную последовательность без необходимости каких-то проверок

int main()
{
  int a[7] = { 0 };

  for (unsigned i = 0; i < 7; ++i)
  {
    unsigned j = rand() % (i + 1);
    a[i] = a[j];
    a[j] = i + 1;
  }

  for (int i : a)
    cout << i << " ";

  cout << endl;
}
2

Так как std::unordered_map хранит пары с уникальным ключом:

const int r = 7;
int a[r] = {0};
unordered_map<int, int> m;
for (int i = 0; i < r; ++i)
    while (!(m.emplace(make_pair(1 + rand()%r, i))).second);
//вводим пару, пока попытка ввода не будет удачной
for (auto p : m)
    a[p.second] = p.first;

Так быстрее (границы случайных чисел могут быть любыми).

Но конкретно для вашего случая, когда элементы массива принимают значения по каким то критериям(например от 1 по r), то можно просто:

for (int i = 0; i < r; ++i)
        a[i] = i + 1;
std::random_shuffle(a, a + r);

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.