Project Euler——Problem 26

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

原题与答案：

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:

¹/₂ = 0.5

¹/₃ = 0.(3)

¹/₄ = 0.25

¹/₅ = 0.2

¹/₆ = 0.1(6)

¹/₇ = 0.(142857)

¹/₈ = 0.125

¹/₉ = 0.(1)

¹/₁₀ = 0.1

Where 0.1(6) means 0.166666..., and has a 1-digit recurring cycle. It can be seen that ¹/₇ has a 6-digit recurring cycle.

Find the value of d < 1000 for which ¹/_d contains the longest recurring cycle in its decimal fraction part.

Answer:983

分析与解答：

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

#include<stdio.h>
#include<string.h>
int i,ans,best,t,fir[1000];
int calc(int s)
{
int i,mod=1;
memset(fir,-1,sizeof(fir));
for (i=0;;i++)
{
mod=(mod*10)%s;
if (fir[mod]==-1) fir[mod]=i;
else return i-fir[mod];
}
}
int main()
{
ans=0;
best=0;
for (i=1;i<1000;i++)
{
t=calc(i);
if (t>best)
{
best=t;
ans=i;
}
}
printf("%d\n",ans);
return 0;
}

¹/₂	=	0.5
¹/₃	=	0.(3)
¹/₄	=	0.25
¹/₅	=	0.2
¹/₆	=	0.1(6)
¹/₇	=	0.(142857)
¹/₈	=	0.125
¹/₉	=	0.(1)
¹/₁₀	=	0.1