Алгоритмы – одна из центральных тем в программировании, они повсюду (особенно на собеседованиях, ха-ха).
(Разве можно обойтись в таком посте без «баяна»?)
Одним из самых известных является так называемый алгоритм Евклида – пожалуй, самый распространенный способ нахождения наибольшего общего делителя (НОД) двух целых неотрицательных чисел. С него также зачастую любят начинать изучение (и обучение) соответствующих разделов математики и информатики.
А Дональд Кнут, небезызвестный автор трактата “Искусство программирования” (и не только), и вовсе считает алгоритм первым в истории (по крайней мере, относительно современных определений). Потому что, не смотря на то, что алгоритм был придуман и использовался еще до, собственно, Евклида, который жил в IV-III вв. до нашей эры (он упоминается уже у Аристотеля, жившего веком ранее), Евклид описывает процесс итеративно, что согласуется с современным значением слова.
Само слово “алгоритм” восходит к имени арабского математика Аль-Хорезми, жившего примерно в VIII-IX вв. уже нашей эры. А началом его использования в смысле, близком современному, считается уже лишь XX век, точнее – его первые десятилетия, восход информационных технологий.
Предложение. Для данных двух положительных целых чисел найти их наибольший общий делитель.
Пусть A и C – два заданных положительных целых числа; требуется найти их НОД. Если число A делится на C, то число C есть общий делитель чисел C и A, поскольку оно делит самое себя. И очевидно, что оно будет и наибольшим делителем, поскольку нет числа большего, чем число C, которое бы делило C.
Но если C не делит число A, то будем непрерывно вычитать меньшее из чисел A и C из большего до тех пор, пока не получим число, которое нацело делит предыдущее вычитаемое. Это должно рано или поздно произойти, потому что, если разность будет равна единице, то единица будет делить предыдущее вычитаемое.
Теперь положим, что E – положительный остаток от деления числа A на C; пусть F – положительный остаток от деления числа C на число E и пусть F делит E. Так как F делит E, а E делит C — F, F также делит C — F. Но оно делит и самое себя, поэтому F делит C, а C делит A — E; поэтому F делит также A — E, но оно делит и E; поэтому F делит A. Следовательно F является общим делителем чисел A и C.
Теперь я утверждаю, что оно является и НОД. Действительно, если F – не наибольший общий делитель чисел A и C, то найдется большее число, которое будет делить оба этих числа. Пусть таким числом будет G.
Так как число G делит число C, а число C – делит A — E, то G также делит число A — E. Число G делит также все число A, поэтому оно делит и остаток E. Но E делит C — F, поэтому G также делит C — F. А число G также делит все число C, так как оно делит и остаток F; таким образом, большее число делит меньшее, а это невозможно.
Таким образом, нет такого числа, большего, чем F, которое бы делило A и C; значит, число F является НОД.
Следствие. Это рассуждение делает очевидным предположение, что всякое число, делящее два числа, делит и их НОД. Ч.т.д.
func subtractionGCD(_ firstNumber: Int, _ secondNumber: Int) -> Int {
if let simpleGCD = simpleCasesGCD(firstNumber, secondNumber) {
return simpleGCD
}
var firstNumber = firstNumber
var secondNumber = secondNumber
while firstNumber != 0, secondNumber != 0 {
if firstNumber > secondNumber {
firstNumber = firstNumber - secondNumber
} else {
secondNumber = secondNumber - firstNumber
}
}
return firstNumber + secondNumber // One of them is 0.
}
func simpleCasesGCD(_ firstNumber: Int, _ secondNumber: Int) -> Int? {
if firstNumber == secondNumber {
return firstNumber // Any.
}
if firstNumber == 0 {
return secondNumber
}
if secondNumber == 0 {
return firstNumber
}
return nil
}
func divisionGCD(_ firstNumber: Int, _ secondNumber: Int) -> Int {
if let simpleGCD = simpleCasesGCD(firstNumber, secondNumber) {
return simpleGCD
}
var firstNumber = firstNumber
var secondNumber = secondNumber
while firstNumber != 0, secondNumber != 0 {
if firstNumber > secondNumber {
firstNumber = firstNumber % secondNumber
} else {
secondNumber = secondNumber % firstNumber
}
}
return firstNumber + secondNumber // One of them is 0.
}
measure(_:)
класса XCTestCase
«нативного» фреймворка для тестирования кода в Xcode-проектах XCTest
.let pairs = (0..<100).map { _ in (Int.random(in: 0..<10000), Int.random(in: 0..<10000)) } // Generates 100 pairs.
func testSubstractionGCDPerformance() {
measure() {
_ = pairs.map { substractionGCD($0, $1) }
}
}
func improvedDivisionGCD(_ firstNumber: Int, _ secondNumber: Int) -> Int {
if let simpleGCD = GCD.simpleCasesGCD(firstNumber, secondNumber) {
return simpleGCD
}
var firstNumber = firstNumber
var secondNumber = secondNumber
while firstNumber != 0, secondNumber != 0 {
if firstNumber > secondNumber {
let firstNumberClaim = firstNumber % secondNumber
if firstNumberClaim > secondNumber / 2 {
firstNumber = abs(firstNumberClaim - secondNumber)
} else {
firstNumber = firstNumberClaim
}
} else {
let secondNumberClaim = secondNumber % firstNumber
if secondNumberClaim > firstNumber / 2 {
secondNumber = abs(secondNumberClaim - firstNumber)
} else {
secondNumber = secondNumberClaim
}
}
}
return firstNumber + secondNumber // One of them is 0.
}
func binaryGCD(_ firstNumber: Int, _ secondNumber: Int) -> Int {
if let simpleGCD = GCD.simpleCasesGCD(firstNumber, secondNumber) {
return simpleGCD
}
var firstNumber = firstNumber
var secondNumber = secondNumber
var shift = 0
while (firstNumber | secondNumber) & 1 == 0 {
shift += 1
firstNumber >>= 1
secondNumber >>= 1
}
while firstNumber & 1 == 0 {
firstNumber >>= 1
}
repeat {
while secondNumber & 1 == 0 {
secondNumber >>= 1
}
if firstNumber > secondNumber {
swap(&firstNumber, &secondNumber)
}
secondNumber -= firstNumber
} while secondNumber != 0
return firstNumber << shift
}
К сожалению, не доступен сервер mySQL