最长的循环数字
我试图找到小于1000的数字，当它除以1时产生最长的重复数字串。我有一个十进制数列表，必须找到具有最长重复序列的数字。
这是我到目前为止所拥有的
numbers = [*2..999] decimal_representations = numbers.map { |number| 1.to_f/number } decimal_representations.map!(&:to_s) 我可以使用正则表达式生成三维数组。 Regex /(.+)\1+/产生一系列重复的子串。 我想找到最长的子字符串，所以我使用了enumerable的max_by函数。
decimal_representations.map! { |decimal| decimal.scan(/(.+)\1+/).max_by(&:length) }.flatten
我必须压缩我的数组以删除nil元素
decimal_representations.compact!
然后我可以找出哪个长度最长。
decimal_representations.max_by(&:length)
我得到0090009009 ，但我无法弄清楚哪个数字具有该十进制值，因为我从数组中删除了nil元素。
有任何想法吗？
你可以这样做。
码
def longest_repeating_decimal(last) n = (3..last).max_by { |i| find_repeating(i).size } end def find_repeating(n) num = 1 a = [] remainders = {} loop do d,r = num.divmod(n) return '' if r.zero? a << d return a[remainders[r]..-1].join if remainders.key?(r) remainders[r] = a.size num = 10*r end end
例子
n = longest_repeating_decimal(999) #=> 983 find_repeating(n).size #=> 982 find_repeating(n) #=> "00101729399796541200...54323499491353" require 'bigdecimal' BigDecimal.new(Rational(1,n),990).to_s('990F') #=> "0.00101729399796541200...5432349949135300101729..." # |repeating-> n = longest_repeating_decimal(9_999) #=> 9967 find_repeating(n).size #=> 9966 n = longest_repeating_decimal(99_999) #=> 99989 (took several minutes) find_repeating(n).size #=> 99988
嗯。 有趣的模式。
以下是3到30之间具有重复小数的数字：
def display(n) (3..n).each do |i| repeat = find_repeating(i) (puts "%2d %9s %23.20f" % [i, repeat, 1.0/i]) unless repeat.empty? end end display(30) n repeating 1.0/n 3 3 0.33333333333333331483 6 6 0.16666666666666665741 7 142857 0.14285714285714284921 9 1 0.11111111111111110494 11 90 0.09090909090909091161 12 3 0.08333333333333332871 13 769230 0.07692307692307692735 14 714285 0.07142857142857142461 15 6 0.06666666666666666574 17 8 0.05882352941176470507 18 5 0.05555555555555555247 19 52631 0.05263157894736841813 21 476190 0.04761904761904761640 22 45 0.04545454545454545581 23 43 0.04347826086956521618 24 6 0.04166666666666666435 26 384615 0.03846153846153846367 27 370 0.03703703703703703498 28 571428 0.03571428571428571230 29 4 0.03448275862068965469 30 3 0.03333333333333333287
说明
当你进行长时间分割并遇到之前的余数时，你知道早期余数的序列将永远重复，所以你停在那里并标记重复序列。 这正是find_repeating所做的。 如果1.0/n （ n是find_repeating的参数）具有重复数字，则返回重复数字的字符串。 如果1.0/n具有有限值，则返回空字符串。
在旁边
你问：“我得到了009009009，但我无法弄清楚哪个数字有十进制值，......”。 （你在中间有一个额外的零，我认为这是一个错字。）这是如何获得数字。
1/n = 0.009009... 10**3 * (1/n) = 9.009009... 10**3 * (1/n) - 1/n = 9 (10**3 - 1)/n = 9 n = (10**3 - 1)/9 = 111
确认：
1.0/111 #=> 0.009009...
您将不得不使用BigDecimal更长的重复小数。
Float不能精确地表示大多数十进制数，因此使用(1.to_f/number).to_s可能不会给出预期的结果。 这意味着您的整个算法不正确。
你需要一个不同的算法。 这是一个提示：数学中的1.0 / 7生成小数0.142857142857... ，重复序列为142857 。 如果你使用这个除法，你会注意到142857是999999的除数，这不是巧合。
数字是2或5倍数需要额外注意。 诀窍在于，例如， 14 （ 7 * 2 ）或35 （ 7 * 5 ），在其1.0 / n十进制表示中具有相同数量的重复序列。
没有代码解释这个想法有点困难。 我已经解决了这个Project Euler问题 ，但希望你能在不先查看我的源代码的情况下解决它。
相应的数字是111.我通过你的答案的倒数来计算它：
1 / 0.009009009009009 = 111
顺便说一下，我并没有声称你的答案是对的，我只是在帮助你解释你得到的答案。 1/7的数字具有更长的重复序列。
真正解决问题的方法
我实际上解决了这个问题。 这是我为解决它而编写的代码/注释。 如果您在查看我的代码之前只是阅读了我的注释，那么您应该能够自己编写代码以便发现这里发生了什么。 如果你想被宠坏，只需到最底层看看答案是什么。
# First, we need to figure out how digits in a decimal representation # of a fraction get calculated. We will write a method that prints # the first 50 decimal digits after the decimal point for the decimal # representation of a/b, where a and b are integers. def print_digits_after_decimal(a, b) raise ArgumentError if !a.is_a?(Integer) raise ArgumentError if !b.is_a?(Integer) # We only care about what's happening after the decimal point. r = a % b print "#{a}/#{b} = ." 50.times do r *= 10 digit = r / b print digit r = r % b end puts end print_digits_after_decimal(1, 7) print_digits_after_decimal(11, 28) # Results: # 1/7 = .14285714285714285714285714285714285714285714285714 # 11/28 = .39285714285714285714285714285714285714285714285714 # The only thing that changes on each iteration of that loop is r. # Observe that r is always within the finite range 0..(b-1). So # eventually r MUST be equal to a value that it already had before. # We will write a method to find that first repeated r value. This # represents the state of the digit-generating state machine for the # first state where the decimal digits start a repeating sequence. def first_repeated_r(a, b) raise ArgumentError if !a.is_a?(Integer) raise ArgumentError if !b.is_a?(Integer) r = a % b log = [] while true do return r if log.include?(r) log << r r = (r * 10) % b end end # Now use that r value to generate the digits that repeat. We need to # call the first_repeated_r method above, and generate digits until we # see that r value again, and then return those digits as an array. def repeating_decimal_sequence(a, b) r_start = r = first_repeated_r(a, b) digits = [] while true r *= 10 digits << r / b r = r % b break if r == r_start end digits end # Keep in mind that each r value corresponds to a digit we print out, # but many different r values can correspond to the same digit. We # have not proved that the sequence returned by # repeating_decimal_sequence doesn't contain a repeated sequence # inside itself. We will write a method that takes an array of digits # and shortens it to the smallest repeating sequence. def decimal_sequence_deduplicate(digits) (1..digits.size).each do |n| subsequence = digits[0, n] q, r = digits.size.divmod(n) if r == 0 && subsequence * q == digits return subsequence end end raise "Impossible!" # math broke end p decimal_sequence_deduplicate([1, 5, 8]) # => [1, 5, 8] p decimal_sequence_deduplicate([1, 5, 1, 5]) # => [1, 5] # Now we can put these pieces together to answer your question. answer = (1...1000).max_by do |n| decimal_sequence_deduplicate(repeating_decimal_sequence(1, n)).size end puts answer # => 983 # And now we should feel kind of dumb because 983 is simply the # largest prime number less than 1000, and Euler probably knew that # without doing this much work!