以1/n的十进制值查找周期长度

给定一个正整数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
喜欢就支持一下吧
点赞14 分享