В очередной раз о НОД, алгоритме Евклида и немного об истории алгоритмов вообще. Конечно, с примерами на Swift
Алгоритмы – одна из центральных тем в программировании, они повсюду (особенно на собеседованиях, ха-ха).
(Разве можно обойтись в таком посте без «баяна»?)
Одним из самых известных является так называемый алгоритм Евклида – пожалуй, самый распространенный способ нахождения наибольшего общего делителя (НОД) двух целых неотрицательных чисел. С него также зачастую любят начинать изучение (и обучение) соответствующих разделов математики и информатики.
А Дональд Кнут, небезызвестный автор трактата “Искусство программирования” (и не только), и вовсе считает алгоритм первым в истории (по крайней мере, относительно современных определений). Потому что, не смотря на то, что алгоритм был придуман и использовался еще до, собственно, Евклида, который жил в 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 является НОД.
Следствие. Это рассуждение делает очевидным предположение, что всякое число, делящее два числа, делит и их НОД. Ч.т.д.
Описание приводит два способа нахождения НОД – вычитанием и делением. Собственно, и в наши дни широко известны эти два способа реализации алгоритма.
Вот пример функции, написанной на «Swift», реализации первого способа:
Здесь, переиспользования ради, я вынес в отдельную функцию случаи поиска НОД, когда он известен сразу, без необходимости следования какому-либо алгоритму:
(Если два числа равны, то, естественно, их НОД также равен им. Если какое-то из чисел равно нулю, то НОД будет равняться второму числу, т.к. ноль делится любым числом (с результатом, понятное дело, тоже ноль).)
В качестве входных данных могут использоваться только неотрицательные значения. Соответственно, для отрицательных можно использовать те же методы, но взяв числа по модулю. (Да, общий делитель может быть и отрицательным, но мы ищем именно НОД, а положительные числа, очевидно, всегда больше отрицательных.)
А вот так может выглядеть реализация версии алгоритма делением:
Вторая версия в наши дни считается предпочтительней, так как содержит в себе, в среднем, ощутимо меньшее количество шагов. Тем не менее, во времена, когда компьютеры были большие и медленные, операция деления могла быть сама по себе сложной процедурой. И тогда первая версия алгоритма могла оказаться эффективней.
Чтобы немного их сравнить, я произвел несколько замеров с использованием любимого мной метода measure(_:) класса XCTestCase «нативного» фреймворка для тестирования кода в Xcode-проектах XCTest .
В качестве входных данных я использовал массив пар случайных чисел. Замеры производились, естественно, с использованием одного и того же массива для каждого способа. Разброс чисел для пар я взял от нуля до 9999. Замеры производились на количестве вычислений (пар чисел): одно, десять, 100, 1000, 10000, 100000, 1000000 и 10000000. Последнее заставляло ожидать результата уже несколько минут, поэтому на нем я решил остановиться.
Вот простой код генерации входных данных:
Сам замер выглядит, например, так:
А вот так выглядят результаты запуска на моем компьютере:
(Subtraction – вычитание, division – деление.)
В общем, очень хорошо видно, как сильно на современных компьютерах проигрывает метод вычитания.
«Улучшенная» версия алгоритма Евклида
В литературе можно встретить версию алгоритма, в которой одно из чисел на каждом шаге вместо остатка от деления на второе заменяется на разность между этим отстатком и вторым числом, но только в случае, если остаток от деления больше половины второго числа. Реализация этой версии может выглядеть так:
Такая модификация сокращает количество шагов алгоритма, но, судя по результатам замеров на моем компьютере, дополнительные вычисления и проверки на каждом шаге, нейтрализуют это преимущество и даже более:
(Improved – «улучшенная» версия.)
Еще немного о значимости алгоритма Евклида
Алгоритм имеет также геометрическую версию (для нахождения наибольшей меры двух отрезков).
Алгоритм был, конечно, обощен и для нахождения НОД любого количества чисел, не только двух. В двух словах идея такова: если обозначить функцию поиска НОД двух чисел как gcd(a, b), то, скажем, НОД трех чисел gcd(a, b, c) равен gcd(gcd(a, b), c). И так далее, для любого количества чисел НОД находится последовательным вычислением НОД НОД-а предыдущей пары чисел и следующего числа. Хотя, конечно, это касается поиска НОД вообще, а не только алгоритма Евклида.
Существует также обощение алгоритма для нахождения НОД полиномов. Но это уже выходит за рамки этого несложного поста, а в некоторой степени, и моих познаний в математике.
Сложность алгоритма Евклида
Временная сложность алгоритма исследовалась давно, не быстро и гораздо более учеными мужами, чем ваш покорный слуга. Тем не менее, вопрос давно закрыт и ответ получен. Собственно, еще в середине позапрошлого века. Габриэлем Ламе.
Если коротко, то ответ формулируется, собственно, теоремой Ламе, связанной с этим алгоритмом. Количество шагов алгоритма будет равно порядковому номеру ближайшего большего числа Фибоначчи наименьшему из двух чисел входных параметров минус 2. Оперируя чуть более традиционно-математическими обозначениями, то если u > v (и v > 1), то число проходов алгоритма будет равняться n — 2 при v
Источник
Fallout New Vegas: квест — Солнечные блики.
XNick
Я не помню точно, что будет, если выбрать 5, может сломается. Сохранись и посмотри. А так из соображений безопасности я бы выбрал «3 — Весь регион», чтобы просто разделить энергию на всех.
Не подлизывайся к НКР, но и не истребляй их. Тебе важно стать хозяином Нью-Вегаса, а НКР — всего лишь твой конкурент 🙂 Под конец они мне потихой мешались.. я их просто прогнал. Может быть, в рамках игры, я сделал очень плохо.. ведь солдаты НРК стали изгоями.. их ненавидели, но возможно, и поделом. Игру сделали так, что хрен проссышь, кто там хороший и кто плохой.. однозначно, легион — это отморозь.. в юбках, но не трансвиститы, похожи на римлян, но ведут себя, как варвары.
>>>Если 4 — НКР обидится
Не обидится. Переводим энергию на Архимед 2 и не включаем тест Архимед 1. Problem solved.
если делать вариант 3 — Игнасио Ривас подарит книжку с + 2 (+4) к науке.
если протестировать Архимед на бойцах НКР — то при следующем визите Гелиос Ван будет кишеть легионерами, Игнасио Риваса убьют, а Фанстастик в легионерской юбке будет рассуждать, что Цезарь — это круто!
Например книга «Николо Тесла и я» давала мне +4 энерго оружие
Тебе и говорят — если взять перк Comprehension, то с каждой учебной книжки ты получаешь +4. Если перка нет, то +3.
Не бывает книг +2, и не бывает книг +4 без перка.
Да и посчитай, если собрать 4 книги и не брать перк, то это будет +12, а с перком +16. Это позволит сильнее развить перса по многим веткам.
С другой стороны это затраченный перк, который, ну лично у меня, не всегда бывает лишним.
4ый — перк на +2 скиллпоинта
8ой — коммандо
10 — точность
12 — бесшумный бег
2,6 у меня ушли на +special, чтобы добить восприятие до 9
При этом мастхэвный перк — hand loader на 6ом лвл, который я взять забыл (а я забыл, что там рецепты))).
12ый лвл — это середина игры. На 12ом я уже убил бенни, сгонял к Цезарю и бомбистам, обзавелся 5ю имплантами, снайперкой, броней анклава, зачистил коттонвуд-коул, 22 убежище, Чертей и запустил гулей на луну. Ну это так, из особо примечательного.
Т.е. да, взять перк — можно. Только это на 2 лвл «сдвинет» наше развитие. Вам критичнее бартер, мне — раньше сделать «бойца», потому что так или иначе воевать нам приходится)
У каждого разный стиль прохождения 🙂
Ну я ж не спорю 🙂 Я просто пример привожу) Что если стараться сделать быстрее бойца «по специальности» — то не до сторонних перков)
С тем фактом, что можно взять и другие перки (в частности обсуждаемый) и быть более широкопрофильным — я не спорю)
Хз, у меня качается на финальном моем персе (было 2 пробных)
единственный боевой навык — guns и все.
Остальные идут:
самые важные —
lockpick 100
science 100
speech 100
guns 100
repair 100
менее важные —
barter 80-100
medicine 80-100
explosives 40-60
survival 40
остальные не качаю вообще,
при этом, можете смеяться, но я стрелком
вообще не качаю sneak, ибо тихо ходить
мне не надо, не ворую из карманов,
и насколько я знаю, шанс крита прокачка
sneak не повышает.
Насчет Comprehension, я играю с модом:
перк каждый лвл, и у меня, представьте,
есть перки куда важнее чем этот, ИМХО
ради +1 и редких книг, а журналы нужны
до середины игры, не дальше, брать целый
перк, не в тему как-то.
и насколько я знаю, шанс крита прокачка
sneak не повышает.
Шанс — нет. Но из сника всегда засчитывается крит.
А учитывая, что мобы даже после выстрела не моментально тебя замечают — можно критануть по 2-3 целям (ну или по одной, если толстая).
Кроме того, сник — единственный шанс критовать с дробовика :)))
Mysterious Stranger
Черт, я не правильно выразился, имелся ввиду множитель крита,
крит-то из сника 100% всегда.
А учитывая, что мобы даже после выстрела не моментально тебя замечают — можно критануть по 2-3 целям (ну или по одной, если толстая).
У меня так же, но зависит от расстояния, мне важнее
всего крит с Анти-Материал, когда я в Слоане
залез на гору, и Детхкло было видно только с оптикой,
я убивал рядом стоящих, а для живых я все еще был
в хайде.
Кроме того, сник — единственный шанс критовать с дробовика :)))
Дробовик я ношу для ближнего боя в пещерах/домах,
или если от всего остального патронов нет.
В пещере так критану из хайда одного хрена, а остальные
уже так и бегут, и даже если сник 100, от звука выстрела
все равно супостаты сбегутся же?
Источник