SICPチックな問題

某福岡の某天神の某社での勉強会で出された宿題。

問題

１からnまでの合計を計算する関数をいろいろな方法で作ってみよう

function sum(n){
}

問１　for,while文

問２　再帰の練習：for,whileなどの制御構造は使わずに作る。（ifは使ってもよいが、使わないほうがなおよい。）*1

問３　★に入るものは何か答えよ。

function accumnlate(init, op, list){

    if (list.length == 0) {

        return init;

   } else {

       return accumnlate(op(init, list.shift()), op, list);

   }

}

var list=[1,2,3,4,5,6,7,8,9,10];

var result = accumnlate(0, ★, list);

alert(result); →55

応用問題１

上のaccumulateを利用して、map関数を作成せよ。
map関数とは、

 var list = [1,2,3];

 map(function(x){return x*10;},list) -> [10,20,30]

のように、要素一つ一つに対して、引数で与えた関数を実行して、実行結果をつめた配列を返すものです。

問４

再帰を利用して、クイックソートを実装せよ。

答え

問1

これは単純にfor文でまわす。

function sum(n){

    var total = 0;

    for(var i=1; i<=n; i++){

	total += i;

    }

    return total;

}

問２

いきなりは無理なので、まずはif文で実装
再帰関数を利用しましょう。

function sum(n){

    if(n<=1){

	return 1;

    }else{

	return n + sum(n-1);

    }

}

制御構造を消す

function sum(n){

    return ( (n<=1)&&1 ) || ( n+sum(n-1) );

}

問3

function accumulate(init,op,list){

    if(list.length==0){

	return init;

    }else{

	return accumulate(op(init,list.shift()), op, list);

    }

}
var list = [1,2,3,4,5,6,7,8,9,10];

var result = accumulate(0,function(a,b){return a + b;},list);

応用問題

var map = function(op,list){

    return accumulate([],

		      function(a,b){

			  a.push(op(b))

			  return a;

		      }

		      ,list)

}

もとのlistがなくなっちゃうのをなくしたい。
deep cloneするしかないかな。

問4

とりあえず、クイックソートで。

var sort = function(ary){

    var length = ary.length    

    if(length<=1){

	return ary;

    }

    

    var pivot = ary[0];

    var right = [];

    var left = [];

    for(var i=1; i

*1:switchとかも。