2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




На страницу 1, 2  След.
 
 Задача вродебы простая. Определить десятичный вид дроби
Сообщение07.12.2014, 15:03 
Даны числа $n$, $m$, надо определить
ее десятичный вид, в случае если это бесконечная периодическая
дробь, выделить период в круглый скобках:

Пример:
$$\frac{1}{3} = 0.(3)$$
$$\frac{1}{2} = 0.5$$

Задачу надо решить алгоритмически, ну, я получил цифры после
запятой и попытался искать повторяющуюся строку, но для некоторых
чисел период вообще большой получается.

Есть какие нибудь математические методы?

 
 
 
 Re: Задача вродебы простая.
Сообщение07.12.2014, 15:07 
Аватара пользователя
Период десятичной дроби $m/n$ не может по длине быть больше, чем $n-1$. Эта граница достигается: известный пример - $1/7$.
С другой стороны, период будет делителем числа $99...9$ для подходящего числа девяток.

Нет, там еще могут повлиять двойки и пятерки.

 
 
 
 Re: Задача вродебы простая.
Сообщение07.12.2014, 15:16 
Получается так:
Если $m > n$, отбрасываем целую часть.
Находим подходящее кол-во девяток, а оно подходящее
если $n$ нацело делит $999...9$,
затем умножаем полученное число на числитель, остаток
от деленая $m$ на $n$.

Я бы мог найти подходящее количество девяток перебором, но думаю
что это будет довольно медленно.

 
 
 
 Re: Задача вродебы простая.
Сообщение07.12.2014, 15:18 
Аватара пользователя
Я там отредактировала немного.
Сейчас убегаю, буду часа через два. Может, еще кто подключится. Или ждите меня.

А вы знаете малую теорему Ферма?

 
 
 
 Re: Задача вродебы простая.
Сообщение07.12.2014, 15:20 
provincialka в сообщении #941800 писал(а):
А вы знаете малую теорему Ферма?

Нет

 
 
 
 Re: Задача вродебы простая.
Сообщение07.12.2014, 15:58 
frankenstein в сообщении #941801 писал(а):
provincialka в сообщении #941800 писал(а):
А вы знаете малую теорему Ферма?

Нет
Ознакомьтесь. И с теоремой Эйлера заодно и с функцией Кармайкла. Жить станет легче.

 
 
 
 Re: Задача вродебы простая.
Сообщение07.12.2014, 15:58 
Sonic86 в сообщении #941820 писал(а):
frankenstein в сообщении #941801 писал(а):
provincialka в сообщении #941800 писал(а):
А вы знаете малую теорему Ферма?

Нет
Ознакомьтесь. И с теоремой Эйлера заодно и с функцией Кармайкла. Жить станет легче.

Ок :mrgreen:

 
 
 
 Re: Задача вродебы простая.
Сообщение07.12.2014, 16:12 
Аватара пользователя
 i  Заголовок темы изменён без согласия с ТС.
frankenstein, давайте, пожалуйста, темам содержательные названия.

 
 
 
 Re: Задача вродебы простая.
Сообщение07.12.2014, 16:14 
Deggial в сообщении #941828 писал(а):
 i  Заголовок темы изменён без согласия с ТС.
frankenstein, давайте, пожалуйста, темам содержательные названия.

Ладно

 
 
 
 Re: Задача вродебы простая. Определить десятичный вид дроби
Сообщение07.12.2014, 16:27 
Аватара пользователя
frankenstein в сообщении #941791 писал(а):
Пример:
$$\frac{1}{3} = 0.(3)$$
$$\frac{1}{2} = 0.5$$

Формально $\frac{1}{2} = 0.5(0)=0.4(9)$.

 
 
 
 Re: Задача вродебы простая. Определить десятичный вид дроби
Сообщение07.12.2014, 16:53 
круто!

 
 
 
 Re: Задача вродебы простая. Определить десятичный вид дроби
Сообщение07.12.2014, 20:15 
frankenstein, если делить как в школе, то начало повтора определяется по повторению очередного остатка — раз он совпал, дальше результаты делений совпадут тоже.

 
 
 
 Re: Задача вродебы простая. Определить десятичный вид дроби
Сообщение07.12.2014, 20:17 
Аватара пользователя
Вообще многое зависит от того, насколько "продвинутую" программу надо делать. Одно дело - учебная однодневка, лишь бы считала. Другое - оптимизированная солидная программа, которая может справиться с огромными числами.

 
 
 
 Re: Задача вродебы простая. Определить десятичный вид дроби
Сообщение07.12.2014, 20:37 
Программа должна уметь работать с таким диапазоном чисел:
$0 \le N,M \le 100000$

Да, думаю школьный метод сработает.

provincialka, я просто пытаюсь решить задачу на http://train.usaco.org :D

 
 
 
 Re: Задача вродебы простая. Определить десятичный вид дроби
Сообщение07.12.2014, 20:42 
Аватара пользователя
А почему у меня "Веб-страница недоступна"?

 
 
 [ Сообщений: 18 ]  На страницу 1, 2  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group