Гость
Целевая тема:
Создать новую тему:
Автор:
Форумы / C++ [игнор отключен] [закрыт для гостей] / Рандомизе... / 19 сообщений из 19, страница 1 из 1
31.05.2005, 16:27
    #33093078
XED
XED
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Рандомизе...
Господа программисты!
Нужен алгоритм. Суть такова: заполнить массив случайными(!) числами от 0 до N, где N - число элементов в массиве. Главное условие - элементы массива не повторяются!
И ещё. Написать-то алгоритм - не сложно, но хотелось бы (а точнее сказать НЕОБХОДИМО), чтобы он не тормозил при большом N. Т.е. был максимально возможно рациональным...
Вот, собственно и всё. Думаю, что вам самим будет это (имеется ввиду процесс оптимизации) интересно.
...
Рейтинг: 0 / 0
31.05.2005, 19:49
    #33093535
maXmo
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Рандомизе...
погугли генератор случайных чисел. Поскольку криптостойкость тебе не нужна, бери самый простой алгоритм регистра сдвига. Тебе хватит. Он же будет и самым быстрым.
------------------
- А как в Интеpнете pаботать? - Сначала нужно узнать, что вам нужно rtfm
...
Рейтинг: 0 / 0
01.06.2005, 07:20
    #33093802
Карабас Барабас
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Рандомизе...
авторзаполнить массив случайными(!) числами от 0 до N, где N - число элементов в массиве. Главное условие - элементы массива не повторяются

заполни попрядку и перемешай
...
Рейтинг: 0 / 0
01.06.2005, 10:23
    #33094054
Ggg_old
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Рандомизе...
Еще в добавок..
Давным давно, на программируемом калькуляторе (МК61) была такая игра - морской бой, - аналог игры на листочке но только для однотрубных кораблей. Как вы думаете калькулятор, у которого память была на 10 чисел мог стрелять по полю 10x10 и при этом не бить в одно поле за игру по 2 и более раза?
Ответ: использовался генератор случайных чисел такой, что он генерил первых 100 неповторяющихся случайных чисел.

все наши на www.corba.kubsu.ru
...
Рейтинг: 0 / 0
01.06.2005, 10:55
    #33094174
Землекоп
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Рандомизе...
Ggg_oldпо полю 10x10
По биту на поле - это всего сто бит. Какая была разрядность регистра? Если 32 бита, то 3-х регистров хватит.
...
Рейтинг: 0 / 0
01.06.2005, 10:57
    #33094181
Карабас Барабас
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Рандомизе...
где ж ты видел МК-61 с 32-разрядными регистрами ?
...
Рейтинг: 0 / 0
01.06.2005, 10:59
    #33094191
Землекоп
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Рандомизе...
Карабас Барабасгде ж ты видел МК-61 с 32-разрядными регистрами ?

Я про двоичные разряды. Какое максимальное число можно было ввести?
...
Рейтинг: 0 / 0
01.06.2005, 11:02
    #33094203
Землекоп
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Рандомизе...
Землекоп Ggg_oldпо полю 10x10
По биту на поле - это всего сто бит. Какая была разрядность регистра? Если 32 бита, то 3-х регистров хватит.

4-х точнее
...
Рейтинг: 0 / 0
01.06.2005, 11:36
    #33094336
Карабас Барабас
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Рандомизе...
Если мне не изменяет память, то там было 8 десятичных разрядов, т.е. макс. число 99999999, хранилось все в BCD, следовательно, действительно, 32 разряда
...
Рейтинг: 0 / 0
01.06.2005, 15:24
    #33095198
Ggg_old
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Рандомизе...
Ну там программа максимум занимала 90 с копейками шагов. Выбор случайного числа с последующим парсаньем содержимого регистров для проверки поля и все это со скоростью около 2 шагов в секенду.... нет уж. Генератор случайных неповторяющихся значений - вот решение.
P.S.
И что-бы поиграться надо было программу ручками ввести, и так каждый раз. Ностальгия ...
все наши на www.corba.kubsu.ru
...
Рейтинг: 0 / 0
01.06.2005, 18:11
    #33095768
White Owl
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Рандомизе...
Ggg_oldНу там программа максимум занимала 90 с копейками шагов.
105 шагов, извините :) МК-61 и МК-52 по 105 шагов, Б3-34 и МК-54 по 98 шагов и Б3-21 кажется около сорока шагов, не помню уже :(

Ggg_oldИ что-бы поиграться надо было программу ручками ввести, и так каждый раз. Ностальгия ...
МК-52 умел запоминать программы в ППЗУ, а еще мы программы на магнитофон записывали :)
...
Рейтинг: 0 / 0
05.06.2005, 05:44
    #33101330
XED
XED
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Рандомизе...
2 Карабас Барабас: хорошо, как перемешать?
2 maXmo: посмотрел, хм... не нашёл ничего РЕАЛЬНОГО
2 остальным: блин, развели тута базар, воздух сотрясают, а у меня прога горит - числа перемешать не могу... а так как могу - не эффективно...
...
Рейтинг: 0 / 0
05.06.2005, 09:37
    #33101347
Землекоп
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Рандомизе...
XED2 Карабас Барабас: хорошо, как перемешать?
2 maXmo: посмотрел, хм... не нашёл ничего РЕАЛЬНОГО
2 остальным: блин, развели тута базар, воздух сотрясают, а у меня прога горит - числа перемешать не могу... а так как могу - не эффективно...

Сделай совсем примитивно через перемешивание, если горит.

Код: plaintext
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.
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <time.h>


main()
	{
	const int n= 7 ;
	int r[n],i,i1,i2,nt;
/*******************************************/
	srand( (unsigned)time( NULL ) );
	for(i= 0 ; i<n; ++i) r[i] = i;

	for(i= 0 ; i<n; ++i)
		{
		i1=rand()%n;
		i2=rand()%n;
		nt = r[i1];
		r[i1]=r[i2];
		r[i2]=nt;
		}
/*******************************************/
	for(i= 0 ; i<n; ++i)
		{
		printf(" %d ",r[i]);
		}
	return  0 ;
	}

...
Рейтинг: 0 / 0
06.06.2005, 03:03
    #33101782
XED
XED
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Рандомизе...
2 Землекоп: подобная идея была, но откуда уверенность в КАЧЕСТВЕННОМ перемешивании?
...
Рейтинг: 0 / 0
06.06.2005, 07:19
    #33101837
Карабас Барабас
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Рандомизе...
XEDоткуда уверенность в КАЧЕСТВЕННОМ перемешивании?
помешай подольше - будет качественнее :)
...
Рейтинг: 0 / 0
06.06.2005, 07:42
    #33101849
VNS
VNS
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Рандомизе...
Оффтоп но все таки МК-61 - понятно, хорошая вещь до сих пор где то валяется. А как правильно БЗ-34 ( бэ три - 34 ) или БЗ-34 ( бэ-зэ - 34 ) меня этот вопрос гложет класса с 5
...
Рейтинг: 0 / 0
06.06.2005, 09:34
    #33101969
Землекоп
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Рандомизе...
XED2 Землекоп: подобная идея была, но откуда уверенность в КАЧЕСТВЕННОМ перемешивании?

Виноват. Должно быть 2*n. Тогда равномерно перемешается.

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
for(i= 0 ; i< 2 *n; ++i)
		{
		i1=rand()%n;
		i2=rand()%n;
		nt = r[i1];
		r[i1]=r[i2];
		r[i2]=nt;
		}
...
Рейтинг: 0 / 0
07.06.2005, 02:11
    #33103741
XED
XED
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Рандомизе...
Пасиб, так действительно лучше...
...
Рейтинг: 0 / 0
07.06.2005, 08:54
    #33103874
MasterZiv
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Рандомизе...
Землекоп Ggg_oldпо полю 10x10
По биту на поле - это всего сто бит. Какая была разрядность регистра? Если 32 бита, то 3-х регистров хватит.
В этих калькуляторах использовалась двоично-десятичная арифметика, так что понятия "бит" там просто не было (биты конечно были, но не были программно доступными), там были десятичные разряды.
...
Рейтинг: 0 / 0
Форумы / C++ [игнор отключен] [закрыт для гостей] / Рандомизе... / 19 сообщений из 19, страница 1 из 1
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]