Задача: Побудова періодичної дробу

Есть (вводиться з терміналу) правильна раціональний дріб 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, то нам не потрібно Шукати це значення в усьому масиві, а потрібно тільки перевірити елемент [До] масиву на його позитивність.

І ось що з цього виходить:

#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 думки про "Задача: Побудова періодичної дробу”

Trigonometron говорить:
21.10.2019 at 15:37
Програма працює неправильно.
Перша цифра періоду помилково зараховується до предперіоду, а період, обчислений програмою, починається з другої цифри справжнього періоду.
відповісти
мадчуй говорить:
05.03.2023 at 14:27
у мене одне питання, автор сайту хоч перевірять код, який йому відправляють? майже в кожних програмах є купа помилок і помилкових обчислень, не зрозумілі для початківців
відповісти