Показать сообщение отдельно
  #30 (permalink)  
Старый 29.07.2012, 14:00
Профессор
Отправить личное сообщение для oneguy Посмотреть профиль Найти все сообщения от oneguy
 
Регистрация: 31.05.2012
Сообщений: 396

Я написал ещё один алгоритм для первой части функции - составления массива d. Первый алгоритм больше подходит для больших n/p, второй - для маленьких. В функцию добавился 4-ый необязательный параметр - номер алгоритма. Если он отсутствует - алгоритм выбирается автоматически.
function divide(a, n, m, alg) {
  if (n*m>a)
    return;
  var b=[], d=[], p=a-(m-1)*n-1;
  if (alg==1||alg!=2&&20*n>p) {
// алгоритм 1
    for (var i=0; i<p; i++)
      b[i]=i; // делаем массив b из чисел 0, 1, ..., p-1
    while (i>p-n+1) {
      var c=Math.floor(Math.random()*i); // выбираем случайный элемент из b
      d.push(b[c]);
      b[c]=b[--i]; // удаляем его, считаем, что длина массива b теперь i
    }
    d.sort(function (x, y) {
      return x-y;
    });
  } else {
// алгоритм 2
    for (i=0; i<n-1; i++) {
      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); // после этой инструкции массив d будет содержать n различных неотрицательных чисел, отсортированных по возрастанию, последнее из которых p. С помощью этого массива формируется выходной массив, для которого будем использовать переменную b заново
  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;
}
//тесты
alert(divide(130, 3, 20)+"\n"+
  divide(100, 4, 25)+"\n"+
  //divide(2000, 1000, 0)+"\n"+
  //divide(100500, 100000, 0)+"\n"+
  divide(1000000000, 3, 0)+"\n");

Последний раз редактировалось oneguy, 29.07.2012 в 21:00.
Ответить с цитированием