There are (terminal input) right a rational fraction / b (Entry form plain fractions).
– a and b – whole numbers;
– if the fraction is correct, then a < b.
It is necessary to programmatically determine the period of the periodic fractions, and bring it in the format of a decimal point, species 0.12(34) (from school arithmetic course remember, it 0.12343434… – endless fraction).
Complicates the task of the, Tom, that number system records an infinite fraction can be arbitrary and is chosen at random (data entry).
For example, 10-cal system, we have to get:
1 / 12 = 0.08(3)
11 / 13 = 0.8(461538)
2 / 5 = 0.4
A 2-ary system, respectively:
17 / 47 = 0.(01011100100110001000001)
This is the 1st challenge. After solving this problem first, We set ourselves the task 2: to alter the program so, that at each step (determining the numbers) do a full search has previously encountered residues…
Decision:
First of all, remember as a rational fraction (1/3) converted into endless (0.3333… or 0.(3)) – it can be read in detail here – Handling of fractions to decimals and vice versa:
- The loop is the quotient and remainder of the division of the numerator by the denominator.
- private – this is another figure of infinite recording. Save the remnants of each step.
- Multiply the balance in the radix – we will have a numerator for the next iteration step.
- If the balance on some step is zero, the fraction – final.
- Otherwise, look for the balance of those previously saved. If you found, we found during (then everything will be repeated periodically).
- If not found, then we maintain the current balance and return to the calculation of the next discharge.
Properly, It's enough, to write the solution of the problem 1 (with the search for the remnants saved):
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; } } |
It is easy to see, the entire algorithm starts with a line 39 and it takes 12 strings – everything else is input and data preparation:
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 |
(The internal mechanics of what is happening is not entirely clear, therefore provides a diagnostic output mode – if you run the program with any parameter)
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) |
And now we see, what we need at each step search the resulting residue in an array (vector) in coincidence with the previously obtained. This is wasteful. Knowing, as the algorithm works, You can go on like this trick:
- denominator N residue can only have values of N 0…N-1
- create an array of N elements, and mark its value -1, which means “a value balance is not met”…
- but if at the next step, we obtain the value of M, in element [M] array write iteration number, where this value was…
- Now, If after the next step, we get the value of K, then we do not need search this value throughout the array, and only need to check the item [K] an array to its positivity.
And that's what comes out of it:
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 |
The program does not work properly.
The first digit of the period is erroneously assigned to the pre-period, and period, calculated by the program, starts with the second digit of the current period.
I have one question, The author of the site will at least check the code that is sent to him? almost every program has a lot of errors and false calculations, not clear for beginners