2014 dxdy logo

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

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


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

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

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

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Задача вродебы простая. Определить десятичный вид дроби
Сообщение07.12.2014, 15:03 


10/05/13
251
Даны числа $n$, $m$, надо определить
ее десятичный вид, в случае если это бесконечная периодическая
дробь, выделить период в круглый скобках:

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

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

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

 Профиль  
                  
 
 Re: Задача вродебы простая.
Сообщение07.12.2014, 15:07 
Заслуженный участник
Аватара пользователя


18/01/13
12044
Казань
Период десятичной дроби $m/n$ не может по длине быть больше, чем $n-1$. Эта граница достигается: известный пример - $1/7$.
С другой стороны, период будет делителем числа $99...9$ для подходящего числа девяток.

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

 Профиль  
                  
 
 Re: Задача вродебы простая.
Сообщение07.12.2014, 15:16 


10/05/13
251
Получается так:
Если $m > n$, отбрасываем целую часть.
Находим подходящее кол-во девяток, а оно подходящее
если $n$ нацело делит $999...9$,
затем умножаем полученное число на числитель, остаток
от деленая $m$ на $n$.

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

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


18/01/13
12044
Казань
Я там отредактировала немного.
Сейчас убегаю, буду часа через два. Может, еще кто подключится. Или ждите меня.

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

 Профиль  
                  
 
 Re: Задача вродебы простая.
Сообщение07.12.2014, 15:20 


10/05/13
251
provincialka в сообщении #941800 писал(а):
А вы знаете малую теорему Ферма?

Нет

 Профиль  
                  
 
 Re: Задача вродебы простая.
Сообщение07.12.2014, 15:58 
Заслуженный участник


08/04/08
8556
frankenstein в сообщении #941801 писал(а):
provincialka в сообщении #941800 писал(а):
А вы знаете малую теорему Ферма?

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

 Профиль  
                  
 
 Re: Задача вродебы простая.
Сообщение07.12.2014, 15:58 


10/05/13
251
Sonic86 в сообщении #941820 писал(а):
frankenstein в сообщении #941801 писал(а):
provincialka в сообщении #941800 писал(а):
А вы знаете малую теорему Ферма?

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

Ок :mrgreen:

 Профиль  
                  
 
 Re: Задача вродебы простая.
Сообщение07.12.2014, 16:12 
Супермодератор
Аватара пользователя


20/11/12
5728
 i  Заголовок темы изменён без согласия с ТС.
frankenstein, давайте, пожалуйста, темам содержательные названия.

 Профиль  
                  
 
 Re: Задача вродебы простая.
Сообщение07.12.2014, 16:14 


10/05/13
251
Deggial в сообщении #941828 писал(а):
 i  Заголовок темы изменён без согласия с ТС.
frankenstein, давайте, пожалуйста, темам содержательные названия.

Ладно

 Профиль  
                  
 
 Re: Задача вродебы простая. Определить десятичный вид дроби
Сообщение07.12.2014, 16:27 
Аватара пользователя


21/01/09
3923
Дивногорск
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 


10/05/13
251
круто!

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


27/04/09
28128
frankenstein, если делить как в школе, то начало повтора определяется по повторению очередного остатка — раз он совпал, дальше результаты делений совпадут тоже.

 Профиль  
                  
 
 Re: Задача вродебы простая. Определить десятичный вид дроби
Сообщение07.12.2014, 20:17 
Заслуженный участник
Аватара пользователя


18/01/13
12044
Казань
Вообще многое зависит от того, насколько "продвинутую" программу надо делать. Одно дело - учебная однодневка, лишь бы считала. Другое - оптимизированная солидная программа, которая может справиться с огромными числами.

 Профиль  
                  
 
 Re: Задача вродебы простая. Определить десятичный вид дроби
Сообщение07.12.2014, 20:37 


10/05/13
251
Программа должна уметь работать с таким диапазоном чисел:
$0 \le N,M \le 100000$

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

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

 Профиль  
                  
 
 Re: Задача вродебы простая. Определить десятичный вид дроби
Сообщение07.12.2014, 20:42 
Заслуженный участник
Аватара пользователя


18/01/13
12044
Казань
А почему у меня "Веб-страница недоступна"?

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 18 ]  На страницу 1, 2  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group