Форум программистов «Весельчак У»
  *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

  • Рекомендуем проверить настройки временной зоны в вашем профиле (страница "Внешний вид форума", пункт "Часовой пояс:").
  • У нас больше нет рассылок. Если вам приходят письма от наших бывших рассылок mail.ru и subscribe.ru, то знайте, что это не мы рассылаем.
   Начало  
Наши сайты
Помощь Поиск Календарь Почта Войти Регистрация  
 
Страниц: [1]   Вниз
  Печать  
Автор Тема: рассеить точки  (Прочитано 15974 раз)
0 Пользователей и 1 Гость смотрят эту тему.
Mfcer__
Команда клуба

ru
Offline Offline

« : 27-10-2004 13:50 » 

есть некоторая матрица, двумерный массив NxM
есть некоторая последовательность данных (длина L < N*M)

необходимо рассеить данные по этому двумерному массиву, причем равномерно
и так чтобы потом их можно было прочитать

то есть нужен закон, формула рассеивания

если изначально известны L, N и M
Записан
Sla
Команда клуба

ua
Offline Offline
Пол: Мужской

WWW
« Ответ #1 : 27-10-2004 14:13 » 

тебе нужен закон распределения.
что такое рассеять равномерно?

выбираешь случайный закон - рассеиваешь равномерно по случайному закону
Записан

Мы все учились понемногу... Чему-нибудь и как-нибудь.
npak
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #2 : 27-10-2004 15:01 » 

Mfcer__, пусть rand_int(min, max) возвращает равномерно распределённое случайное целое число не меньше min и меньше max.
Код:
повторить L раз
   do
     z = rand_int(0, M*N).

     X = z mod N (остаток от деления) -- номер колонки,
     Y = z div N (целая часть частного) -- номер строки.
   while (позиция X,Y уже занята)

  занять позицию X,Y
конец цикла
« Последнее редактирование: 02-12-2007 16:42 от Алексей1153++ » Записан

UniTesK -- индустриальная технология надежного тестирования.

http://www.unitesk.com/ru/
Mfcer__
Команда клуба

ru
Offline Offline

« Ответ #3 : 27-10-2004 21:44 » 

а как мне потом прочитать то что я записал зная только L, N и M

то есть необходимо не просто рендомить, но еще и знать закономерность, чтобы можно было обратно прочитать рассеянные данные
Записан
Dimka
Деятель
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #4 : 28-10-2004 06:14 » 

rand() повторит последовательность при одинаковом начальном значении генератора.
Записан

Программировать - значит понимать (К. Нюгард)
Невывернутое лучше, чем вправленное (М. Аврелий)
Многие готовы скорее умереть, чем подумать (Б. Рассел)
npak
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #5 : 28-10-2004 08:33 » 

Mfcer__, сделай свой генератор псевдо-случайных чисел.  Например, посмотри у Кнута.  При каждом запуске генератор будет строить одну и ту же последовательность, поэтому таблица будет заполняться каждый раз одинаково.
Записан

UniTesK -- индустриальная технология надежного тестирования.

http://www.unitesk.com/ru/
Mfcer__
Команда клуба

ru
Offline Offline

« Ответ #6 : 28-10-2004 21:59 » 

Цитата: dimka
rand() повторит последовательность при одинаковом начальном значении генератора.


если несложно
можно пример на си
Записан
Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #7 : 29-10-2004 03:29 » 

Mfcer__, например

вот например (на скорую руку):
Код:
rnd=pi;

int GetRND()
{
rnd=rnd*rnd;
   {
      //тут делаем целую часть числа rnd равной 1
   }
return ((UINT)(rnd*10))%10 //первый знак после запятой
}
« Последнее редактирование: 02-12-2007 16:45 от Алексей1153++ » Записан

Anchorite
Гость
« Ответ #8 : 29-10-2004 16:17 » 

В stdlib.h есть две функции - rand и srand.
С помощью srand можно установить новую последовательнось псевдослучайных чисел. Обычно это делается так:

Код:
srand((unsigned int)time(NULL));
« Последнее редактирование: 02-12-2007 16:46 от Алексей1153++ » Записан
Mfcer__
Команда клуба

ru
Offline Offline

« Ответ #9 : 29-10-2004 22:13 » 

Цитата: npak
Mfcer__,  При каждом запуске генератор будет строить одну и ту же последовательность, поэтому таблица будет заполняться каждый раз одинаково.


как это доказывается, то есть почему это так а не иначе
и будет ли это работать с любым генератором
Записан
Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #10 : 30-10-2004 02:48 » 

Mfcer__, это доказывается тем, что компутер - вещь очень логичная и дискретная, и одни и те же вычисления приведут к одинаковому результату
Записан

Mfcer__
Команда клуба

ru
Offline Offline

« Ответ #11 : 30-10-2004 21:32 » 

даже на разном железе? то есть на разных компьютерах?

И ДОПОЛНЕНИЕ:

допустим дано не только l, n и m
а еще некоторый массив данных - char к примеру

необходимо к этому массиву привязаться так чтобы
генерировались эти самые 0<x<n и 0<y<m
 :?
Записан
Alf
Гость
« Ответ #12 : 30-10-2004 22:16 » 

Mfcer__, вообще-то поставленная задача весьма смахивает на хэширование. Поэтому вместо того, чтобы колдовать с генератором псевдослучайных последовательностей (который в общем-то предназначен для несколько другой цели), я бы воспользовался хэш-функцией, которая отображает входную последовательность на числовой отрезок N*M (либо исходя из номера значения, либо из величины самого значения, тут уж трудно подсказать оптимальное решение, не зная деталей задачи).

Во-первых, это позволит организовать произвольный доступ к элементам рассеянной последовательности (в случае, если она достаточно велика, а обращений к данным много, последовательный перебор псевдослучайной последовательности может оказаться не столь уж безобидной затеей). Во-вторых, алгоритм не будет зависеть от реализации генератора случайных чисел в данной системе программирования.

Если не знаком с хэш-функциями, рекомендую посмотреть третий том Кнута. Или же, если цель этой затеи - путем перемешивания спрятать данные от непосвященных, а тот самый массив char является ключом или паролем для доступа, попробовать какую-либо из хэш-функций, используемых в криптографии.
Записан
Mfcer__
Команда клуба

ru
Offline Offline

« Ответ #13 : 31-10-2004 01:28 » 

Цитата

на числовой отрезок N*M (либо исходя из номера значения, либо из величины самого значения,


а можно алгоритм, что нужно сделать чтобы таким образом получить координаты
не важно из чего исходя подойдет любой способ
Записан
Dimka
Деятель
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #14 : 31-10-2004 09:59 » 

Mfcer__, в простейшем случае определяешь диапазон входной последовательности и делишь его на N * M участков. Далее для каждого элемента последовательности определяешь, в какой из участков он попал, и пишешь туда. Числа  от 1 до N*M определяют номер участка. Хэш в общем случае подразумевает, что у тебя может несколько элементов попасть в один и тот же участок, тогда внутри участка они образуют массив. Удачный выбор хэш-функции позволяет минимизировать массивы, обеспечивая более быстрый доступ к элементам последовательности. Структура данных может быть представлена как список хэш-ключей, где в каждом ключе хранится список значений, относящихся к этому ключу (список списков, можно массив массивов).
Записан

Программировать - значит понимать (К. Нюгард)
Невывернутое лучше, чем вправленное (М. Аврелий)
Многие готовы скорее умереть, чем подумать (Б. Рассел)
Alf
Гость
« Ответ #15 : 31-10-2004 21:58 » 

Цитата: Mfcer__
а можно алгоритм, что нужно сделать чтобы таким образом получить координаты
не важно из чего исходя подойдет любой способ
Если исходить из номера элемента, я бы для простоты взял такую функцию.

Для начала стоило бы избавиться от двумерности массива, чтобы не городить два хэша - для строк и столбцов. Если представить массив N*M как линейный соответствующей длины, то можно будет обойтись одним-единственным индексом.

Теперь осталось определить саму хэш-функцию. Предположим для простоты, что размер нашего одномерного массива кратен степени 2 (скажем, 2^n). Тогда,  если мы хотим распределить элементы данных максимально равномерно, имеет смысл инвертировать порядок n первых бит индекса.

Пример: n=8, число элементов массива N=2^8=256. Тогда хэш-функция H(i) будет выглядеть так:

Код:
H(0) = H(00000000) = 00000000 = 0
H(1) = H(00000001) = 10000000 = 128
H(2) = H(00000010) = 01000000 = 64
H(3) = H(00000011) = 11000000 = 192
...

То есть сначала массив делится пополам, потом каждая половина - еще раз пополам и т.д.

Если задача все же обязательно требует, чтобы массив был двумерный, то придется поделить значение хэш-функции на длину строки массива. Тогда частное даст номер строки, а остаток от деления - номер столбца.
« Последнее редактирование: 02-12-2007 16:47 от Алексей1153++ » Записан
Страниц: [1]   Вверх
  Печать  
 

Powered by SMF 1.1.21 | SMF © 2015, Simple Machines