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

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

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

Рандом C++
рандом C++
Рандом C++
Рандом C++
рандом C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
HighPredator
 Аватар для HighPredator
5352 / 1735 / 320
Регистрация: 10.12.2010
Сообщений: 5,120
Записей в блоге: 3
26.11.2012, 12:55     Другой рандом #2
Цитата Сообщение от taras atavin Посмотреть сообщение
У меня решение есть
Поздравляю. Цель создания этой темы какая?
ithyphallic
 Аватар для ithyphallic
14 / 14 / 1
Регистрация: 27.10.2012
Сообщений: 141
26.11.2012, 13:39     Другой рандом #3
Тема актуальна. Сейчас делаю простенькую игру, там нужно очень часто генерировать направление движения для ботов (вверх-вниз-влево-вправо), пробовал несколько рандомов, они либо не очень рандомные, либо жрут много памяти. Если поделитесь будет атлична-атлична, например
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
26.11.2012, 13:48  [ТС]     Другой рандом #4
Цитата Сообщение от HighPredator Посмотреть сообщение
Цель создания этой темы какая?
Интересуют альтернативы.
Croessmah
Модератор
Эксперт С++
 Аватар для Croessmah
11845 / 6824 / 771
Регистрация: 27.09.2012
Сообщений: 16,919
Записей в блоге: 2
Завершенные тесты: 1
26.11.2012, 13:49     Другой рандом #5
Цитата Сообщение от ithyphallic Посмотреть сообщение
там нужно очень часто генерировать направление движения для ботов
может стоит выбрать какую то точку и просчитать путь до нее заранее? Потом выбрать следующую точку и т.д.
ithyphallic
 Аватар для ithyphallic
14 / 14 / 1
Регистрация: 27.10.2012
Сообщений: 141
26.11.2012, 13:55     Другой рандом #6
Цитата Сообщение от Croessmah Посмотреть сообщение
может стоит выбрать какую то точку и просчитать путь до нее заранее? Потом выбрать следующую точку и т.д.
В моей игре есть овцы и волки. Для волков буду делать ИИ с waypoint'ами, примерно то о чем вы говорите. А овцы перемещаются рандомно на одну клеточку (аналогично как в варкрафте овцы и прочие нейтральные небоевые существа). Но я уже решил проблему, там рандом зависит в том числе от одной сложной переменной, которая зависит от сгенерированной местности. В общем загнался. Но это не по теме этой темы
taras atavin
Ушёл с форума.
 Аватар для 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
2425 / 1597 / 232
Регистрация: 24.11.2012
Сообщений: 3,919
26.11.2012, 15:39     Другой рандом #8
taras atavin, а можно описание решения русским языком, чтобы не вчитываться в код?

Если я правильно понял задание, необходимо генерировать последовательность случайных чисел из заданного диапазона, исключая повторы. Для этого достаточно использовать один массив известного размера и пару вспомогательных целочисленных переменных.
MrGluck
Ворчун
Эксперт С++
 Аватар для MrGluck
4927 / 2670 / 243
Регистрация: 29.11.2010
Сообщений: 7,429
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
Ушёл с форума.
 Аватар для 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++
рандом C++
Рандом C++

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

Или воспользуйтесь поиском по форуму:
0x10
2425 / 1597 / 232
Регистрация: 24.11.2012
Сообщений: 3,919
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     Другой рандом
Ответ Создать тему
Опции темы

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