рассеить точки

[Mfcer__]

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

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

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

если изначально известны L, N и M

[Sla]

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

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

[npak]

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
конец цикла

[Mfcer__]

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

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

[Dimka]

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

[npak]

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

[Mfcer__]

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

если несложно
можно пример на си

[Алексей++]

Mfcer__, например

вот например (на скорую руку):

Код:

rnd=pi;

int GetRND()
{
rnd=rnd*rnd;
   {
      //тут делаем целую часть числа rnd равной 1
   }
return ((UINT)(rnd*10))%10 //первый знак после запятой
}

[Anchorite]

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

Код:

srand((unsigned int)time(NULL));

[Mfcer__]

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

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

[Алексей++]

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

[Mfcer__]

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

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

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

необходимо к этому массиву привязаться так чтобы
генерировались эти самые 0<x<n и 0<y<m
 :?

[Alf]

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

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

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

[Mfcer__]

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

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

[Dimka]

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

[Alf]

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

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

Для начала стоило бы избавиться от двумерности массива, чтобы не городить два хэша - для строк и столбцов. Если представить массив 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
...

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

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