Форум программистов, компьютерный форум CyberForum.ru

Массив случайных неповторяющихся чисел - C++

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 27, средняя оценка - 4.89
aletelegov
0 / 0 / 0
Регистрация: 21.05.2012
Сообщений: 8
13.06.2012, 13:58     Массив случайных неповторяющихся чисел #1
Ребят работал всю ночь и сейчас голова не пашет! объясните в чем проблема
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
private: System::Void button2_Click(System::Object^  sender, System::EventArgs^  e) 
{
                                  n: int a = rand()%20+1;
   {
            for (int j=1; j<10; j++)
            {
                if (mase[j] == a)
                {
                    goto n;
                }
            }
            mase[post]=a;
            cout <<mase[post]<< endl;
                                  post++;
}
post и mase[] - глобальные перменные
и как бы я не страрался все время числа повторяются
по логике вроде все правильно
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
13.06.2012, 13:58     Массив случайных неповторяющихся чисел
Посмотрите здесь:

C++ Сформировать одномерный массив целых чисел, используя датчик случайных чисел
C++ Генератор случайных неповторяющихся чисел
C++ Сформировать одномерный массив целых чисел, используя датчик случайных чисел.
C++ Составить функцию, которая возвращает N случайных неповторяющихся целых чисел из диапазона
Сформировать одномерный массив целых чисел, используя датчик случайных чисел, и распечатать массив. Удалить из массива все элементы, совпадающие с его C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
AnyOne697
 Аватар для AnyOne697
134 / 106 / 5
Регистрация: 22.05.2010
Сообщений: 532
13.06.2012, 19:00     Массив случайных неповторяющихся чисел #21
Цитата Сообщение от Aesonet Посмотреть сообщение
Напишите пример кода с std::set.
Вот
И на будущее.

Добавлено через 4 минуты
Правда здесь, наверное, надо будет пояснить, почему std::set.

Это реализация "самосортирующегося" контейнера данных STL. Может создан быть для любого класса, у которого определён оператор сравнения <
Суть работы заключается в работе двоичного дерева поиска в общем и красно-чёрных деревьях в частности.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
cactus09
Чайник
 Аватар для cactus09
69 / 69 / 4
Регистрация: 15.02.2012
Сообщений: 475
13.06.2012, 19:01     Массив случайных неповторяющихся чисел #22
AnyOne697, У вас ссылки на пустые страницы http://www.cyberforum.ru/redirector....UzQSUzQXNldA==
http://www.cyberforum.ru/redirector....VDMiVFRSVGMg==
AnyOne697
 Аватар для AnyOne697
134 / 106 / 5
Регистрация: 22.05.2010
Сообщений: 532
13.06.2012, 19:05     Массив случайных неповторяющихся чисел #23
??? Фигово. Вставлял - были нормальные. Окей - всё равно вкладки не закрываю.
http://www.cplusplus.com/reference/stl/set/find/
https://www.google.ru/search?q=std::set
http://ru.wikipedia.org/wiki/красно-чёрное_дерево
http://ru.wikipedia.org/wiki/двоичное_дерево_поиска

Добавлено через 27 секунд
P.S. Проблема не моя, а форума.
grizlik78
Эксперт С++
 Аватар для grizlik78
1882 / 1414 / 101
Регистрация: 29.05.2011
Сообщений: 2,960
13.06.2012, 19:20     Массив случайных неповторяющихся чисел #24
Если диапазон чисел не сильно больше необходимого количества чисел, или равен ему, то может оказаться проще выкинуть лишние и перемешать оставшиеся. Например так:
C++
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
#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>
 
int main()
{
    int const RANDOM_RANGE = 20; // числа от 0 до RANDOM_RANGE-1
    int const ARRAY_SIZE = 10; // количество чисел
    srand(time(NULL));
    std::vector<int> array(RANDOM_RANGE);
 
    // формируем массив из всех чисел
    for (int i = 0; i < RANDOM_RANGE; ++i)
        array[i] = i;
 
    // случайным образом удаляем лишние
    for (int i = RANDOM_RANGE; i > ARRAY_SIZE; --i)
        std::swap(array[i-1], array[rand() % i]);
    array.resize(ARRAY_SIZE);
 
    // перемешиваем оставшиеся
    for (int i = 0; i < ARRAY_SIZE; ++i)
        std::swap(array[i], array[rand() % ARRAY_SIZE]);
 
    for (int i = 0; i < ARRAY_SIZE; ++i)
        std::cout << array[i] << ' ';
    std::cout << std::endl;
 
    return 0;
}
AnyOne697
 Аватар для AnyOne697
134 / 106 / 5
Регистрация: 22.05.2010
Сообщений: 532
13.06.2012, 19:32     Массив случайных неповторяющихся чисел #25
Цитата Сообщение от grizlik78 Посмотреть сообщение
Если диапазон чисел не сильно больше необходимого количества чисел, или равен ему, то может оказаться проще выкинуть лишние и перемешать оставшиеся. Например так:
На самом деле - так даже лучше. Уж всяко лучше, чем держать довольно тяжёлый контейнер std::set. По памяти тоже самое, но по времени будет выигрыш - нет "долгих" поисков.

Эх, блин. Экспер =) Почему до меня эта идея не дошла?..
grizlik78
Эксперт С++
 Аватар для grizlik78
1882 / 1414 / 101
Регистрация: 29.05.2011
Сообщений: 2,960
13.06.2012, 19:38     Массив случайных неповторяющихся чисел #26
На самом деле метод можно даже упростить, если сначала перемешать, а потом удалить.
C++
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
#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>
 
int main()
{
    int const RANDOM_RANGE = 20; // числа от 0 до RANDOM_RANGE-1
    int const ARRAY_SIZE = 10; // количество чисел
    srand(time(NULL));
    std::vector<int> array(RANDOM_RANGE);
 
    // формируем массив из всех чисел
    for (int i = 0; i < RANDOM_RANGE; ++i)
        array[i] = i;
 
    // перемешиваем все числа 
    for (int i = 0; i < RANDOM_RANGE; ++i)
        std::swap(array[i], array[rand() % RANDOM_RANGE]);
 
    // удаляем последние
    array.resize(ARRAY_SIZE);
 
    for (int i = 0; i < ARRAY_SIZE; ++i)
        std::cout << array[i] << ' ';
    std::cout << std::endl;
 
    return 0;
}
Добавлено через 2 минуты
И да, есть стандартный алгоритм для перемешивания std::random_shuffle, но мне с ним не хотелось
AnyOne697
 Аватар для AnyOne697
134 / 106 / 5
Регистрация: 22.05.2010
Сообщений: 532
13.06.2012, 19:38     Массив случайных неповторяющихся чисел #27
Цитата Сообщение от grizlik78 Посмотреть сообщение
упростить
Цитата Сообщение от grizlik78 Посмотреть сообщение
"Premature optimization is the root of all evil". D. E. Knuth
Перемещая std::vector::resize после перемешивания мы ничего толком не делаем.
Зато можем сократить немного перемешивание заменив ARRAY_SIZE на ARRAY_SIZE/2.
grizlik78
Эксперт С++
 Аватар для grizlik78
1882 / 1414 / 101
Регистрация: 29.05.2011
Сообщений: 2,960
13.06.2012, 19:57     Массив случайных неповторяющихся чисел #28
Цитата Сообщение от AnyOne697 Посмотреть сообщение
Зато можем сократить немного перемешивание заменив ARRAY_SIZE на ARRAY_SIZE/2.
Вот этого не стоит. А ресайз просто закрепляет количество действительных элементов в размере вектора. Можно, конечно и не делать.
AnyOne697
 Аватар для AnyOne697
134 / 106 / 5
Регистрация: 22.05.2010
Сообщений: 532
13.06.2012, 20:05     Массив случайных неповторяющихся чисел #29
Цитата Сообщение от grizlik78 Посмотреть сообщение
Вот этого не стоит.
Не знаю. Вот примерно мои мысли (относятся к первой реализации):
ARRAY_SIZE = 1: один бессмысленный swap ( имеет ли смысл n % 1? )
ARRAY_SIZE = 2: одна итерация -> 50% будет swap, 50% - нет => всё огонь; вторая явно лишняя
ARRAY_SIZE = 3: тоже самое
ARRAY_SIZE = 100500^42^146: без разницы - всё равно будет МНОГО
grizlik78
Эксперт С++
 Аватар для grizlik78
1882 / 1414 / 101
Регистрация: 29.05.2011
Сообщений: 2,960
13.06.2012, 20:19     Массив случайных неповторяющихся чисел #30
Если делать ARRAY_SIZE/2 итераций, то в среднем половина элементов из второй части массива останутся на своих местах. Это чересчур много. Вырожденный случай с размером 1 не показателен. Да элемент будет бессмысленно обмениваться сам с собой. Ну так для одного элемента и алгоритм никакой не нужен Да, для двух элементов тоже достаточно было бы одной итерации, но вторая ничего не портит. А вот с большими размерами увы, половины итераций недостаточно.
AnyOne697
 Аватар для AnyOne697
134 / 106 / 5
Регистрация: 22.05.2010
Сообщений: 532
15.06.2012, 19:31     Массив случайных неповторяющихся чисел #31
Ну... Немного посидев с листом и карандашом, решил, что да. Математическая индукция здесь ни к чёрту. Как всегда
Цитата Сообщение от grizlik78 Посмотреть сообщение
"Premature optimization is the root of all evil". D. E. Knuth
Впрочем, если бы рандом был действительно рандомным, то всё было бы довольно не плохо. Если сделать что-то вроде
C++
1
2
3
for(int i = 0; i < ARRAY_SIZE/2; i++)
    if(rand()%2)
        swap(arr+i, arr+i+1);
.
Понятно, что здесь перемещаются только соседние элементы, но не знаю. Может есть какой-то гениальный математический способ более эффективного перемешивания массива основанный на чём-то похожем. Или вообще на одной очень сложной математической истины. Какие-нибудь n-мерные пространства. А для простых смертных сойдёт и
C++
1
2
3
4
5
6
7
8
template <class RandomAccessIterator, class RandomNumberGenerator>
  void random_shuffle ( RandomAccessIterator first, RandomAccessIterator last,
                        RandomNumberGenerator& rand )
{
  iterator_traits<RandomAccessIterator>::difference_type i, n;
  n = (last-first);
  for (i=n-1; i>0; --i) swap (first[i], first[rand(i+1)]);
}
vetal10
35 / 35 / 5
Регистрация: 25.05.2010
Сообщений: 211
15.06.2012, 21:04     Массив случайных неповторяющихся чисел #32
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int main()
{
    const int n = 10; 
    int arr[n];
    int a = 0;
    int j;
    int i = 0;
    srand(time(NULL));
    while(i < n)
    {
    a = rand()%20 + 1;
    for(j = 0; j <= i; ++j )
        while(arr[j] == a)
        a = rand()%30 + 1;
    arr[i++] = a;
    }
    for(j = 0; j < n; ++j )
    printf("%d ", arr[j]);
    return 0;
}
MrGluck
Ворчун
Эксперт С++
 Аватар для MrGluck
4927 / 2670 / 243
Регистрация: 29.11.2010
Сообщений: 7,427
15.06.2012, 21:11     Массив случайных неповторяющихся чисел #33
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <iostream>
#include <algorithm>
#include <iterator>
#include <cstddef>
 
int main()
{
    const std::size_t N = 50;
    int arr[N];
    for (std::size_t i=0; i < N; i++)
        arr[i] = i + 1;
    std::random_shuffle(arr, arr + N);
    std::copy(arr, arr + N, std::ostream_iterator<int> (std::cout, " ") );
    return 0;
}
http://liveworkspace.org/code/4e2336...10cd8ad4d9e4e1
novi4ok
549 / 502 / 8
Регистрация: 23.07.2009
Сообщений: 2,359
Записей в блоге: 1
15.06.2012, 21:56     Массив случайных неповторяющихся чисел #34
Цитата Сообщение от AnyOne697 Посмотреть сообщение
На самом деле - так даже лучше. Уж всяко лучше, чем держать довольно тяжёлый контейнер std::set. По памяти тоже самое, но по времени будет выигрыш - нет "долгих" поисков.

Эх, блин. Экспер =) Почему до меня эта идея не дошла?..
а ты возьми да проверь. сгенери одним и другим способом тыщ 10 чисел и посмотри, что будет быстрее.
это хорошо сказано: "тяжелый контейнер std::set"
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
15.06.2012, 23:46     Массив случайных неповторяющихся чисел
Еще ссылки по теме:

Эксперты! Одномерный массив неповторяющихся чисел не могу понять почему криво работает C++
C++ Сформировать одномерный массив целых чисел, используя датчик случайных чисел
Преобразовать одномерный массив вещественных случайных чисел в массив целых чисел C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
AnyOne697
 Аватар для AnyOne697
134 / 106 / 5
Регистрация: 22.05.2010
Сообщений: 532
15.06.2012, 23:46     Массив случайных неповторяющихся чисел #35
Цитата Сообщение от novi4ok Посмотреть сообщение
а ты возьми да проверь. сгенери одним и другим способом тыщ 10 чисел и посмотри, что будет быстрее.
это хорошо сказано: "тяжелый контейнер std::set"
А вот взял и сгенерил.

Сначала быстро наваял в codepad.org, прямо в input'е. Но он не хотел долго работать, а на "малых" рэнжах время конца работы почти не отличалось от времени начала (в секундах, было лениво вспоминать, как адекватно отображать миллисекунды). Переехал на minGW - массив обрабатывал очень быстро, а вот коллекция вешалась начиная с какого-то AMOUNT (кол-во требуемых элементов). Определил - где-то на 32760 элементе. Потом просто виснул. Перехал на Visual Studio - с std::set тоже самое, а массив очень долго работал (видимо антиоптимизации для дебага) - секунд 30, в тридцать раз дольше по сравнению с minGW. Хотел был переключаться на Linux, но увидел эту вкладку и стало влом.
Yandex
Объявления
15.06.2012, 23:46     Массив случайных неповторяющихся чисел
Ответ Создать тему
Опции темы

Текущее время: 16:26. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru