Форум программистов, компьютерный форум CyberForum.ru

АнтиЕвклид! - C++

Восстановить пароль Регистрация
 
alekola
 Аватар для alekola
21 / 21 / 1
Регистрация: 04.08.2011
Сообщений: 103
01.08.2012, 06:40     АнтиЕвклид! #1
Добрый день,
из спортивного интереса пытаюсь найти число для которого алгоритм Евклида,
выполниться хотя бы 6 раз!
На работе включил перебором, но думаю это на долго. Может кто то элегантное решение подскажет?
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
nexen
187 / 180 / 3
Регистрация: 27.01.2012
Сообщений: 1,335
01.08.2012, 07:37     АнтиЕвклид! #2
Собственно, если ищешь перебором, то это не долго, ибо для миллиарда будет всего 5 миллиардов операций максимум, а, т.е, 2 секунды на одноядерном, так что это быстро. Ну а если за этот миллиард найдет n>5, то ещё меньше
alekola
 Аватар для alekola
21 / 21 / 1
Регистрация: 04.08.2011
Сообщений: 103
01.08.2012, 08:59  [ТС]     АнтиЕвклид! #3
там 2 числа..у меня 2 цикла от 2 до максимального значения инт
на каждой интерации внутреннего цикла выполняеться вычисление. уже 3 часа ищет..нашел что то но файл пока занят программой
golatin
259 / 216 / 38
Регистрация: 12.10.2011
Сообщений: 311
Завершенные тесты: 1
01.08.2012, 11:04     АнтиЕвклид! #4
1/2+1=3/2 переворачиваем дробь
2/3+1=5/3 .....
3/5+1=8/5 .....
5/8+1=13/8 .....
8/13+1=21/13 ......
13/21+1=34/21 и т.д.


Проверяю этим алгоритмом
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def Nod(a,b):
    while a and b:
        print "%s - %s"%(a,b)
        if a>=b:
            a%=b
        else:
            b%=a
    return b|a
 
 
>>> Nod(34,21)
34 - 21
13 - 21
13 - 8
5 - 8
5 - 3
2 - 3
2 - 1
1
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
01.08.2012, 18:57     АнтиЕвклид! #5
алгоритм Евклида выполняется за O(log(min(a, b)))... сделайте из этого какие-то выводы
Yandex
Объявления
01.08.2012, 18:57     АнтиЕвклид!
Ответ Создать тему
Опции темы

Текущее время: 07:03. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru