给定一个正整数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