|
|
|
Forum Member
 
участник
Last Login: 11.08.2006 13:25
Сообщ.: 41,
Visits: 436
|
|
Подскажите, пожалуйста как составить алгоритм для решения следующей задачи:
Есть N-ое количество стрел. Нужно выбрать из них все возможные комбинации стрел,
но каждая комбинация должна состоять из M стрел. Иными словами есть числа от 0 до N,
нужно сформировать все возможные комбинации которые состоят из етих чисел и количество
чисел в одной комбинации равно М.
|
|
|
|
|
Supreme Being
участник
Last Login: 23.08.2008 19:49
Сообщ.: 1 577,
Visits: 17 092
|
|
Это VBScript
Const n=10
Const m=3
Dim b(3)
For i = 1 To m
b(i) = i
Next
b(m)=m-1
Do
For i=m To 1 Step -1
b(i)=b(i)+1
If b(i) <= n+i-m Then
If i<m Then
For j=i+1 To m
b(j)=b(j-1)+1
Next
End If
Exit For
Else
If i=1 Then
Exit Do
End If
End If
Next
print_result
Loop
Sub print_result
s = ""
For i = 1 To m
s = s & b(i) & " "
Next
MsgBox s
End Sub
|
|
|
|
|
Supreme Being
участник
Last Login: 18.02.2005 10:12
Сообщ.: 109,
Visits: 1 200
|
|
Насколько я понял условие задачи, тут имеет место быть перестановка.
Число перестановок N объектов равно N!.
Если требуется выбрать все варианты K сочетаний из N элементов, то, если мне не изменяет склероз:
N!
----------
K!(N-K)!
|
|
|
|
|
Junior Member
участник
Last Login: 27.02.2003 8:42
Сообщ.: 11,
Visits: 122
|
|
Формула в предыдущем сообщении правильная, которая последняя. Но!..
С большими n этого на компе не посчитать, особенно, если N меняется.
Рекомендую формулы стирлинга.
И предельные теоремы из курса Теории Вероятности.
Например Пуассона или Муавра. Получите функцию Лапласа, посмотрите в табличку. И готов ответ на все вопросы!
Факториал - это слишком серьезно для компьютера.
|
|
|
|
|
Supreme Being
участник
Last Login: 18.02.2005 10:12
Сообщ.: 109,
Visits: 1 200
|
|
Ну так не надо слеоп применять формулу. Можно же и привести ее к более-менее нормальному виду.
Я понимаю, что в формуле
А!/В!
проще сначала посчитать первый факт. потом второй и потом разделить, но, господа, а как же сокращения? Хотя, понимаю, что это не спасет при очень больших числах. Но для больших чисел есть множество способов вычислений, независящих от размерности представления числа в компьютере.
|
|
|
|
|
Supreme Being
участник
Last Login: 23.08.2008 19:49
Сообщ.: 1 577,
Visits: 17 092
|
|
Насколько я понял задачу требовалось ПЕРЕЧИСЛИТЬ все сочетания а не определить их количество. Именно на это и был нацелен алгоритм, который я привел.
А что касается формул, то для вычисления удобнее всего пользоваться следующей:
N(N-1)...(N-K+1)
----------------
K!
При этом для того, чтобы не было риска переполнения следует по очереди использовать по одному множителю сначала в числителе, а затем в знаменателе. Несложно показать, что все деления будут осуществляться без остатка. В ходе выполнения цикла величина c сначала растет, а затем, когда i становится больше N/2 начинает уменьшаться. Ясно, что когда N велико, а K немного меньше, чем N, то сам результат может иметь приемлимую величину, а вот промежуточные результаты могут вызвать переполнение. Поэтому нужно дополнительно перед выполнением алгоритма заменить K на N-K в том случае, если K>N/2. Окончательный алгоритм может быть таким:
Function cons(N, K)
Dim c, u, d
If 2 * K > N Then K = N - K
c = 1
u = N
d = 1
For i = 1 to K
c = c * u / d
u = u - 1
d = d + 1
Next
cons = c
End Function
|
|
|
|