题目26：找出小于1000的数字中令1/d拥有最长循环圈的数字d
本帖最后由 永恒的蓝色梦想 于 2020-6-14 12:34 编辑Reciprocal cycles
A unit fraction contains 1 in the numerator. The decimal representation of the unit fractions with denominators 2 to 10 are given:
1/2 = 0.5
1/3 = 0.(3)
1/4 = 0.25
1/5 = 0.2
1/6 = 0.1(6)
1/7 = 0.(142857)
1/8 = 0.125
1/9 = 0.(1)
1/10 = 0.1
Where 0.1(6) means 0.166666..., and has a 1-digit recurring cycle. It can be seen that 1/7 has a 6-digit recurring cycle.
Find the value of d < 1000 for which 1/d contains the longest recurring cycle in its decimal fraction part.
题目：
分子为1的分数称为单分数。分母是 2 到 10 的单分数用十进制表示如下：
1/2 = 0.5
1/3 = 0.(3)
1/4 = 0.25
1/5 = 0.2
1/6 = 0.1(6)
1/7 = 0.(142857)
1/8 = 0.125
1/9 = 0.(1)
1/10 = 0.1
其中 0.1(6) 表示 0.166666...，因此它有一个长度为 1 的循环圈。可以看出 1/7 拥有一个 6 位的循环圈。
找出小于 1000 的数字 d，1/d 的十进制表示含有最长的循环圈。
def func(x):
list1 = []
temp = 10%x
list1.append(temp)
while True:
if (temp *10)%x == 0:
length = 0
break
elif (temp *10) %x not in list1:
temp = (temp *10) %x
list1.append(temp)
elif temp in list1:
length = len(list1)
break
return length
first = 0
list1 = []
for i in range(2,1001):
length = func(i)
if first < length:
first = length
list1.append(i)
else:
continue
print(list1[-1])
运行结果是983 # -*- coding: utf-8 -*-
"""
Created on Sat Jan7 08:58:29 2017
@author: Jerry Xu
"""
import time
start = time.time()
def getprimes(n=1000):
primes = *n
primes,primes=False,False
for i,prime in enumerate(primes):
if prime:
for j in range(i*i,n,i):
primes=False
primes,primes=False,False
return
def loop(n):
tmp = []
m = 10
while m%n not in tmp:
tmp.append(m%n)
m *= 10
if not tmp[-1]:
return 0
else:
return len(tmp)
longest, x = 0, 0
for i in getprimes():
if loop(i)>longest:
longest = loop(i)
x = i
print (x, longest)
print ('Time used: %.3f sec' % (time.time()-start))
输出：
983 982
Time used: 0.429 sec 此代码使用matlab编程
Problem26所用时间为0.63431秒
Problem26的答案为983
%% Problem26
% 题目26：找出1000以内的数字d，使得1/d拥有最大的循环圈
function Output=Problem26(Input)
tic
if nargin==0
Input=1000;
end
Circle_Max=0;%储存最大的循环圈
Circle=0;%当前数的循环圈
R=1;
r=1;
Flag=0;
for ii=1:Input
R=1;
r=1;
while (Flag==0)
r=mod(r*10,ii);
if r==0
Circle=0;%1、r=0表示能除尽,没有循环圈；
break
else
inx=find(r==R);
if isempty(inx)==0
%2、看r是否出现在R中,如果出现,表示已完成了循环圈,计算循环圈长度即可；
Circle=length(R)-length(inx)+1;
break
else
%3、如果r未出现在R中,则把r添加到R,然后继续循环.
Temp=;
R=Temp;
end
end
end
if Circle>=Circle_Max
Circle_Max=Circle;
d=ii;
end
end
Output=d;
toc
disp('此代码使用matlab编程')
disp(['Problem26所用时间为',num2str(toc),'秒'])
disp(['Problem26的答案为',num2str(Output)]) def Recip(x):
a=1
l=[]
while 1:
if a<x:
l.append(a)
a=10*a
elif a%x:
a=a%x
else:
return 0
if a in l:
return(len(l)-l.index(a))
l_recip=
for d in range(1,1000):
l_recip.append(Recip(d))
print('数字='+str(l_recip.index(max(l_recip))),'循环圈='+str(max(l_recip)))
>>>
数字=983 循环圈=982 jerryxjr1220 发表于 2017-1-7 09:24
输出：
983 982
Time used: 0.429 sec
你的27行改为:
return len(tmp)-tmp.index(m%n)
应该才更准确。
下面是我借鉴了你的循环圈算法，写的：
def Recip(x):
a=1
l=[]
while a%x not in l:
l.append(a%x)
a*=10
if not l[-1]:
return 0
else:
return(len(l)-l.index(a%x))
l_recip=
for d in range(1,1000):
l_recip.append(Recip(d))
print('数字='+str(l_recip.index(max(l_recip))),'循环圈='+str(max(l_recip))) 99592938 发表于 2017-3-15 17:03
>>>
数字=983 循环圈=982
果然是大神，用了相除统计余数，只要余数有相等的情况就会出现循环。
我是真笨，根本就想不到。。。。。。 本帖最后由 永恒的蓝色梦想 于 2021-1-31 11:52 编辑
#include<iostream>
#include<cstring>
int main() {
using namespace std;
ios::sync_with_stdio(false);
constexpr unsigned short UPPER_BOUND = 1000;
static unsigned short n, max_n, length, max_length, a, appeared;
for (n = 1; n < UPPER_BOUND; n++) {
a = 1;
for (length = 1;; length++) {
a *= 10;
a %= n;
if (a) {
if (appeared) {
length -= appeared;
if (length > max_length) {
max_n = n;
max_length = length;
}
break;
}
appeared = length;
}
else {
break;
}
}
memset(appeared, 0, n * sizeof(unsigned short));
}
cout << max_n << endl;
return 0;
} #include <stdio.h>
int check_num(int n) //标记法
{
int i, a = { 0 }, count = 0;
i = 10 % n;
if (i)
{
while (1)
{
if (a)
{
return count;
}
a = 1;
i *= 10;
i %= n;
count++;
}
}
else
{
return 0;
}
}
main()
{
int i, count, max = 0, num;
for (i = 2; i < 1000; i++)
{
count = check_num(i);
if (max < count)
{
max = count;
num = i;
}
}
printf("%d%d"， num, max);
}
数字是983， 圈数是982 #找出小于 1000 的数字 d，1/d 的十进制表示含有最长的循环圈
#求1/n的循环圈长度
def loop(n):
result = []
res = 1
while True:
if n <= 10:
res = (res*10) % n
if res not in result:
result.append(res)
else:
break
elif 10 < n <= 100:
res = (res*100) % n
if res not in result:
result.append(res)
else:
break
elif 100 <= n <= 1000:
res = (res*1000) % n
if res not in result:
result.append(res)
else:
break
return len(result)
d = []
for i in range(1, 1001):
d.append(loop(i))
print((d.index(max(d))+ 1), max(d))
/*
答案：983
耗时：0.0230429秒（单核）
0.00499988秒（八核）
*/
#include <iostream>
#include <algorithm>
#include <vector>
#include <omp.h>
using namespace std;
int getCycleLen(int n)//求出数n的循环节长度
{
vector<int> vC;
int r = 1;
vector<int>::iterator itr;
while (r > 0)
{
r = r % n;
itr = find(vC.begin(), vC.end(), r);
if (itr != vC.end())
break;
vC.push_back(r);
r *= 10;
}
if (r == 0)
return 0;
int k = int(vC.end() - itr);
return k;
}
int main(void)
{
volatile int nMaxLen = 0, nVal = 0;
#pragma omp parallel for shared(nMaxLen,nVal) schedule(dynamic)
for (int i = 1; i < 1000; ++i)
{
int k = getCycleLen(i);
if (k > nMaxLen)
{
#pragma omp critical
{
nMaxLen = k;
nVal = i;
}
}
}
cout << nVal << endl;
return 0;
}
import math
prime =
def isprime(n):
if n<=prime[-1]:
return n in prime
else:
i = prime[-1]+2
while n>prime[-1]:
j = 0
while j<math.sqrt(len(prime)):
s = True
if i%prime==0:
s = False
break
j = j+1
if s:
prime.append(i)
i = i+1
return n in prime
def odd(up,down):
bits=[]
sign=[]
up %= down;
up *= 10;
bits.append(up//down)
up %= down
while up not in sign:
sign.append(up)
up *= 10;
bits.append(up//down)
up %= down
bits.pop()
return bits
maxv = 0
maxi = 0
for i in range(2,1000):
if isprime(i):
if len(odd(1,i))>maxv:
maxv = len(odd(1,i))
maxi = i
print(maxi,maxv)
页:
[1]