拡張DNCLのプログラム例

奇数・偶数の判定

/*
入力された整数が奇数か偶数かを判定するプログラム
※通常実行モードでは動きません.
*/
suji←入力()
x←数値に変換(suji)
もしx%2=0ならば
 |  xと"は偶数です"を表示する
を実行し,そうでなければ
 | xと"は奇数です"を表示する
を実行する

1からNまでの総和

/*1からNまでの総和*/
N←100
S←0
iを1からNまで1ずつ増やしながら,
 |  S←S+i
を繰り返す
Sを表示する

ユークリッドの互除法

/*ユークリッドの互除法*/
x←432,y←342
x%y≠0の間,
 |  copy←y
 | y←x%y
 | x←copy
を繰り返す
yを表示する

素因数分解

/*素因数分解*/
n←892371480
p←2
n+" = "を改行なしで表示する
p≦平方根(n)の間,
 |  n%p=0の間,
 |  | pと"×"を改行なしで表示する
 |  | n←n÷p
 | を繰り返す
 | pを1増やす
を繰り返す
nを表示する

エラトステネスの篩

/*エラトステネスの篩*/
N←30
iを2からNまで1ずつ増やしながら,
 |  p[i]←i
を繰り返す
sqrt←平方根(N)
i←2
i≦sqrtの間,
 | もしp[i]>0ならば
 |  | j←2×i
 |  | j≦Nの間,
 |  |  | p[j]←0
 |  |  | j←j+i
 |  | を繰り返す
 | を実行する
 | iを1増やす
を繰り返す
iを2からNまで1ずつ増やしながら,
 | もしp[i]>0ならば
 |  | i+" "を改行なしで表示する
 | を実行する
を繰り返す

行列式

/*行列式の値を求めるプログラム*/
関数 det(k,N)は
 |  もしN=1ならば
 |  | k[1,1]を返す
 | を実行し,そうでなくもしN=2ならば
 |  | k[1,1]×k[2,2]-k[2,1]×k[1,2]を返す
 | を実行する
 | sum←0,sgn←1
 | iを1からNまで1ずつ増やしながら,
 |  | tmp←配列初期化(N-1,N-1)
 |  | x←1
 |  | jを1からNまで1ずつ増やしながら,
 |  |  | もしi≠jならば
 |  |  |  | y←1
 |  |  |  | tを2からNまで1ずつ増やしながら,
 |  |  |  |  | tmp[x,y]←k[j,t]
 |  |  |  |  | yを1増やす
 |  |  |  | を繰り返す
 |  |  |  | xを1増やす
 |  |  | を実行する
 |  | を繰り返す
 |  | sum←sum+sgn×k[i,1]×det(tmp,N-1)
 |  | sgn←-sgn
 | を繰り返す
 | sumを返す
を実行する
A←{{1,1,0},
{1,2,1},
{1,0,2}}
det(A,大きさ(A))を表示する

文字列反転

/*文字列を反転させて表示する*/
moji←"Hello World!!"
length←大きさ(moji)
iをlengthから1まで1ずつ減らしながら,
 |  moji[i]を改行なしで表示する
を繰り返す

挿入ソート

/*挿入ソート*/
A←{17,32,18,41,52,20,87,12,59,69}
N←大きさ(A)
iを2からNまで1ずつ増やしながら,
 |  v←A[i]
 | j←i-1
 | j≧1かつA[j]>vの間,
 |  | A[j+1]←A[j]
 |  | jを1減らす
 | を繰り返す
 | A[j+1]←v
を繰り返す
Aを表示する

選択ソート

/*選択ソート*/
arr←{17,32,18,41,52,20,87,12,59,69}
N←大きさ(arr)
iを1からN-1まで1ずつ増やしながら,
 |  tmp←i
 | jをi+1からNまで1ずつ増やしながら,
 |  | もしarr[tmp]>arr[j]ならば
 |  |  | tmp←j
 |  | を実行する
 | を繰り返す
 | copy←arr[tmp]
 | arr[tmp]←arr[i]
 | arr[i]←copy
を繰り返す
iを1からNまで1ずつ増やしながら,
 | arr[i]と" "を改行なしで表示する
を繰り返す

バブルソート

/*バブルソート*/
A←{17,32,18,41,52,20,87,12,59,69}
N←大きさ(A)
繰り返し,
 |  flag←0
 | iをNから1まで1ずつ減らしながら,
 |  | もしA[i]<A[i-1]ならば
 |  |  | copy←A[i]
 |  |  | A[i]←A[i-1]
 |  |  | A[i-1]←copy
 |  |  | flag←1
 |  | を実行する
 | を繰り返す
を,flag=0になるまで実行する
Aを表示する

クイックソート

/*クイックソート*/
関数 分割(A,p,r)は
 |  x←A[r]
 | i←p-1
 | jをpからr-1まで1ずつ増やしながら,
 |  | もしA[j]<=xならば
 |  |  | i←i+1
 |  |  | copy←A[i]
 |  |  | A[i]←A[j]
 |  |  | A[j]←copy
 |  | を実行する
 | を繰り返す
 | copy←A[i+1]
 | A[i+1]←A[r]
 | A[r]←copy
 | i+1を返す
を実行する

関数 クイックソート(A,p,r)は
 | もしp<rならば
 |  | q←分割(A,p,r)
 |  | クイックソート(A,p,q-1)
 |  | クイックソート(A,q+1,r)
 | を実行する
を実行する
A←{22,375,721,110,399,222,19,544}
Aを改行して表示する
クイックソート(A,1,大きさ(A))
Aを改行して表示する

マージソート

/*マージソート*/
関数 マージソート(a,len,left,right)は
 |  もしright≦leftならば
 |  | 0を返す
 | を実行する
 | mid←(left+right)÷2
 | マージソート(a,mid,left,mid)
 | マージソート(a,len-mid,mid+1,right)
 | iをleftからmidまで1ずつ増やしながら,
 |  | tmp[i]←a[i]
 | を繰り返す
 | i←mid+1,j←right
 | i≦rightの間,
 |  | tmp[i]←a[j]
 |  | iを1増やす
 |  | jを1減らす
 | を繰り返す
 | L←left,R←right
 | iをleftからrightまで1ずつ増やしながら,
 |  | もしtmp[L]≦tmp[R]ならば
 |  |  | a[i]←tmp[L]
 |  |  | Lを1増やす
 |  | を実行し,そうでなければ
 |  |  | a[i]←tmp[R]
 |  |  | Rを1減らす
 |  | を実行する
 | を繰り返す
を実行する
A←{22,375,721,110,399,222,19,544}
L←大きさ(A)
マージソート(A,L,1,L)
Aを表示する

バイナリサーチ

/*バイナリサーチ*/
関数 バイナリサーチ(key,A)は
 |  left←1,right←大きさ(A)
 | left<rightの間,
 |  | mid←(left+right)÷2
 |  | もしA[mid]=keyならば
 |  |  | midを返す
 |  | を実行し,そうでなくもしkey<A[mid]ならば
 |  |  | right←mid
 |  | を実行し,そうでなければ
 |  |  | left←mid+1
 |  | を実行する
 | を繰り返す
 | -1を返す
を実行する
A←{19,22,110,201,222,375,399,503,544,721}
バイナリサーチ(544,A)を表示する

モンテカルロ法

/*モンテカルロ法による円周率の近似値の計算*/
kaisu←100000
inside←0
iを1からkaisuまで1ずつ増やしながら,
 |  x←乱数(),y←乱数()
 | もしx*x+y*y≦1ならば
 |  | inside←inside+1
 | を実行する
を繰り返す
"π≒"+4.0*inside/kaisuを改行して表示する

再帰

/*nCrの値を返す関数*/
関数 組合せ(n,r)は
 |  もしn=rならば
 |  | 1を返す
 | を実行し,そうでなくもしr=0ならば
 |  | 1を返す
 | を実行し,そうでなくもしr=1ならば
 |  | nを返す
 | を実行し,そうでなければ
 |  | 組合せ(n-1,r-1)+組合せ(n-1,r)を返す
 | を実行する
を実行する
"5C2 = "+組合せ(5,2)を改行して表示する

/*numの階乗を返す関数*/
関数 階乗(num)は
 | もしnum=0ならば
 |  | 1を返す
 | を実行し,そうでなければ
 |  | num*階乗(num-1)を返す
 | を実行する
を実行する
"5! = "+階乗(5)を改行して表示する

/*フィボナッチ数列の第n項を返す関数*/
関数 数列(n)は
 | もしn<2ならば
 |  | nを返す
 | を実行し,そうでなければ
 |  | 数列(n-1)+数列(n-2)を返す
 | を実行する
を実行する
"fib(10) = "+数列(10)を改行して表示する

パターン列挙

/*パターン列挙*/
関数 パターン(s,k)は
 |  もしk=0ならば
 |  | sを表示する
 |  | sを返す
 | を実行する
 | パターン(s+"A",k-1)
 | パターン(s+"B",k-1)
 | パターン(s+"C",k-1)
を実行する
パターン("",3)

再帰下降構文解析

/*
再帰下降構文解析により文字列表現の数式を計算するプログラム
*/
関数 数字(n)は
 |  n="0"またはn="1"またはn="2"またはn="3"またはn="4"またはn="5"またはn="6"またはn="7"またはn="8"またはn="9"を返す
を実行する

関数 分割(f)は
 | length←大きさ(f)
 | pos←1
 | cnt←1
 | pos≦lengthの間,
 |  | もし数字(f[pos])ならば
 |  |  | num←""
 |  |  | flag←true
 |  |  | flagの間,
 |  |  |  | もしpos≦lengthならば
 |  |  |  |  | もし数字(f[pos])ならば
 |  |  |  |  |  | num←num+f[pos]
 |  |  |  |  |  | pos←pos+1
 |  |  |  |  | を実行し,そうでなければ
 |  |  |  |  |  | flag←false
 |  |  |  |  | を実行する
 |  |  |  | を実行し,そうでなければ
 |  |  |  |  | flag←false
 |  |  |  | を実行する
 |  |  | を繰り返す
 |  |  | token[cnt]←num
 |  | を実行し,そうでなければ
 |  |  | token[cnt]←f[pos]
 |  |  | pos←pos+1
 |  | を実行する
 |  | cnt←cnt+1
 | を繰り返す
 | tokenを返す
を実行する

//<expr> ::= <term> | <expr> + <term> | <expr> - <term>
関数 expr(p,t)は
 | n←term(p,t)
 | trueの間,
 |  | もしt[p[1]]="+"ならば
 |  |  | p[1]を1増やす
 |  |  | n←n+term(p,t)
 |  | を実行し,そうでなくもしt[p]="-"ならば
 |  |  | p[1]を1増やす
 |  |  | n←n-term(p,t)
 |  | を実行し,そうでなければ
 |  |  | nを返す
 |  | を実行する
 | を繰り返す
を実行する

//<term> ::= <fact> | <term> * <fact> | <term> / <fact>
関数 term(p,t)は
 | n←fact(p,t)
 | trueの間,
 |  | もしt[p[1]]="*"ならば
 |  |  | p[1]を1増やす
 |  |  | n←n×fact(p,t)
 |  | を実行し,そうでなくもしt[p[1]]="/"ならば
 |  |  | p[1]を1増やす
 |  |  | n←n/fact(p,t)
 |  | を実行し,そうでなければ
 |  |  | nを返す
 |  | を実行する
 | を繰り返す
を実行する

//<fact> ::= "(" <expr> ")" | 整数
関数 fact(p,t)は
 | もしt[p[1]]="("ならば
 |  | p[1]を1増やす
 |  | exp←expr(p,t)
 |  | もしt[p[1]]=")"ならば
 |  |  | p[1]を1増やす
 |  |  | expを返す
 |  | を実行する
 | を実行し,そうでなければ
 |  | n←t[p[1]]
 |  | p[1]を1増やす
 |  | 数値に変換(n)を返す
 | を実行する
を実行する
t←分割("(1+2+3)*(4+5+6)")
p←{1}
expr(p,t)を表示する

動的計画法

/*動的計画法によるナップザック問題*/

/*
価値がv[i]重さがw[i]であるようなN個の品物と
容量がWのナップザックに,

・選んだ品物の価値の合計をできるだけ高くする.
・選んだ品物の重さの総和はWを超えない.

という条件を満たすように品物を選んでナップザックに入れる.
このときの価値の合計の最大値を求めるプログラム.
*/
N←4
W←5
v←{4,5,2,8}
w←{2,2,1,3}
dp←配列初期化(N+1,W+1)
/*xとyのうち,大きい方の値を返す関数*/
関数 最大値(x,y)は
 |  もしx<yならば
 |  | yを返す
 | を実行し,そうでなければ
 |  | xを返す
 | を実行する
を実行する
iを1からNまで1ずつ増やしながら,
 | jを1からW+1まで1ずつ増やしながら,
 |  | もしj-w[i]≧1ならば
 |  |  | dp[i+1,j]←最大値(dp[i,j-w[i]]+v[i],dp[i,j])
 |  | を実行し,そうでなければ
 |  |  | dp[i+1,j]←dp[i,j]
 |  | を実行する
 | を繰り返す
を繰り返す
"最大値:"とdp[N+1,W+1]を改行して表示する

2018年 情報関係基礎 第3問 問2

/*2018年 情報関係基礎 第3問 問2*/
tate←9,yoko←11
Masu←{{1,1,1,1,1,1,1,1,1},
{1,0,0,0,1,0,0,0,1},
{1,1,1,0,0,0,1,0,1},
{9,0,0,0,1,0,1,0,1},
{1,1,1,0,1,0,1,0,1},
{1,0,1,1,1,0,1,1,1},
{1,0,0,0,1,0,1,0,1},
{1,1,1,0,0,0,1,0,9},
{1,0,0,0,1,1,1,0,1},
{1,0,1,0,0,0,0,0,1},
{1,1,1,1,1,1,1,1,1}}
繰り返し,
 |  nutta←0
 | yを2からtate-1まで1ずつ増やしながら,
 |  | xを2からyoko-1まで1ずつ増やしながら,
 |  |  | s←Masu[x-1,y]+Masu[x+1,y]+Masu[x,y-1]+Masu[x,y+1]
 |  |  | もしMasu[x,y]=0かつs=3ならば
 |  |  |  | Masu[x,y]←1,nutta←1
 |  |  | を実行する
 |  | を繰り返す
 | を繰り返す
を,nutta=0になるまで実行する
yを1からtateまで1ずつ増やしながら,
 | xを1からyokoまで1ずつ増やしながら,
 |  | もしMasu[x,y]=1ならば
 |  |  | "■"を改行なしで表示する
 |  | を実行し,そうでなければ
 |  |  | "□"を改行なしで表示する
 |  | を実行する
 | を繰り返す
 | 改行を表示する
を繰り返す

©2019 Takumi Daimon