5/26 問題の解き方

質問と回答

Q.
ターミナルが難しかった。
Q.
ターミナルで間違って入力してしまったとき、一からやり直さなければいけないのが大変だった。
A.
ターミナルを使いこなせるようになると，繰り返し作業の代わりにコマンド一行でおこなえるようになるなど，強力な武器になりますが，詳しい使い方は講義では扱わない(ことになっている)ので苦労している人が多いようですね．自習教材のはいぱーワークブックの以下のあたりを自習すると良いと思います． なお，コマンドを誤って入力した時は15.4 ターミナルの便利な使い方にあるように，過去のコマンド入力を修正して入力しなおすことができるので，参考にしてください(telnetの中では使えないようですが)．
Q.
プログラミングについてもっと勉強したい
A.
この教科「情報」は全学の必修科目なので，プログラミングに関しては深いところまでは扱いません．興味をもった人は，Aセメスターの「アルゴリズム入門」の受講をお勧めします．

5/19課題 について

今日の講義

講義は約1時間10分で30分は演習とする．講義の時間中は，端末は使わないように(電源をつける，ログインしておくのは可)． 今日の範囲は第6章「問題の解き方」．

教科書の補足

「計算の方法」ではプログラミングの概念だけを説明している．本格的なプログラミ ングは，冬学期の情報科学でRuby言語を題材に扱う予定だが， ブラウザ上で，Processing というプログラミング言語を使って，簡単なプログラミングが体験でき るので，紹介する． なお，終了しないプログラムを実行した時などは，ブラウザ(Safariなど)がフリーズすることがある．この時は，[Option]+[Command]+[Esc] の3つのキーを同時に押して，「アプリケーションの強制終了」のメニューを出して，ブラウザ(Safariなど)を強制終了すると良い．

アルゴリズム1(反復による平方根の計算) 

x = 2; // 2の平方根を求める．ここを書き換えると別の数の平方根を求められる．
delta = 0.0001; // 解の精度

y = 0;
while((y+delta) * (y+delta) < x){
  y = y + delta;
}
alert(str(x)+"の平方根は"+str(y));
アルゴリズム2(二分法による平方根の計算) 
x = 2; // 2の平方根を求める．ここを書き換えると別の数の平方根を求められる．
delta = 0.0000001; // 解の精度を上げても大丈夫

a = 0;
b = x;
while(b-a > delta){
  c = (a+b)/2
  if(c*c > x){
    b = c;
  }
  else{
    a = c;
  }
}
alert(str(x)+"の平方根は"+str(a));
アルゴリズム3(ニュートン・ラプソン法による平方根の計算) 
x = 2; // 2の平方根を求める．ここを書き換えると別の数の平方根を求められる．
delta = 0.0000001; // 解の精度を上げても大丈夫

y = x;
while(abs(x - y * y)/(2*y) > delta){
  y = (y*y+x)/(2*y);
}
alert(str(x)+"の平方根は"+str(y));
アルゴリズム4(再帰的なフィボナッチ数の計算) 
int f(i){
  if(i==0 || i == 1) { return 1; }
  else{
    int a = f(i-1);
    int b = f(i-2);
    return a + b;
  }
}
alert("fib(10)="+str(f(10)));
アルゴリズム5(メモ化によるフィボナッチ数の計算) 
int[] v=new int[1000];
int f(i){
  if(i==0 || i == 1) { return 1; }
  else if(v[i] != 0) { return v[i]; }
  else{
    int a = f(i-1);
    int b = f(i-2);
    v[i] = a + b;
    return v[i];
  }
}
alert("fib(10)="+str(f(10)));
アルゴリズム6(二分探索による辞書の検索) 
words = {"apple","banana","melon","orange","pineapple"};
N = 5;
w = "orange";
// w = "watermelon";

int search(w){
  int a = 0;
  int b = N;
  while(a <= b){
    int c = floor((a+b)/2);
    if(w == words[c]){
      return c;
    }
    else {
      if(w < words[c]){
        b = c - 1;
      }
      else{
        a = c + 1;
      }
    }
  }
  return -1;
}
j = search(w);
if(j < 0){
  alert(w+"は収録されていなかった");
}
else{
  alert(w+"は辞書の"+j+"番目に収録されている");
}
アルゴリズム7(再帰的な最短経路長の計算) 
// 駅に番号をつける
// 渋谷 : 0, 新宿 : 1, 表参道 : 2, 目黒 : 3, 池袋 : 4, 
// 国会議事堂前 : 5, 後楽園 : 6, 本郷三丁目 : 7
w = {{-1, 3.4, 1.3, 3.1,  -1,  -1,  -1,  -1},
     {-1,  -1,  -1,  -1, 4.8, 5.1,  -1,  -1},
     {-1,  -1,  -1,  -1,  -1, 3.3,  -1,  -1},
     {-1,  -1,  -1,  -1,  -1, 5.7,  -1,  -1},
     {-1,  -1,  -1,  -1,  -1,  -1, 4.8,  -1},
     {-1,  -1,  -1,  -1,  -1,  -1, 6.8, 5.9},
     {-1,  -1,  -1,  -1,  -1,  -1,  -1, 0.8},
     {-1,  -1,  -1,  -1,  -1,  -1,  -1,  -1}};
double d(v){
  if(v == 7){ return 0.0; }
  else{
    double minv=100.0;
    for(int i=0;i < 8;i++){
      if(w[v][i]>=0.0){
        minv=min(minv, d(i)+w[v][i]);
      }
    }
    return minv;
  }
}
alert(str(d(0)));
アルゴリズム8(メモ化による最短経路長の計算) 
// 駅に番号をつける
// 渋谷 : 0, 新宿 : 1, 表参道 : 2, 目黒 : 3, 池袋 : 4, 
// 国会議事堂前 : 5, 後楽園 : 6, 本郷三丁目 : 7
w = {{-1, 3.4, 1.3, 3.1,  -1,  -1,  -1,  -1},
     {-1,  -1,  -1,  -1, 4.8, 5.1,  -1,  -1},
     {-1,  -1,  -1,  -1,  -1, 3.3,  -1,  -1},
     {-1,  -1,  -1,  -1,  -1, 5.7,  -1,  -1},
     {-1,  -1,  -1,  -1,  -1,  -1, 4.8,  -1},
     {-1,  -1,  -1,  -1,  -1,  -1, 6.8, 5.9},
     {-1,  -1,  -1,  -1,  -1,  -1,  -1, 0.8},
     {-1,  -1,  -1,  -1,  -1,  -1,  -1,  -1}};
int[] m=new int[8];
double d(v){
  if(v == 7){ return 0.0; }
  else if(m[v]>0){ return m[v]; }
  else{
    double minv=100.0;
    for(int i=0;i < 8;i++){
      if(w[v][i]>=0.0){
        minv=min(minv, d(i)+w[v][i]);
      }
    }
    m[v] = minv;
    return minv;
  }
}
alert(str(d(0)));
「情報」授業用　プログラミング演習：図形描画プログラムを作ろうにコピー & ペーストで貼り付けて実行できる．

今回の課題