Генерация массива чисел без повторов (С++)

Прикладное программирование Программирование на С++ Генерация массива чисел без повторов (С++)

  • В этой теме 0 ответов, 1 участник, последнее обновление 1 месяц, 1 неделя назад сделано Васильев Владимир Сергеевич.
Просмотр 0 веток ответов
  • Автор
    Сообщения
    • #6897
      @admin
      StudLance.ru

      Задача: Составьте программу генерации одномерного целочисленного массива, в котором нет повторяющихся элементов. Оцените эффективность построенного алгоритма.

      Решение:
      В задании не указан диапазон генерируемых элементов. Однако:

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

      Реализован третий вариант. Для более эффективного поиска, элементы массива можно хранить упорядоченными, однако затраты на сортировку (по крайней мере для массива) скорее всего будут существенно выше полученной выгоды. Поэтому в решении применяется линейный поиск (по ссылке функция is_member), на рисунке — блок-схема алгорима генерации. При генерации используется интервал [0, 2*n], однако мог бы быть любой другой с шириной не меньше n. Для генерации числа в диапазоне используется функции rand_between, описанная раньше.

      Реализация алгоритмов на языке С++:

      #include <iostream>
      #include <stdlib.h>
      #include <time.h>
      using namespace std;
      
      int rand_between(const int from, const int to) {
       // взять по ссылке
      }
      
      bool is_member(int* array, int n, int value) {
       // взять по ссылке
      }
      
      int *get_random_unique_array(int n) {
        int* arr = new int[n];
        int i = 0;
        while (i < n) {
          arr[i] = rand_between(0, n*2);
          if (is_member(arr, i-1, arr[i]))
            continue;
          ++i;
        }
        return arr;
      }
      
      void print_array(const string& name, int* arr, int n) {
        cout << "array - " << name << ":" << endl;
        for (int i = 0; i < n; ++i) {
          cout << arr[i] << " ";
        }
        cout << endl;
      }
      
      int main() {
        srand(time(NULL));
        int *a = get_random_unique_array(10);
        int *b = get_random_unique_array(15);
        int *c = get_random_unique_array(3);
        print_array("a", a, 10);
        print_array("b", b, 15);
        print_array("c", c, 3);
        delete[] a;
        delete[] b;
        delete[] c;
      }

      Объем работы, выполняемый таким алгоритмом зависит от вероятности необходимости повторной генерации (обозначим p). Вероятность зависит от соотношения ширины интервала генерируемых элементов и количества элементов массива. Очевидно, худшим случаем будет их равенство (последний элемент масссива будет генерироваться много раз), а лучшим — генериация маленького массива с числами в диапазоне [-INT_MAX; +INT_MAX].

      Объем работы (сложность алгоритма) можно оценить как:

      $$
      O(N \cdot (1−p) + 2 \cdot N \cdot p^2 + 3 \cdot N \cdot p^4 + 4 \cdot N \cdot p^6 + … + K \cdot N \cdot p^{K \cdot 2}) = O(N)
      $$

      Формула в левой части выражения описывает следующее (разберем для случая p = 0.2):

      • в 80 процентах случаев генерация будет выполнена с первого раза:
        $$(N*(1-p))$$
      • в 20 процентха случаев потребуется выполнить ее повторно, при этом будет обработано 20 процентов массива (N*p), вероятность такого события равна p, отсюда слагаемое:
        $$(2*N*(p^2))$$
      • с вероятностью p^2 нужно будет генерировать элементы трижды (количество таких элементов можно оценить как N*p*p). Получаем слагаемое:
        $$3*N*(p^4)$$

      Однако, в этой формуле p находится в диапазоне [0, 1]. Это значит, что последние члены ряда имеют очень маленькое значение. Кроме того, в асимтотическом анализе не учитываются константные члены, а p является константой. Отсюда получаем оценку, записанную в правой части выражения.

      StudLance.ru

Просмотр 0 веток ответов
  • Для ответа в этой теме необходимо авторизоваться.
×