Top | INDEX | UP

冬季レポート解説


1. 自分の名前と学籍番号を表示するプログラムを考えてください。

# プログラム例1
puts "私の名前は学芸花子、学籍番号はAB-1234です"

# プログラム例2
myname = "学芸花子"       # 名前を変数 myname へ代入
mycode = "AB-1234"        # 学籍番号を変数 mycode へ代入
printf("私の名前は%s、学籍番号は%sです", myname, mycode) # 清書して印字

2. 階乗の10進表記の末尾に含まれる0の数を表示するプログラムを考えてください。たとえば 10! = 3628800 ですから末尾に含まれる 0 の数は 2 です。どのようなアルゴリズム(アイデア)で作られたプログラムかも明記してください。

(注: 以下の記述で / は整除を意味します)
一般にある自然数 x に対して

と定義します。我々の目標は z(n!) を計算することです。
さて z(x) を求めるためには(z の定義から) x を 10 で割れるだけ割って、その回数を数えればよいことになります(アルゴリズム1)。
また 10 = 2*5 ですから z(x) = min{ i(2,x), i(5,x) } となります。 そこで x = n! のときは、階乗の性質を使ってもうすこし計算を楽にできます。 n! = 1*2*...*n ですから、n! を素因数分解したとき素数 p に対して
i(p,n!) = n/p + n/p2 + n/p3 + ...
となります(つまり n 以下の、 p の倍数の数 + p2 の倍数の数 + ... のこと)。 また p1 < p2 であれば
n/p1 + n/p22 + ... > n/p2 + n/p22 + ...
となります(分母が大きければ分数全体は小さくなる)。すなわち
i(2,n!) > i(5,n!)
ですから、結論としては
z(n!) = i(5,n!) = n/5 + n/52 + n/53 + ...
となります(アルゴリズム2)。

プログラム例

def fact(n) # 階乗の計算
  s = 1
  while n > 0
    s *= n 
    n -= 1
  end
  return s
end

# アルゴリズム1
# n! を 10 で割り続ける
def z1(n)             
  i = 0               
  nn = fact(n)        
  while nn % 10 == 0
    i += 1
    nn /= 10
  end
  return i
end

# アルゴリズム2
# n/5 + n/25 + n/125 + ... を計算する
def z2(n) 
  i = 0                                        
  d = 5                                       
  while n/d > 0 
    i += n/d                                  
    d *= 5                                      
  end                                          
  return i                                       
end                                               
                                                  
# チェック                                           
n=gets.to_i                                      
puts fact(n)                                       
puts z1(n)                                            
puts z2(n)                                             

3.自然数 n が入力されたときに n 未満の素数の総和を計算して表示するプログラムを考えてください。どのようなアルゴリズム(アイデア)で作られたプログラムかも明記してください。

「エラトステネスの篩」により「n 未満の素数の一覧」を生成(*1)して、 その総和を計算(*2)する、という素朴な方針(アルゴリズム)でプログラムを作ります。

# 添字 0〜n-1 について、要素が
# - 素数ならば true
# - 合成数ならば false
# となっている配列を生成する関数
def sieve_of_eratosthenes (n)
  p = [false, false]   # 0,1 は合成数
  for i in 2 ... n     # 2 以上は素数とまず仮定
    p[i] = true
  end
  for i in 2 ... n
    if p[i]               # i は素数である
      d = 2*i             
      while d < n         # 素数の倍数は合成数
        p[d] = false
        d += i
      end
    end
  end
  return p
end

# 配列 a の要素が true である添字
# について総和を計算する関数
def summarize (a)
  s = 0
  for i in 0 ... a.length
    if a[i]
      s += i
    end
  end
  return s
end

puts summarize(sieve_of_eratosthenes(gets.to_i))

4.自由課題: 自分の興味ある・面白いと思う数学的な題材を使ったプログラムを作ってみてください。どのようなアルゴリズム(アイデア)で作られたプログラムかも明記してください。

解答例: なし