n を自然数とし、
1/n の小数点第i位から第j位までの和を求める
Rubyのプログラムを教えてください。
可能であれば、そのプログラムにおいて、
j の上限も教えてください。
以下途中経過を示しておきます。
Ruby
1def sum(str, i, j) 2 x, y, *z = str.split('') 3 z.map(&:to_i)[i - 1..j - 1].inject(:+) 4end 5# 本来以下のstr に 1 / n の小数点表示がくる 6str = 7"0.010309278350515463917525773195876288659793814432989690721649484536082474226804123711340206185567" 8p sum(str, 2, 96) # 1 + 0 + 3 + 0 + … + 5 + 6 + 7 = 432
(追記)2015/07/25 21:57
(回答を受けつけてから気がついたのですが、)
1 / n の小数点表示を用いて解いていただけたら幸いです。
気になる質問をクリップする
クリップした質問は、後からいつでもMYページで確認できます。
またクリップした質問に回答があった際、通知やメールを受け取ることができます。
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
2015/07/25 11:10
回答7件
0
ベストアンサー
jの上限はメモリが許す限りです。
Ruby
1require 'bigdecimal' 2def dec_sum(n, i, j) 3 BigDecimal(1r/n, j+1).to_s[i+1..j+1].each_char.map(&:to_i).reduce(&:+) 4end 5# 使い方 6puts dec_sum(7, 3, 8) # => 0.1428571428..のうち285714を全部足して27 7puts dec_sum(97,2,96) #=> 431 ← これ、間違いです!
(修正)有効桁数は1つ多めにしないと四捨五入されちゃうときがある。
参考: Ruby docs: library bigdecimal
(追記) 間違っていました><
上のコードではE-nを考慮してなかったです。
E-n部分はmanmanさんの回答を参照して下さい。
で、BigDecimal#to_sに"F"渡すとEじゃなくなるので、それでの回答を
Ruby
1require 'bigdecimal' 2def dec_sum(n, i, j) 3 BigDecimal(1r/n, j+1).to_s("F")[i+1..j+1].each_char.map(&:to_i).reduce(&:+) 4end 5# 使い方 6puts dec_sum(7, 3, 8) # => 0.1428571428..のうち285714を全部足して27 7puts dec_sum(97,2,96) #=> 432
投稿2015/07/25 14:18
編集2015/07/26 00:06総合スコア21735
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
2015/07/26 04:39 編集
2015/07/26 00:00
2015/07/26 04:34
2015/07/26 05:40
0
sun(2, 109, 109) は 0
sum(3, 109, 109) は 3 ですが、いままでの回答例ではこの計算は数秒では終わらないはずです。
1/n の小数表現を 10**9 桁目まで実際に求めているからです。(掲載時間も消費メモリもそれなりに必要)
そこで、小数表現の 数字が循環しない部分、循環する部分を求め、そこから 小数n桁目を得るようにしてみました。この方法だと 10**9 桁目という場合も一瞬で求める事ができます。
ruby
1# coding: utf-8 2 3# See http://qiita.com/katoy/items/b25696acb91c0d3b1134 4 5# a / b の小数表現を得る。 6# 配列 [符号、巡廻しない部分, 巡廻する部分] を返す。 7# 例: 8# 1/3 => [1, [1], [3]] 9# 1/7 -> [1, [0], [1, 4, 2, 8, 5, 7]] 10def get_repeat_string(a, b) 11 s = [] # 商を保存 12 m = [] # 余りを保存 13 sign = (1.0 * a / b > 0) ? 1: -1 14 a = a.abs 15 b = b.abs 16 17 r = a / b 18 a = a % b 19 s << r 20 21 i = nil 22 while a > 0 23 m << a 24 a = a * 10 25 26 r = a / b 27 a = a % b 28 s << r 29 i = m.index(a) 30 break if i != nil # 余りが繰り返されたので 31 end 32 33 if i == nil 34 [sign, s, []] 35 else 36 [sign, s[0..i], s[(i + 1)..-1]] 37 end 38end 39 40# 1/n の小数 i 桁目 .. j 桁目 までの数字の和を求める。 41def sum(n, i, j) 42 (sign, fix_str, repeat_str) = get_repeat_string(1, n) 43 44 # 1/n の小数 n 桁目の数字を得る。 45 def get_nth(n, fix_str, repeat_str) 46 if n < fix_str.length - 1 47 return fix_str[n + 1] 48 else 49 return 0 if repeat_str.length == 0 50 51 r = n - fix_str.length 52 return repeat_str[r % repeat_str.length] 53 end 54 end 55 56 sum = 0 57 (i..j).each do |x| 58 d = get_nth(x, fix_str, repeat_str) 59 sum += d 60 end 61 sum 62end 63 64tests = [ 65 [7, 1, 1, 1], # 1 => 1 66 [7, 1, 2, 5], # 14 => 5 67 [7, 1, 3, 7], # 142 => 7 68 [7, 1, 4, 15], # 1428 => 15 69 [7, 1, 5, 20], # 14285 => 20 70 71 [7, 2, 2, 4], # 4 => 4 72 [7, 2, 3, 6], # 42 => 6 73 [7, 2, 4, 14], # 428 => 14 74 [7, 2, 5, 19], # 4285 => 19 75 76 # [7, 3, 8, 27], 77 # [95, 2, 96, 432] 78] 79tests.each do |t| 80 v = sum(t[0], t[1], t[2]) 81 # p v 82 puts "# fail #{t} -> #{v}}" if t[3] != v 83end 84 85p sum(7, 3, 8) # => 0.1428571428..のうち285714を全部足して27 86p sum(97,2,96) #=> 432 87p sum(3, 10**9, 10**9) #=> 3 88p sum(2, 10**9, 10**9) #=> 0
投稿2015/08/08 13:27
総合スコア22324
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
2015/08/08 15:07 編集
2015/08/08 15:17
0
方針だけを書きます。
- 1/n の小数部分の数字を1 つずつ得る Stream を作る。
- その Strem の i 番目から j 番目を得て、毎回 足し算するようにする。
これだと、j の上限は無いとおもわれます。
// 循環小数に扱えるはずだし。
投稿2015/07/25 15:30
編集2015/07/25 23:42総合スコア22324
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
2015/07/25 23:38
2015/07/26 00:32 編集
2015/07/26 05:23
2015/07/26 09:24
0
シンプルに解いてみた。
jの上限はメモリが許す限りです。
Ruby
1require 'bigdecimal' 2 3# 1/nが有限小数でないとき 4def sum(n, i, j) 5 if n > 10 6 a, remain = BigDecimal("1").div(n, j + n).to_s.split('E-') # 念のためn余分に位をとっている 7 else 8 a, remain = BigDecimal("1").div(n, j + n).to_s.split('E') # 念のためn余分に位をとっている 9 end 10 x, y, *z = a.split('') 11 z.map(&:to_i).unshift(0 * remain.to_i)[i - 1..j - 1].inject(:+) 12end 13 14p sum(7, 3, 8) 15p sum(97, 2, 96)
実行結果
27
432
投稿2015/07/25 15:04
編集2015/07/25 17:59総合スコア233
0
多倍長整数で処理してみました。
ruby
1# See 2# http://melborne.github.io/2009/01/22/Ruby-Ruby-Problem16/ 3# > Rubyで桁の合計を求める 4 5# 1/n の小数点第i位から第j位までの和を求める。 6def sum(n, i, j) 7 v = (10 ** j) / n 8 v = v % (10 ** (j - i + 1)) 9 v.to_s.split("").map { |s| s.to_i }.inject(:+) 10end 11 12# 動作のチェック 13# 1/7 = 0.14285714285714285 14tests = [ 15 [7, 1, 1, 1], # 1 => 1 16 [7, 1, 2, 5], # 14 => 5 17 [7, 1, 3, 7], # 142 => 7 18 [7, 1, 4, 15], # 1428 => 15 19 [7, 1, 5, 20], # 14285 => 20 20 21 [7, 2, 2, 4], # 4 => 4 22 [7, 2, 3, 6], # 42 => 6 23 [7, 2, 4, 14], # 428 => 14 24 [7, 2, 5, 19], # 4285 => 19 25] 26tests.each do |t| 27 v = sum(t[0], t[1], t[2]) 28 puts "# fail #{t} -> #{v}}" if t[3] != v 29end
投稿2015/07/25 12:58
総合スコア22324
0
###strを使うパターン
Ruby
1def sum(str,i,j) 2 i +=1 3 total=0 4 for n in i..(j+1) 5 total += str[n,1].to_i 6 end 7 total 8end 9 10str = 11"0.010309278350515463917525773195876288659793814432989690721649484536082474226804123711340206185567" 12p sum(str, 2, 96)
###jが無制限なパターン
検証のしようが無いのですが、多分無制限なはず
Ruby
1def sum(n,i,j) 2 total=0 3 amari=1 4 for num in 1..j do 5 b = (amari*10)/n 6 if num >= i then total += b end 7 if b then print(b) else print(0) end 8 amari = ((amari*10)%n) 9 end 10 total 11end 12print("1.") 13print("\n",sum(97,2,96))
###最初に投稿したもの
限界は14?
※ 15桁目以降の数値が1/nのほうと一致しませんし
※ それ以降は成否の検証方法が分からなかったため
ruby
1def c(n,i,j) 2 r=0 3 for num in i..j do 4 r += ((1.0*10**num)/n).floor % 10 5 print(((1.0*10**num)/n).floor % 10, " + ") 6 end 7 r 8end 9 10print(1.0/7, ": ") 11print("= ",c(7,1,16)) 12#0.142857142857143: 1 + 4 + 2 + 8 + 5 + 7 + 1 + 4 + 2 + 8 + 5 + 7 + 1 + 4 + 2 + 8 + = 69
投稿2015/07/25 12:41
編集2015/07/25 14:17総合スコア2068
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
2015/07/25 13:22 編集
2015/07/25 13:22
2015/07/25 14:23
2015/07/25 16:25 編集
0
Float
で計算するなら、有効桁数はFloat::DIG
になります。環境依存ですが、おそらく15。
有効桁数が15だとすると、jの最大値は"1/nの小数点以下の最初の非ゼロの数値の位置"+14ですね。
Ruby
1def foo(n,i,j) 2 fraction = sprintf("%.#{j+1}f",1.0/n)[1..-1] 3 fraction[i..j].split(//).inject(0){|sum,x| sum+=x.to_i} 4end
BigDecimal
ライブラリを使うと、任意精度(jの上限無し)にも出来ます。
追記:
BigDecimal
版です。j+1
のところはj
でも良いかもしれないけど考えてません。
Ruby
1require "bigdecimal" 2 3def foo(n,i,j) 4 fraction = BigDecimal(1).div(BigDecimal(n),j+1).to_s("f")[1..-1] 5 fraction[i..j].split(//).inject(0){|sum,x| sum+=x.to_i} 6end
投稿2015/07/25 11:33
編集2015/07/25 23:50総合スコア84555
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
あなたの回答
tips
太字
斜体
打ち消し線
見出し
引用テキストの挿入
コードの挿入
リンクの挿入
リストの挿入
番号リストの挿入
表の挿入
水平線の挿入
プレビュー
質問の解決につながる回答をしましょう。 サンプルコードなど、より具体的な説明があると質問者の理解の助けになります。 また、読む側のことを考えた、分かりやすい文章を心がけましょう。