Python-сообщество

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

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

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

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

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

_________________________________________________________________________________
полезный блог о python john16blog.blogspot.com

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

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

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

Отредактировано Euler (Окт. 22, 2013 01:41:55)

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

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

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

_________________________________________________________________________________
полезный блог о python john16blog.blogspot.com

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/

Отредактировано Aris_P@ (Окт. 23, 2013 13:21:26)

Python-сообщество

Уведомления

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

Дроби в Python

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

Дроби в Python

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

Дроби в Python

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

Дроби в Python

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

Дроби в Python

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

Дроби в Python

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

Дроби в Python

Board footer