ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Andrew Plyako                        2:5030/922.20  10 Jan 2002  07:28:06
 To : Sergey Popkov
 Subject : дайте алгоритм, plz!
 -------------------------------------------------------------------------------- 
 

 
  SP>  имеется матрица, пусть 10x10, в которой заложены определеные
  SP> неповторяющиеся числа (целые числа), причем каждое ичсло в своей
  SP> ячейке.. необходимо эти числа как бы размешать и поместить в матрицу
  SP> (в другую, для простоты) случайным образом..
 
 Для матрицы или для отрезка ты это делаешь, на самом деле не важно.
 Занумеруем все ячейки матрицы (в твоем случае -- числами от 1 до 100). Hапример,
 построчно (первая строка -- 1..10, вторая -- 11..20 и т.д.)
 
 Тогда алгоритм такой (считается, что у нас есть датчик псевдослучайных чисел):
 Получаем A1 -- случайное число от 1 до 100. Число из ячейки 1 оригинальной
 матрицы записываем в ячейку под номером A1 матрицы результата
 Получаем A2 -- случайное число из [1..100]/[A1] (то есть случайное число из
 множества 1..A1-1,A1+1..100). Число из ячейки 2 оригинальной матрицы записываем 
 в ячейку под номером A2 матрицы результата
 Получаем A3 -- случайное число [1..100]/[A1,A2]. Число из ячейки 3 оригинальной 
 матрицы записываем в ячейку под номером A3 матрицы результата.
 И т.д.
 
 Таким образом (если считать датчик случ.чисел непогрешимым) любая конкретная
 матрица может быть получена с вероятностью 1/(100!). То есть, наше
 преобразование равновероятно даст одну из возможных матриц. То есть, это
 "случайное в обывательском смысле" преобразование.
 
 Предвосхищаю вопрос, как получать случайное число из множества вида [1..N]/[..]
 Hапример так (здесь удобно воспользоваться синтаксисом паскаля):
 
 function MyRandom(const Range: byte; const NotInclude: set of byte): byte;
 { NotInclude - множество чисел, которые нельзя получить в качестве ответа
   Range - мощность target-множества,
           то есть 100 минус число элементов в NotInclude              }
 var i, result: byte;
 begin
   // Если не ошибаюсь, random выдает число от 0 до X-1.
   result := random(Range)+1;
   i := 1;
   while i<= result do
    begin
     if i in NotInclude then inc(result);
     inc(i);
    end;
    MyRandom := result;
 end;
 
 Таким образом, сама программа выглядит так:
 NotInclude := [];
 for i:=1 to 100 do
   begin
    CurCell := MyRandom(101-i, NotInclude);
    Ячейку i оригинальной матрицы записать в ячейку CurCell итоговой матрицы;
    NotInclude := NotInclude + [CurCell];
   end;
 Вот. Это простейший алгоритм. Есть более элегантный алгоритм "перетасовки"
 матрицы прямо на месте (то есть, без введения дополнительной итоговой матрицы), 
 которая использует только простейший генератор случ.чисел (без всяких
 премудростей, типа MyRandom). Если интересно -- пиши.
 
 Andrew
 
 ---
  * Origin: Думать безОбразно -- безобрАзно!!! (2:5030/922.20)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор 

Тема:    Автор:    Дата:    дайте алгоритм, plz!   Sergey Popkov   09 Jan 2002 02:59:43   Hа: дайте алгоритм, plz!   Alex Chudnovsky   09 Jan 2002 14:44:12   дайте алгоритм, plz!   Andrew Plyako   10 Jan 2002 07:28:06   Re: дайте алгоритм, plz!   Sergey Politov   12 Jan 2002 05:43:26   Re: дайте алгоритм, plz!   Sergey Politov   10 Jan 2002 06:08:52   дайте алгоритм, plz!   Andrew Plyako   11 Jan 2002 01:30:44   Re: дайте алгоритм, plz!   Sergey Politov   12 Jan 2002 05:31:04   дайте алгоритм, plz!   Andrew Plyako   13 Jan 2002 01:49:00   Re: дайте алгоритм, plz!   Sergey Politov   14 Jan 2002 05:51:37   дайте алгоритм, plz!   Andrew Plyako   14 Jan 2002 16:15:44   Re: дайте алгоритм, plz!   Sergey Politov   15 Jan 2002 05:07:06   Re^2: дайте алгоритм, plz!   Sergey Politov   12 Jan 2002 09:35:44   Re: дайте алгоритм, plz!   Vasily Shmelev   10 Jan 2002 18:25:23   дайте алгоритм, plz!   Nickita A Startcev   10 Jan 2002 22:36:00   дайте алгоритм, plz!   Anton Dorofeev   11 Jan 2002 14:48:20