Форум: "Потрепаться";
Текущий архив: 2004.04.11;
Скачать: [xml.tar.bz2];

Вниз

задача:распределить число между элементами массива   Найти похожие ветки 

← →
q13   (2004-04-18 18:01) [0]

Здравствуйте,
Подскажите, как решить наиболее оптимально такую простую задачу:
Дано некоторое целое число (W). Надо случайным образом распределить W между элементами целочисленного массива X (X:array[1..N]) таким образом, чтобы значение каждого элемента находилось в диапазоне [Xmin,Xmax].
Понятно, что Xmin*N<=W<=Xmax*N.
Заранее благодарен

---

← →
q13   (2004-04-18 18:01) [0]

Здравствуйте,
Подскажите, как решить наиболее оптимально такую простую задачу:
Дано некоторое целое число (W). Надо случайным образом распределить W между элементами целочисленного массива X (X:array[1..N]) таким образом, чтобы значение каждого элемента находилось в диапазоне [Xmin,Xmax].
Понятно, что Xmin*N<=W<=Xmax*N.
Заранее благодарен

---

← →
default ©   (2004-04-18 19:23) [1]

покажите своё "неоптимальное" решение этой "простой" задачи

---

← →
default ©   (2004-04-18 19:23) [1]

покажите своё "неоптимальное" решение этой "простой" задачи

---

← →
default ©   (2004-04-18 19:44) [2]

чтобы работало быстро можно поступить так
получаем среднее AVG = W div N, остаток OST = W mod N
генерируем первое значение произвольно из отрезка [X_min;X_max]
обозначим его FirstRandom
следующее же находим из соотношения 2*AVG - FirstRandom
и тд. с остатком думаю сообразите что делать
например, остаток 1 даёт возможность написать(только однажды)
2*AVG - FirstRandom + 1
то есть первое значение получаем случайно, следующее полностью определяется предыдущим и тд

---

← →
default ©   (2004-04-18 19:44) [2]

чтобы работало быстро можно поступить так
получаем среднее AVG = W div N, остаток OST = W mod N
генерируем первое значение произвольно из отрезка [X_min;X_max]
обозначим его FirstRandom
следующее же находим из соотношения 2*AVG - FirstRandom
и тд. с остатком думаю сообразите что делать
например, остаток 1 даёт возможность написать(только однажды)
2*AVG - FirstRandom + 1
то есть первое значение получаем случайно, следующее полностью определяется предыдущим и тд

---

← →
default ©   (2004-04-18 19:57) [3]

+
первое значение должно быть таким
2 * AVG - FirstRandom >= X_min
(мда, на этом потеряем скорость...)
хотя какой бы способ генерации Вы не придумали всё равно каких-либо проверок не избежать

---

← →
default ©   (2004-04-18 19:57) [3]

+
первое значение должно быть таким
2 * AVG - FirstRandom >= X_min
(мда, на этом потеряем скорость...)
хотя какой бы способ генерации Вы не придумали всё равно каких-либо проверок не избежать

---

← →
Юрий Зотов ©   (2004-04-18 19:57) [4]

Похоже, что для СФОРМУЛИРОВАННОЙ задачи самое быстрое и простое (и в этом смысле самое оптимальное) решение - тривиально: все элементы массива равны W.

Вряд ли такое решение Вас устроит. Но, если Вы хотите получить другие варианты, то Вам, вероятно, нужно пояснить, что же означает "распределить целое число между элементами массива".

Записать в каждый элемент этого массива какое-то другое число, полученное исходя из исходного числа и какого-то закона его распределения? Если да, то из какого именно закона? Если нет, то что тогда имелось в виду?

Нужно ли при формировании массива сортировать его? Если да, то каким образом?

И еще - что означает "оптимальное"? Самое простое в смысле алгоритма? Самое быстрое в смысле машинного времени? Требующее минимума памяти? Еще что-то?

И т.д.

---

← →
Юрий Зотов ©   (2004-04-18 19:57) [4]

Похоже, что для СФОРМУЛИРОВАННОЙ задачи самое быстрое и простое (и в этом смысле самое оптимальное) решение - тривиально: все элементы массива равны W.

Вряд ли такое решение Вас устроит. Но, если Вы хотите получить другие варианты, то Вам, вероятно, нужно пояснить, что же означает "распределить целое число между элементами массива".

Записать в каждый элемент этого массива какое-то другое число, полученное исходя из исходного числа и какого-то закона его распределения? Если да, то из какого именно закона? Если нет, то что тогда имелось в виду?

Нужно ли при формировании массива сортировать его? Если да, то каким образом?

И еще - что означает "оптимальное"? Самое простое в смысле алгоритма? Самое быстрое в смысле машинного времени? Требующее минимума памяти? Еще что-то?

И т.д.

---

← →
default ©   (2004-04-18 20:07) [5]

Юрий Зотов ©   (18.04.04 19:57) [4]
иcходя из условия "Xmin*N<=W<=Xmax*N."
ему надо что-то вроде этого
если
X_min=21, X_max=33, N=3, 63<=W<=99
пусть W=76
например, такая послед-ть нам подойдёт
25 25 26

---

← →
default ©   (2004-04-18 20:07) [5]

Юрий Зотов ©   (18.04.04 19:57) [4]
иcходя из условия "Xmin*N<=W<=Xmax*N."
ему надо что-то вроде этого
если
X_min=21, X_max=33, N=3, 63<=W<=99
пусть W=76
например, такая послед-ть нам подойдёт
25 25 26

---

← →
Jack128 ©   (2004-04-18 20:23) [6]

например  такая процедурка тоже подойдет
procedure Test(out arr: array of Integer; W, XMin, XMax: Cardinal);
var
 t: Cardinal;
 i: integer;
begin
 t := W;
 for i := Low(arr) to High(arr) - 1 do
 begin
   arr[i] := Random(XMax - XMin) + XMin;
   dec(t, arr[i]);
 end;
 arr[High(arr)] := t;
end;

---

← →
Jack128 ©   (2004-04-18 20:23) [6]

например  такая процедурка тоже подойдет
procedure Test(out arr: array of Integer; W, XMin, XMax: Cardinal);
var
 t: Cardinal;
 i: integer;
begin
 t := W;
 for i := Low(arr) to High(arr) - 1 do
 begin
   arr[i] := Random(XMax - XMin) + XMin;
   dec(t, arr[i]);
 end;
 arr[High(arr)] := t;
end;

---

← →
nikkie ©   (2004-04-18 20:26) [7]

>jack128
последний элемент легко может выйти за границы диапазона.

---

← →
nikkie ©   (2004-04-18 20:26) [7]

>jack128
последний элемент легко может выйти за границы диапазона.

---

← →
default ©   (2004-04-18 20:30) [8]

вместо OST = W mod N
есте-нно OST = W - AVG * N

---

← →
default ©   (2004-04-18 20:30) [8]

вместо OST = W mod N
есте-нно OST = W - AVG * N

---

← →
Юрий Зотов ©   (2004-04-18 20:40) [9]

> default ©   (18.04.04 20:07) [5]
> например, такая послед-ть нам подойдёт: 25 25 26

Подойдет. А также подойдет последовательность 76 76 76. И существует еще огромное множество других последовательностей, удовлетворяющих условию
Xmin <= X[i] <= Xmax
где Xmin <= W div N, а Xmax >= W div N.

То есть, вопрос, в том виде, как он задан, ответа не имеет. О чем и речь.

---

← →
Юрий Зотов ©   (2004-04-18 20:40) [9]

> default ©   (18.04.04 20:07) [5]
> например, такая послед-ть нам подойдёт: 25 25 26

Подойдет. А также подойдет последовательность 76 76 76. И существует еще огромное множество других последовательностей, удовлетворяющих условию
Xmin <= X[i] <= Xmax
где Xmin <= W div N, а Xmax >= W div N.

То есть, вопрос, в том виде, как он задан, ответа не имеет. О чем и речь.

---

← →
default ©   (2004-04-18 20:43) [10]

Jack128 ©   (18.04.04 20:23) [6]
X_min = 21; X_max = 50; N = 2; 42<=W<=100
пусть W = 50
пусть первым числом выпало 100
тогда твой код выдаст
100 -50
в сумме, конечно, полтос, но не то...

---

← →
default ©   (2004-04-18 20:43) [10]

Jack128 ©   (18.04.04 20:23) [6]
X_min = 21; X_max = 50; N = 2; 42<=W<=100
пусть W = 50
пусть первым числом выпало 100
тогда твой код выдаст
100 -50
в сумме, конечно, полтос, но не то...

---

← →
nikkie ©   (2004-04-18 20:44) [11]

V := W;
M := N;
for i := 1 to N do
begin
 // решаем задачу разбиения числа V на M слагаемых.
 x[i] := случайное_число_из_диапазона(V - Xmax * (M - 1), V - Xmin * (M - 1));
 V := V - x[i];
 Dec(M);
end;

---

← →
nikkie ©   (2004-04-18 20:44) [11]

V := W;
M := N;
for i := 1 to N do
begin
 // решаем задачу разбиения числа V на M слагаемых.
 x[i] := случайное_число_из_диапазона(V - Xmax * (M - 1), V - Xmin * (M - 1));
 V := V - x[i];
 Dec(M);
end;

---

← →
uny   (2004-04-18 20:45) [12]

возможно вопрос задан не правильно. возможно из-за поведения автора вопроса он должен остаться без ответа. но если кому то вопрос понравился? разве не отходит остальное на второй план? главное жить с удовольствием, хотя у каждого оно своё...:)

---

← →
uny   (2004-04-18 20:45) [12]

возможно вопрос задан не правильно. возможно из-за поведения автора вопроса он должен остаться без ответа. но если кому то вопрос понравился? разве не отходит остальное на второй план? главное жить с удовольствием, хотя у каждого оно своё...:)

---

← →
Jack128 ©   (2004-04-18 21:02) [13]

> nikkie ©   (18.04.04 20:44)
а разве V - Xmax * (M - 1) гарантированно > XMin, а V - Xmin * (M - 1) < XMax??

---

← →
Jack128 ©   (2004-04-18 21:02) [13]

> nikkie ©   (18.04.04 20:44)
а разве V - Xmax * (M - 1) гарантированно > XMin, а V - Xmin * (M - 1) < XMax??

---

← →
Jack128 ©   (2004-04-18 21:04) [14]

например W := 100 N := 10 XMin := 9 XMax := 100, на 1 иттерации
x[i] := случайное_число_из_диапазона(100 - 100 * (10 - 1), 100 - 9 * (10 - 1));

---

← →
Jack128 ©   (2004-04-18 21:04) [14]

например W := 100 N := 10 XMin := 9 XMax := 100, на 1 иттерации
x[i] := случайное_число_из_диапазона(100 - 100 * (10 - 1), 100 - 9 * (10 - 1));

---

← →
nikkie ©   (2004-04-18 21:07) [15]

>jack128
ммм... согласен - надо взять пересечение интервалов
[V - Xmax * (M - 1), V - Xmin * (M - 1)] и [Xmin, Xmax]

---

← →
nikkie ©   (2004-04-18 21:07) [15]

>jack128
ммм... согласен - надо взять пересечение интервалов
[V - Xmax * (M - 1), V - Xmin * (M - 1)] и [Xmin, Xmax]

---

← →
default ©   (2004-04-18 21:08) [16]

nikkie ©   (18.04.04 20:44) [11]
пусть
X_min=21; X_max=33; N=3; 63<=W<=99
пусть W=76
подставим это сюда "(V - Xmax * (M - 1), V - Xmin * (M - 1));"
(76-33*2, ... = (10, ...)
у нас отрезок [21;33]!

---

← →
default ©   (2004-04-18 21:08) [16]

nikkie ©   (18.04.04 20:44) [11]
пусть
X_min=21; X_max=33; N=3; 63<=W<=99
пусть W=76
подставим это сюда "(V - Xmax * (M - 1), V - Xmin * (M - 1));"
(76-33*2, ... = (10, ...)
у нас отрезок [21;33]!

---

← →
Jack128 ©   (2004-04-18 21:13) [17]

> nikkie ©
Не забываем про условие с суммой!!! И опять же где гарантия, что последний элемент не выдет за границу [xmin..xmax]

> [12] uny   (18.04.04 20:45)
Ну так так видишь, решаем..Пока не очень успешно, правда..

---

← →
Jack128 ©   (2004-04-18 21:13) [17]

> nikkie ©
Не забываем про условие с суммой!!! И опять же где гарантия, что последний элемент не выдет за границу [xmin..xmax]

> [12] uny   (18.04.04 20:45)
Ну так так видишь, решаем..Пока не очень успешно, правда..

---

← →
nikkie ©   (2004-04-18 21:15) [18]

>Не забываем про условие с суммой!!!
не забываем. при i = N имеем M = 1, т.е. x[N] = V;

>И опять же где гарантия, что последний элемент не выдет за границу [xmin..xmax]
подумай.

---

← →
nikkie ©   (2004-04-18 21:15) [18]

>Не забываем про условие с суммой!!!
не забываем. при i = N имеем M = 1, т.е. x[N] = V;

>И опять же где гарантия, что последний элемент не выдет за границу [xmin..xmax]
подумай.

---

← →
default ©   (2004-04-18 22:22) [19]


unit Unit1;

interface

uses
 Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
 Dialogs, StdCtrls;

type
 TForm1 = class(TForm)
   Button1: TButton;
   procedure Button1Click(Sender: TObject);
 private
   { Private declarations }
 public
   { Public declarations }
 end;

 TReturn = Array of Cardinal;

var
 Form1: TForm1;
 M: TReturn;

implementation

{$R *.dfm}

function GetRandomArray(W, XMin, XMax, N: Cardinal): TReturn;
var
AVG, OST, C: Cardinal;
begin

if (W < XMin * N) or (W > XMax * N) then Exit;
SetLength(Result, N);
AVG := W div N;
OST := W mod AVG;
C := AVG shl 1 - XMin shl 1 + 1;
while N <> 1 do begin
 Result[N - 1] := XMin + Random(C);
 Dec(W, Result[N - 1]);
 Dec(N, 1);
 if N = 1 then Break;
 Dec(N);
 Result[N] := AVG shl 1 - Result[N + 1];
 if OST <> 0 then begin
  Dec(OST);
  Inc(Result[N])
 end;
 Dec(W, Result[N])
end;
Result[0] := W

end;

procedure TForm1.Button1Click(Sender: TObject);
var
i: Byte;
begin

M := GetRandomArray(22, 3, 6, 4);
Caption := "";
for i := 0 to 3 do Caption := Caption + " " + IntToStr(M[i])

end;

end.

могут быть огрехи...
код не отшлифован
главно пока что пашет

---

← →
default ©   (2004-04-18 22:22) [19]


unit Unit1;

interface

uses
 Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
 Dialogs, StdCtrls;

type
 TForm1 = class(TForm)
   Button1: TButton;
   procedure Button1Click(Sender: TObject);
 private
   { Private declarations }
 public
   { Public declarations }
 end;

 TReturn = Array of Cardinal;

var
 Form1: TForm1;
 M: TReturn;

implementation

{$R *.dfm}

function GetRandomArray(W, XMin, XMax, N: Cardinal): TReturn;
var
AVG, OST, C: Cardinal;
begin

if (W < XMin * N) or (W > XMax * N) then Exit;
SetLength(Result, N);
AVG := W div N;
OST := W mod AVG;
C := AVG shl 1 - XMin shl 1 + 1;
while N <> 1 do begin
 Result[N - 1] := XMin + Random(C);
 Dec(W, Result[N - 1]);
 Dec(N, 1);
 if N = 1 then Break;
 Dec(N);
 Result[N] := AVG shl 1 - Result[N + 1];
 if OST <> 0 then begin
  Dec(OST);
  Inc(Result[N])
 end;
 Dec(W, Result[N])
end;
Result[0] := W

end;

procedure TForm1.Button1Click(Sender: TObject);
var
i: Byte;
begin

M := GetRandomArray(22, 3, 6, 4);
Caption := "";
for i := 0 to 3 do Caption := Caption + " " + IntToStr(M[i])

end;

end.

могут быть огрехи...
код не отшлифован
главно пока что пашет

---

← →
default ©   (2004-04-18 22:44) [20]


function GetRandomArray(W, XMin, XMax, N: Cardinal): TReturn;
var
AVG, OST, C: Cardinal;
F: Byte;
begin

if (W < XMin * N) or (W > XMax * N) then Exit;
SetLength(Result, N);
AVG := W div N;
OST := W mod AVG;
C := (AVG - XMin) shl 1 + 1;
F := Byte(Odd(N));
while N <> F do begin
 Result[N - 1] := XMin + Random(C);
 Dec(N, 2);
 Result[N] := AVG shl 1 - Result[N + 1];
 if OST <> 0 then begin
  Dec(OST);
  Inc(Result[N])
 end;
 Dec(W, Result[N] + Result[N + 1])
end;
if F = 1 then Result[0] := W

end;

чуть получше)а случайность пусть оценивает автор сабжа...

---

← →
default ©   (2004-04-18 22:44) [20]


function GetRandomArray(W, XMin, XMax, N: Cardinal): TReturn;
var
AVG, OST, C: Cardinal;
F: Byte;
begin

if (W < XMin * N) or (W > XMax * N) then Exit;
SetLength(Result, N);
AVG := W div N;
OST := W mod AVG;
C := (AVG - XMin) shl 1 + 1;
F := Byte(Odd(N));
while N <> F do begin
 Result[N - 1] := XMin + Random(C);
 Dec(N, 2);
 Result[N] := AVG shl 1 - Result[N + 1];
 if OST <> 0 then begin
  Dec(OST);
  Inc(Result[N])
 end;
 Dec(W, Result[N] + Result[N + 1])
end;
if F = 1 then Result[0] := W

end;

чуть получше)а случайность пусть оценивает автор сабжа...

---

← →
SergP ©   (2004-04-19 09:05) [21]

>например, такая послед-ть нам подойдёт
>25 25 26

Если такая подойдет, то все число W можно представить в виде суммы чисел A и A+1. Причем А := W div N
Количество чисел А будет равно N - (W mod N), а кол-во чисел A+1 будет W mod N,
причем очевидно, что если (A<Xmin) or (A+1>Xmax) то задача решения не имеет.

Если же так уж очень нужно случайное распределение чисел, то:
...
var
c,k,i:integer;
begin
C:=(xmax-xmin)*N;
for i:=1 to N do
begin
 K:=random(c);
 c:=c-k;
 A[i]:=xmin+k;
end;

---

← →
SergP ©   (2004-04-19 09:05) [21]

>например, такая послед-ть нам подойдёт
>25 25 26

Если такая подойдет, то все число W можно представить в виде суммы чисел A и A+1. Причем А := W div N
Количество чисел А будет равно N - (W mod N), а кол-во чисел A+1 будет W mod N,
причем очевидно, что если (A<Xmin) or (A+1>Xmax) то задача решения не имеет.

Если же так уж очень нужно случайное распределение чисел, то:
...
var
c,k,i:integer;
begin
C:=(xmax-xmin)*N;
for i:=1 to N do
begin
 K:=random(c);
 c:=c-k;
 A[i]:=xmin+k;
end;

---

Страницы: 1 вся ветка

Форум: "Потрепаться";
Текущий архив: 2004.04.11;
Скачать: [xml.tar.bz2];

Наверх

Память: 0.57 MB
Время: 0.049 c