プログラミング小手調べ

プログラミング技術としては、以下の２項目は押さえておこう。

例題１

例題２

解説１

例題３

フィボナッチ数列、および、素数列のそれぞれ最初から２０個を印字させる（縦でも横でもいい）。

Ruby

素数列

まずは手抜き（既製品活用）バージョン

require 'prime'
puts Prime.each(100).to_a.join(' ')
  # ただし、最初の20個という指定はけっこう面倒
  # （多めに生成して20個だけ取り出すぐらいか）
  Prime.each(100).to_a.size
  Prime.each(100).to_a.take(20).join(' ')

またはこんな再帰でも書ける

def gen(n,m=2,a=[])
  if(a.length>=n) then a
  elsif(a.find{|e|m%e==0}) then
    gen(n,m+1,a)
  else gen(n,m+1,a+[m])
  end
end
gen(20)

Enumerator を使うなら

prm=Enumerator.new{|q|
  a=[];m=2; loop{
    if !(a.find{|e|m%e==0}) then q<<m;  a<<m end 
    m+=1
  }
}

フィボナッチ

フィボナッチ数は、

n 番目のフィボナッチ数を求める関数、として、再帰で書ける。が

呼び出し回数が爆発的に増大するのが難点

# フィボナッチ(再帰も使う版)
fib=Enumerator.new{|q|
  fn=->(n){n<2?n:fn.(n-2)+fn.(n-1)}
  m=0;loop{q<<fn.(m);m+=1}
}
fib.take(20)

# 再帰使わない版
fib=Enumerator.new{|q|
  f_1,f_2=1,2;loop{
    q<<f_1; f_1,f_2=f_2,f_2+f_1
  }
}

JavaScript

再帰を使った単純版。よく見られるフィボナッチ数列の定義（右図はRubyの文法だが）を素直に実装したもの。
```
function fib(n) {
  if(n<3) return(n)
  else return(fib(n-1)+fib(n-2))
  }
```
fibの計算量
- n が大きくなると計算時間がかなり大きくなるのがわかるだろう。
- これは右図のように同じ値に対する呼び出しが何度も行われる（その度に律儀に計算を行う）のが原因。
- この計算量にどう対処するかが課題になる。一度計算した値は２回目以降はあらためて計算しない（メモ化）などの工夫が必要だろう。

呼び出しの回数がばかにならないので方針変更

rubyのEnumeratorにも似た）generator を使う

/// その前に 整数列を生成するgenerator の例：
 　 　 function* ns(){
　 　 　let n=0;
　 　 　while(true){
     yield n; n+=1
     }
   }
   // let n=ns  としておいて
   // ns.next().value が呼ばれる毎に増える整数を返す

ここから、Generetor版（function* というアスタリスク付の定義）

function* fib(){
  let n1=1 ; yield n1
  let n2=1 ; yield n2
  while(true){
    let n=n1+n2; yield n
    n1=n2 ; n2=n
  }
}
fb=fib() 
[...Array(20)].map((_)=>fb.next().value)
  // （これが最もシンプルなのかどうか議論は別れるが）

素数列

律儀版（総当たりで割り切れるかどうか検査）を提示しておく。
```
numbers:
for(let i=1;i<1000;i++) {
  for(let j=2;j<i;j++)
    if(i%j==0) continue numbers
  console.log(i)
}
```
- 割り切れるかどうかチェックする数（上のリストの j）の、範囲としては
  - i の平方根を超えない範囲がいい、とか
  - すでに生成された素数に限定したほうがいいとか
  工夫の余地が多々あるが今日はこの先は省略しておく。

Haskell

まずはプログラム例だけ示しておく。はじめは理解するのに時間がかかるが、（わかってしまうと）かなりシンプルで強力。

-- フィボナッチ
fib = 0:1: zipWith (+) fib (tail fib)
  -- と、定義しておいて（無限数列を作ってしまうので先頭だけ取り出すために）
take 20 fib

-- 素数列
erato (x:xs)=x: erato [y|y<-xs, y `mod` x /= 0]
  -- と定義して（これはエラトステネスの篩）
take 20 $ erato [2..]

例題４

Ruby

Rubyでは（最近の版では）GUIライブラリは同梱されなくなっている

ので、代わりに HTMLを出力させるためのプログラムを１つ示しておく。

require 'prime'
puts "<!doctype html>"
Prime.each(100).take(20).each do |n|
  puts "<button>#{n}</button>"
end

JS版でテンプレート（pug）を使った（後述）のと同様に

ruby用テンプレートエンジン（erb slim等）も使えるだろう。

プログラミング小手調べ（解説編）

このページの狙い

例題１

例題２

解説１

例題３

Ruby

素数列

フィボナッチ

JavaScript

素数列

Haskell

例題４

Ruby

Haskell

javascript

プログラミング 小手調べ（解説編）

このページの狙い

例題１

例題２

解説１

例題３

Ruby

素数列

フィボナッチ

JavaScript

素数列

Haskell

例題４

Ruby

Haskell

javascript

プログラミング小手調べ（解説編）