Задача: Построение периодической дроби

Есть (вводится с терминала) правильная рациональная дробь a / b (запись в виде простой дроби).
– a и b – целые числа;
– если дробь правильная, то a < b.

Нужно программно определить период периодической дроби и вывести её в формате с десятичной точкой, вида 0.12(34) (из курса школьной арифметики помним, что это 0.12343434… – бесконечная дробь).

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

Например, в 10-тичной системе мы должны получить:
1 / 12 = 0.08(3)
11 / 13 = 0.8(461538)
2 / 5 = 0.4
А в 2-ичной системе, соответственно:
17 / 47 = 0.(01011100100110001000001)

Это 1-я задача. А после решения этой первой задачи, ставим себе задачу 2: переделать программу так, чтобы на каждом шаге (определения цифры) не делать полный поиск уже встречавшихся ранее остатков…

Решение:

Прежде всего, вспомним как рациональная дробь (1/3) преобразовывается в бесконечную (0.3333… или 0.(3)) – это можно подробно почитать здесь – Обращение обыкновенных дробей в десятичные и обратно:

- В цикле находим частное и остаток от деления числителя на знаменатель.
- Частное – это очередная цифра в бесконечной записи. Сохраняем остатки на каждом шаге.
- Умножаем остаток на основание системы счисления – это у нас будет числитель для следующего шага итерации.
- Если остаток на каком-то шаге равен нулю, то дробь – конечная.
- Иначе ищем остаток в числе ранее сохранённых. Если нашли, то мы нашли период (дальше всё будет периодически повторяться).
- Если не нашли, то сохраняем текущий остаток и возвращаемся к вычислению следующего разряда.

Собственно, этого достаточно, чтобы записать решение задачи 1 (с поиском сохранённых остатков):

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

typedef unsigned long long data_t;

inline char simb( data_t val ) {
   return val < 10 ? '0' + val : 'A' + val - 10;
}

// только для отладки:
ostream& operator << ( ostream& stream, vector<data_t>& obj ) {
   stream << "{[" <<  obj.size() << "]: ";
   for( vector<data_t>::iterator i = obj.begin(); i != obj.end(); i++ )
      stream << *i << ( i + 1 != obj.end() ? ", " : " " ); 
   return stream << "}";
};

int main( int argc, char **argv ) {
   bool debug = argc > 1;
   while( true ) {
      int metr;
      cout << "система счисления (2...)?: ";
      cin >> metr;
      data_t ch, zn;
      cout << "числитель (1...)?: ";
      cin >> ch;
      cout << "знаменатель (" << ch + 1 << "...)?: ";
      cin >> zn;
      if( ch >= zn ) {
         cout << "должнв быть правльная дробь!" << endl;
         continue;
      }
      string sval( "0." );
      vector<data_t> list;
      data_t ost = ch % zn;
      while( true ) {
         data_t ch = ost * metr; 
         ost = ch % zn;
         sval.push_back( simb( ch / zn ) );
         if( debug ) cout << ost << " -> " << list << endl;
         if( 0 == ost ) break;
         vector<data_t>::iterator it = 
            find( list.begin(), list.end(), ost );
         if( it == list.end() ) 
            list.push_back( ost );
         else {
            ost = list.end() - it;
            break; 
         }
      };
      if( ost != 0 ) { // периодическая дробь, ost - период
         string::iterator is = sval.end() - ost;
         sval.insert( is, '(' );
         sval += ")";
      }
      cout << "длина периода " << ost << " : "
           << ch << " / " << zn << " = " << sval << endl;
   }
}

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

typedef unsigned long long data_t;

inline char simb( data_t val ) {

return val < 10 ? '0' + val : 'A' + val - 10;

}

// только для отладки:

ostream& operator << ( ostream& stream, vector<data_t>& obj ) {

stream << "{[" << obj.size() << "]: ";

for( vector<data_t>::iterator i = obj.begin(); i != obj.end(); i++ )

stream << *i << ( i + 1 != obj.end() ? ", " : " " );

return stream << "}";

};

int main( int argc, char **argv ) {

bool debug = argc > 1;

while( true ) {

int metr;

cout << "система счисления (2...)?: ";

cin >> metr;

data_t ch, zn;

cout << "числитель (1...)?: ";

cin >> ch;

cout << "знаменатель (" << ch + 1 << "...)?: ";

cin >> zn;

if( ch >= zn ) {

cout << "должнв быть правльная дробь!" << endl;

continue;

}

string sval( "0." );

vector<data_t> list;

data_t ost = ch % zn;

while( true ) {

data_t ch = ost * metr;

ost = ch % zn;

sval.push_back( simb( ch / zn ) );

if( debug ) cout << ost << " -> " << list << endl;

if( 0 == ost ) break;

vector<data_t>::iterator it =

find( list.begin(), list.end(), ost );

if( it == list.end() )

list.push_back( ost );

else {

ost = list.end() - it;

break;

}

};

if( ost != 0 ) { // периодическая дробь, ost - период

string::iterator is = sval.end() - ost;

sval.insert( is, '(' );

sval += ")";

}

cout << "длина периода " << ost << " : "

<< ch << " / " << zn << " = " << sval << endl;

}

Как легко видеть, весь алгоритм начинается со строки 39 и занимает всего 12 строк – всё остальное это ввод и подготовка данных:

$ ./periodf
система счисления (2...)?: 2
числитель (1...)?: 17
знаменатель (18...)?: 47
длина периода 23 : 17 / 47 = 0.0(10111001001100010000010)
система счисления (2...)?: 10
числитель (1...)?: 53
знаменатель (54...)?: 59
длина периода 58 : 53 / 59 = 0.8(9830508474576271186440677966101694915254237288135593220338)
система счисления (2...)?: 10
числитель (1...)?: 2
знаменатель (3...)?: 5
длина периода 0 : 2 / 5 = 0.4
система счисления (2...)?: 3
числитель (1...)?: 1
знаменатель (2...)?: 9
длина периода 0 : 1 / 9 = 0.01
система счисления (2...)?: ^C

$ ./periodf

система счисления (2...)?: 2

числитель (1...)?: 17

знаменатель (18...)?: 47

длина периода 23 : 17 / 47 = 0.0(10111001001100010000010)

система счисления (2...)?: 10

числитель (1...)?: 53

знаменатель (54...)?: 59

длина периода 58 : 53 / 59 = 0.8(9830508474576271186440677966101694915254237288135593220338)

система счисления (2...)?: 10

числитель (1...)?: 2

знаменатель (3...)?: 5

длина периода 0 : 2 / 5 = 0.4

система счисления (2...)?: 3

числитель (1...)?: 1

знаменатель (2...)?: 9

длина периода 0 : 1 / 9 = 0.01

система счисления (2...)?: ^C

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

$ ./periodf debug
система счисления (2...)?: 10
числитель (1...)?: 11
знаменатель (12...)?: 13
6 -> {[0]: }
8 -> {[1]: 6 }
2 -> {[2]: 6, 8 }
7 -> {[3]: 6, 8, 2 }
5 -> {[4]: 6, 8, 2, 7 }
11 -> {[5]: 6, 8, 2, 7, 5 }
6 -> {[6]: 6, 8, 2, 7, 5, 11 }
длина периода 6 : 11 / 13 = 0.8(461538)

$ ./periodf debug

система счисления (2...)?: 10

числитель (1...)?: 11

знаменатель (12...)?: 13

6 -> {[0]: }

8 -> {[1]: 6 }

2 -> {[2]: 6, 8 }

7 -> {[3]: 6, 8, 2 }

5 -> {[4]: 6, 8, 2, 7 }

11 -> {[5]: 6, 8, 2, 7, 5 }

6 -> {[6]: 6, 8, 2, 7, 5, 11 }

длина периода 6 : 11 / 13 = 0.8(461538)

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

- для знаменателя N остаток может иметь только N значений 0…N-1
- создадим массив из N элементов, и разметим его значением -1, которое означает “такое значение остатка ещё не встречалось”…
- а вот если на очередном шаге мы получим значение M, то в элемент [M] массива запишем номер итерации, на котором было это значение…
- теперь, если после очередного шага, мы получим значение K, то нам не нужно искать это значение во всём массиве, а нужно только проверить элемент [K] массива на его положительность.

И вот что из этого получается:

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;

typedef unsigned long long data_t;

inline char simb( data_t val ) {
   return val < 10 ? '0' + val : 'A' + val - 10;
}

// только для отладки:
string show( long long arr[], data_t size ) {
   char str[ 1000 ];
   strcpy( str, "{ ");
   for( data_t i = 0; i < size; i++ )
      if( arr[ i ] < 0 ) strcat( str, ". " );
      else sprintf( str + strlen( str ), "%lld ",  arr[ i ] );
   strcat( str, "}" );
   return string( str );
}

int main( int argc, char **argv ) {
   bool debug = argc > 1;
   while( true ) {
      int metr;
      cout << "система счисления (2...)?: ";
      cin >> metr;
      data_t ch, zn;
      cout << "числитель (1...)?: ";
      cin >> ch;
      cout << "знаменатель (" << ch + 1 << "...)?: ";
      cin >> zn;
      if( ch >= zn ) {
         cout << "должнв быть правльная дробь!" << endl;
         continue;
      }
      string sval( "0." );
      data_t ost = ch % zn;
      long long *list = new long long [ zn ];
      for( data_t i = 0; i < zn; i++ ) list[ i ] = -1;
      for( int i = 0; ; i++ ) {
         data_t ch = ost * metr; 
         ost = ch % zn;
         sval.push_back( simb( ch / zn ) );
         if( debug ) cout << ost << " -> " << show( list, zn ) << endl;
         if( 0 == ost ) break;
         if( list[ ost ] < 0 ) 
            list[ ost ] = i;
         else {
            ost = i - list[ ost ];
            break; 
         }
      };
      delete [] list;
      if( ost != 0 ) { // периодическая дробь, ost - период
         string::iterator is = sval.end() - ost;
         sval.insert( is, '(' );
         sval += ")";
      }
      cout << "длина периода " << ost << " : "
           << ch << " / " << zn << " = " << sval << endl;
   }
}

#include <iostream>

#include <cstring>

#include <cstdio>

using namespace std;

typedef unsigned long long data_t;

inline char simb( data_t val ) {

return val < 10 ? '0' + val : 'A' + val - 10;

}

// только для отладки:

string show( long long arr[], data_t size ) {

char str[ 1000 ];

strcpy( str, "{ ");

for( data_t i = 0; i < size; i++ )

if( arr[ i ] < 0 ) strcat( str, ". " );

else sprintf( str + strlen( str ), "%lld ", arr[ i ] );

strcat( str, "}" );

return string( str );

}

int main( int argc, char **argv ) {

bool debug = argc > 1;

while( true ) {

int metr;

cout << "система счисления (2...)?: ";

cin >> metr;

data_t ch, zn;

cout << "числитель (1...)?: ";

cin >> ch;

cout << "знаменатель (" << ch + 1 << "...)?: ";

cin >> zn;

if( ch >= zn ) {

cout << "должнв быть правльная дробь!" << endl;

continue;

}

string sval( "0." );

data_t ost = ch % zn;

long long *list = new long long [ zn ];

for( data_t i = 0; i < zn; i++ ) list[ i ] = -1;

for( int i = 0; ; i++ ) {

data_t ch = ost * metr;

ost = ch % zn;

sval.push_back( simb( ch / zn ) );

if( debug ) cout << ost << " -> " << show( list, zn ) << endl;

if( 0 == ost ) break;

if( list[ ost ] < 0 )

list[ ost ] = i;

else {

ost = i - list[ ost ];

break;

}

};

delete [] list;

if( ost != 0 ) { // периодическая дробь, ost - период

string::iterator is = sval.end() - ost;

sval.insert( is, '(' );

sval += ")";

}

cout << "длина периода " << ost << " : "

<< ch << " / " << zn << " = " << sval << endl;

}

$ ./perioda debug
система счисления (2...)?: 10
числитель (1...)?: 1
знаменатель (2...)?: 12
10 -> { . . . . . . . . . . . . }
4 -> { . . . . . . . . . . 0 . }
4 -> { . . . . 1 . . . . . 0 . }
длина периода 1 : 1 / 12 = 0.08(3)
система счисления (2...)?: 10
числитель (1...)?: 11
знаменатель (12...)?: 13
6 -> { . . . . . . . . . . . . . }
8 -> { . . . . . . 0 . . . . . . }
2 -> { . . . . . . 0 . 1 . . . . }
7 -> { . . 2 . . . 0 . 1 . . . . }
5 -> { . . 2 . . . 0 3 1 . . . . }
11 -> { . . 2 . . 4 0 3 1 . . . . }
6 -> { . . 2 . . 4 0 3 1 . . 5 . }
длина периода 6 : 11 / 13 = 0.8(461538)
система счисления (2...)?: 10
числитель (1...)?: 2
знаменатель (3...)?: 5
0 -> { . . . . . }
длина периода 0 : 2 / 5 = 0.4
система счисления (2...)?: ^C

$ ./perioda debug

система счисления (2...)?: 10

числитель (1...)?: 1

знаменатель (2...)?: 12

10 -> { . . . . . . . . . . . . }

4 -> { . . . . . . . . . . 0 . }

4 -> { . . . . 1 . . . . . 0 . }

длина периода 1 : 1 / 12 = 0.08(3)

система счисления (2...)?: 10

числитель (1...)?: 11

знаменатель (12...)?: 13

6 -> { . . . . . . . . . . . . . }

8 -> { . . . . . . 0 . . . . . . }

2 -> { . . . . . . 0 . 1 . . . . }

7 -> { . . 2 . . . 0 . 1 . . . . }

5 -> { . . 2 . . . 0 3 1 . . . . }

11 -> { . . 2 . . 4 0 3 1 . . . . }

6 -> { . . 2 . . 4 0 3 1 . . 5 . }

длина периода 6 : 11 / 13 = 0.8(461538)

система счисления (2...)?: 10

числитель (1...)?: 2

знаменатель (3...)?: 5

0 -> { . . . . . }

длина периода 0 : 2 / 5 = 0.4

система счисления (2...)?: ^C

2 thoughts on “Задача: Построение периодической дроби”

Тригонометрон:
21.10.2019 в 15:37
Программа работает неправильно.
Первая цифра периода ошибочно причисляется к предпериоду, а период, вычисленный программой, начинается со второй цифры настоящего периода.
Ответить
mladchui:
05.03.2023 в 14:27
у меня один вопрос, автор сайта хоть проверят код который ему отправляют? почти в каждых программа есть куча ошибок и ложных вычислений, не понятные для начинающих
Ответить

Задача: Построение периодической дроби

2 thoughts on “Задача: Построение периодической дроби”

Добавить комментарий Отменить ответ

Свежие записи

Свежие комментарии

Статистика