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

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

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

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

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

Есть некоторое беззнаковое целое 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++
рандом C++
C++ Рандом в границах
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
HighPredator
 Аватар для HighPredator
5411 / 1794 / 327
Регистрация: 10.12.2010
Сообщений: 5,296
Записей в блоге: 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
Модератор
Эксперт CЭксперт С++
 Аватар для Croessmah
12508 / 7070 / 794
Регистрация: 27.09.2012
Сообщений: 17,461
Записей в блоге: 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
2442 / 1614 / 235
Регистрация: 24.11.2012
Сообщений: 3,962
26.11.2012, 15:39     Другой рандом #8
taras atavin, а можно описание решения русским языком, чтобы не вчитываться в код?

Если я правильно понял задание, необходимо генерировать последовательность случайных чисел из заданного диапазона, исключая повторы. Для этого достаточно использовать один массив известного размера и пару вспомогательных целочисленных переменных.
MrGluck
Ворчун
Эксперт CЭксперт С++
 Аватар для MrGluck
6219 / 3464 / 423
Регистрация: 29.11.2010
Сообщений: 9,176
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++ Неправильный рандом
Рандом rand C++
Рандом C++
не получается рандом C++
C++ Рандом

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

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

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