Rubyで桁の合計を求める Rubyでオイラープロジェクトを解こう!Problem16

Rubyで桁の合計を求める 〜Rubyでオイラープロジェクトを解こう!Problem16

Problem 16 - Project Eulerより

2^15 = 32768 and the sum of its digits is 3 +たす 2 +たす 7 +たす 6 +たす 8 =わ 26.

What is the sum of the digits of the number 2^1000 ?

2^15 = 32768 の各桁の合計は 3 +たす 2 +たす 7 +たす 6 +たす 8 =わ 26である。

2^1000 の各桁の合計はいくつか。

算数的でないけど

def sum_of_digits(n)
 n.to_s.split("").map { |s| s.to_i }.inject(:+)
 end
 sum_of_digits(2**1000) # => 1366

もう少し算数的に

def sum_of_digits(n)
 sum = 0
 begin
 n, b = n.divmod(10)
 sum += b
 end until n == 0 and b == 0
 sum
 end
 sum_of_digits(2**1000) # => 1366

Rubyで最短ルート数を探す 〜Rubyでオイラープロジェクトを解こう!Problem15

Problem 15 - Project Eulerより

Starting in the top left corner of a ×ばつ2 grid, there are 6 routes (without backtracking) to the bottom right corner.

image

How many routes are there through a ×ばつ20 grid?

×ばつ2グリッドの左上の角からスタートした場合、右下の角に至るには6つのルートがある(引き返しはなし)。

×ばつ20のグリッドではいくつのルートがあるか。

任意の交点に至るルートは その真上と左隣の交点からだけなので そこまでのルートの合計が 任意の交点に至るルートの数になる

交点横一列の要素数の配列を作り ここに対応する交点に至るルート数を格納する

def routes(x,y)
 points = Array.new(x+1, 1)
 y.times do |n|
 (points.length).times do |i|
 next if i == 0
 points[i] = points[i-1] + points[i]
 end
 end
 points.last
 end
 routes(20,20) # => 137846528820

これは再帰でもいけそうだ こちらのほうがエレガントだ

def routes(x, y)
 return 1 if x == 0 or y == 0
 routes(x, y-1) + routes(y, x-1)
 end
 routes(20, 20) # =>

でもいつまで待っても答えが出ない...

• このエントリーをはてなブックマークに追加

• このエントリーをはてなブックマークに追加