|
Сообщение от oneguy
|
|
В задаче нужно сделать, чтоб каждая возможность выпадала с одинаковой вероятностью
|
O RLY?
|
Сообщение от leny
|
|
Необходимо написать функцию деления числа "A" на несколько случайных, сумма которых в итоге будет числом "A".
|
Во-первых, "на несколько случайных" != "с равным шансом на одну из всех возможных комбинаций"
Во-вторых, ничего не сказано о том, что последовательность имеет значение.
А поэтому:
|
Сообщение от oneguy
|
|
Не нужно подгонять распределение под ваше решение
|
- что в такой же степени касается и вас.
Но по большому счету, пока ТС не озвучил способ распределения вероятностей - любое решение, удовлетворяющее исходным условиям, будет технически правильным.
Расходимость наших решений в том, что у вас количество возможных ситуаций внутри функции с учетом динамики их возникновения равно
(a - m*n + n-1)! / (a - m*n)!
а у меня
(a - m*n + 1)^(n-1) * (n-1)!
Поэтому у вас все комбинации равновероятны, а у меня нет.
А вот
ваша последняя функция мне понравилась.
Я тоже решил попробовать двоичный поиск и комбинаторику, чтобы сделать все комбинации равновероятными. И хотя, ради чистоты эксперимента, в вашу функцию я нарочно не подглядывал, но всё же наши решения оказались очень похожи. Сравнение буду делать только на двоичном поиске, поэтому первый алгоритм из вашей функции я намеренно удалил.
function divide (a, n, m) { // by oneguy
if (n*m>a) return;
var b=[], d=[], p=a-(m-1)*n-1;
for (i=0; i<n-1; i++) {
var c=Math.floor(Math.random()*(p-i));
var x=0, y=i;
while (x<y) {
var t=Math.floor((x+y)/2);
if (d[t]-t>c) y=t; else x=t+1;
}
d.splice(x, 0, c+x);
}
d.push(p);
b.length=0; b[0]=d[0]+m;
for (i=0; i<n-1; i++) b.push(d[i+1]-d[i]+m-1);
return b;
}
function SplitNum2 (a, n, m) { // by Дзен-трансгуманист
if (n < 1 || n * m > a) { return []; }
if (n == 1) { return [a]; }
var i, j, q = -1, w, e;
var r = a - (m * n) + n - 1;
var f = Math.floor(Math.random() * r);
var p = [f], s = [];
for (i=1; i<n-1; i++) {
if (!(i & (i-1))) { q++; }
j = Math.floor(Math.random() * (r-i));
if (j < f) { f = j; p.unshift(j); continue; }
w = 1 << q;
e = w >> 1;
while (e) {
if (w > i || j+w <= p[w-1]) { w -= e; }
else if (w == i || j+w < p[w]) { break; }
else { w += e; }
e >>= 1;
}
p.splice(w, 0, j+w);
}
p.push(r);
s[0] = p[0] + m;
for (i=1; i<n; i++) { s[i] = p[i] - p[i-1] + m - 1; }
return s;
}
function testPerformance (a, n, m, iterations) {
var i, j, fn, time1, time2;
var fnarr = [ "divide", "SplitNum2" ];
var result = "a = " + a + "; n = " + n + "; m = " + m + "; ( " + iterations + "x )\n\n";
function Now () { return (new Date()).getTime(); }
for (i=0; i<fnarr.length; i++) {
fn = eval(fnarr[i]);
time1 = Now();
for (j=0; j<iterations; j++) { fn(a, n, m); }
time2 = Now();
result += fnarr[i] + ": " + ((time2 - time1) / 1000).toFixed(3) + " sec.\n";
}
return result + "\n";
}
var text = "";
text += testPerformance(130, 3, 20, 10000);
text += testPerformance(130, 30, 0, 1000);
text += testPerformance(100, 4, 25, 10000);
text += testPerformance(1000, 1000, 0, 10);
text += testPerformance(1000000000, 10000, 0, 1);
alert(text);
Чот соврал - и пол-секунды не было (Опера 11.52
