Есть (вводится с терминала) правильная рациональная дробь 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 (с поиском сохранённых остатков):
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 | #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 строк – всё остальное это ввод и подготовка данных:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | $ ./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 |
(Внутренняя механика происходящего не совсем очевидная, поэтому предусмотрен режим диагностического вывода – если запускать программу с любым параметром)
1 2 3 4 5 6 7 8 9 10 11 12 | $ ./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] массива на его положительность.
И вот что из этого получается:
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 | #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; } } |
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 | $ ./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 |
Программа работает неправильно.
Первая цифра периода ошибочно причисляется к предпериоду, а период, вычисленный программой, начинается со второй цифры настоящего периода.
у меня один вопрос, автор сайта хоть проверят код который ему отправляют? почти в каждых программа есть куча ошибок и ложных вычислений, не понятные для начинающих