Project Euler——Problem 26 - Daybreakcx's Blog - Keep Programming! With Algorithm! With Fun!
Project Euler——Problem 25
Project Euler——Problem 27

Project Euler——Problem 26

daybreakcx posted @ 2009年7月27日 16:43 in Prject Euler , 1000 阅读

原题与答案:

Problem 26

13 September 2002

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.

Answer:983

 

分析与解答:

这个题目是求在1000内的某个整数,其循环节最长。这个题目其实是很简单的,先说说常规算法,常规的方法直接想到的是列出各个位数,然后强行判定循环节,这样算法的复杂度十分的高,等待必然也是很漫长的。我们可以换个角度考虑,利用数学知识来想问题,从除法的运算法则入手,我们做除法无非就是每次将上次的余数乘以10然后再对除数取余,如此往复,那么循环节有什么特点呢?当前的余数相同!相同的余数必然引出一个相同的商序列,也就是我们的结果数字排列,因此我们的算法就非常简单了,先利用一个数值表示每次的余数,一直取余直到其重复出现为止,此时两次出现的距离就是我们的循环节了。那么我们需要最多判断多少次呢?根据取余规则我们可以肯定是不超过除数自身的非负整数,因此规模实际上十分的小,这题可以很轻松的解决,下面是我的程序源代码:

 

  1. #include<stdio.h>
  2. #include<string.h>
  3. int i,ans,best,t,fir[1000];
  4. int calc(int s)
  5. {
  6.         int i,mod=1;
  7.         memset(fir,-1,sizeof(fir));
  8.         for (i=0;;i++)
  9.         {
  10.                 mod=(mod*10)%s;
  11.                 if (fir[mod]==-1) fir[mod]=i;
  12.                 else return i-fir[mod];
  13.         }
  14. }
  15. int main()
  16. {
  17.         ans=0;
  18.         best=0;
  19.         for (i=1;i<1000;i++)
  20.         {
  21.                 t=calc(i);
  22.                 if (t>best)
  23.                 {
  24.                         best=t;
  25.                         ans=i;
  26.                 }
  27.         }
  28.         printf("%d\n",ans);
  29.         return 0;
  30. }

 

 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter