根据 米德定理 ，如果为 
，其中p是 首要的 和 是一个 还原分数 ，有偶数个数字，然后将重复部分分成两半，再加上，得到一个9的字符串。
null
例如：
a=1，p=7 1/7 = 0.14285714285.. 所以1/7是一个重复的十进制数，142857是重复的。现在，根据这个定理，它有偶数个重复数字，即142857。再进一步，如果我们把它分成两半，我们得到142和857。因此，把这两个加起来，我们得到999，它是9的字符串，符合我们的定理。 a=2，p=11 2/11 = 0.18181818181.. 这里，重复小数是18。现在这是偶数，所以1+8=9，这再次证明了米德定理的有效性。
给定分子和分母，任务是找出结果浮点数是否遵循Midy定理。
方法： 让我们模拟一下分数到小数的转换过程。让我们看看我们已经计算出整数部分的那部分，也就是地板（分子/分母）。现在我们剩下（余数=分子%分母）/分母。 如果您还记得转换为十进制的过程，我们将在每个步骤中执行以下操作：
- 把余数乘以10。
- 将余数/分母追加到结果中。
- 余数=余数%分母。
在任何时刻，如果余数变成0，我们就完成了。 然而，当存在循环序列时，余数永远不会变为0。例如，如果你看1/3，余数永远不会变成0。
以下是一个重要的观察结果： 如果我们从余数“rem”开始，如果余数在任何时间点重复，那么两个“rem”之间的数字会不断重复。 因此，我们的想法是将看到的剩余物存储在地图中。每当一个余数重复，我们就在下一次出现之前返回序列。
下面是Midy定理的实现：
C++
// C++ implementation as a // proof of the Midy's theorem #include <bits/stdc++.h> using namespace std; // Returns repeating sequence of a fraction. // If repeating sequence doesn't exits, // then returns -1 string fractionToDecimal( int numerator, int denominator) { string res; /* Create a map to store already seen remainders remainder is used as key and its position in result is stored as value. Note that we need position for cases like 1/6. In this case, the recurring sequence doesn't start from first remainder. */ map< int , int > mp; mp.clear(); // Find first remainder int rem = numerator % denominator; // Keep finding remainder until either remainder // becomes 0 or repeats while ((rem != 0) && (mp.find(rem) == mp.end())) { // Store this remainder mp[rem] = res.length(); // Multiply remainder with 10 rem = rem * 10; // Append rem / denr to result int res_part = rem / denominator; res += to_string(res_part); // Update remainder rem = rem % denominator; } return (rem == 0) ? "-1" : res.substr(mp[rem]); } // Checks whether a number is prime or not bool isPrime( int n) { for ( int i = 2; i <= n / 2; i++) if (n % i == 0) return false ; return true ; } // If all conditions are met, // it proves Midy's theorem void Midys(string str, int n) { int l = str.length(); int part1 = 0, part2 = 0; if (!isPrime(n)) { cout << "Denominator is not prime, " << "thus Midy's theorem is not applicable" ; } else if (l % 2 == 0) { for ( int i = 0; i < l / 2; i++) { part1 = part1 * 10 + (str[i] - '0' ); part2 = part2 * 10 + (str[l / 2 + i] - '0' ); } cout << part1 << " + " << part2 << " = " << (part1 + part2) << endl; cout << "Midy's theorem holds!" ; } else { cout << "The repeating decimal is of odd length " << "thus Midy's theorem is not applicable" ; } } // Driver code int main() { int numr = 2, denr = 11; string res = fractionToDecimal(numr, denr); if (res == "-1" ) cout << "The fraction does not have repeating decimal" ; else { cout << "Repeating decimal = " << res << endl; Midys(res, denr); } return 0; } |
JAVA
// Java implementation as a // proof of the Midy's theorem import java.util.*; class GFG{ // Returns repeating sequence of a fraction. // If repeating sequence doesn't exits, // then returns -1 static String fractionToDecimal( int numerator, int denominator) { String res = "" ; /* Create a map to store already seen remainders remainder is used as key and its position in result is stored as value. Note that we need position for cases like 1/6. In this case, the recurring sequence doesn't start from first remainder. */ HashMap<Integer, Integer> mp = new HashMap<>(); // Find first remainder int rem = numerator % denominator; // Keep finding remainder until either remainder // becomes 0 or repeats while ((rem != 0 ) && !mp.containsKey(rem)) { // Store this remainder mp.put(rem, res.length()); // Multiply remainder with 10 rem = rem * 10 ; // Append rem / denr to result int res_part = rem / denominator; res += res_part + "" ; // Update remainder rem = rem % denominator; } return (rem == 0 ) ? "-1" : res.substring(mp.get(rem)); } // Checks whether a number is prime or not static boolean isPrime( int n) { for ( int i = 2 ; i <= n / 2 ; i++) if (n % i == 0 ) return false ; return true ; } // If all conditions are met, // it proves Midy's theorem static void Midys(String str, int n) { int l = str.length(); int part1 = 0 , part2 = 0 ; if (!isPrime(n)) { System.out.print( "Denominator is not prime, " + "thus Midy's theorem is not " + "applicable" ); } else if (l % 2 == 0 ) { for ( int i = 0 ; i < l / 2 ; i++) { part1 = part1 * 10 + (str.charAt(i) - '0' ); part2 = part2 * 10 + (str.charAt(l / 2 + i) - '0' ); } System.out.println(part1 + " + " + part2 + " = " + (part1 + part2)); System.out.print( "Midy's theorem holds!" ); } else { System.out.print( "The repeating decimal is " + "of odd length thus Midy's " + "theorem is not applicable" ); } } // Driver code public static void main(String []args) { int numr = 2 , denr = 11 ; String res = fractionToDecimal(numr, denr); if (res == "-1" ) System.out.print( "The fraction does not " + "have repeating decimal" ); else { System.out.println( "Repeating decimal = " + res); Midys(res, denr); } } } // This code is contributed by rutvik_56 |
C#
// C# implementation as a // proof of the Midy's theorem using System; using System.Collections; using System.Collections.Generic; class GFG{ // Returns repeating sequence of a fraction. // If repeating sequence doesn't exits, // then returns -1 static String fractionToDecimal( int numerator, int denominator) { String res = "" ; /* Create a map to store already seen remainders remainder is used as key and its position in result is stored as value. Note that we need position for cases like 1/6. In this case, the recurring sequence doesn't start from first remainder. */ Dictionary< int , int > mp = new Dictionary< int , int >(); // Find first remainder int rem = numerator % denominator; // Keep finding remainder until either remainder // becomes 0 or repeats while ((rem != 0) && !mp.ContainsKey(rem)) { // Store this remainder mp[rem]= res.Length; // Multiply remainder with 10 rem = rem * 10; // Append rem / denr to result int res_part = rem / denominator; res += res_part + "" ; // Update remainder rem = rem % denominator; } return (rem == 0) ? "-1" : res.Substring(mp[rem]); } // Checks whether a number is prime or not static bool isPrime( int n) { for ( int i = 2; i <= n / 2; i++) if (n % i == 0) return false ; return true ; } // If all conditions are met, // it proves Midy's theorem static void Midys(String str, int n) { int l = str.Length; int part1 = 0, part2 = 0; if (!isPrime(n)) { Console.Write( "Denominator is not prime, " + "thus Midy's theorem is not " + "applicable" ); } else if (l % 2 == 0) { for ( int i = 0; i < l / 2; i++) { part1 = part1 * 10 + (str[i] - '0' ); part2 = part2 * 10 + (str[l / 2 + i] - '0' ); } Console.WriteLine(part1 + " + " + part2 + " = " + (part1 + part2)); Console.Write( "Midy's theorem holds!" ); } else { Console.Write( "The repeating decimal is " + "of odd length thus Midy's " + "theorem is not applicable" ); } } // Driver code public static void Main( string []args) { int numr = 2, denr = 11; string res = fractionToDecimal(numr, denr); if (res == "-1" ) Console.Write( "The fraction does not " + "have repeating decimal" ); else { Console.WriteLine( "Repeating decimal = " + res); Midys(res, denr); } } } // This code is contributed by pratham76. |
输出：
Repeating decimal = 181 + 8 = 9Midy's theorem holds!
关于Midy定理的更多信息可以在 http://www.kurims.kyoto-u.ac.jp/EMIS/journals/INTEGERS/papers/h2/h2.pdf http://digitalcommons.unl.edu/cgi/viewcontent.cgi?article=1047&context=mathfacpub
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
