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

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 15, средняя оценка - 4.87
Shef4u
15 / 15 / 0
Регистрация: 31.10.2011
Сообщений: 116
15.03.2013, 21:53     Рандом без повторений #1
Здравствуйте! Искал по форуме, но так и не нашел подходящее решение такой задачи:
пользователь вводит К ПРИМЕРУ число 7. я беру от него логарифм за основанием 2 и заокругляю к большему n=ceil(log(Np)/log(2)); это выйдет n=3. ага, теперь я знаю, что мне надо 7 комбинаций по 3 символа в двочином коде не считая 000 так как всего может быть восемь: 000 111 100 101 011 001 110 010. 000 мне не надо. внимание вопрос: как это сделать через rand или как-то иначе?? вот мой код, но в нем числа повторяютя и комбинация 000 присутствует((
Код
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
Эксперт С++
 Аватар для Ev[G]eN
5093 / 1531 / 381
Регистрация: 23.01.2011
Сообщений: 3,148
15.03.2013, 22:15     Рандом без повторений #2
так?
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 / 15 / 0
Регистрация: 31.10.2011
Сообщений: 116
15.03.2013, 22:30  [ТС]     Рандом без повторений #3
Цитата Сообщение от 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 / 15 / 0
Регистрация: 31.10.2011
Сообщений: 116
15.03.2013, 22:32  [ТС]     Рандом без повторений #4
Цитата Сообщение от 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
Эксперт С++
 Аватар для Ev[G]eN
5093 / 1531 / 381
Регистрация: 23.01.2011
Сообщений: 3,148
15.03.2013, 22:34     Рандом без повторений #5
Цитата Сообщение от 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 / 15 / 0
Регистрация: 31.10.2011
Сообщений: 116
15.03.2013, 22:42  [ТС]     Рандом без повторений #6
Цитата Сообщение от 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
2426 / 1598 / 232
Регистрация: 24.11.2012
Сообщений: 3,919
16.03.2013, 07:49     Рандом без повторений #7
Shef4u, как я понимаю, диапазон значений известен, допустимые значения известны - заполняем массив и перемешиваем std::random_shuffle.


Ev[G]eN, ну вот не надо такой "угадайки". Будем кидать рандом до посинения пока не найдем неиспользованное число? И сколько раз оно сработает в ситуации, когда нужно получить случайную последовательность размером 100 со значениями в диапазоне от 0 до 99, когда остался незаполненным один последний элемент?
Vaste
1 / 1 / 0
Регистрация: 23.04.2012
Сообщений: 42
16.03.2013, 08:16     Рандом без повторений #8
Кидай сгенерированные значения в массив, чтоб смореть было или нет. Иначе никак.
olea
5 / 5 / 1
Регистрация: 30.01.2012
Сообщений: 153
28.04.2013, 13:07     Рандом без повторений #9
Shef4u, а не могли бы вы привести синтаксис де Брейновской функции?
Shef4u
15 / 15 / 0
Регистрация: 31.10.2011
Сообщений: 116
29.04.2013, 16:52  [ТС]     Рандом без повторений #10
Цитата Сообщение от olea Посмотреть сообщение
Shef4u, а не могли бы вы привести синтаксис де Брейновской функции?
если б я его знал
MrGluck
Ворчун
Эксперт С++
 Аватар для MrGluck
4928 / 2671 / 243
Регистрация: 29.11.2010
Сообщений: 7,429
29.04.2013, 16:55     Рандом без повторений #11
Делается все так:
берется массив, заполняется всеми возможными значениями, далее с помощью std::random_shuffle перемешивается, и, если нам нужно получить новое "неповторяющееся число" - берем следующий элемент массива, сдвигая индекс.

Я уже раз 5 отвечал на данный вопрос, не верю, что в поиске не было результатов.
Ternsip
 Аватар для Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
29.04.2013, 16:58     Рандом без повторений #12
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
Ворчун
Эксперт С++
 Аватар для MrGluck
4928 / 2671 / 243
Регистрация: 29.11.2010
Сообщений: 7,429
29.04.2013, 16:59     Рандом без повторений #13
Ternsip,
C++
1
2
#include <cstdlib>
#include <algorithm>
Ternsip
 Аватар для Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
29.04.2013, 17:01     Рандом без повторений #14
MrGluck, в Microsoft Visual C++ 2012 уже не нужно
MrGluck
Ворчун
Эксперт С++
 Аватар для MrGluck
4928 / 2671 / 243
Регистрация: 29.11.2010
Сообщений: 7,429
29.04.2013, 17:07     Рандом без повторений #15
Ternsip, ничто не гарантирует, что данные хедеры подключатся какими-то косыми-кривыми путями. Если используете функцию из файла - укажите явно где её искать.

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

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

Я уже раз 5 отвечал на данный вопрос, не верю, что в поиске не было результатов.
спасибо, но что делать если всеможможных значений 36 и больше? не записывать же все в массив. и что вы имели ввиду под сдвигом индекса? побитовое? >>
0x10
2426 / 1598 / 232
Регистрация: 24.11.2012
Сообщений: 3,919
01.05.2013, 21:47     Рандом без повторений #17
Цитата Сообщение от Shef4u Посмотреть сообщение
спасибо, но что делать если всеможможных значений 36 и больше?
Мелочевка.

Цитата Сообщение от Shef4u Посмотреть сообщение
и что вы имели ввиду под сдвигом индекса? побитовое? >>
Уже столько раз обсасывалось, что даже отвечать лень... У тебя есть массив array из N случайных чисел. Если нужно K чисел, то выбираешь array[i] где i = [0..K]. Если нужно очередное число, берешь i+1.
MrGluck
Ворчун
Эксперт С++
 Аватар для MrGluck
4928 / 2671 / 243
Регистрация: 29.11.2010
Сообщений: 7,429
01.05.2013, 23:10     Рандом без повторений #18
Shef4u, вы считаете, что каждый раз тыкаться по всему массиву из n чисел, проверяя есть ли данное число в массиве и если нет - повторять операцию до посинения - лучший вариант? Нет, к сожалению более производительного решения, чем я предложил нет. Да и недолго это на ЭВМ то.

Цитата Сообщение от Shef4u Посмотреть сообщение
сдвигом индекса
инкремент
nonedark2008
624 / 502 / 92
Регистрация: 28.07.2012
Сообщений: 1,343
02.05.2013, 00:36     Рандом без повторений #19
По мне так генерировать последовательность неповторяющихся простых чисел оптимальнее всего было бы с использованием конгруэнтного метода, который замечательно описан во втором томе Кнута.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
03.05.2013, 11:44     Рандом без повторений
Еще ссылки по теме:

Random, значения без повторений C++
C++ Нужно сделать рандом без повторений
Последовательность чисел без повторений C++

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

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

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