Страница: 1 |
Страница: 1 |
Вопрос: НОД и НОК
Добавлено: 23.01.07 21:13
Автор вопроса: Fever
Подскажите пожалуйста, как эффективно считать НОК(x1,x2,x3,...) и НОД(x,y)
Ответы
Всего ответов: 10
Номер ответа: 1
Автор ответа:
Sharp
Лидер форума
ICQ: 216865379
Вопросов: 106
Ответов: 9979
Web-сайт:
Профиль | | #1
Добавлено: 24.01.07 01:59
По алгоритму Эвклида
Номер ответа: 2
Автор ответа:
Fever
Вопросов: 60
Ответов: 808
Профиль | | #2
Добавлено: 28.01.07 16:30
Ну и редиска. Суть в том, что реализация НОК через НОД легко ведет к переполнениям.
Номер ответа: 3
Автор ответа:
Fever
Вопросов: 60
Ответов: 808
Профиль | | #3
Добавлено: 28.01.07 16:49
QuickSort по-любому нужен для исходного массива НОXаемых чисел
Переводил с дельфей с форума по олимпиадам
Option Explicit
Private A() As Long
Private Sub QuickSort(Left As Long, Right As Long) ' Упорядочивание по неубыванию чисел
Dim M As Long
Dim i As Long, J As Long
Dim TMP As Long
M = A((Left + Right) \ 2)
i = Left
J = Right
Do
Do While A(i) < M
i = i + 1
Loop
Do While A(J) > M
J = J - 1
Loop
If i <= J Then
TMP = A(i)
A(i) = A(J)
A(J) = TMP
i = i + 1
J = J - 1
End If
Loop Until i > J
If J > Left Then QuickSort Left, J
If i < Right Then QuickSort i, Right
End Sub
Private Function NOD(ByVal x As Long, ByVal y As Long) As Long ' Функция нахождения НОД 2-ух чисел
Dim r As Long
Do While y > 0
r = x Mod y
x = y
y = r
Loop
NOD = x
End Function
Private Function NOK(x As Long, y As Long) As Long ' Функция нахождения НОК 2-ух чисел
NOK = (x \ NOD(x, y)) * y
End Function
Private Function NOKK() As Long ' Функция нахождения НОК нескольких чисел
Dim Q As Long, S As Long
Dim i As Long
S = 1
For i = 0 To UBound - 1
Q = NOK(A(i), A(i + 1))
S = NOK(S, Q)
Next
NOKK = S
End Function
Function NODD() As Long ' Функция нахождения НОД нескольких чисел
Dim W As Long
Dim i As Long
W = NOD(A(1), A(2))
For i = 2 To UBound
If (A(i) Mod W) <> 0 Then
W = 1
Exit For
End If
Next
NODD = W
End Function
Номер ответа: 4
Автор ответа:
Fever
Вопросов: 60
Ответов: 808
Профиль | | #4
Добавлено: 28.01.07 16:51
Да, и еще. Перед вызовом NOD нада убедицца, что X>Y
Вопрос про НОК без НОД еще открыт.
Номер ответа: 5
Автор ответа:
Sharp
Лидер форума
ICQ: 216865379
Вопросов: 106
Ответов: 9979
Web-сайт:
Профиль | | #5
Добавлено: 28.01.07 22:52
Ну блин, раскладываешь все числа по простым множителям, а затем для каждого числа берешь максимум степени. Перемножаешь числа в степенях, получаешь НОК. Не хочешь переполнения, юзай длинную арифметику.
Номер ответа: 6
Автор ответа:
HACKER
Разработчик Offline Client
Вопросов: 236
Ответов: 8362
Профиль | | #6
Добавлено: 29.01.07 00:28
'This code is generated by the AlgoPascal translator
'
'This code is distributed under the ALGLIB license
'  see http://www.alglib.net/copyrules.php for details)
''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
'Routines
''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
'Функция ищет наибольший общий делитель двух
'чисел алгоритмом Евклида.
'
''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
Public Function GCD(ByVal A As Long, ByVal B As Long) As Long
Dim Result As Long
A = Abs
B = Abs(B)
If a=0# Or b=0# then
Result = a+b
GCD = Result
Exit Function
End If
Do While a<>b
If a>b then
a = a-b
Else
b = b-a
End If
Loop
Result = b
GCD = Result
End Function
а вообще на algolist.manual.ru ...
Номер ответа: 7
Автор ответа:
Fever
Вопросов: 60
Ответов: 808
Профиль | | #7
Добавлено: 21.07.07 16:29
Ггыгы какой я топик нашел А ведь мне так и не ответили
Номер ответа: 8
Автор ответа:
shuffle
Администратор
ICQ: 201502381
Вопросов: 15
Ответов: 737
Профиль | | #8
Добавлено: 22.07.07 02:17
Public Function LCM(ByVal A As Long, ByVal B As Long) As Long
LCM = A * B / GCD(A, B)
End Function
Номер ответа: 9
Автор ответа:
shuffle
Администратор
ICQ: 201502381
Вопросов: 15
Ответов: 737
Профиль | | #9
Добавлено: 22.07.07 02:29
А зачем без НОД?
Номер ответа: 10
Автор ответа:
Sharp
Лидер форума
ICQ: 216865379
Вопросов: 106
Ответов: 9979
Web-сайт:
Профиль | | #10
Добавлено: 22.07.07 12:11
Без НОД я уже написал в 5-м посте.