НОД и НОК элементов массива

[saleens7]

Умные люди, помогите решить задачку в EXEl-е на Visual Basic... Найти НОД и НОК элемента массива! Внимание,не двух чисел,а именно масства!! Я весь инет перелазил,везде только для двух чисел,а для массива найти не могу решение...Как сделать не знаю... Блин если через два дня не здам,меня пнут с универа, поэтому прошу срочно помочь!
Помогите пожалуйста!!!

[cent]

Ну, с НОД вроде получилось... по поводу НОК - хз... нужен алгоритм.
Будет алгоритм - сделать можно!

НОД.zip




=================================== ======
Attribute VB_Name = "Module1"
Sub NOD()
' макрос находит НОД для массива данных. в данном примере массив из N чисел расположен в столбце [А] начиная с [A1]
Dim Ar() As Long ' для хранения массива данных
Dim ArT As Long ' для временного хранения значений при сортировке
Dim i As Long, j As Long, N As Long ' переменные
Dim Temp1 As Single, Temp2 As Long
' определяем колличество чисел в массиве
N = InputBox("Сколько чисел в массиве?")
ReDim Ar(1 To N) As Long
' импорт данных в массив c проверкой
For i = 1 To N
If ActiveSheet.Range("A1").Offset(i - 1, 0).Value <> 0 Then
Ar(i) = ActiveSheet.Range("A1").Offset(i - 1, 0).Value
Else
MsgBox ("Один из элементов равен 0!")
Exit Sub
End If
Next i
' Сортировка массива по возростанию пузырьковым методом
For i = 1 To N
For j = 1 To N - 1
If Ar(i) <= Ar(j) Then
ArT = Ar(i)
Ar(i) = Ar(j)
Ar(j) = ArT
End If
Next j
Next i
' поиск НОД
For i = 1 To N - 1
Temp1 = Ar(i + 1) / Ar(i)
If Temp1 - Int(Temp1) = 0 Then
Ar(i + 1) = Ar(i)
Else
Do While Temp1 - Int(Temp1) <> 0
Temp2 = Ar(i + 1)
Ar(i + 1) = Ar(i)
Ar(i) = Temp2 - Int(Temp1) * Ar(i + 1)
Temp1 = Ar(i + 1) / Ar(i)
Loop
Ar(i + 1) = Ar(i)
End If
Next i
MsgBox ("НОД = " & Ar(N))
End Sub

=================================== ======

[cent]

А вообще, может кому-нить интересен алгоритм:

Наибольшим общим делителем (greatest common divisor, GCD) двух чисел называется наибольшее целое, на которое делятся два числа без остатка. Например, наибольший общий делитель чисел 12 и 9 равен 3. Два числа называются взаимно простыми (relatively prime), если их наибольший общий делитель равен 1.
Математик Эйлер, живший в восемнадцатом веке, обнаружил интересный факт:

Если A нацело делится на B, то GCD(A, B) = A.
Иначе GCD(A, B) = GCD(B Mod A, A).

Этот факт можно использовать для быстрого вычисления наибольшего общего делителя. Например:

GCD(9, 12) = GCD(12 Mod 9, 9)
= GCD(3, 9)
= 3

[saleens7]

Нифига здесь код... есть небольшой недочёт...мне надо её сделать в Public Function. Блин забыл уточнить... Карочи например есть массив ну пусть 4(строки) на 4(столбца) тоесть 16 чисел, их вводить в ячейки! Нажимаем ALT+F11 Создаём модуль и процедуру Public Function. А вводить данные используя мастер функции -> определено пользавателем и показываем проге наш массив... я тут скину пример как мы делали другую лабу, просто чисто как пример посмотрите... Прошу переделайте плиз...

[cent]

Держи функцию

НОД-функция.zip

И собственно сам код:
====================
Public Function NOD(Rng As Range) As Long
' функция находит НОД для массива данных
Dim Ar() As Long ' для хранения массива данных
Dim ArT As Long ' для временного хранения значений при сортировке
Dim i As Long, j As Long, N As Long ' переменные
Dim Temp1 As Single, Temp2 As Long
Dim R As Long, C As Long, R1 As Long, C1 As Long
R = Rng.Rows.Count
C = Rng.Columns.Count
N = R * C
ReDim Ar(1 To N) As Long
' импорт данных в массив c проверкой
R1 = Rng.Row
C1 = Rng.Column
For i = 1 To R
For j = 1 To C
If Cells(R1, C1).Offset(i - 1, j - 1).Value <> 0 Then
Ar(j + C * (i - 1)) = Cells(R1, C1).Offset(i - 1, j - 1).Value
Else
MsgBox ("Один из элементов равен 0!")
Exit Function
End If
Next j
Next i
' Сортировка массива по возростанию пузырьковым методом
For i = 1 To N
For j = 1 To N - 1
If Ar(i) <= Ar(j) Then
ArT = Ar(i)
Ar(i) = Ar(j)
Ar(j) = ArT
End If
Next j
Next i
' поиск НОД
For i = 1 To N - 1
Temp1 = Ar(i + 1) / Ar(i)
Do While Temp1 - Int(Temp1) <> 0
Temp2 = Ar(i + 1)
Ar(i + 1) = Ar(i)
Ar(i) = Temp2 - Int(Temp1) * Ar(i + 1)
Temp1 = Ar(i + 1) / Ar(i)
Loop
Ar(i + 1) = Ar(i)
Next i
NOD = Ar(N)
End Function

====================

[saleens7]

Огромное спасибо!!!!!!!!!! А можно вопрос? вот "Сортировка массива по возростанию пузырьковым методом" в ноде это обязательно? Теперь осталось НОК... у меня есть НОК для двух чисел,а как для массива его переделать у меня ума не хватает.... Может посмотрите?

[cent]

Сортировка обязательна, т.к. сначала ищется НОД для наименьших чисел из массива. Иначе ошибки не избежать.

По НОК алгоритм понятен, 15мин и будет готово

[saleens7]

Спасиб!!!!

[cent]

Функция НОК
НОК-функция.zip

Есть правда одно условие к обеим функциям:
Массив должен быть полным (квадратным )
Например:
20......... 15
10......... 40
30.........15

но не таким:
20......... 15
............ 40
30.........15
и тп

[saleens7]

Тоесть вы имеете ввиду чтоб ни одна клетка нашего массива не должна быть пустой?