Рандом без повторений

@Shef4u · Регистрация: 31.10.2011

Author24 — интернет-сервис помощи студентам

Здравствуйте! Искал по форуме, но так и не нашел подходящее решение такой задачи:
пользователь вводит К ПРИМЕРУ число 7. я беру от него логарифм за основанием 2 и заокругляю к большему n=ceil(log(Np)/log(2)); это выйдет n=3. ага, теперь я знаю, что мне надо 7 комбинаций по 3 символа в двочином коде не считая 000 так как всего может быть восемь: 000 111 100 101 011 001 110 010. 000 мне не надо. внимание вопрос: как это сделать через rand или как-то иначе?? вот мой код, но в нем числа повторяютя и комбинация 000 присутствует((

Code    
        
            
                
                
                
                
            
        
    Скопировано
1
2
3
4
5
6
7
8
9
10
11
12
int Np;
float n;
cout<<"Введите Np="; cin>>Np;
n=ceil(log(Np)/log(2));
cout<<"n="<<n<<endl;
randomize();
for (int i=0; i<Np; i++)
{
  for (int j=0; j<n; j++)
cout<<rand()%2;
cout<<endl;      
}

Добавлено через 3 часа 7 минут
покапался еще на форуме и нашел вариант с записью в массив и потом сравнением. как тогда записать в цикле значение в массив? если просто написать

C++    
        
            
                
                
                
                
            
        
    Скопировано
1
2
3
4
5
6
7
8
9
10
11
12
int Np, *mas=new int[Np];
float n;
cout<<"Введите Np="; cin>>Np;
n=ceil(log(Np)/log(2));
cout<<"n="<<n<<endl;
randomize();
for (int i=0; i<Np; i++)
{
  for (int j=0; j<n; j++)
cout<<rand()%2; cin>>mas[i];
cout<<endl;      
}

не подходит ((

@Ev[G]eN · 15.03.2013, 22:15

так?

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
32
33
34
35
36
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <ctime>
#include <cmath>
 
int main ()
{
    srand(time(0));
 
    int Np;
    std::cout << "Input Np: ";
    std::cin >> Np;
 
    int n = ceil(log(Np) / log(2));
    std::cout << "N: " << n << std::endl;
 
    int fLimit = pow(10, n - 1) - 1;
    int sLimit = pow(10, n);
    int *array = new int [Np];
    for (int i = 0; i < Np; i++) {
        int genElem = (rand() % (sLimit - fLimit + 1));
        if (!std::count(array, array + Np, genElem))
            array[i] = genElem;
        else
            i--;
    }
 
    std::cout << "Your array: " << std::endl;
    for (int i = 0; i < Np; i++)
        std::cout << array[i] << " ";
    std::cout << std::endl;
 
    delete [] array;
    return 0;
}

@Shef4u · 15.03.2013, 22:30 **[ТС]**

Сообщение от Ev[G]eN

так?

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
32
33
34
35
36
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <ctime>
#include <cmath>
 
int main ()
{
    srand(time(0));
 
    int Np;
    std::cout << "Input Np: ";
    std::cin >> Np;
 
    int n = ceil(log(Np) / log(2));
    std::cout << "N: " << n << std::endl;
 
    int fLimit = pow(10, n - 1) - 1;
    int sLimit = pow(10, n);
    int *array = new int [Np];
    for (int i = 0; i < Np; i++) {
        int genElem = (rand() % (sLimit - fLimit + 1));
        if (!std::count(array, array + Np, genElem))
            array[i] = genElem;
        else
            i--;
    }
 
    std::cout << "Your array: " << std::endl;
    for (int i = 0; i < Np; i++)
        std::cout << array[i] << " ";
    std::cout << std::endl;
 
    delete [] array;
    return 0;
}

спасибо, cmath не работало, по этому заменил на math.h . Да и выводит не то что мне надо

@Shef4u · 15.03.2013, 22:32 **[ТС]**

Сообщение от Ev[G]eN

так?

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
32
33
34
35
36
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <ctime>
#include <cmath>
 
int main ()
{
    srand(time(0));
 
    int Np;
    std::cout << "Input Np: ";
    std::cin >> Np;
 
    int n = ceil(log(Np) / log(2));
    std::cout << "N: " << n << std::endl;
 
    int fLimit = pow(10, n - 1) - 1;
    int sLimit = pow(10, n);
    int *array = new int [Np];
    for (int i = 0; i < Np; i++) {
        int genElem = (rand() % (sLimit - fLimit + 1));
        if (!std::count(array, array + Np, genElem))
            array[i] = genElem;
        else
            i--;
    }
 
    std::cout << "Your array: " << std::endl;
    for (int i = 0; i < Np; i++)
        std::cout << array[i] << " ";
    std::cout << std::endl;
 
    delete [] array;
    return 0;
}

можете написать кусок кода который будет делать каждый раз проверку, не равен ли результат какому-либо из уже полученных и, если равен, вызывать rand()%2 ещё раз b еще раз?

@Ev[G]eN · 15.03.2013, 22:34

Сообщение от Shef4u

кусок кода который будет делать каждый раз проверку, не равен ли результат какому-либо из уже полученных

C++    
        
            
                
                
                
                
            
        
    Скопировано
1
2
3
4
5
6
7
for (int i = 0; i < Np; i++) {
        int genElem = (rand() % (sLimit - fLimit + 1));
        if (!std::count(array, array + Np, genElem))
            array[i] = genElem;
        else
            i--;
    }

@Shef4u · 15.03.2013, 22:42 **[ТС]**

Сообщение от Ev[G]eN

C++    
        
            
                
                
                
                
            
        
    Скопировано
1
2
3
4
5
6
7
for (int i = 0; i < Np; i++) {
        int genElem = (rand() % (sLimit - fLimit + 1));
        if (!std::count(array, array + Np, genElem))
            array[i] = genElem;
        else
            i--;
    }

может вам что-нибудь известно о синтаксисе де Брейновской ф-ции?
де Брейновская функция это булева функция порождающая псевдослучацную последовательность длины 2^n.
Важное свойство: Все числа в этой последовательности различны и находятся в диапазоне от 0 до 2^n.
де Брейновская функция для n = 3:
|x2|x1|x0|f|
| 0| 0| 0|1|
| 0| 0| 1|0|
| 0| 1| 0|1|
| 0| 1| 1|1|
| 1| 0| 0|0|
| 1| 0| 1|1|
| 1| 1| 0|0|
| 1| 1| 1|0|

@0x10 · 16.03.2013, 07:49

Shef4u, как я понимаю, диапазон значений известен, допустимые значения известны - заполняем массив и перемешиваем std::random_shuffle.

Ev[G]eN, ну вот не надо такой "угадайки". Будем кидать рандом до посинения пока не найдем неиспользованное число? И сколько раз оно сработает в ситуации, когда нужно получить случайную последовательность размером 100 со значениями в диапазоне от 0 до 99, когда остался незаполненным один последний элемент?

@Vaste · 16.03.2013, 08:16

Кидай сгенерированные значения в массив, чтоб смореть было или нет. Иначе никак.

@olea · 28.04.2013, 13:07

Shef4u, а не могли бы вы привести синтаксис де Брейновской функции?

@Shef4u · 29.04.2013, 16:52 **[ТС]**

Сообщение от olea

Shef4u, а не могли бы вы привести синтаксис де Брейновской функции?

если б я его знал

MrGluck · 29.04.2013, 16:55

Делается все так:
берется массив, заполняется всеми возможными значениями, далее с помощью std::random_shuffle перемешивается, и, если нам нужно получить новое "неповторяющееся число" - берем следующий элемент массива, сдвигая индекс.

Я уже раз 5 отвечал на данный вопрос, не верю, что в поиске не было результатов.

Ternsip · 29.04.2013, 16:58

C++    
        
            
                
                
                
                
            
        
    Скопировано
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
#include <vector>
#include <ctime>  
 
using namespace std;
 
int main(){            
    std::srand ( unsigned ( std::time(0) ) );
    vector <int> a;
    int n = 100;
    for (int i = 0; i < n; i++) {
        a.push_back(i);
    }
    std::random_shuffle(a.begin(), a.end());
    for (int i = 0; i < a.size(); i++) {
        printf("%d ", a[i]);
    }
    return 0;
}

Добавлено через 16 секунд
MrGluck, эххх, вы меня обогнали))

MrGluck · 29.04.2013, 16:59

Ternsip,

C++    
        
    Скопировано
1
2
#include <cstdlib>
#include <algorithm>

Ternsip · 29.04.2013, 17:01

MrGluck, в Microsoft Visual C++ 2012 уже не нужно

MrGluck · 29.04.2013, 17:07

Ternsip, ничто не гарантирует, что данные хедеры подключатся какими-то косыми-кривыми путями. Если используете функцию из файла - укажите явно где её искать.

Если что, mingw не пропустит random_shuffle, а gcc еще и на srand ругнется.

Добавлено через 1 минуту
Кстати, правила п.5.10 прочтите.
Как бы ни хотелось - но закон есть закон.

@Shef4u · 01.05.2013, 21:42 **[ТС]**

Сообщение от MrGluck

Делается все так:
берется массив, заполняется всеми возможными значениями, далее с помощью std::random_shuffle перемешивается, и, если нам нужно получить новое "неповторяющееся число" - берем следующий элемент массива, сдвигая индекс.

Я уже раз 5 отвечал на данный вопрос, не верю, что в поиске не было результатов.

спасибо, но что делать если всеможможных значений 36 и больше? не записывать же все в массив. и что вы имели ввиду под сдвигом индекса? побитовое? >>

@0x10 · 01.05.2013, 21:47

Сообщение от Shef4u

спасибо, но что делать если всеможможных значений 36 и больше?

Мелочевка.

Сообщение от Shef4u

и что вы имели ввиду под сдвигом индекса? побитовое? >>

Уже столько раз обсасывалось, что даже отвечать лень... У тебя есть массив array из N случайных чисел. Если нужно K чисел, то выбираешь array[i] где i = [0..K]. Если нужно очередное число, берешь i+1.

MrGluck · 01.05.2013, 23:10

Shef4u, вы считаете, что каждый раз тыкаться по всему массиву из n чисел, проверяя есть ли данное число в массиве и если нет - повторять операцию до посинения - лучший вариант? Нет, к сожалению более производительного решения, чем я предложил нет. Да и недолго это на ЭВМ то.

Сообщение от Shef4u

сдвигом индекса

инкремент

@nonedark2008 · 02.05.2013, 00:36

По мне так генерировать последовательность неповторяющихся простых чисел оптимальнее всего было бы с использованием конгруэнтного метода, который замечательно описан во втором томе Кнута.

@Shef4u · 03.05.2013, 11:44 **[ТС]**

Сообщение от nonedark2008

По мне так генерировать последовательность неповторяющихся простых чисел оптимальнее всего было бы с использованием конгруэнтного метода, который замечательно описан во втором томе Кнута.

спасибо. наслышан уже об этой книге от профессора который ведет теорию вероятности но все никак не дойдут руки прочесть

Новые блоги и статьи Все статьи Все блоги /
Вопросы на собеседовании по Android mobDevWorks 14.03.2025 По данным статистики, Android занимает более 70% мирового рынка мобильных операционных систем, что делает платформу привлекательной как для начинающих разработчиков, так и для опытных профессионалов. . . .	Лучшие игровые движки для Python py-thonny 14.03.2025 Python обеспечивает разработчиков игр мощными движками и фреймворками, которые позволяют воплотить практически любую идею — от простой аркады до визуального романа с разветвленным сюжетом. Главное. . .	Бессерверный JavaScript: Разработка масштабируемых API с AWS Lambda run.dev 14.03.2025 Но что такое бессерверные вычисления на самом деле? По сути, это модель облачных вычислений, где разработчик фокусируется исключительно на создании бизнес-логики, не тратя время на настройку. . .	Безопасность кода в C++26: Менеджеры ресурсов и висячие ссылки NullReferenced 14.03.2025 C++ всегда был языком, предоставляющим разработчикам большие возможности и гибкость, но вместе с тем требующим ответственности. Одной из самых коварных проблем даже для опытных программистов остаются. . .	smart-agent proper interface settings (2025) jigi33 14.03.2025 Smart-agent proper interface settings (mart 2025). (see screenshots to look at "Etalon" ARM)
Продвинутые настройки JVM Javaican 14.03.2025 Стандартные параметры запуска JVM хороши для повседневной разработки, но совершенно недостаточны для высоконагруженных систем. Представьте, что вы запускаете финансовую платформу, обрабатывающую. . .	CI/CD для приложений Java с Azure DevOps и Docker Mr. Docker 14.03.2025 Разработка современных Java-приложений немыслима без системы непрерывной интеграции и доставки (CI/ CD). Azure DevOps в сочетании с Docker предоставляет мощный инструментарий для создания таких. . .	Разработка на PHP и интернет вещей (IoT) Jason-Webb 14.03.2025 Интернет вещей (IoT) произвел настоящую революцию в способах взаимодействия устройств с окружающим миром. В эпоху, когда холодильники сами заказывают молоко, а термостаты учатся вашим привычкам,. . .	Node.js 20: Новые возможности и улучшения производительности Reangularity 14.03.2025 Что же принёс нам релиз Node. js 20? В первую очередь, это существенные улучшения в производительности. Движок V8 получил серьёзные оптимизации, благодаря чему JavaScript-код выполняется заметно. . .	Безопасность кластеров Apache Kafka Javaican 14.03.2025 Apache Kafka стал одним из ключевых компонентов современных архитектур, обрабатывающих потоки данных в режиме реального времени. Его используют тысячи компаний от стартапов до технологических. . .

@0x10 3258 / 2060 / 351 Регистрация: 24.11.2012 Сообщений: 4,909
	16.03.2013, 07:49	7
	Shef4u, как я понимаю, диапазон значений известен, допустимые значения известны - заполняем массив и перемешиваем std::random_shuffle. Ev[G]eN, ну вот не надо такой "угадайки". Будем кидать рандом до посинения пока не найдем неиспользованное число? И сколько раз оно сработает в ситуации, когда нужно получить случайную последовательность размером 100 со значениями в диапазоне от 0 до 99, когда остался незаполненным один последний элемент? 0

@Vaste 1 / 1 / 0 Регистрация: 23.04.2012 Сообщений: 42
	16.03.2013, 08:16	8
	Кидай сгенерированные значения в массив, чтоб смореть было или нет. Иначе никак. 0

@olea 5 / 5 / 2 Регистрация: 30.01.2012 Сообщений: 153
	28.04.2013, 13:07	9
	Shef4u, а не могли бы вы привести синтаксис де Брейновской функции? 0

@Shef4u 15 / 15 / 4 Регистрация: 31.10.2011 Сообщений: 116
	29.04.2013, 16:52 [ТС]	10
	Сообщение от olea Shef4u, а не могли бы вы привести синтаксис де Брейновской функции? если б я его знал 0

MrGluck Форумчанин 8216 / 5047 / 1437 Регистрация: 29.11.2010 Сообщений: 13,453
	29.04.2013, 16:55	11
	Делается все так: берется массив, заполняется всеми возможными значениями, далее с помощью std::random_shuffle перемешивается, и, если нам нужно получить новое "неповторяющееся число" - берем следующий элемент массива, сдвигая индекс. Я уже раз 5 отвечал на данный вопрос, не верю, что в поиске не было результатов. 0

Ternsip 670 / 198 / 29 Регистрация: 10.05.2012 Сообщений: 595
	29.04.2013, 17:01	14
	MrGluck, в Microsoft Visual C++ 2012 уже не нужно 0

MrGluck Форумчанин 8216 / 5047 / 1437 Регистрация: 29.11.2010 Сообщений: 13,453
	29.04.2013, 17:07	15
	Ternsip, ничто не гарантирует, что данные хедеры подключатся какими-то косыми-кривыми путями. Если используете функцию из файла - укажите явно где её искать. Если что, mingw не пропустит random_shuffle, а gcc еще и на srand ругнется. Добавлено через 1 минуту Кстати, правила п.5.10 прочтите. Как бы ни хотелось - но закон есть закон. 1

@Shef4u 15 / 15 / 4 Регистрация: 31.10.2011 Сообщений: 116
	01.05.2013, 21:42 [ТС]	16
	Сообщение от MrGluck Делается все так: берется массив, заполняется всеми возможными значениями, далее с помощью std::random_shuffle перемешивается, и, если нам нужно получить новое "неповторяющееся число" - берем следующий элемент массива, сдвигая индекс. Я уже раз 5 отвечал на данный вопрос, не верю, что в поиске не было результатов. спасибо, но что делать если всеможможных значений 36 и больше? не записывать же все в массив. и что вы имели ввиду под сдвигом индекса? побитовое? >> 0

@0x10 3258 / 2060 / 351 Регистрация: 24.11.2012 Сообщений: 4,909
	01.05.2013, 21:47	17
	Сообщение от Shef4u спасибо, но что делать если всеможможных значений 36 и больше? Мелочевка. Сообщение от Shef4u и что вы имели ввиду под сдвигом индекса? побитовое? >> Уже столько раз обсасывалось, что даже отвечать лень... У тебя есть массив array из N случайных чисел. Если нужно K чисел, то выбираешь array[i] где i = [0..K]. Если нужно очередное число, берешь i+1. 0

MrGluck Форумчанин 8216 / 5047 / 1437 Регистрация: 29.11.2010 Сообщений: 13,453
	01.05.2013, 23:10	18
	Shef4u, вы считаете, что каждый раз тыкаться по всему массиву из n чисел, проверяя есть ли данное число в массиве и если нет - повторять операцию до посинения - лучший вариант? Нет, к сожалению более производительного решения, чем я предложил нет. Да и недолго это на ЭВМ то. Сообщение от Shef4u сдвигом индекса инкремент 1

@nonedark2008 1394 / 1023 / 325 Регистрация: 28.07.2012 Сообщений: 2,813
	02.05.2013, 00:36	19
	По мне так генерировать последовательность неповторяющихся простых чисел оптимальнее всего было бы с использованием конгруэнтного метода, который замечательно описан во втором томе Кнута. 0

@Shef4u 15 / 15 / 4 Регистрация: 31.10.2011 Сообщений: 116
	03.05.2013, 11:44 [ТС]	20
	Сообщение от nonedark2008 По мне так генерировать последовательность неповторяющихся простых чисел оптимальнее всего было бы с использованием конгруэнтного метода, который замечательно описан во втором томе Кнута. спасибо. наслышан уже об этой книге от профессора который ведет теорию вероятности но все никак не дойдут руки прочесть 0