Re: торможу...

From

Alexander Efremov (2:6090/11.9)

To

Alexey Cheglyakov

Date

2002-07-22T20:36Z

Area

RU.ALGORITHMS

 Alexey Cheglyakov (20 Jul 02/01:57) -> All
 in RU.ALGORITHMS

 AC> Есть массив из неизвестного к-ва строк. Нужно за один проход
 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)//Нахождение позиции точки
        {
        wsum+=w[i];
        i++;
        }
    }
В результате выполнения алгоритма выбранная строка будет - string[i-1]. Ну а если выбор всех строк равновероятен, то это то же самое, что все весы равны 1.
В таком случае выбираемая строка - string[rand%N].

Вот собственно говоря и всё, что я хотел сказать..
--- GoldED+/W32 1.1.4.7
 * Origin: Чем меньше женщину мы любим, тем больше устает рука. (2:6090/11.9)