Форум программистов, компьютерный форум, киберфорум
C для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
 
Рейтинг 5.00/19: Рейтинг темы: голосов - 19, средняя оценка - 5.00
1 / 1 / 0
Регистрация: 24.06.2016
Сообщений: 143

Написать программу, определяющую период дроби

26.06.2016, 14:34. Показов 6552. Ответов 49
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Любое рациональное число представляется в виде бесконечной десятичной периодической дроби. Написать программу, определяющую период дроби n / m, где n и m – натуральные числа.
0
IT_Exp
Эксперт
34794 / 4073 / 2104
Регистрация: 17.06.2006
Сообщений: 32,602
Блог
26.06.2016, 14:34
Ответы с готовыми решениями:

Определить период дроби
Помогите пожалуйста составить программу. Нужно определить период дроби.

Написать программу определяющую произведение цифр
Здравствуйте, помогите пожалуйста написать программу Дано натуральное число. Определить: а) произведение его цифр, больших семи; ...

Написать программу определяющую коды ASCII
Напишите программу, определяющую коды ASCII, введенных с клавиатуры букв. Выход из программы по нажатию клавиши ESC.

49
17.12.2024, 21:57
Студворк — интернет-сервис помощи студентам

Не по теме:

Цитата Сообщение от TheCalligrapher Посмотреть сообщение
Несколько компактнее, осмелюсь заметить
стиль полубога, не иначе
Цитата Сообщение от TheCalligrapher Посмотреть сообщение
Catstailовской стены кода, невероятных копипаст и ресканов строк
не ну смертные пишут только так
Цитата Сообщение от TheCalligrapher Посмотреть сообщение
Ссылку на его описание и С++ реализацию я дал в #28.
наверное, для многих прочесть описание алгоритма в посте Pphantom проще, чем по ссылкам переходить и коды анализировать. И этот алгоритм был тыщу раз описан, обкатан и пережеван только на этом форуме, не говоря уже о всем инете...

0
 Аватар для Pphantom
2446 / 1589 / 738
Регистрация: 17.03.2022
Сообщений: 5,151
17.12.2024, 22:13
Цитата Сообщение от TheCalligrapher Посмотреть сообщение
Ссылку на его описание и С++ реализацию я дал в #28. Его же реализовал выше Catstail.
В общем да, но истребить среди себя желание сначала ответить на заданный в теме вопрос, а потом прочитать все, что было позже, слишком сложно.
0
17.12.2024, 23:40

Не по теме:

Цитата Сообщение от Royal_X Посмотреть сообщение
наверное, для многих прочесть описание алгоритма в посте Pphantom проще, чем по ссылкам переходить и коды анализировать. И этот алгоритм был тыщу раз описан, обкатан и пережеван только на этом форуме, не говоря уже о всем инете...
Какой интерес, если все равно полным перебором решается...

0
Вездепух
Эксперт CЭксперт С++
 Аватар для TheCalligrapher
13205 / 6840 / 1822
Регистрация: 18.10.2014
Сообщений: 17,302
18.12.2024, 02:04
Однако, возможно, разговор пошел совсем не о той задаче. "Определить период" может означать, что ТСу нужно лишь найти длину периода, а не напечатать его десятичное разложение. Длина периода - это совсем другая задача из теории чисел.

Длина периода зависит только от знаменателя b. Чтобы найти длину периода, нужно избавить b от факторов 2 и 5, а затем просто найти наименьшее p, для которого 10p = 1 (mod b). И все.

C
1
2
3
4
5
6
7
8
9
10
11
12
13
unsigned period_length(unsigned b)
{
  for (; b % 2 == 0; b /= 2);
  for (; b % 5 == 0; b /= 5);
 
  if (b <= 1)
    return 0;
 
  unsigned p = 1;
  for (unsigned d = 10 % b; d > 1; d = (d * 10) % b, ++p);
 
  return p;
}
Понятно, что это задача дискретного логарифма, которая в таком варианте в худшем случае может потребовать b итераций приведенного цикла (после избавления b от факторов 2 и 5). Для основания 10 её, насколько я знаю, можно решить и более эффективно.

(Учитывая, что степени 10 и препроцессированное b являются взаимно простыми числами, вышеприведенному соотношению будет удовлетворять значение Функции Эйлера для b. Однако Функция Эйлера не гарантирует минимальности такого значения, а нам нужно именно минимальное.)

Добавлено через 36 минут
Степени факторов 2 и 5 в исходном значении знаменателя определяют длину непериодического префикса десятичного представления. Прикрутив все это к алгоритму генерации десятичного разложения, мы получим то, что мы делали выше, но уже без необходимости хранить и перебирать остатки.

Вот вариант формирования строкового представления, основанный на этом принципе. Никакого хранения (и перебора) остатков, единственное выделения памяти (нет переаллокации):

C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <assert.h>
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
 
char *periodic_decimal(unsigned a, unsigned b)
{
  assert(b > 0);
  size_t n_whole = snprintf(NULL, 0, "%u", a / b);
 
  unsigned reduced_b = b;
  unsigned n2 = 0, n5 = 0;
  for (; reduced_b % 2 == 0; reduced_b /= 2, ++n2);
  for (; reduced_b % 5 == 0; reduced_b /= 5, ++n5);
  size_t n_non_periodic = n2 >= n5 ? n2 : n5;
 
  size_t n_periodic = 0;
  if (reduced_b > 1)
  {
    n_periodic = 1;
    for (unsigned d = 10 % reduced_b; d > 1; d = (d * 10) % reduced_b, ++n_periodic);
  }
 
  size_t n_full = n_whole + 1 + n_non_periodic + (n_periodic > 0 ? 1 + n_periodic + 1 : 0);
  char *full = malloc(n_full + 1), *p = full;
 
  p += snprintf(p, n_full + 1, "%u.", a / b);
  a %= b;
  assert(p - full == n_whole + 1);
 
  for (; n_non_periodic > 0; --n_non_periodic)
  {
    assert(a < b);
    a *= 10;
    assert(a / b < 10);
    *p++ = '0' + a / b;
    a %= b;
  }
 
  if (n_periodic > 0)
  {
    *p++ = '(';
 
    for (; n_periodic > 0; --n_periodic)
    {
      assert(a < b);
      a *= 10;
      assert(a / b < 10);
      *p++ = '0' + a / b;
      a %= b;
    }
 
    *p++ = ')';
  }
 
  *p++ = '\0';
  assert(p - full == n_full + 1);
 
  return full;
}
 
int main(void)
{
  char *s;
  printf("%s\n", s = periodic_decimal(435, 28)); free(s);
  printf("%s\n", s = periodic_decimal(1, 24)); free(s);
  printf("%s\n", s = periodic_decimal(7, 12)); free(s);
  printf("%s\n", s = periodic_decimal(1, 50)); free(s);
  printf("%s\n", s = periodic_decimal(1, 3)); free(s);
}
1
Супер-модератор
Эксперт функциональных языков программированияЭксперт Python
 Аватар для Catstail
38207 / 21139 / 4311
Регистрация: 12.02.2012
Сообщений: 34,751
Записей в блоге: 14
18.12.2024, 06:00
TheCalligrapher, осторожно замечу, что в строках 36, 49 и 53 не проверяется, доступна ли память (по указателю p).
0
Вездепух
Эксперт CЭксперт С++
 Аватар для TheCalligrapher
13205 / 6840 / 1822
Регистрация: 18.10.2014
Сообщений: 17,302
18.12.2024, 07:09
Цитата Сообщение от Catstail Посмотреть сообщение
TheCalligrapher, осторожно замечу, что в строках 36, 49 и 53 не проверяется, доступна ли память (по указателю p).
В С не существует способа проверки валидности указателя.

Доступность памяти в данном случае держится на корректности математических вычислений, на основе которых был вычислен размер выделенного блока. Никаких сомнений в правильности этого математического аппарата у меня нет (см. сообщение #44). Если они есть у вас - пожалте их в студию. А я произвожу лишь отладочные sanity checks на основе assert. В частности, последний assert (строка 57), проверяет, что вычисленный размер точен до символа.

Придраться можно только к тому, что я не проверяю успешность malloc. Но это всем и так понятно. Оставлено читателю в качестве упражнения.
1
Супер-модератор
Эксперт функциональных языков программированияЭксперт Python
 Аватар для Catstail
38207 / 21139 / 4311
Регистрация: 12.02.2012
Сообщений: 34,751
Записей в блоге: 14
18.12.2024, 07:13
Да, вы рассчитываете размер периода заранее. Так рациональнее. А я просто добавляю память по мере необходимости.
0
Вездепух
Эксперт CЭксперт С++
 Аватар для TheCalligrapher
13205 / 6840 / 1822
Регистрация: 18.10.2014
Сообщений: 17,302
18.12.2024, 08:11
Цитата Сообщение от Catstail Посмотреть сообщение
Да, вы рассчитываете размер периода заранее. Так рациональнее. А я просто добавляю память по мере необходимости.
Ну, собственно, критическое отличие, ради которого этот вариант и затевался, состоит в том, что вычисление размера на основе теории из #44, само по себе не требует никакой дополнительной памяти: на надо хранить остатки, не надо проверять остатки. Именно благодаря этому и удается полностью избежать работы с памятью вплоть до того момента, когда размер требуемой памяти становится полностью известен.

В предыдущих вариантах (включая мой и ваш) у нас вообще не было такой возможности, ибо тот способ расчета длины периода требовал хранения остатков. А для них уже требовалась память заранее неизвестного размера.
1
Супер-модератор
Эксперт функциональных языков программированияЭксперт Python
 Аватар для Catstail
38207 / 21139 / 4311
Регистрация: 12.02.2012
Сообщений: 34,751
Записей в блоге: 14
18.12.2024, 08:36
TheCalligrapher, да, я понял. Прошу прощения, в дискуссию не вник.
0
Вездепух
Эксперт CЭксперт С++
 Аватар для TheCalligrapher
13205 / 6840 / 1822
Регистрация: 18.10.2014
Сообщений: 17,302
19.12.2024, 18:03
Цитата Сообщение от TheCalligrapher Посмотреть сообщение
Длина периода зависит только от знаменателя b.
Погнавшись за теорией, я упустил практику. Зависимость от a, конечно, есть. Результат является конечной дробью не только когда редуцированное b равно 1, а всегда, когда a делится на редуцированное b. Это тоже нужно учитывать, если вы не хотите, чтобы 3/6 превращалось в 0.5(0)

C
17
18
19
20
21
22
23
  assert(reduced_b > 0);
  size_t n_periodic = 0;
  if (a % reduced_b != 0)
  {
    n_periodic = 1;
    for (unsigned d = 10 % reduced_b; d > 1; d = (d * 10) % reduced_b, ++n_periodic);
  }
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
BasicMan
Эксперт
29316 / 5623 / 2384
Регистрация: 17.02.2009
Сообщений: 30,364
Блог
19.12.2024, 18:03
Помогаю со студенческими работами здесь

Составьте программу, определяющую период десятичной дроби
составьте программу, определяющую период десятичной дроби m\n (m, n - натуральные числа).

Составить программу, которая для натуральных чисел m и n вычисляет период десятичной дроби m/n
Помогите пожалуйста сделать такую интересную программу(а то все перепробывал нифига не выходит) Составить программу, которая для...

Напишите программу, которая переводит правильную дробь в десятичную, выделив (если нужно), период дроби
Напишите программу, которая переводит правильную дробь в десятичную, выделив (если нужно), период дроби. Входные данные Входная...

Определить длину периода десятичной дроби M/N и период данной десятичной дроби M/N
Даны два натуральных числа M и N, M &lt; N. Определить длину периода десятичной дроби M/N и период данной десятичной дроби M/N. Добавлено...

Период у дроби
Найти период бесконечной периодической дроби. Если десятичная дробь конечна, её период — цифра 0. Период должен начинаться с той цифры,...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
50
Ответ Создать тему
Новые блоги и статьи
20. Мат мед. Абсентеизм как отдельный тип простоя
anaschu 29.05.2026
Апдейт модели: исправленные баги, абсентеизм и новые механизмы Продолжаю развивать ранее описанную модель рабочего коллектива на AnyLogic. За последние несколько дней был проведён серьёзный. . .
19. здоровье, усталость и психотип работника влияют на производительность предприятия, и наоборот, производительность на здоровье, усталось и психотип
anaschu 28.05.2026
Дискретно-событийная модель рабочего коллектива на AnyLogic: здоровье, выгорание, психотипы и микростимуляция Привет, коллеги. Хочу поделиться итогами нескольких недель работы над симуляционной. . .
"Прокси" для последовательного порта
Eddy_Em 28.05.2026
Эту штуку написал я достаточно давно. Но сейчас вот понадобилось настроить датчик грозы, но при этом не отключать его от "метеодемона". Соответственно, надо запустить этот "прокси": метеодемон будет. . .
Рефакторинг программы уравнивания.
Massaraksh7 26.05.2026
Пример по предыдущей записи в блоге. Но, надо заметить, что, во-первых, там оптимизация не только математики, но и работы с базой данных, и с графами, а во-вторых, это ещё не всё.
Использование TThread в Lazarus для математических вычислений.
Massaraksh7 25.05.2026
Производя рефакторинг своих программ на предмет ускорения их работы, обратил внимание на такой аспект, как сокращение времени матвычислений. Дело в том, что приходится работать с большими матрицами. . .
Модель здравосохранения 18. Чем здоровее работник, тем быстрее выгорает
anaschu 24.05.2026
Имитационная модель корпоративного здравоохранения: что показывает математика Сегодня в модели рабочего коллектива на AnyLogic появились три новые механики — выгорание через накопленную усталость,. . .
Модель здравосохранения 17. Планы на выгорание
anaschu 23.05.2026
Вот конкретная схема реализации: В классе Работник добавить: накопленнаяУсталость — растёт каждый час работы, снижается в перерывы и болезни коэффициентПрезентеизма — снижает продуктивность. . .
Изменение цветов в палитре gif файла aka фавикона
russiannick 23.05.2026
Изменение цветов в палитре gif файла, юзаемого как фавиконка в составе html-файла, помещенная в base64, средствами нативного Java Script, навеянное сном в майский день. Для работы необходим браузер,. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru