ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Boris Sivko                          2:452/26.14    31 Aug 2001  17:02:56
 To : Sergey Kabikov
 Subject : Hужно решение
 -------------------------------------------------------------------------------- 
 

 
  По данным контрразведки я узнал, что в Четверг Август 30 2001 14:59, Sergey
 Kabikov писал Boris Sivko:
 
  A>>> Есть массив целых чисел от 0 до N (на практике N не больше 100).
  A>>> Числа в массиве расположенны по порядку (0-100). Требуется
  A>>> перемешать массив произвольным образом. Скорость критична (счет
  A>>> идет на ms).
  BS>> ------ From: Leonid Troyanovsky
  BS>>   for i := Low(a) to High(a) do
  BS>>     begin
  BS>>       idx := Low(a) + Random(SizeOf(a));
  BS>>       tmp := a[i];
  BS>>       a[i] := a[idx];
  BS>>       a[idx] := tmp;
  BS>>     end;
  SK> Это не совсем оптимальный способ. Легко заметить,
 
                                        ^^^^^^^^^^^^^^
 Легко заметить, что Земля плоская. Hо оказывается, что она как суслик.
 
  SK> что N перестановок хорошо перемешают массив из N элементов не всегда.
  SK> Я бы сделал так :
  SK> for i := Low(a) to High(a)-1 do begin
  SK>    idx := i + Low(a) + Random(SizeOf(a) - i);
  SK> и далее по тексту.
  SK> Разница в том, что на каждом шаге фиксируется один случайно выбранный
  SK> элемент массива, который в дальнейших перестановках не участвует.
  SK> IMHO статистически это правильнее.
 
   Чтобы доказать правильность статистически, нужно сделать кучу опытов,
 прогенерить миллиарды массивов и показать, что все параметры(матожидание,
 независимость событий, дисперсия и пр..) являются такими же, как и у
 действительно случайно перемешанного массива. Либо доказать это аналитически.
 
   В этом примере ты точно что-то напортачил, т.к. при массиве a:array[10..11]
 имеем:
 
   for i:=10 to 10 do idx:=10+10+Random(2-10);
 
   Hаверное это имел ввиду: idx:=i+Random(Low(a)+SizeOf(a)-i);
 
   Я бы твой способ описал как "бросаем жебий программно". ИМХО, народ поймёт.
 
         Счастливо, Sergey. Вспоминай обо мне...
 ... I'll be back...
  * Origin: Раскачаем этот мир! (2:452/26.14)
 
 

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

Тема:    Автор:    Дата:    Hужно решение   Sergey Kabikov   30 Aug 2001 14:59:54   Hужно решение   Leonid Troyanovsky   30 Aug 2001 21:35:26   Hужно решение   Boris Sivko   31 Aug 2001 17:02:56