Visual Basic, .NET, ASP, VBScript
Новости | Примеры | Библиотека кодов | НеЧаВо | VBA | Справочник по VB | Справочник по WinAPI | ActiveX контролы | Статьи по VB | Мастерская разработчика | Форум VBNet | Яndex bar! | Голосование | Полезные программы | Магазин VBNet | Рассылка | Конкурсы | Юмор | Чат | Реклама на VBNet | Автора! | Ссылки | Бета-тестирование | Послать пример на сайт
 

   
   
     

Форум - Общий форум

Страница: 1 |

 

  Вопрос: НОД и НОК Добавлено: 23.01.07 21:13  

Автор вопроса:  Fever
Подскажите пожалуйста, как эффективно считать НОК(x1,x2,x3,...) и НОД(x,y)

Ответить

  Ответы Всего ответов: 10  

Номер ответа: 1
Автор ответа:
 Sharp


Лидер форума

ICQ: 216865379 

Вопросов: 106
Ответов: 9979
  Web-сайт: sharpc.livejournal.com
 Профиль | | #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(A) - 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(A)
        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-сайт: sharpc.livejournal.com
 Профиль | | #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(A)
    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-сайт: sharpc.livejournal.com
 Профиль | | #10 		Добавлено: 22.07.07 12:11
Без НОД я уже написал в 5-м посте.

Ответить

Страница: 1 |

Поиск по форуму



© Copyright 2002-2011 VBNet.RU | Пишите нам