小テスト解説
問1 オイラーの定理とはどういう定理か、説明せよ。
ある離散グラフが連結であって、かつ、全ての節点の次
数が偶数ならば、オイラー閉路が存在する。
問2 次の中置記法で書かれた数式を、前置記法に直せ。
12 + 23 ×(34 + 45)+(56 + 67)× 78 × 89
=12 + 23 ×(+ 34 45)+(+ 56 67)× 78 × 89
=12+[×23 (+ 34 45)]+[××(+ 56 67) 78 89]
=++12 [×23 (+ 34 45)] [××(+ 56 67) 78
89]
=++12×23 + 34 45××+ 56 67 78 89
小テスト解説
問3 次の後置記法で書かれた式を計算せよ。
1 2 3 × + 4 5 6 7 × + 8 9 + × 10 + × +
=1 6 + 4 5 42 + 17 × 10 + × +
=7 4 47 17 × 10 + × +
=7 4 799 10 + × +
=7 4 809 × +
=7 3236 +
=3243
小テスト解説
問4 次の推論について正しいか正しくないか論ぜよ。
(1) 前提1 Aさんは、A型だ。
前提2 A型は几帳面だ。
結論 よって、Aさんは几帳面だ。
前提2が正しくないから、正しくない。
(2) 前提1 グーならばパーにまける。
前提2 パーならばチョキにまける。
結論 よって、グーならばチョキにまける。
推論形式が正しくないから、正しくない。
(正しい三段論法にするなら、前提2の前の部分は
パーにまけるならば~ としないとだめ)
小テスト解説
問5 チューリングマシンの全域性と部分性について、説
明せよ。
任意の入力データに対して停止して結果を出力する
動作表をもつチューリングマシンを全域的であるといい、
全域的でないチューリングマシンは部分的であるという。
問6 万能チューリングマシンとはどんなチューリングマシ
ンか、簡潔に説明せよ。
他のあらゆるチューリングマシンの動作を模倣できる
チューリングマシン
小テスト解説

問7 図のような状態遷移図の有限オートマトンの
受理する言語を言葉で説明せよ。
1
S1
初期状態
0
0
1
S2
最終状態
受理: 停止した時点で内部状態が最終状態(◎で
表わされる状態)になっていれば受理される。
0 あるいは 1と0を繰り返した後、1つ以上の0で終
わる言語
授業展開#13
BASICによるアルゴリズム
基本操作
“filename” 」でプログラムの読み込み
 「save “filename” 」でプログラムの保存
 「new」でメモリからプログラム等を消去
 「clear」で変数の内容を消去
 「list」でプログラム表示
 「cls」で画面表示を消去
 「run」でプログラム実行
 「load
基本命令
A=2
B=3
C=A+B
PRINT C
END
:変数Aに2を代入
:変数Bに3を代入
:変数CにAとBの和を代入
:変数Cの中身を表示
:プログラムの終了
PRINT “C”
:これでは「C」が表示される
PRINT
PRINT 式
(例) PRINT 4+5
9が出力される
 PRINT 変数
(例) PRINT A
Aの値が出力される
 PRINT “<文字列>”
(例) PRINT “HELLO“
HELLOが出力される
 式、変数、文字列を組み合わせる場合、データ区切りと
して , (カンマ: 空白が空く) ;(セミコロン: 続けて出
力)を使う
(例)PRINT “金額”,A*100;“円”
金額
0円 と出力される

数学的取り扱い
 和:「A+B」
A+B
 差:「A-B」
A-B
 積:「A*B」
A×B
 商:「A/B」
A÷B
 n乗:「A^n」
An
 平方根「SQR(A)」 √A
 大小関係
A>B
関数、命令
MOD x
 INT(X)
 SQR(A)
 INPUT A
 DIM A(100)
N
 GOTO
XX
:Nをxで割った時の余り
:少数をカットして整数化
:Aの平方根
:Aに数値を入力
:関数Aを100個用意
A(1), A(2),・・・,A(100)
:行番号XXにジャンプ
ユーザー関数の定義
10
20
30
40
50
def fnplus(x,y)=x+y
def fnsqare(x)=x^2
input x,y
print fnplus(x,y), fnsqare(x)
end
fnの後は任意の英数字
判断
 IF
10
20
30
40
50
~ THEN ~ ELSE ~
A=2
B=3
IF A>B THEN C=A ELSE C=B
PRINT C
END
繰り返し
 FOR
10
20
30
40
~ NEXT
FOR I=1 TO 5
PRINT I
NEXT I
END
1から10までの和を求める
10
20
30
40
50
60
S=0
FOR I=1 TO 10
S=S+I
NEXT I
PRINT S
END
10!を求める
10
20
30
40
50
60
K=1
FOR I=1 TO 10
K=K*I
NEXT I
PRINT K
END
A,Bを入力して積を計算
10
20
30
40
INPUT A,B
C=A*B
PRINT C
END
三角形の面積計算
10
20
30
40
INPUT A,B
S=A*B/2
PRINT S
END
3入力の最大値を求める
10 DIM X(3)
20 FOR I=1 TO 3
30 INPUT X(I)
40 NEXT I
50 XMAX=X(1)
60 FOR J=2 TO 3
70 IF X(J)>XMAX THEN XMAX=X(J)
80 NEXT J
90 PRINT XMAX
100 END
ランダム関数
10
20
30
40
50
60
DIM N(5)
FOR I=1 TO 5
N(I)=INT(RND(1)*6)+1
PRINT N(I)
NEXT I
END
RND(1):0 以上、1 未満の範囲の値を乱数で返す。
INT() : 指定した数値の整数部分を返す。
サイコロ目の確認
10 DIM N(1000),A(6)
20 FOR I=1 TO 1000
30 LET N(I)=0
40 NEXT I
50 FOR I=1 TO 6
60 LET A(I)=0
70 NEXT I
80 FOR I=1 TO 1000
90 LET N(I)=INT(RND(1)*6)+1
100 LET A(N(I))=A(N(I))+1
110 NEXT I
120 FOR K=1 TO 6
130 PRINT K,A(K),1000/6
140 NEXT K
150 END
関数の置き換え
「N MOD X」をMODを用いないで記述せよ。
 MOD:2つの数値の除算を行い、その剰余を返す。
A=5
B=3
C=A MOD B
PRINT C

A=N/X
B=INT(A)
C=N-B*X
nの約数を全て求める
10
20
30
40
50
60
70
input n
print "The factors of";n;" are"
for i=1 to n/2
if n mod I=0 then print i
next i
print
END
nの素数判定
5 cls
10 input n
20 for i=2 to sqr(n)
30 if n mod i=0 then 70
40 next i
50 print n;" is a prime number"
60 goto 90
70 print n;" is not a prime number"
80 print i;" is the smallest factor"
90 end
ダウンロード

(+ 56 67)× 78 × 89