[アルゴリズム]
練習のための問題は 競技プログラミングの履歴
単位分数とは分子が1の分数である. 分母が2から10の単位分数を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桁ある.
d < 1000 なる 1/d の中で小数部の循環節が最も長くなるような d を求めよ.
+
|
解答
|
|
|
- やり方がわからないのでググってたら応用情報に解答があった。草生える。
正式なアルゴリズム名は
def cycle_finding(n)
p, q = 1, 1
s, t = 1, 1 # start : s, goal : t
while true
p = (p*10) % n
q = (q*10) % n
q = (q*10) % n
break if p==q
end
if p!=0
q = 1;
s = 1;
while p!=q
s+=1
p = (p*10) % n
q = (q*10) % n
end
q = (q*10) % n
t = s
while p!=q
t+=1
q = (q*10) % n
end
end
cycle = t-s+1
puts "1/#{n} = #{1.to_f/n.to_f} : #{cycle}"
cycle
end
a = 1.upto(1000).to_a.map do |n|
cycle_finding(n)
end
puts a.max
|