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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
taras atavin
Ушёл с форума.
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
#1

Другой рандом - C++

26.11.2012, 12:38. Просмотров 518. Ответов 10
Метки нет (Все метки)

Есть некоторое беззнаковое целое N, нужна рандомная последовательность не повторяющихся беззнаковых целых меньше N. Длина последовательности не превышает N, но может быть меньше N, функция должна гарантировать генерацию одного члена последовательности менее, чем за 50 миллисекунд при каждом вызове, включая N-ный. После каждого вызова функции её значение используется в качестве индекса массива из N элементов-объектов, разрешается хранить в этих объектах любую необходимую функции вспомогательную информацию. Можно также использовать любые вспомогательные списки/массивы. У меня решение есть.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
26.11.2012, 12:38     Другой рандом
Посмотрите здесь:

рандом - C++
подскажите что не так #include <iostream> #include <string> #include <vector> using namespace std; int main() ...

рандом - C++
подскажите,плз,как рандомно выводить значения типа цццАцц, где ц-цифра, А-буква.

Не работает рандом - C++
Здравствуйте, я тут столкнулся с проблемой, хотел написать функцию рандома от x до y, x и y передаются как параметры в функцию, так вот,...

Структура и рандом. - C++
у меня в структуре есть пять типов данных struct Dzho { int pid; double burst; int priority; int working; int waiting; ...

Дробовой рандом - C++
Можно как то в массиве сделать дробовой ввод чисел random? a=random(100); - ввод чисел от 1 до 100, а вот как сделать дробовой?

Рандом растет - C++
srand(time(0)); int j=rand()%1000; char s="afasfa"; switch (message) /* handle the messages */ ...

Рандом rand - C++
Решаю задачу из одной книги, так там нужно чтоб пользователю выбивало число (номер счета), не обязательно рандомное, но я решил что лучше...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
HighPredator
5477 / 1843 / 343
Регистрация: 10.12.2010
Сообщений: 5,434
Записей в блоге: 3
26.11.2012, 12:55     Другой рандом #2
Цитата Сообщение от taras atavin Посмотреть сообщение
У меня решение есть
Поздравляю. Цель создания этой темы какая?
ithyphallic
14 / 14 / 1
Регистрация: 27.10.2012
Сообщений: 141
26.11.2012, 13:39     Другой рандом #3
Тема актуальна. Сейчас делаю простенькую игру, там нужно очень часто генерировать направление движения для ботов (вверх-вниз-влево-вправо), пробовал несколько рандомов, они либо не очень рандомные, либо жрут много памяти. Если поделитесь будет атлична-атлична, например
taras atavin
Ушёл с форума.
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
26.11.2012, 13:48  [ТС]     Другой рандом #4
Цитата Сообщение от HighPredator Посмотреть сообщение
Цель создания этой темы какая?
Интересуют альтернативы.
Croessmah
Модератор
Эксперт CЭксперт С++
13063 / 7326 / 817
Регистрация: 27.09.2012
Сообщений: 18,085
Записей в блоге: 3
Завершенные тесты: 1
26.11.2012, 13:49     Другой рандом #5
Цитата Сообщение от ithyphallic Посмотреть сообщение
там нужно очень часто генерировать направление движения для ботов
может стоит выбрать какую то точку и просчитать путь до нее заранее? Потом выбрать следующую точку и т.д.
ithyphallic
14 / 14 / 1
Регистрация: 27.10.2012
Сообщений: 141
26.11.2012, 13:55     Другой рандом #6
Цитата Сообщение от Croessmah Посмотреть сообщение
может стоит выбрать какую то точку и просчитать путь до нее заранее? Потом выбрать следующую точку и т.д.
В моей игре есть овцы и волки. Для волков буду делать ИИ с waypoint'ами, примерно то о чем вы говорите. А овцы перемещаются рандомно на одну клеточку (аналогично как в варкрафте овцы и прочие нейтральные небоевые существа). Но я уже решил проблему, там рандом зависит в том числе от одной сложной переменной, которая зависит от сгенерированной местности. В общем загнался. Но это не по теме этой темы
taras atavin
Ушёл с форума.
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
26.11.2012, 14:21  [ТС]     Другой рандом #7
Моё решение основано на помеси массива с кольцевым списком:
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
37
38
39
40
class TItem
{
 ...
 public:
  bool Flag;
  TItem *Next;
  TItem *Previus;
};
TItem Array[60];
void Init (TItem *Array, unsigned int N) // Вызывается перед первым доступом к массиву
{
 TItem *p;
 Array->Previus=Array+N-1;
 Array->Previus->Next=Array;
 for (p=Array+N-2; p>Array; --p)
 {
  p->Next=p+1;
  p->Previus=p-1;
 }
 for (p=Array+N-1; p>=Array; --p)
 {
  p->Flag=false;
 }
}
unsigned int GetIndex(TItem *Array, unsigned int N)
{
 unsigned int Index;
 TItem *p;
 Index=rnd%N;
 p=Array+Index;
 if (p->Flag)
 {
  p->Previus->Next=p->Next;
  p->Next->Previus=p->Previus;
  p=p->Next;
  Index=p-Array;
 }
 p->Flag=true;
 return Index;
}
.

Добавлено через 1 минуту
Ну и может кому будет интересно подумать над такой задачей.

Добавлено через 4 минуты
После каждого вызова GetIndex человек должен не только нажать кнопку, но ещё и подумать, это вообще то не самостоятельная задача, а подзадача в тестилке знаний. Тестовую форму допуска/зачёта/экзамена знаете? Ну вот, прога в целом реализует её. Поэтому пользователь будет тормозить по полой и вся система будет работать целую пару. При любой скорости счёта.
0x10
2459 / 1631 / 238
Регистрация: 24.11.2012
Сообщений: 4,013
26.11.2012, 15:39     Другой рандом #8
taras atavin, а можно описание решения русским языком, чтобы не вчитываться в код?

Если я правильно понял задание, необходимо генерировать последовательность случайных чисел из заданного диапазона, исключая повторы. Для этого достаточно использовать один массив известного размера и пару вспомогательных целочисленных переменных.
MrGluck
Модератор
Эксперт CЭксперт С++
7185 / 4351 / 634
Регистрация: 29.11.2010
Сообщений: 11,843
26.11.2012, 16:35     Другой рандом #9
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <iostream>
#include <algorithm>
#include <iterator>
#include <numeric>
 
int main()
{
    int N;
    std::cin>> N;
    std::vector<int> v(N);
    std::iota(v.begin(), v.end(), 0);
    std::random_shuffle(v.begin(), v.end());
    std::copy(v.begin(), v.end(), std::ostream_iterator<int> (std::cout, " ") );
    return 0;
}
taras atavin
Ушёл с форума.
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
26.11.2012, 16:50  [ТС]     Другой рандом #10
Цитата Сообщение от 0x10 Посмотреть сообщение
taras atavin, а можно описание решения русским языком, чтобы не вчитываться в код?
Одни и те же элементы одновременено принадлежат массиву и двусвязному циклическому списку, в памяти располагаются последовательно и без промежутков, как в массиве, но соединены указателями, снабжены флагами, при каждой выборке индекса элемента проверяется, выдавался ли этот индекс, если выдавался, то выдаётся индекс следующего элемента списка, для чего по индексу вычисляется указатель, потом по этому указателю читается указатель на следующий элемент списка, а по этому указателю снова вычисляется индекс, кроме того, при всякой выборке индекса он удаляется из списка, но не из массива. Немного прогнал.
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
37
38
39
40
class TItem
{
 ...
 public:
  bool Flag;
  TItem *Next;
  TItem *Previus;
};
TItem Array[60];
void Init (TItem *Array, unsigned int N) // Вызывается перед первым доступом к массиву
{
 TItem *p;
 Array->Previus=Array+N-1;
 Array->Previus->Next=Array;
 for (p=Array+N-2; p>Array; --p)
 {
  p->Next=p+1;
  p->Previus=p-1;
 }
 for (p=Array+N-1; p>=Array; --p)
 {
  p->Flag=false;
 }
}
unsigned int GetIndex(TItem *Array, unsigned int N)
{
 unsigned int Index;
 TItem *p;
 Index=rnd%N;
 p=Array+Index;
 while (p->Flag)
 {
  p=p->Next;
  Index=p-Array;
 }
 p->Previus->Next=p->Next;
 p->Next->Previus=p->Previus;
 p->Flag=true;
 return Index;
}
Добавлено через 1 минуту
N не может быть большим.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
26.11.2012, 18:05     Другой рандом
Еще ссылки по теме:

Массив и рандом - C++
2. Дан одномерный массив, состоящий из N целочисленных элементов. 2.1. Заполнить массив случайными числами. 2.2. Найти минимальный...

Не повторяющий рандом - C++
Переменная rnd генерирует числа от 1 до 5 Как сделать, чтобы при выводе в консоли цифры не повторялись?

Подтормаживающий рандом - C++
Сделал простую змейку. #include &lt;iostream&gt; #include &lt;Windows.h&gt; #include &lt;cstdlib&gt; #include &lt;ctime&gt; #include &lt;conio.h&gt; enum...

Рандом в табилце - C++
Народ я только только начал учить C++ работаю в qt cretor вопрос такой: Есть таблица 10 на 10 как сделать так что бы в ней рандомно...

символы и рандом - C++
Здравствуйте, у меня пара вопросов: 1. Надо выдать символы: сердечко,крест,пика,буби. (искал как выводить через юникод, но не...


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

Или воспользуйтесь поиском по форуму:
0x10
2459 / 1631 / 238
Регистрация: 24.11.2012
Сообщений: 4,013
26.11.2012, 18:05     Другой рандом #11
Звучит... Сложновато.
Одно решение с std::random_shuffle уже написали выше. Если нужна вся последовательность целиком, ничего больше и не нужно придумывать. Если же нужна только часть последовательности и не хочется перемешивать весь массив, можно поступить так:
1. Берем массив объектов array.
2. r = размер массива.
3. rand_index = случайное число из [0, r).
4. Меняем местами объекты с полученным случайным значением и последний: swap(array[rand_index], array[r - 1])
5. r = r - 1
При следущей попытке получить случайный объект индекс будет выбираться снова из интервала [0, r), что не затронет уже выбранные ранее объекты.
Yandex
Объявления
26.11.2012, 18:05     Другой рандом
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru