鱼C论坛

 找回密码
 立即注册
查看: 3284|回复: 11

题目26:找出小于1000的数字中令1/d拥有最长循环圈的数字d

[复制链接]
发表于 2015-4-23 16:40:50 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
本帖最后由 永恒的蓝色梦想 于 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 的十进制表示含有最长的循环圈。

评分

参与人数 1荣誉 +1 收起 理由
cwhsmile + 1 科普:两自然数相除不会得到无限不循环数

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2016-8-31 17:58:06 | 显示全部楼层
  1. def func(x):
  2.       list1 = []
  3.       temp = 10%x
  4.       list1.append(temp)
  5.       while True:
  6.             if (temp *10)%x == 0:
  7.                   length = 0
  8.                   break
  9.                   
  10.             elif (temp *10) %x not in list1:
  11.                   temp = (temp *10) %x
  12.                   list1.append(temp)
  13.             elif temp in list1:
  14.                   length = len(list1[list1.index((temp *10) %x):])
  15.                   break
  16.       return length
  17. first = 0
  18. list1 = []
  19. for i in range(2,1001):
  20.       length = func(i)
  21.       if first < length:
  22.             first = length
  23.             list1.append(i)
  24.       else:
  25.             continue
  26. print(list1[-1])
复制代码

运行结果是983
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-1-7 09:24:26 | 显示全部楼层
  1. # -*- coding: utf-8 -*-
  2. """
  3. Created on Sat Jan  7 08:58:29 2017

  4. @author: Jerry Xu
  5. """
  6. import time
  7. start = time.time()
  8. def getprimes(n=1000):
  9.     primes = [True]*n
  10.     primes[0],primes[1]=False,False
  11.     for i,prime in enumerate(primes):
  12.         if prime:
  13.             for j in range(i*i,n,i):
  14.                 primes[j]=False
  15.     primes[2],primes[5]=False,False
  16.     return [k for k,trueprime in enumerate(primes) if trueprime]
  17. def loop(n):
  18.     tmp = []
  19.     m = 10
  20.     while m%n not in tmp:
  21.         tmp.append(m%n)
  22.         m *= 10
  23.     if not tmp[-1]:
  24.         return 0
  25.     else:
  26.         return len(tmp)

  27. longest, x = 0, 0
  28. for i in getprimes():
  29.     if loop(i)>longest:
  30.         longest = loop(i)
  31.         x = i
  32. print (x, longest)
  33. print ('Time used: %.3f sec' % (time.time()-start))
复制代码

输出:
983 982
Time used: 0.429 sec
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-1-23 09:51:48 | 显示全部楼层
此代码使用matlab编程
Problem26所用时间为0.63431秒
Problem26的答案为983
  1. %% Problem26
  2. % 题目26:找出1000以内的数字d,使得1/d拥有最大的循环圈        
  3. function Output=Problem26(Input)
  4. tic
  5. if nargin==0
  6. Input=1000;
  7. end
  8. Circle_Max=0;%储存最大的循环圈
  9. Circle=0;%当前数的循环圈
  10. R=1;
  11. r=1;
  12. Flag=0;
  13. for ii=1:Input
  14.     R=1;
  15.     r=1;
  16.     while (Flag==0)
  17.         r=mod(r*10,ii);
  18.         if r==0
  19.             Circle=0;%1、r=0表示能除尽,没有循环圈;
  20.             break
  21.         else
  22.             inx=find(r==R);
  23.             if isempty(inx)==0
  24.                 %2、看r是否出现在R中,如果出现,表示已完成了循环圈,计算循环圈长度即可;
  25.                 Circle=length(R)-length(inx)+1;
  26.                 break
  27.             else
  28.                 %3、如果r未出现在R中,则把r添加到R,然后继续循环.
  29.                 Temp=[R,r];
  30.                 R=Temp;               
  31.             end
  32.         end
  33.     end
  34.     if Circle>=Circle_Max
  35.         Circle_Max=Circle;
  36.         d=ii;
  37.     end
  38. end
  39. Output=d;
  40. toc
  41. disp('此代码使用matlab编程')
  42. disp(['Problem26所用时间为',num2str(toc),'秒'])
  43. disp(['Problem26的答案为',num2str(Output)])
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-3-15 17:03:35 | 显示全部楼层
  1. def Recip(x):
  2.     a=1
  3.     l=[]
  4.     while 1:
  5.         if a<x:
  6.             l.append(a)
  7.             a=10*a
  8.         elif a%x:
  9.             a=a%x
  10.         else:
  11.             return 0
  12.         if a in l:
  13.             return(len(l)-l.index(a))

  14. l_recip=[0]
  15. for d in range(1,1000):
  16.     l_recip.append(Recip(d))
  17. print('数字='+str(l_recip.index(max(l_recip))),'循环圈='+str(max(l_recip)))
复制代码


>>>
数字=983 循环圈=982
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-3-15 17:38:23 | 显示全部楼层
jerryxjr1220 发表于 2017-1-7 09:24
输出:
983 982
Time used: 0.429 sec

你的27行改为:
  1.         return len(tmp)-tmp.index(m%n)
复制代码

应该才更准确。
下面是我借鉴了你的循环圈算法,写的:
  1. def Recip(x):
  2.     a=1
  3.     l=[]
  4.     while a%x not in l:
  5.         l.append(a%x)
  6.         a*=10
  7.     if not l[-1]:
  8.         return 0
  9.     else:
  10.         return(len(l)-l.index(a%x))

  11. l_recip=[0]
  12. for d in range(1,1000):
  13.     l_recip.append(Recip(d))
  14. print('数字='+str(l_recip.index(max(l_recip))),'循环圈='+str(max(l_recip)))
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2019-4-28 00:00:14 | 显示全部楼层
99592938 发表于 2017-3-15 17:03
>>>
数字=983 循环圈=982

果然是大神,用了相除统计余数,只要余数有相等的情况就会出现循环。

我是真笨,根本就想不到。。。。。。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-12-8 22:41:00 | 显示全部楼层
本帖最后由 永恒的蓝色梦想 于 2021-1-31 11:52 编辑
  1. #include<iostream>
  2. #include<cstring>



  3. int main() {
  4.     using namespace std;
  5.     ios::sync_with_stdio(false);

  6.     constexpr unsigned short UPPER_BOUND = 1000;
  7.     static unsigned short n, max_n, length, max_length, a, appeared[UPPER_BOUND];


  8.     for (n = 1; n < UPPER_BOUND; n++) {
  9.         a = 1;

  10.         for (length = 1;; length++) {
  11.             a *= 10;
  12.             a %= n;

  13.             if (a) {
  14.                 if (appeared[a]) {
  15.                     length -= appeared[a];

  16.                     if (length > max_length) {
  17.                         max_n = n;
  18.                         max_length = length;
  19.                     }

  20.                     break;
  21.                 }

  22.                 appeared[a] = length;
  23.             }
  24.             else {
  25.                 break;
  26.             }
  27.         }

  28.         memset(appeared, 0, n * sizeof(unsigned short));
  29.     }


  30.     cout << max_n << endl;
  31.     return 0;
  32. }
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2021-3-12 17:06:31 | 显示全部楼层
  1. #include <stdio.h>

  2. int check_num(int n) //标记法
  3. {
  4.         int i, a[1000] = { 0 }, count = 0;
  5.         i = 10 % n;
  6.         if (i)
  7.         {
  8.                 while (1)
  9.                 {
  10.                         if (a[i])
  11.                         {
  12.                                 return count;
  13.                         }
  14.                         a[i] = 1;
  15.                         i *= 10;
  16.                         i %= n;
  17.                         count++;
  18.                 }
  19.         }
  20.         else
  21.         {
  22.                 return 0;
  23.         }
  24. }
  25. main()
  26. {
  27.         int i, count, max = 0, num;
  28.         for (i = 2; i < 1000; i++)
  29.         {
  30.                 count = check_num(i);
  31.                 if (max < count)
  32.                 {
  33.                         max = count;
  34.                         num = i;
  35.                 }

  36.         }
  37.         printf("%d  %d", num, max);
  38. }
复制代码


数字是983, 圈数是982
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2021-10-17 12:11:06 | 显示全部楼层
#找出小于 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))
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2022-1-2 21:56:10 | 显示全部楼层
  1. /*
  2. 答案:983
  3. 耗时:0.0230429秒(单核)
  4.       0.00499988秒(八核)
  5. */
  6. #include <iostream>
  7. #include <algorithm>
  8. #include <vector>
  9. #include <omp.h>
  10. using namespace std;

  11. int getCycleLen(int n)//求出数n的循环节长度
  12. {
  13.   vector<int> vC;
  14.   int r = 1;
  15.   vector<int>::iterator itr;
  16.   while (r > 0)
  17.   {
  18.     r = r % n;
  19.     itr = find(vC.begin(), vC.end(), r);
  20.     if (itr != vC.end())
  21.       break;
  22.     vC.push_back(r);
  23.     r *= 10;
  24.   }
  25.   if (r == 0)
  26.     return 0;
  27.   int k = int(vC.end() - itr);
  28.   return k;
  29. }

  30. int main(void)
  31. {
  32.   volatile int nMaxLen = 0, nVal = 0;
  33. #pragma omp parallel for shared(nMaxLen,nVal) schedule(dynamic)
  34.   for (int i = 1; i < 1000; ++i)
  35.   {
  36.     int k = getCycleLen(i);
  37.     if (k > nMaxLen)
  38.     {
  39. #pragma omp critical
  40.       {
  41.         nMaxLen = k;
  42.         nVal = i;
  43.       }
  44.     }
  45.   }
  46.   cout << nVal << endl;
  47.   return 0;
  48. }
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2022-2-23 12:48:38 | 显示全部楼层
  1. import math
  2. prime = [2,3]
  3. def isprime(n):
  4.         if n<=prime[-1]:
  5.                 return n in prime
  6.         else:
  7.                 i = prime[-1]+2
  8.                 while n>prime[-1]:
  9.                         j = 0
  10.                         while j<math.sqrt(len(prime)):
  11.                                 s = True
  12.                                 if i%prime[j]==0:
  13.                                         s = False
  14.                                         break
  15.                                 j = j+1
  16.                         if s:
  17.                                 prime.append(i)
  18.                         i = i+1
  19.                 return n in prime
  20. def odd(up,down):
  21.         bits=[]
  22.         sign=[]
  23.         up %= down;
  24.         up *= 10;
  25.         bits.append(up//down)
  26.         up %= down
  27.         while up not in sign:
  28.                 sign.append(up)
  29.                 up *= 10;
  30.                 bits.append(up//down)
  31.                 up %= down
  32.         bits.pop()
  33.         return bits
  34. maxv = 0
  35. maxi = 0
  36. for i in range(2,1000):
  37.         if isprime(i):
  38.                 if len(odd(1,i))>maxv:
  39.                         maxv = len(odd(1,i))
  40.                         maxi = i
  41. print(maxi,maxv)
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-3-29 04:56

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表