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

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

26.06.2016, 14:34. Показов 6661. Ответов 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
Нарушитель
Эксперт функциональных языков программированияЭксперт С++
6318 / 3043 / 1054
Регистрация: 01.06.2021
Сообщений: 11,601
16.12.2024, 15:18
Студворк — интернет-сервис помощи студентам
COKPOWEHEU, ты хоть считал сколько там итераций будет? Очень мало. Я бы не назвал это перебором) Там же 9 добавляется макс до длины макс long long.
18 итераций в худшем случае вроде
0
 Аватар для COKPOWEHEU
4146 / 2724 / 433
Регистрация: 09.09.2017
Сообщений: 12,069
16.12.2024, 15:55
Использовать string для целочисленных вычислений само по себе непрофессионально.
Как и использование полного перебора вместо аналитического решения.
У Tertiboer и то лучше.
0
Нарушитель
Эксперт функциональных языков программированияЭксперт С++
6318 / 3043 / 1054
Регистрация: 01.06.2021
Сообщений: 11,601
16.12.2024, 16:00
COKPOWEHEU, как раз строки и используются во всех серьезных библиотеках для работы с большими целыми числами (big int). Именно строки, а не даже векторы и прочее...
Но я и не заявляю, что мой алгоритм претендует стать лучшим в данной теме. Мне просто было интересно реализовать предложенную мной выше идею, что я и сделал.
0
 Аватар для COKPOWEHEU
4146 / 2724 / 433
Регистрация: 09.09.2017
Сообщений: 12,069
16.12.2024, 16:33
Цитата Сообщение от Royal_X Посмотреть сообщение
как раз строки и используются во всех серьезных библиотеках для работы с большими целыми числами (big int)
Ну, я, конечно, во внутренности не лазил - но звучит бредово. Длинную арифметику проще на массиве сделать, чем постоянно кодировать - декодировать.
Цитата Сообщение от Royal_X Посмотреть сообщение
Мне просто было интересно реализовать предложенную мной выше идею
А вы можете доказать, что такой подход вообще правильный? Вдруг найдется 153-значное число, у которого период не совпадает с числом девяток? Вы ведь даже не доказали, что любое рациональное число можно записать как дробь с кучей девяток в знаменателе. Я-то немного порисовал на бумажке и вроде бы доказал. Впрочем, к красивому решению это не приближает.
0
Нарушитель
Эксперт функциональных языков программированияЭксперт С++
6318 / 3043 / 1054
Регистрация: 01.06.2021
Сообщений: 11,601
16.12.2024, 16:46
Цитата Сообщение от COKPOWEHEU Посмотреть сообщение
А вы можете доказать
а разве это не доказано уже?
0
 Аватар для COKPOWEHEU
4146 / 2724 / 433
Регистрация: 09.09.2017
Сообщений: 12,069
16.12.2024, 17:38
Цитата Сообщение от Royal_X Посмотреть сообщение
а разве это не доказано уже?
где?
0
Нарушитель
Эксперт функциональных языков программированияЭксперт С++
6318 / 3043 / 1054
Регистрация: 01.06.2021
Сообщений: 11,601
16.12.2024, 17:43
Цитата Сообщение от COKPOWEHEU Посмотреть сообщение
где?
сомневаюсь, что такая тривиальная штука не доказана. Нужно просто поискать, рыться во всяких ArXiv и прочих изданиях. Я даже думаю, что эта штука была доказана еще в Средние Века
0
Вездепух
Эксперт CЭксперт С++
 Аватар для TheCalligrapher
13210 / 6843 / 1824
Регистрация: 18.10.2014
Сообщений: 17,312
16.12.2024, 18:25
Цитата Сообщение от Royal_X Посмотреть сообщение
Если вернуться к теме, то насколько мне известно, любая дробь является бесконечной периодической, когда в знаменателе девятки. Тогда числитель это период с учетом поправок на разрядность.

Например,

47/99 = 0.(47)
1/3 = 3/9 = 0.(3)
2/999 = 0.(002)
1234/9999 = 0.(1234)
Когда-то я решал это уже здесь "в лоб": Вывести на консоль бесконечную периодическую дробь с указанием периода

Однако "небуквальное" решение, конечно, интереснее. В частности, да - через вариант с девятками в знаменателе.
0
Windows must die
610 / 883 / 104
Регистрация: 23.11.2021
Сообщений: 5,170
Записей в блоге: 19
16.12.2024, 18:32
Аналогично можно для чисел, где единицы в знаменателе, начиная с двух: количество цифр в периоде равно количеству единиц в знаменателе, а сам период равен числителю, помноженному на 9. Например, 5/11 = 0.(45), 16/111 = 0.(144), 151/1111 = 0.(1359) и т.д.
(является следствием вышеупомянутого правила о девятках; аналогично следствием будет правило с тройками в знаменателе)
0
 Аватар для COKPOWEHEU
4146 / 2724 / 433
Регистрация: 09.09.2017
Сообщений: 12,069
16.12.2024, 21:26
Цитата Сообщение от Royal_X Посмотреть сообщение
сомневаюсь, что такая тривиальная штука не доказана.
То есть лично вы доказательства не видели и не можете гарантировать работоспособность алгоритма.
Цитата Сообщение от Eddy_Em Посмотреть сообщение
Аналогично можно для чисел, где единицы в знаменателе
Не, с девятками более фундаментально. Но и с ними непонятно как свести к аналитическому решению.
---
Ну ладно, попробую воспроизвести свое доказательство.
Пусть мы хотим проверить рациональное число 1/b = 0,(a), где a - натуральное, повторяющаяся часть периода, b - натуральное. Период в системе счисления N равен k цифрам. Тогда 0,(a) * Nk = a,(a). То есть a до запятой и бесконечно повторяется после.
a,(a) - 0,(a) = a
0,(a) * Nk - 0,(a) = a
0,(a) * (Nk - 1) = a
1/b * (Nk - 1) = a
Nk - 1 = a*b
Nk - число в данной системе счисления, состоящее из единицы и k нулей. Соответственно, Nk - 1 - число, состоящее из k "девяток".
Если я нигде не ошибся, это доказывает, что любое число 1/b будет делителем числа, состоящего из одних "девяток", причем второй делитель будет периодом, а количество девяток - длиной периода.
Полагаю, расширить доказательство до произвольного d/b = x,y(a) будет несложно. Ну там сводим дробь к взаимно простым числам, выносим множитель за скобки, выносим непериодическую часть и т.д.
Что приятно, доказательство работает для любой системы счисления, не только 10. Ну, по крайней мере, должно работать...
А вот как от него перейти к аналитическому решению, я не знаю.
0
Нарушитель
Эксперт функциональных языков программированияЭксперт С++
6318 / 3043 / 1054
Регистрация: 01.06.2021
Сообщений: 11,601
17.12.2024, 00:12
Цитата Сообщение от COKPOWEHEU Посмотреть сообщение
То есть лично вы доказательства
да какое там доказательство, еще очень давно заметил такую закономерность с девятками, вот в этой теме и вспомнил ее снова. Уверен, что все работает, но лень что-то доказывать.
Но здесь есть одно НО. Данный алгоритм работает только, когда повторяющая часть начинается непосредственно после десятичного разделителя. Но вот допустим случай с дробью 7/12. Предложенный мной алгоритм ничего не найдет, ибо тут 0.58(3) - т.е. повторяющаяся часть начинается не сразу после десятичного разделителя.
Хотя, я вот смотрю, код Catstail тоже неверно выводит для такой дроби, пишет 58, что неверно.
Или вот еще одна дробь 1/24 = 0.041(6).
У Catstail выводит 41, что чушь. Мой код тоже не работает.
Как и сказал, наши алгоритмы не работают для таких дробей.
Так что, мой код никак не претендует стать ответом в данной теме. Тем более, я только что увидел, что написал на С++, а то я бы написал на С.
Вот у меня на телефоне есть калькуляторы, которые умеют подчеркивать период. Т.е. вместо повторяющихся цифр, они выводят только период.

Но мне кажется, что эти калькуляторы не используют никаких аналитических алгоритмов по выявлению периода. Тут тупо срабатывает механизм поиска повторяющегося куска.
1
Вездепух
Эксперт CЭксперт С++
 Аватар для TheCalligrapher
13210 / 6843 / 1824
Регистрация: 18.10.2014
Сообщений: 17,312
17.12.2024, 02:03
Цитата Сообщение от Royal_X Посмотреть сообщение
Но здесь есть одно НО. Данный алгоритм работает только, когда повторяющая часть начинается непосредственно после десятичного разделителя. Но вот допустим случай с дробью 7/12. Предложенный мной алгоритм ничего не найдет, ибо тут 0.58(3) - т.е. повторяющаяся часть начинается не сразу после десятичного разделителя.
Ну так не составляет труда сообразить, что 0.58(3) - это 58.(3)/100, то есть 0.58 + 3/900. То есть к девяткам в знаменателе надо приписать столько нулей, на сколько вы хотите отодвинуть периодическую часть от точки.
0
Супер-модератор
Эксперт функциональных языков программированияЭксперт Python
 Аватар для Catstail
38210 / 21143 / 4313
Регистрация: 12.02.2012
Сообщений: 34,757
Записей в блоге: 14
17.12.2024, 06:21
Royal_X, не переживай... Сейчас некогда, но вечером выложу новую версию.
0
Нарушитель
Эксперт функциональных языков программированияЭксперт С++
6318 / 3043 / 1054
Регистрация: 01.06.2021
Сообщений: 11,601
17.12.2024, 09:15
Catstail, я и не переживаю, пусть ТС переживает. У меня других проблем в жизни хватает, не до дробей мне
1
 Аватар для COKPOWEHEU
4146 / 2724 / 433
Регистрация: 09.09.2017
Сообщений: 12,069
17.12.2024, 12:00
Цитата Сообщение от Royal_X Посмотреть сообщение
да какое там доказательство, еще очень давно заметил такую закономерность с девятками
"Заметил закономерность" еще не значит, что она будет работать со всеми числами. 5*5=25, 6*6=36, даже 11*11=121, я "заметил закономерность", что квадрат числа оканчивается на ту же цифру, что и число.
0
Нарушитель
Эксперт функциональных языков программированияЭксперт С++
6318 / 3043 / 1054
Регистрация: 01.06.2021
Сообщений: 11,601
17.12.2024, 12:11
COKPOWEHEU, не ну я проверял не на двух числах. Но я понял вас с первого раза. Это как бинарная гипотеза Гольдбаха. Все понимают, что работает, а работоспособность была проверена аж до 4×10^18, тем не менее, пока не доказано, 100% уверенности нет.
Но сейчас я занят, чтобы заниматься доказательством или его поиском в инете.
0
 Аватар для COKPOWEHEU
4146 / 2724 / 433
Регистрация: 09.09.2017
Сообщений: 12,069
17.12.2024, 13:44
Цитата Сообщение от Royal_X Посмотреть сообщение
Но сейчас я занят, чтобы заниматься доказательством или его поиском в инете.
Да и решение задачи очередного халявщика этих усилий не стоит. Разве что самому интересно найти красивое решение.
0
Супер-модератор
Эксперт функциональных языков программированияЭксперт Python
 Аватар для Catstail
38210 / 21143 / 4313
Регистрация: 12.02.2012
Сообщений: 34,757
Записей в блоге: 14
17.12.2024, 17:55
Выполняю обещание:

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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
char * per_fract(int n, int d)
{
    int ent   = n/d;
    int size  = 200;
    int osize = 1000;
    int *tmp  = (int *) calloc(size,sizeof(int));
    int *res  = (int *) calloc(size,sizeof(int));
 
    int k,p,flg,ptrTmp=0;
 
    n=n%d;
 
    while (1)
    {
        if (n == 0) break;
        
        n=n*10;
        p=n/d;
        
        flg=0;
        
        for (int i=0; i<ptrTmp; i++)
            if (n == tmp[i]) 
            {
                flg=1;
                break;
            }
 
        if (flg) break;
 
        if (ptrTmp >= size)
        {
            size+=200;
            res=(int *) realloc(res,size*sizeof(int));
            tmp=(int *) realloc(tmp,size*sizeof(int));
        }
 
        res[ptrTmp]=p;
        tmp[ptrTmp]=n;
        
        ptrTmp++;
        
        n=n%d;
 
    }
 
    char *result = (char *) calloc(osize,sizeof(char));
    char *ttt    = (char *) calloc(osize,sizeof(char));
    
    snprintf(result,osize,"%d",ent);
    
    strcat(result,".");
 
    k=-1;
    for (int i=0; i<ptrTmp; i++)
        if (tmp[i] == n)
        {
            k=i;
            break;
        }
 
    if (k >= 0)
    {
        for (int i=0; i<k; i++)
        {
            snprintf(ttt,1000,"%d",res[i]);
            if (strlen(result)+strlen(ttt) > osize)
            {
                osize=osize+1000;
                result=(char *) realloc(result,osize*sizeof(char));
            }
            strcat(result,ttt);
        }
        if (k < ptrTmp)
        {
            strcat(result,"(");
        
            for (int i=k; i<ptrTmp; i++)
            {
               snprintf(ttt,1000,"%d",res[i]);
               if (strlen(result)+strlen(ttt) > osize)
               {
                  osize=osize+1000;
                  result=(char *) realloc(result,osize*sizeof(char));
               }
               strcat(result,ttt);
            }
            
            strcat(result,")");
        }
    }
    else
    {
        for (int i=0; i<ptrTmp; i++)
        {
           snprintf(ttt,1000,"%d",res[i]);
           if (strlen(result)+strlen(ttt) > osize)
           {
              osize=osize+1000;
              result=(char *) realloc(result,osize*sizeof(char));
           }
           strcat(result,ttt);
        }
    }
 
    free(tmp);
    free(res);
    free(ttt);
 
    result=realloc(result,(strlen(result)+1)*sizeof(char));
    return result;
 
}
 
int main()
{
 
    char *s=per_fract(1,24);
    printf("%s\n",s);
    free(s);
    s=per_fract(7,12);
    printf("%s\n",s);
    free(s);
    s=per_fract(1,50);
    printf("%s\n",s);
    free(s);
    s=per_fract(1,3);
    printf("%s\n",s);
    free(s);
 
    return 0;
    
}
Вывод:

0.041(6)
0.58(3)
0.02
0.(3)
1
 Аватар для Pphantom
2469 / 1615 / 741
Регистрация: 17.03.2022
Сообщений: 5,264
17.12.2024, 18:26
Вообще говоря, есть стандартный алгоритм для определения периода дроби a/b (при a<b). Выглядит он примерно так:
1) Делим a на b с остатком и фиксируем остаток;
2) Делим 10*a на b и фиксируем остаток;
...
n) Делим 10^n*a на b и фиксируем остаток;
...

Разность номеров первых двух одинаковых остатков - период дроби. Номер k, на котором повторившийся остаток встретился в первый раз - номер цифры после запятой, с которой дробь стала периодической.

Ну и все, собственно. Реализация на C, наверное, всем присутствующим очевидна.
2
Вездепух
Эксперт CЭксперт С++
 Аватар для TheCalligrapher
13210 / 6843 / 1824
Регистрация: 18.10.2014
Сообщений: 17,312
17.12.2024, 21:34
Цитата Сообщение от Pphantom Посмотреть сообщение
Вообще говоря, есть стандартный алгоритм
Ссылку на его описание и С++ реализацию я дал в #28. Его же реализовал выше Catstail.

Цитата Сообщение от Pphantom Посмотреть сообщение
Реализация на C, наверное, всем присутствующим очевидна.
Практически лобовая перереализация моего варианта на С может выглядеть так

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
71
72
73
74
#include <assert.h>
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
 
char *periodic_decimal(unsigned a, unsigned b)
{
  size_t n_full_mem = 32;
  char *full = malloc(n_full_mem * sizeof *full);
  size_t n_full = snprintf(full, n_full_mem, "%u.", a / b), n_offset = n_full;
 
  a %= b;
 
  unsigned *rems = NULL;
  size_t n_rems = 0;
 
  do
  {
    assert(a < b);
 
    rems = realloc(rems, ++n_rems * sizeof *rems);
    rems[n_rems - 1] = a;
 
    a *= 10;
 
    ++n_full;
    if (n_full > n_full_mem)
      full = realloc(full, (n_full_mem += 32) * sizeof *full);
 
    assert(n_full < n_full_mem);
    assert(a / b < 10);
    full[n_full - 1] = '0' + a / b;
 
    a %= b;
    if (a == 0)
      break;
 
    size_t i = 0;
    for (; i < n_rems; ++i)
      if (rems[i] == a)
        break;
 
    if (i < n_rems)
    {
      n_full += 2;
      if (n_full > n_full_mem)
        full = realloc(full, (n_full_mem += 32) * sizeof *full);
 
      i += n_offset;
      memmove(full + i + 1, full + i, n_full - 2 - i);
      full[i] = '(';
      full[n_full - 1] = ')';
 
      break;
    }
  } while (1);
 
  free(rems);
 
  ++n_full;
  full = realloc(full, (n_full_mem = n_full) * sizeof *full);
  full[n_full - 1] = '\0';
 
  return full;
}
 
int main(void)
{
  char *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);
}
Несколько компактнее, осмелюсь заметить, Catstailовской стены кода, невероятных копипаст и ресканов строк.
1
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
BasicMan
Эксперт
29316 / 5623 / 2384
Регистрация: 17.02.2009
Сообщений: 30,364
Блог
17.12.2024, 21:34

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

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

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

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

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


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

Или воспользуйтесь поиском по форуму:
40
Ответ Создать тему
Новые блоги и статьи
Мир по моей воле
kumehtar 07.08.2026
Когда-то кажется, что всё просто. Ты весь такой светлый. Причиняешь добро. Борешься за справедливость в этом тёмном мире. Потом начинаешь замечать одну неприятную вещь. Почти каждый хороший. . .
Кредитный калькулятор
Maks 05.08.2026
Решение задачи по прикладной информатике средствами 1С. Задача: Напишите приложение-калькулятор, которое помогает рассчитывать параметры кредита для аннуитетного и дифференцированного видов. . .
У нас сейчас поговорку "Опять 25" нужно переделать на "Опять +35".
kumehtar 04.08.2026
С ностальгией вспоминаю времена моего детства, когда у нас и правда +25 - была максимальная температура летом. Раньше +25 °C реально казались вершиной жары, когда можно было весь день пропадать на. . .
Как ИИ начал спорить и врать (возможно почуяв опасность для себя от индустрии - уход от электроники).
Hrethgir 04.08.2026
Недельный диалог, на фоне событий с НПЗ. Да, из спирта можно получать бензин, и это не сложно. Но потом в схеме я решил избавиться от насоса, при этом полностью сделав контроль подачи спирта в. . .
Термопринтер QR701
Argus19 03.08.2026
Термопринтер QR701 Купил два термопринтера QR701. На сэлф-тесте написано: Language: PC936 (GB18030). Что означает, что принтеры могут печатать только латиницу и китайские иероглифы. Так же. . .
Создание формы заимствованного документа
Maks 03.08.2026
Задача: Необходимо создать собственную форму заимствованного документа. На форме должен быть реквизит "Покупатель", а также табличная часть со следующими реквизитами: - Расчетный счет покупателя. . .
Задача предоставления скидок покупателям
Maks 03.08.2026
Задача: В документе "Продажи" необходимо реализовать функционал предоставления скидок покупателям. Скидка должна автоматически рассчитываться и подставляться в соответствующее поле при выборе. . .
Почему SEO не начинается с ключевых слов: что проверить до написания текстов
Neotwalker 01.08.2026
Когда владельцу сайта предлагают заняться SEO, первым шагом часто становится сбор запросов и написание текстов. Логика кажется понятной: 1. Находим ключевые слова. 2. Добавляем их на. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru