给定一个正整数n，找出小数点后的句点1/n。小数点后的句点是不断重复的位数（小数点后的某个位置）。 例如：
null
Input: n = 3Output: 1The value of 1/3 is 0.333333...Input: n = 7Output: 6The value of 1/7 is 0.142857142857142857.....Input: n = 210Output: 6The value of 1/210 is 0.0047619047619048.....
让我们首先讨论一个更简单的问题，即在1/n的值中寻找单个数字。 如何找到1/n值中的单个数字？ 让我们举个例子来理解这个过程。例如，n=7。第一个数字可以通过执行10/7来获得。第二位数字可以通过30/7获得（3是前一除法中的余数）。第三位数字可以通过20/7获得（2是前一除法的余数）。因此，我们的想法是获取第一个数字，然后继续将（余数*10）/n的值作为下一个数字，并将余数更新为（余数*10）%10。讨论了整个程序 在这里 . 如何找到经期？ 1/n的周期等于上述过程中使用的余数序列中的周期。这可以很容易地从数字直接从余数派生的事实中得到证明。 关于余数序列的一个有趣的事实是，在这个余数序列的周期中，所有的燕鸥都是不同的。原因很简单，如果余数重复，那么它就是新时期的开始。 以下是上述想法的实施。
CPP
// C++ program to find length of period of 1/n #include <iostream> #include <map> using namespace std; // Function to find length of period in 1/n int getPeriod( int n) { // Create a map to store mapping from remainder // its position map< int , int > mymap; map< int , int >::iterator it; // Initialize remainder and position of remainder int rem = 1, i = 1; // Keep finding remainders till a repeating remainder // is found while ( true ) { // Find next remainder rem = (10*rem) % n; // If remainder exists in mymap, then the difference // between current and previous position is length of // period it = mymap.find(rem); if (it != mymap.end()) return (i - it->second); // If doesn't exist, then add 'i' to mymap mymap[rem] = i; i++; } // This code should never be reached return INT_MAX; } // Driver program to test above function int main() { cout << getPeriod(3) << endl; cout << getPeriod(7) << endl; return 0; } |
输出：
16
我们可以使用以下事实来避免使用map或hash。对于数字n，最多可以有n个不同的余数。此外，该期间可能不会从第一个余数开始，因为一些初始余数可能是不重复的（不是任何期间的一部分）。因此，为了确保从一个周期中选取一个余数，请从第（n+1）个余数开始，并继续查找它的下一次出现。（n+1）次余数与其下一次出现之间的距离是周期的长度。
C++
// C++ program to find length of period of 1/n without // using map or hash #include <iostream> using namespace std; // Function to find length of period in 1/n int getPeriod( int n) { // Find the (n+1)th remainder after decimal point // in value of 1/n int rem = 1; // Initialize remainder for ( int i = 1; i <= n+1; i++) rem = (10*rem) % n; // Store (n+1)th remainder int d = rem; // Count the number of remainders before next // occurrence of (n+1)'th remainder 'd' int count = 0; do { rem = (10*rem) % n; count++; } while (rem != d); return count; } // Driver program to test above function int main() { cout << getPeriod(3) << endl; cout << getPeriod(7) << endl; return 0; } |
JAVA
// Java program to find length // of period of 1/n without using // map or hash class GFG { // Function to find length of period in 1/n static int getPeriod( int n) { // Find the (n+1)th remainder after // decimal point in value of 1/n int rem = 1 ; // Initialize remainder for ( int i = 1 ; i <= n + 1 ; i++) rem = ( 10 * rem) % n; // Store (n+1)th remainder int d = rem; // Count the number of remainders before next // occurrence of (n+1)'th remainder 'd' int count = 0 ; do { rem = ( 10 * rem) % n; count++; } while (rem != d); return count; } // Driver code public static void main(String[] args) { System.out.println(getPeriod( 3 ) ); System.out.println(getPeriod( 7 )); } } // This code is contributed by Smitha Dinesh Semwal |
Python3
# Python3 program to find length of # period of 1/n without using map or hash # Function to find length # of period in 1/n def getPeriod( n) : # Find the (n+1)th remainder after # decimal point in value of 1/n rem = 1 # Initialize remainder for i in range ( 1 , n + 2 ): rem = ( 10 * rem) % n # Store (n+1)th remainder d = rem # Count the number of remainders # before next occurrence of # (n+1)'th remainder 'd' count = 0 rem = ( 10 * rem) % n count + = 1 while rem ! = d : rem = ( 10 * rem) % n count + = 1 return count # Driver Code if __name__ = = "__main__" : print (getPeriod( 3 )) print (getPeriod( 7 )) # This code is contributed # by ChitraNayal |
C#
// C# program to find length of // period of 1/n without using // map or hash using System; class GFG { // Function to find length of period in 1/n static int getPeriod( int n) { // Find the (n+1)th remainder after // decimal point in value of 1/n int rem = 1; // Initialize remainder for ( int i = 1; i <= n + 1; i++) rem = (10 * rem) % n; // Store (n+1)th remainder int d = rem; // Count the number of remainders before next // occurrence of (n+1)'th remainder 'd' int count = 0; do { rem = (10 * rem) % n; count++; } while (rem != d); return count; } // Driver code public static void Main() { Console.Write(getPeriod(3) + "" ); Console.Write(getPeriod(7)); } } // This code is contributed by Smitha Dinesh Semwal |
PHP
<?php // PHP program to find length // of period of 1/n without // using map or hash // Function to find length // of period in 1/n function getPeriod( $n ) { // Find the (n+1)th remainder // after decimal point // in value of 1/n // Initialize remainder $rem = 1; for ( $i = 1; $i <= $n + 1; $i ++) $rem = (10 * $rem ) % $n ; // Store (n+1)th // remainder $d = $rem ; // Count the number of // remainders before next // occurrence of (n+1)'th // remainder 'd' $count = 0; do { $rem = (10 * $rem ) % $n ; $count ++; } while ( $rem != $d ); return $count ; } // Driver Code echo getPeriod(3), "" ; echo getPeriod(7), "" ; // This code is contributed by ajit. ?> |
Javascript
<script> // Javascript program to find length // of period of 1/n without using // map or hash // Function to find length of period in 1/n function getPeriod(n) { // Find the (n+1)th remainder after // decimal point in value of 1/n let rem = 1; // Initialize remainder for (let i = 1; i <= n + 1; i++) rem = (10 * rem) % n; // Store (n+1)th remainder let d = rem; // Count the number of remainders before next // occurrence of (n+1)'th remainder 'd' let count = 0; do { rem = (10 * rem) % n; count++; } while (rem != d); return count; } // Driver code document.write(getPeriod(3)+ "<br>" ) document.write(getPeriod(7)+ "<br>" ) // This code is contributed by rag2127 </script> |
输出：
16
参考： 算法与编程：问题与解决方案亚历山大·申 本文由 萨钦 。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请发表评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
