Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск  
 
 
Рейтинг 4.51/55: Рейтинг темы: голосов - 55, средняя оценка - 4.51
0 / 0 / 0
Регистрация: 21.05.2012
Сообщений: 8

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

13.06.2012, 13:58. Показов 12183. Ответов 34
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Ребят работал всю ночь и сейчас голова не пашет! объясните в чем проблема
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[] - глобальные перменные
и как бы я не страрался все время числа повторяются
по логике вроде все правильно
0
cpp_developer
Эксперт
20123 / 5690 / 1417
Регистрация: 09.04.2010
Сообщений: 22,546
Блог
13.06.2012, 13:58
Ответы с готовыми решениями:

Генератор случайных неповторяющихся чисел
Народ помогите! Проблема следующая. Я создал массив и заполнил его числами с помощью rand от -20 до 20. Как сделать так, чтобы при выводе...

Матрица из случайных неповторяющихся чисел
Здравствуйте! В C++ я новичок (что по-моему и так понятно, иначе этого вопроса бы не было :D). Скажите, пожалуйста, как составить матрицу...

Составить функцию, которая возвращает N случайных неповторяющихся целых чисел из диапазона
Помогите плизз Составить функцию, которая возвращает N случайных неповторяющихся целых чисел из диапазона . Главная...

34
 Аватар для AnyOne697
134 / 106 / 10
Регистрация: 22.05.2010
Сообщений: 533
13.06.2012, 19:00
Студворк — интернет-сервис помощи студентам
Цитата Сообщение от Aesonet Посмотреть сообщение
Напишите пример кода с std::set.
Вот
И на будущее.

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

Это реализация "самосортирующегося" контейнера данных STL. Может создан быть для любого класса, у которого определён оператор сравнения <
Суть работы заключается в работе двоичного дерева поиска в общем и красно-чёрных деревьях в частности.
1
Чайник
 Аватар для cactus09
70 / 70 / 9
Регистрация: 15.02.2012
Сообщений: 475
13.06.2012, 19:01
AnyOne697, У вас ссылки на пустые страницы https://www.cyberforum.ru/redi... UzQXNldA==
https://www.cyberforum.ru/redi... VFRSVGMg==
0
 Аватар для AnyOne697
134 / 106 / 10
Регистрация: 22.05.2010
Сообщений: 533
13.06.2012, 19:05
??? Фигово. Вставлял - были нормальные. Окей - всё равно вкладки не закрываю.
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. Проблема не моя, а форума.
1
Эксперт С++
 Аватар для grizlik78
2383 / 1667 / 279
Регистрация: 29.05.2011
Сообщений: 3,402
13.06.2012, 19:20
Если диапазон чисел не сильно больше необходимого количества чисел, или равен ему, то может оказаться проще выкинуть лишние и перемешать оставшиеся. Например так:
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;
}
1
 Аватар для AnyOne697
134 / 106 / 10
Регистрация: 22.05.2010
Сообщений: 533
13.06.2012, 19:32
Цитата Сообщение от grizlik78 Посмотреть сообщение
Если диапазон чисел не сильно больше необходимого количества чисел, или равен ему, то может оказаться проще выкинуть лишние и перемешать оставшиеся. Например так:
На самом деле - так даже лучше. Уж всяко лучше, чем держать довольно тяжёлый контейнер std::set. По памяти тоже самое, но по времени будет выигрыш - нет "долгих" поисков.

Эх, блин. Экспер =) Почему до меня эта идея не дошла?..
0
Эксперт С++
 Аватар для grizlik78
2383 / 1667 / 279
Регистрация: 29.05.2011
Сообщений: 3,402
13.06.2012, 19:38
На самом деле метод можно даже упростить, если сначала перемешать, а потом удалить.
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, но мне с ним не хотелось
0
 Аватар для AnyOne697
134 / 106 / 10
Регистрация: 22.05.2010
Сообщений: 533
13.06.2012, 19:38
Цитата Сообщение от grizlik78 Посмотреть сообщение
упростить
Цитата Сообщение от grizlik78 Посмотреть сообщение
"Premature optimization is the root of all evil". D. E. Knuth
Перемещая std::vector::resize после перемешивания мы ничего толком не делаем.
Зато можем сократить немного перемешивание заменив ARRAY_SIZE на ARRAY_SIZE/2.
0
Эксперт С++
 Аватар для grizlik78
2383 / 1667 / 279
Регистрация: 29.05.2011
Сообщений: 3,402
13.06.2012, 19:57
Цитата Сообщение от AnyOne697 Посмотреть сообщение
Зато можем сократить немного перемешивание заменив ARRAY_SIZE на ARRAY_SIZE/2.
Вот этого не стоит. А ресайз просто закрепляет количество действительных элементов в размере вектора. Можно, конечно и не делать.
0
 Аватар для AnyOne697
134 / 106 / 10
Регистрация: 22.05.2010
Сообщений: 533
13.06.2012, 20:05
Цитата Сообщение от grizlik78 Посмотреть сообщение
Вот этого не стоит.
Не знаю. Вот примерно мои мысли (относятся к первой реализации):
ARRAY_SIZE = 1: один бессмысленный swap ( имеет ли смысл n % 1? )
ARRAY_SIZE = 2: одна итерация -> 50% будет swap, 50% - нет => всё огонь; вторая явно лишняя
ARRAY_SIZE = 3: тоже самое
ARRAY_SIZE = 100500^42^146: без разницы - всё равно будет МНОГО
0
Эксперт С++
 Аватар для grizlik78
2383 / 1667 / 279
Регистрация: 29.05.2011
Сообщений: 3,402
13.06.2012, 20:19
Если делать ARRAY_SIZE/2 итераций, то в среднем половина элементов из второй части массива останутся на своих местах. Это чересчур много. Вырожденный случай с размером 1 не показателен. Да элемент будет бессмысленно обмениваться сам с собой. Ну так для одного элемента и алгоритм никакой не нужен Да, для двух элементов тоже достаточно было бы одной итерации, но вторая ничего не портит. А вот с большими размерами увы, половины итераций недостаточно.
0
 Аватар для AnyOne697
134 / 106 / 10
Регистрация: 22.05.2010
Сообщений: 533
15.06.2012, 19: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)]);
}
0
35 / 35 / 11
Регистрация: 25.05.2010
Сообщений: 211
15.06.2012, 21:04
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;
}
0
Форумчанин
Эксперт CЭксперт С++
 Аватар для MrGluck
8217 / 5048 / 1437
Регистрация: 29.11.2010
Сообщений: 13,453
15.06.2012, 21:11
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/... 8ad4d9e4e1
0
556 / 510 / 25
Регистрация: 23.07.2009
Сообщений: 2,359
Записей в блоге: 1
15.06.2012, 21:56
Цитата Сообщение от AnyOne697 Посмотреть сообщение
На самом деле - так даже лучше. Уж всяко лучше, чем держать довольно тяжёлый контейнер std::set. По памяти тоже самое, но по времени будет выигрыш - нет "долгих" поисков.

Эх, блин. Экспер =) Почему до меня эта идея не дошла?..
а ты возьми да проверь. сгенери одним и другим способом тыщ 10 чисел и посмотри, что будет быстрее.
это хорошо сказано: "тяжелый контейнер std::set"
1
 Аватар для AnyOne697
134 / 106 / 10
Регистрация: 22.05.2010
Сообщений: 533
15.06.2012, 23:46
Цитата Сообщение от novi4ok Посмотреть сообщение
а ты возьми да проверь. сгенери одним и другим способом тыщ 10 чисел и посмотри, что будет быстрее.
это хорошо сказано: "тяжелый контейнер std::set"
А вот взял и сгенерил.

Сначала быстро наваял в codepad.org, прямо в input'е. Но он не хотел долго работать, а на "малых" рэнжах время конца работы почти не отличалось от времени начала (в секундах, было лениво вспоминать, как адекватно отображать миллисекунды). Переехал на minGW - массив обрабатывал очень быстро, а вот коллекция вешалась начиная с какого-то AMOUNT (кол-во требуемых элементов). Определил - где-то на 32760 элементе. Потом просто виснул. Перехал на Visual Studio - с std::set тоже самое, а массив очень долго работал (видимо антиоптимизации для дебага) - секунд 30, в тридцать раз дольше по сравнению с minGW. Хотел был переключаться на Linux, но увидел эту вкладку и стало влом.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
15.06.2012, 23:46

Сгенерировать массив из N неповторяющихся четных чисел в заданном диапазоне
Создать функцию, которая генерирует массив из N элементов неповторяющихся четными числами в диапазоне K.M

Преобразовать одномерный массив вещественных случайных чисел в массив целых чисел
Преобразовать одномерный массив вещественных случайных чисел в массив целых чисел больших исходных на два порядка. Напечатать массивы в два...

Эксперты! Одномерный массив неповторяющихся чисел не могу понять почему криво работает
Задание: Нужно вывести массив из случайных чисел. Размер массива 8. Случайные числа от 1 до 8. Числа не должны повторяться. #include...

Сформировать одномерный массив целых чисел, используя датчик случайных чисел.
Сформировать одномерный массив целых чисел, используя датчик случайных чисел. Удалить 5 последних элементов массива. Добавить в...

Сформировать одномерный массив целых чисел, используя датчик случайных чисел
1) Сформировать одномерный массив целых чисел, используя датчик случайных чи-сел. 2) Распечатать полученный массив. 3) Удалить элементы...


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

Или воспользуйтесь поиском по форуму:
35
Ответ Создать тему
Новые блоги и статьи
Сезонность и суточность закисления почв
anaschu 04.07.2026
200 часов это все равно моловато. Есть ситуации, но нестандартные, когда смена происходит за 5 лет. Но обычно это 50 лет и более. Наверное, закисление почвы происходит сезонно в средней. . .
В чем ценность человеческого опыта в глобальном смысле?
kumehtar 03.07.2026
Возможно, ценность человека не в том, что он однажды достигает мудрости, а в том, что он становится носителем карты пути. Он знает не только истину, но и последовательность внутренних изменений,. . .
интеграция AnyLogic с самописным REST API и переход на Odoo
anaschu 03.07.2026
Успешная интеграция AnyLogic с самописным REST API и переход на промышленную Odoo WMS Сегодня проделал огромный путь от простой симуляции физических процессов до построения полноценной. . .
Поиск всех путей на ориентированном графе. Linux
dcc0 02.07.2026
Переработка старого кода из моей статьи. Через несколько переработок от PHP кода к C89 (надеюсь, 89). Но довольно запутанно получилось. Код для Linux. Но если убрать time и то, что с ним. . .
Сам себя обучал rest api
anaschu 02.07.2026
Педагогический лайфхак: Почему чистый REST API для ученика намного круче, чем готовые библиотеки Когда мы отказались от капризного JAR-файла AnyLogic и переписали код на стандартный HttpClient,. . .
rest api anylogic - выполнение модели на своём русском сайте
anaschu 02.07.2026
Как подружиться с AnyLogic Cloud API, победить провайдеров и развернуться Java-бэкенд в Docker на бесплатном хостинге: Двухдневный лог борьбы Всем привет! Хочу поделиться свежим (и довольно. . .
Где деньги лежат
kumehtar 02.07.2026
Это - японская подводная лодка I-52 (тип C2, кодовое имя Momi) вышла из Японии в марте 1944 года с миссией в оккупированную немцами Францию (Лорьян). Это была одна из «Янаги»-миссий по обмену. . .
Krabik для WoW 3.3.5a, многоязычный
AmbA 02.07.2026
Допилил бота, думаю что окончательно. Изменения: - добавлена многоязычность - добавлено снятие скриншотов - добавлено поддержание бафов хождения по воде (для жреца, дк и шамана) - и так, по. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru