特殊な並びの数字を出力したい

Question

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1

というように両端に1を置き、左上と右上との数を足すという規則で数を配置したときに、段を指定するとその段の数字を表示するようなシステムをつくりたいです。
例えば4と入力したら「1 3 3 1」出力されるというイメージです。
どうすれば出来るでしょうか？

Answer 1

ソースコードは分かりませんが、二項定理を調べてみるとヒントがあるかもしれませんね。

Answer 2

jun68ykt さんの回答の
(i > 0 ? prev[i-1] : 0) + ( i < prev.length ? prev[i] : 0)
の部分をもうすこし単純に書けないかを考えてみました。

つぎのように考えました。
[0, 前の段...]
[姉の段, ... 0]
の配列の要素ごとの和を計算することにする。
さらに、和をとる配列は 他方を reverse すれば得られることも考慮しました。

rrr.rb

def base_of_pascals_triangle(n)
  return [1] if n == 1

  prev = [0] + base_of_pascals_triangle(n - 1)
  prev.zip(prev.reverse).map(&:sum)
end

(1..10).each do |x|
  puts base_of_pascals_triangle(x).to_s
end

実行例

追記：

結果の配列が左右対称であることを考慮すれば、計算は 約 1/2 に減らすことができますが、
h が空数か奇数かで処理分岐をすることでコードが長くなってしまう気がしたので、
そのことは取り込んでいません。

追記
数列が左右対称であることをして、足し算の回数を約按分にしてみました。

def base_of_pascals_triangle(n)
  return [1] if n == 1

  prev = [0] + base_of_pascals_triangle(n - 1)
  left = (0..((n - 1) / 2)).map { |x| prev[x] + prev[x + 1] }
  left + left[0...(n / 2)].reverse
end

Comments

[jun68ykt]

なるほど〜。Rubyならではの配列操作を使っていて、こっちのほうが Rubyistな感じです！

Answer 3

上の段から順に、そのまま算出すればよいです。
Pythonでのコード例です。このままだと100段くらいだとかなり時間かかりますが。
お手軽にlru_cacheを使ってメモ化してみました。100段でも瞬時に求まります。

from functools import lru_cache

@lru_cache(maxsize=1000) # サイズは適当に
def val( row, col):
    if col <= 0 or col >= row:
        return 1
    return val( row-1, col-1) + val(row-1,col)

with open('ret.txt','w') as f: # 見づらいのでファイルに出力
    for row in range(100):
        for col in range(row+1):
            f.write('{:40d}'.format( val( row, col))) # 40桁で足りる
        f.write('\n')

Answer 4

参考情報

• 続・パスカルの三角形

http://gamescripting.hatenablog.jp/entry/20060530/1149000099

k = 6
(1..k).inject([1]) { |a, dummy| ([0] + a).zip(a).map { |x, y| y ? x + y : x} }
=> [1, 5, 10, 10, 5, 1]

k = 10
(1..k).inject([1]) { |a, dummy| ([0] + a).zip(a).map { |x, y| y ? x + y : x} }
=> [1, 10, 45, 120, 210, 252, 210, 120, 45, 10, 1]

Answer 5

再帰を使ってやってみました。

（※以下のコードで、メソッド名 base_of_pascals_triangle は、「パスカルの三角形の底辺」の意）

[ykt68@macbook15]$ ruby -v

ruby 2.4.2p198 (2017-09-14 revision 59899) [x86_64-darwin17]
[ykt68@macbook15]$ cat tera118837.rb

def base_of_pascals_triangle(n)
    if n == 1
        [1]
    else
        prev = base_of_pascals_triangle(n-1)
        (0...n).map do |i|
            (i > 0 ? prev[i-1] : 0) + ( i < prev.length ? prev[i] : 0)
        end
    end
end

puts "#{base_of_pascals_triangle(6)}"

[ykt68@macbook15]$ ruby tera118837.rb

[1, 5, 10, 10, 5, 1]
[ykt68@macbook15]$