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

@Pomogitemnepj · Регистрация: 05.02.2018

Author24 — интернет-сервис помощи студентам

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

Входные данные
Входная строка содержит два числа M и N , разделённых пробелами. Гарантируется, что M < N .

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

Примеры
входные данные
1 2
выходные данные
0,5
входные данные
3 14
выходные данные
0,2(142857)

@Hitoku · 10.02.2018, 01:44

Что-то вроде того

Pascal

var n, m, dot: integer;
    s: string;
begin
  read(n, m);
  s := FloatToStr(n / m);
  dot := pos('.', s);
  if (length(copy(s, dot, length(s) - dot)) <> 1) then begin
    insert('(', s, dot + 2);
    insert(')', s, length(s) + 1);
  end;
  delete(s, dot, 1);
  insert(',', s, dot);
  writeln(s);
end.

@Cyborg Drone · 11.02.2018, 01:22

Hitoku, я даже и не знаю, что сказать... Не решение. 1/47, например?

Добавлено через 3 часа 5 минут
Hitoku, гляди. Не оптимизировал. Алгоритм в общих чертах:

Любая правильная или неправильная дробь представима в виде c,r(p), где с - целая часть, r - предпериод, p - период дроби. Например, 3/14=0,2142857142857142857...=0,2(142857): 0 - целая часть, 2 - предпериод, 142857 - период. Целая часть есть всегда, а вот есть ли предпериод и / или период - это нужно выяснять.

Сразу выделяем и печатаем целую часть дроби, и сокращаем дробь.

Теперь у нас есть дробь m/n, причём будем считать, что m < n, и m и n - взаимно простые (мы уже выделили целую часть дроби и сократили дробь).

Вычисление десятичных цифр дроби, очевидный цикл: d = 10m div n - цифра, m = 10m mod n - остаток числителя для вычисления следующей цифры.

О предпериоде. Выяснено, что длина предпериода равняется максимальной степени чисел вида 2^p и 5^q, которые делят знаменатель. В самом деле, если знаменатель представим в виде n=2^p5^qz, и пусть с=max(p, q), тогда

$https://www.cyberforum.ru/cgi-bin/latex.cgi?<br /> \frac{m}{n}=\frac{m}{2^p5^qz}=\left. \frac{2^c5^cm}{2^p5^qz}\right/10^c=\left. \frac{2^{c-p}5^{c-q}m}{z}\right/10^c<br />$

Вычисляем длину предпериода и печатаем его.

О периоде. Выяснено, что длина периода равна количеству разрядов числа, составленных из цифры 9, делящегося на z.

Вычисляем длину периода и печатаем его.

Конец алгоритма.

Пример: 62/28.
Целая часть: 62 div 28 = 2 - печатаем.
Выделяем целую часть из дроби: 62 mod 28 = 6, получили правильную дробь 6/28.
Сокращаем, НОД(6, 28)=2, получаем 3/14.
Определяем длину предпериода: 14=2¹5⁰7, максимальная степень при 2 и 5 равна 1, значит, длина предпериода равна 1.
Печатаем предпериод: d = 30 div 14 = 2 - двойку и печатаем, остаток числителя дроби m = 30 mod 14 = 2.
вычисляем длину предпериода, выясняем, что 9, 99, 999, 9999, 99999 на z=7 не делятся, а 999999 делится. Следовательно, длина периода будет 6. Здорово, правда? Только вот есть подводный камень: длина периода может быть очень большой, и эти девятки ни в какой uint64 не влезут. Можно пойти экстенсивным путём, и применить тип BigInteger, но лучше делить по модулю z, умножая на 10 остаток от деления на z, и снова получать остаток от деления на z, пока остаток не станет равным 0, например, для этого случая:

Шаг	Что делим	Остаток	Примечание
1	9	2	считаем, что первый остаток был равен 0, приписываем к нему 9, получаем 9
2	29	1	предыдущий остаток был 2, приписываем 9, получаем 29
3	19	5	предыдущий остаток был 1, приписываем 9, получаем 19
4	59	3	просто, правда?
5	39	4
6	49	0	ура, наконец-то остаток равен 0

Так, для сравнения, с девятками:

Шаг	Что делим	Остаток
1	9	2
2	99	1
3	999	5
4	9999	3
5	99999	4
6	999999	0

Остатки те же. Но в первом случае "что делим" не превосходит 10(z-1).

Что получилось (для простоты писал для сдачи на проверочный сайт, без контроля ввода и интерфейса):

Pascal

var
  m, n, p, q, k, z: longint;
 
begin
  //вводим
  readln(m, n);
  //печатаем целую часть дроби
  write(m div n);
  //избавляемся от целой части дроби
  m := m mod n;
  if m > 0 //если числитель > 0, то есть дробная часть
    then begin
      write(','); //печатаем десятичную запятую, можно и десятичную точку.
      //сокращаем дробь, находим НОД (алгоритм Евклида)
      p := m; //будущий НОД
      q := n;
      while p <> q do
        if q > p
          then q := q - p
          else p := p - q;
      //сокращаем дробь
      m := m div p;
      n := n div p;
      //находим длину предпериода дроби (максимум из количества делителей 2 и 5)
      p := 0; //будущая длина предпериода
      q := 0;
      z := n; //будущий остаток знаменателя после деления на 2 и на 5
      while z mod 2 = 0 do
        begin
          inc(p);
          z := z div 2
        end;
      while z mod 5 = 0 do
        begin
          inc(q);
          z := z div 5
        end;
      if p < q then p := q;
      //печатаем предпериод дроби
      for k := 1 to p do
        begin
          m := m * 10;
          write(m div n);
          m := m mod n
        end;
      //если есть период, находим его длину и печатаем
      if z > 1 //если делители знаменателя не только 2 и 5, то есть период
        then begin
          write('(');
          q := 9; //первое число вида 9999999999999999999999999999999999999...
          p := 1; //количество разрядов в числе вида (см. выше)
          while q mod z > 0 do //пока число 999.. не разделится нацело на z, цикл
            begin
              inc(p); //на один разряд больше
              q := q mod z * 10 + 9 //делим 999.. по модулю z, во избежание переполнения
            end;
          //печатаем цифры периода
          for k := 1 to p do
            begin
              m := m * 10;
              write(m div n);
              m := m mod n
            end;
          write(')')
        end
    end;
  writeln
end.

Наверное, можно немножко соптимизировать, есть повторяющиеся фрагменты, может, в подпрограмму их выделить, может, кое-где ускорить, типа, заменить div 2 на shr 1, ещё всяких блох половить... Неохота.

Проверка. Программа выдерживает прямое попадание дроби maxlongint/(maxlongint div 10)=2147483647/214748364, результат:

10,00(00000325962902329723918176158957839604310093836151413009134728495533497987
43984843581858439675936250671506861863683394579900035932287707672594888778756889
62175283440110398233348124598518478119814686923528786463770219921209737364984070
37922766200910382721239264015999674856661538990816246683956111535266457256922339
1150025245361124148075)

Виндовый калькулятор нервно курит в сторонке, но как бы намекает, что всё верно:

10,000000032596290232972391817616

Ужос... Без применения деления по модулю для выяснения длины периода нужно было бы число из 336 девяток...

@kitya · 15.12.2020, 00:26

Cyborg Drone, мужик ты просто гений, спасибо тебе за ответ, зарегался для этого, удачки)

@Pomogitemnepj 0 / 0 / 0 Регистрация: 05.02.2018 Сообщений: 20
		1
	Напишите программу, которая переводит правильную дробь в десятичную, выделив (если нужно), период дроби 09.02.2018, 23:24. Показов 17113. Ответов 3 Метки нет (Все метки) Напишите программу, которая переводит правильную дробь в десятичную, выделив (если нужно), период дроби. Входные данные Входная строка содержит два числа M и N , разделённых пробелами. Гарантируется, что M < N . Выходные данные Программа должна вывести десятичную запись дроби , выделив (если нужно) её период. В качестве разделителя целой и дробной части используйте запятую. Примеры входные данные 1 2 выходные данные 0,5 входные данные 3 14 выходные данные 0,2(142857) 0

@kitya 0 / 0 / 0 Регистрация: 15.12.2020 Сообщений: 1
	15.12.2020, 00:26	4
	Cyborg Drone, мужик ты просто гений, спасибо тебе за ответ, зарегался для этого, удачки) 0

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

Решение