Период десятичной дроби
Задача : на вход в функцию подается два целых числа (int(a), int(b)) . Вернуть нужно частное a/b , причем повторяющиеся числа (период) нужно взять в скобки. Примеры:
1/3 = > 0.(3) 29/12 = > 2.41(6) 5/3 = > 1.(6) Подошел к решению задачи методом брутфорса. Перебирал дробную часть , искал совпадения. Но в случае 1/117 в период входит более 90 чисел и перебор чисел занимает больше времени, чем позволено в задаче. Как по-другому решить эту задачу? Может есть более элегантное решение?
Отслеживать
48.7k 17 17 золотых знаков 56 56 серебряных знаков 100 100 бронзовых знаков
задан 17 авг 2017 в 20:15
325 1 1 золотой знак 3 3 серебряных знака 13 13 бронзовых знаков
Брут бывает разный. Я реализовывал в свое время деление в столбик и как только получал ту же пару делимое-делитель что уже была — считал что нашел период.
17 авг 2017 в 20:57
По времени прошло?
18 авг 2017 в 9:25
Да ,все идеально.Жалко, что рейтинга у меня пока нету, чтобы отблагодарить лайком 🙂
18 авг 2017 в 9:26
Отметьте решением 🙂
18 авг 2017 в 9:28
1/117 в периоде 6 цифр, а не «более 90 чисел».
7 янв 2020 в 17:14
3 ответа 3
Сортировка: Сброс на вариант по умолчанию
Для поиска периода рационального числа существует отдельный алгоритм. Перебираем одну за другой степени числа 10: 10, 100, 1000, 10000 и т.д. Смотрим на остаток от деления этого числа на знаменатель. Если остаток от деления равняется 1, значит степень числа 10, это длина периода. Например, если в знаменателе стоит 13, то:
10 % 13 = 10 100 % 13 = 9 1000 % 13 = 12 10000 % 13 = 3 100000 % 13 = 4 1000000 % 13 = 1 Получается, период равен 6. Этот период не зависит от того, что стоит в числителе (если дробь сокращена).
Метод не работает, если знаменатель делится на 5 или 2. В таком случае его нужно делить на 2, или 5, пока получится число, которое не делится на 2, 5.
В общем случае (как для вашего примера 1/117), придется использовать длинную арифметику.
Алгоритм ищет только длину периода, что бы получить сам период, нужно делить самому.
Python. Из десятичной дроби — в обычную
У класса float есть прекрасный метод as_integer_ratio() , который представляет десятичную дробь в виде обычной — пары «числитель, знаменатель»:
>>> (0.25).as_integer_ratio() (1, 4) >>> (0.5).as_integer_ratio() (1, 2) >>> (0.75).as_integer_ratio() (3, 4) Так вот. Никогда им не пользуйтесь ツ Потому что:
>>> (0.2).as_integer_ratio() (3602879701896397, 18014398509481984) Виной всему стандарт представления дробных чисел IEEE 754, который реализует float.
>>> from decimal import Decimal >>> Decimal("0.2").as_integer_ratio() (1, 5) Уверен, вы и так это знаете. Просто на всякий случай ツ
Подписывайтесь на канал, чтобы не пропустить новые заметки ��
Как записать десятичную дробь в питоне
Для целых чисел определены операции + , — , * и ** . Операция деления / для целых чисел возвращает вещественное число (значение типа float ). Также функция возведения в степень возвращает значение типа float , если показатель степени — отрицательное число.
Но есть и специальная операция целочисленного деления, выполняющегося с отбрасыванием дробной части, которая обозначается // (она соответствует операции div в Паскале). Она возвращает целое число: целую часть частного. Другая близкая ей операция − это операция взятия остатка от деления, обозначаемая % (она соответствует операции mod в Паскале). Например:
print(17 / 3) # выведет 5.66666666667 print(17 // 3) # выведет 5 print(17 % 3) # выведет 2
2. Действительные числа
В этом разделе речь пойдет о действительных числах, имеющих тип float .
Обратите внимание, что если вы хотите считать с клавиатуры действительное число, то результат, возращаемый функцией input() необходимо преобразовывать к типу float :
1.492
x = float(input()) print(x)
Действительные (вещественные) числа представляются в виде чисел с десятичной точкой (а не запятой, как принято при записи десятичных дробей в русских текстах). Для записи очень больших или очень маленьких по модулю чисел используется так называемая запись «с плавающей точкой» (также называемая «научная» запись). В этом случае число представляется в виде некоторой десятичной дроби, называемой мантиссой, умноженной на целочисленную степень десяти (порядок). Например, расстояние от Земли до Солнца равно 1.496·10 11 , а масса молекулы воды 2.99·10 -23 .
Числа с плавающей точкой в программах на языке Питон, а также при вводе и выводе записываются так: сначала пишется мантисса, затем пишется буква e , затем пишется порядок. Пробелы внутри этой записи не ставятся. Например, указанные выше константы можно записать в виде 1.496e11 и 2.99e-23 . Перед самим числом также может стоять знак минус.
Напомним, что результатом операции деления / всегда является действительное число ( float ), в то время как результатом операции // является целое число ( int ).
Преобразование действительных чисел к целому производится с округлением в сторону нуля, то есть int(1.7) == 1 , int(-1.7) == -1 .
3. Библиотека math
Для проведения вычислений с действительными числами язык Питон содержит много дополнительных функций, собранных в библиотеку (модуль), которая называется math .
Для использования этих функций в начале программы необходимо подключить математическую библиотеку, что делается командой
import math
Например, пусть мы хотим округлять вещественные числа до ближайшего целого числа вверх. Соответствующая функция ceil от одного аргумента вызывается, например, так: math.ceil(x) (то есть явно указывается, что из модуля math используется функция ceil ). Вместо числа x может быть любое число, переменная или выражение. Функция возращает значение, которое можно вывести на экран, присвоить другой переменной или использовать в выражении:
import math x = math.ceil(4.2) y = math.ceil(4.8) print(x) print(y)
Другой способ использовать функции из библиотеки math , при котором не нужно будет при каждом использовании функции из модуля math указывать название этого модуля, выглядит так:
from math import ceil x = 7 / 2 y = ceil(x) print(y)
from math import * x = 7 / 2 y = ceil(x) print(y)
Ниже приведен список основных функций модуля math . Более подробное описание этих функций можно найти на сайте с документацией языка Питон.
Некоторые из перечисленных функций ( int , round , abs ) являются стандартными и не требуют подключения модуля math для использования.
Числа: целые, вещественные, комплексные
Числа в Python 3: целые, вещественные, комплексные. Работа с числами и операции над ними.
Целые числа (int)
Числа в Python 3 ничем не отличаются от обычных чисел. Они поддерживают набор самых обычных математических операций:
| x + y | Сложение |
| x — y | Вычитание |
| x * y | Умножение |
| x / y | Деление |
| x // y | Получение целой части от деления |
| x % y | Остаток от деления |
| -x | Смена знака числа |
| abs(x) | Модуль числа |
| divmod(x, y) | Пара (x // y, x % y) |
| x ** y | Возведение в степень |
| pow(x, y[, z]) | x y по модулю (если модуль задан) |
Также нужно отметить, что целые числа в python 3, в отличие от многих других языков, поддерживают длинную арифметику (однако, это требует больше памяти).
Над целыми числами также можно производить битовые операции
| x | y | Побитовое или |
| x ^ y | Побитовое исключающее или |
| x & y | Побитовое и |
| x | Битовый сдвиг влево |
| x >> y | Битовый сдвиг вправо |
| ~x | Инверсия битов |
Дополнительные методы
int.bit_length() — количество бит, необходимых для представления числа в двоичном виде, без учёта знака и лидирующих нулей.
int.to_bytes(length, byteorder, *, signed=False) - возвращает строку байтов, представляющих это число.
int.from_bytes(bytes, byteorder, *, signed=False) - возвращает число из данной строки байтов.
Те, у кого в школе была информатика, знают, что числа могут быть представлены не только в десятичной системе счисления. К примеру, в компьютере используется двоичный код, и, к примеру, число 19 в двоичной системе счисления будет выглядеть как 10011. Также иногда нужно переводить числа из одной системы счисления в другую. Python для этого предоставляет несколько функций:
- int([object], [основание системы счисления]) — преобразование к целому числу в десятичной системе счисления. По умолчанию система счисления десятичная, но можно задать любое основание от 2 до 36 включительно.
- bin(x) — преобразование целого числа в двоичную строку.
- hex(х) — преобразование целого числа в шестнадцатеричную строку.
- oct(х) — преобразование целого числа в восьмеричную строку.
Вещественные числа поддерживают те же операции, что и целые. Однако (из-за представления чисел в компьютере) вещественные числа неточны, и это может привести к ошибкам:
Для высокой точности используют другие объекты (например Decimal и Fraction)).
Также вещественные числа не поддерживают длинную арифметику:
Простенькие примеры работы с числами:
float.as_integer_ratio() — пара целых чисел, чьё отношение равно этому числу.
float.is_integer() — является ли значение целым числом.
float.hex() — переводит float в hex (шестнадцатеричную систему счисления).
classmethod float.fromhex(s) — float из шестнадцатеричной строки.
Помимо стандартных выражений для работы с числами (а в Python их не так уж и много), в составе Python есть несколько полезных модулей.
Модуль math предоставляет более сложные математические функции.
В Python встроены также и комплексные числа:
: complex() Для работы с комплексными числами используется также модуль cmath.
Для вставки кода на Python в комментарий заключайте его в теги
- Модуль csv - чтение и запись CSV файлов
- Создаём сайт на Django, используя хорошие практики. Часть 1: создаём проект
- Онлайн-обучение Python: сравнение популярных программ
- Книги о Python
- GUI (графический интерфейс пользователя)
- Курсы Python
- Модули
- Новости мира Python
- NumPy
- Обработка данных
- Основы программирования
- Примеры программ
- Типы данных в Python
- Видео
- Python для Web
- Работа для Python-программистов
- Сделай свой вклад в развитие сайта!
- Самоучитель Python
- Карта сайта
- Отзывы на книги по Python
- Реклама на сайте