アルゴリズム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)));
「情報」授業用 プログラミング演習：図形描画プログラムを作ろうにコピー & ペーストで貼り付けて実行できる．