DjangoBB LoFi version

xANTONx

Окт. 21, 2013 23:59:37

Помогите, пожалуйста, с решением вот этой задачки на Python.
“Найти все простые несократимые дроби, заключенные между 0 и 1, знаменатели которых не превышают 7 (дробь задается двумя натуральными числами — числителем и знаменателем)”

JOHN_16

Окт. 22, 2013 00:41:33

xANTONx
Если идти классическим путем, то я вижу решение путем двойного цикла for: первый перебирает знаменатели второй числители, в теле цикла выполняется некая проверка на сократимость. Как ее реализовать? ПУти наверняка разные - для меня самый очевидный и напрашивающийся это перебор значений числителя от 1 до текущего и попытка разделить без остатка текущий знаменатель на этот числитель. Деления без остатка осуществляется символом %, например 4%2

Пробуйте писать код - что будет не получаться, мы поможем.

Euler

Окт. 22, 2013 01:39:49

JOHN_16
ПУти наверняка разные - для меня самый очевидный и напрашивающийся это перебор значений числителя от 1 до текущего и попытка разделить без остатка текущий знаменатель на этот числитель. Деления без остатка осуществляется символом %, например 4%2

Э нет, дробь несократима, если НОД(GCD) числителя и знаменателя равен единице. Т.е. простейший способ - это перебрать все числители и знаменатели и если fractions.gcd(numerator, denominator)==0, то дробь несократима. Более “умный” способ - это найти все простые числа на указанном промежутке и составлять из них числители и знаменатели так, чтобы никакой простой множитель не попал одновременно и в числитель и в знаменатель, все такие дроби будут несократимы по основной теореме арифметики. Причём второй способ реально станет лучше только на гораздо бОльшем промежутке.

JOHN_16

Окт. 22, 2013 02:07:17

Euler
сходу немного запутался) я имел ввиду другое несколько… если делится без остатка числитель и знаменатель на это перебираемое значение.

Я описывал решение именно с точки зрения моего мозга = прямолинейно. решение после выложу, как ТС справится с заданием.

Aris_P@

Окт. 23, 2013 09:14:01

думаю тут отлично поможет дерево штерна-броко
http://ru.wikipedia.org/wiki/%D0%94%D0%B5%D1%80%D0%B5%D0%B2%D0%BE_%D0%A8%D1%82%D0%B5%D1%80%D0%BD%D0%B0_%E2%80%94_%D0%91%D1%80%D0%BE%D0%BA%D0%BE

Isem

Окт. 23, 2013 12:24:27

Aris_P@
думаю тут отлично поможет дерево штерна-броко

Хорошая мысль, разве что удобнее дерево Калкина — Уилфа.

max_N = 7
def get_fraction( m, n ):
    if n <= max_N:
        if m <= n: yield m,n
        elif m+n > max_N: raise StopIteration
        for f in get_fraction( m, n+m ): yield f
        for f in get_fraction( m+n, n ): yield f
print( *sorted(get_fraction(1,1)), sep='\n' )

Aris_P@

Окт. 23, 2013 13:19:51

самым удобным будет ряд Фарея :) (частный случай дерева Штерна-Броко) - в нем всем дроби меньше 1
все уже украдено до нас http://habrahabr.ru/post/188160/