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

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

26.06.2016, 14:34. Показов 6673. Ответов 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
2469 / 1615 / 741
Регистрация: 17.03.2022
Сообщений: 5,266
17.12.2024, 22:13
Цитата Сообщение от TheCalligrapher Посмотреть сообщение
Ссылку на его описание и С++ реализацию я дал в #28. Его же реализовал выше Catstail.
В общем да, но истребить среди себя желание сначала ответить на заданный в теме вопрос, а потом прочитать все, что было позже, слишком сложно.
0
17.12.2024, 23:40

Не по теме:

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

0
Вездепух
Эксперт CЭксперт С++
 Аватар для TheCalligrapher
13211 / 6844 / 1824
Регистрация: 18.10.2014
Сообщений: 17,322
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
38221 / 21153 / 4314
Регистрация: 12.02.2012
Сообщений: 34,764
Записей в блоге: 14
18.12.2024, 06:00
TheCalligrapher, осторожно замечу, что в строках 36, 49 и 53 не проверяется, доступна ли память (по указателю p).
0
Вездепух
Эксперт CЭксперт С++
 Аватар для TheCalligrapher
13211 / 6844 / 1824
Регистрация: 18.10.2014
Сообщений: 17,322
18.12.2024, 07:09
Цитата Сообщение от Catstail Посмотреть сообщение
TheCalligrapher, осторожно замечу, что в строках 36, 49 и 53 не проверяется, доступна ли память (по указателю p).
В С не существует способа проверки валидности указателя.

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

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

В предыдущих вариантах (включая мой и ваш) у нас вообще не было такой возможности, ибо тот способ расчета длины периода требовал хранения остатков. А для них уже требовалась память заранее неизвестного размера.
1
Супер-модератор
Эксперт функциональных языков программированияЭксперт Python
 Аватар для Catstail
38221 / 21153 / 4314
Регистрация: 12.02.2012
Сообщений: 34,764
Записей в блоге: 14
18.12.2024, 08:36
TheCalligrapher, да, я понял. Прошу прощения, в дискуссию не вник.
0
Вездепух
Эксперт CЭксперт С++
 Аватар для TheCalligrapher
13211 / 6844 / 1824
Регистрация: 18.10.2014
Сообщений: 17,322
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
Ответ Создать тему
Новые блоги и статьи
Часы электронные
Uhbif79 12.08.2026
Выкладываю программу часов. Программа позволяет: 1. Использовать системное время и дату, 2. Есть возможность вводить время и дату вручную. 3. Реализованы 2 будильника: начало и конец рабочего дня. . . .
Часы с будильником на основе класса QLCDNumber
Uhbif79 12.08.2026
Всем добрый день, выкладываю программу часов с будильником на основе класса QLCDNumber. Здесь я пробовал самостоятельно создавал классы, впервые столкнулся с видимостью переменной одного класса из. . .
Установка MinGW GCC 16.2 и CMake
8Observer8 10.08.2026
VK Видео: https:/ / vkvideo. ru/ video-240781534_456239017 YouTube: eY5-5PyI9NM Текстовая версия
Неделя из жизни имитационной модели склада: мои кривые руки растут, откуда надо
anaschu 10.08.2026
Неделя из жизни имитационной модели склада: как я почти написал неправильную логику и что с этим делать Работаю сейчас над учебно-рабочим проектом: строю в AnyLogic имитационную модель процессов. . .
Калькулятор для расчета родства
russiannick 07.08.2026
1. Задача: Создать калькулятор для расчета родства. Родственных связей существует 8 ступеней, такие как: p - отец P - мать q - муж Q - жена b - брат B - сестра s - сын S - дочь
Мир по моей воле
kumehtar 07.08.2026
Когда-то кажется, что всё просто. Ты весь такой светлый. Причиняешь добро. Борешься за справедливость в этом тёмном мире. Потом начинаешь замечать одну неприятную вещь. Почти каждый хороший. . .
Кредитный калькулятор
Maks 05.08.2026
Решение задачи по прикладной информатике средствами 1С. Задача: Напишите приложение-калькулятор, которое помогает рассчитывать параметры кредита для аннуитетного и дифференцированного видов. . .
У нас сейчас поговорку "Опять 25" нужно переделать на "Опять +35".
kumehtar 04.08.2026
С ностальгией вспоминаю времена моего детства, когда у нас и правда +25 - была максимальная температура летом. Раньше +25 °C реально казались вершиной жары, когда можно было весь день пропадать на. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru