ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Alexander Efremov                    2:6090/11.9    22 Jul 2002  20:36:00
 To : Alexey Cheglyakov
 Subject : Re: торможу...
 -------------------------------------------------------------------------------- 
 

  Alexey Cheglyakov (20 Jul 02/01:57) -> All
  in RU.ALGORITHMS
 
  AC> Есть массив из неизвестного к-ва строк. Hужно за один проход
  AC> случайным образом выбрать одну строку. Вероятность выбора для всех
  AC> строк одинаковая.
 
  AC> Усложнение задачи - для каждой строки имеется весовой коэфициент
  AC> (целое число), повышающий вероятность выбора этой строки.
 
     Я встречался с такой проблемой, когда писал генератор ников, смысл был
 такой: задавалась произв. длина имени и буквы в имени выбирались поочерёдно
 гласные и согласные. Сначала я выбирал буквы с помощью счётчика случайных чисел,
 но потом решил приблизить это дело к русскому языку, взял "Войну и мир" в
 электронном варианте, и провёл анализ количества в нём букв алфавита, результаты
 я занёс в массив весов. Дальше я использовал такой принцип:
 если на линейке отметить n-1 чёрточек и произвольно ткнуть в любое место на
 линейке, то выбранная область будет хар-ся своей шириной(весом), чем больше
 область, тем больше вероятность попадения в неё, и наоборот.
 
 |________|____|__|_________|_______|_____|_|_______|______|______|_______|____|
                                                             ^
 
 В приложении к твоему случаю алгоритм на Сях будет примерно такой:
 
     #include <stdlib.h>
 
     const N=10;
     void main(void)
     {
     char string[N][100];
     int w[N],wsum,i,chance;
 
 ..Инициализация строк и весов к ним..
 
     for(i=0;i<N;i++) wsum+=w[i]; //Подсчёт суммы всех весов
     chance=rand%wsum;//Выбор произвольной точки
     i=0;
     wsum=0;
     while(chance>=wsum)//Hахождение позиции точки
         {
         wsum+=w[i];
         i++;
         }
     }
 В результате выполнения алгоритма выбранная строка будет - string[i-1]. Hу а
 если выбор всех строк равновероятен, то это то же самое, что все весы равны 1.
 В таком случае выбираемая строка - string[rand%N].
 
 Вот собственно говоря и всё, что я хотел сказать..
 --- GoldED+/W32 1.1.4.7
  * Origin: Чем меньше женщину мы любим, тем больше устает рука. (2:6090/11.9)
 
 

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

Тема:    Автор:    Дата:    торможу...   Alexey Cheglyakov   20 Jul 2002 01:57:34   торможу...   Max Alekseyev   19 Jul 2002 17:52:02   торможу...   Georgy Plechanov   20 Jul 2002 23:52:06   Re: торможу...   Alexander Efremov   22 Jul 2002 20:36:00