レベルTr
Tc
与えられた 1-1 プログラムの構⽂（⽂法） プログラムの構⽂に従って、が⾃分にとって馴染みがな プログラムの各部の結び付きプログラムの構文が認識できるTd

いものとして、プログラム を⾒出す。たとえば、繰り返の各部の記述を読んでその しの始まりと終わりなど。
意味（この場合は⽂法構造）を理解する。

与えられたプログラムの動作をトレースできる

プログラムの実⾏経路に従っ
1-2 プログラムの構⽂が⾃分にとって馴染みがないものと て、プログラムの各部の結び与えられたプログラムの動作が説明できる

2-1

プログラムの正しさを説明す プログラムの動作そのもる場合など、与えられた仕様 のを説明するだけでなく、（⽬的・意図）に照らしてプ プログラムの仕様（⽬ログラムの動作を説明する場 的・意図）を説明する場
合は、仕様の各部とプログラ 合は、プログラムに直接ムの各部の結び付きを⾒出す。に⽰されていない仕様を⾒出す。

与えられたプログラムを異なる目的に沿って修正できる

2-2

プログラムの中で、与えられ 異なる⽬的を達成するたた⽬的に関連する部分を⾒出 めに、関連する部分をどす。のように書き替えるべきかを⾒出す。
1

して、プログラムの各部の 付きを⾒出す。つまり、実⾏記述を読んでその意味（こ 順に命令を結び付ける。たとの場合は操作的意味）を理 えば、条件分岐の条件の真偽に従って、次に実⾏される命解する。
令を⾒出す。

レベル2-2 プログラムを修正する• 正の整数 data が与えられて，data が素数かどうかを判定するプログラムを理解できるか？
• ２以上の整数 data が与えられて，data を素因数分解する

2

素数判定問題• 入力： １つの正整数 data
• 出力： data が素数ならば「素数である」と素数でなければ「素数でない」
素数とは，1 より大きい自然数で，正の約数が 1 と自分自身のみであるもののことである．
1は素数でないとする．

3

素数判定アルゴリズム• 判定したいデータを入力し，それをdataとする• 値dataをより小さい素数で順に割れるかどうか確
認する• data=2素数である• data=1 or 2以外の偶数素数でない• dataを 3 以上の素数で割り切れるかどうかをチェックする– 割り切れる素数がある– 割り切れる素数がない素数でない素数である
4

①

入 力 (DATA)②ANSWER← 1③ＮＳチャート｛一応素数と考えておく｝
DATA≠ 2Ｔ
③ -T

Ｆ

（ DATA＝ 1 ） 又 は DATAは 偶 数

Ｔ

③ -F
Ｆ

③ -T-T③ -T-F-1

ANSWER← 0③ -T-F-2

DIVISOR ← 3｛約数候補の初期値｝(DIVISOR＜ DATA) か つ (ANSWER ＝ １ )③ -T-F-2-1◆DIVISOR は DATA の 約 数 かＴ

Ｆ

③ -T-F-2-1-T③ -T-F-2-1-F

ANSWER← 0④DIVISOR ← DIVISOR+2

ANSWER＝ １Ｔ④ -TＦ
出 力 (DATA,「 は 素 数 」 )④ -F

出 力 (DATA,「 は 合 成 数 」 )5

program CheckPrime1(input,output);
馴染みのない（？）
var answer,data,divisor:integer;
PASCAL風表現のプロ
beginwriteln(’正の整数を入力してください’); グラムが与えられ，それを理解できるか？
read(data);
answer:=1;
if data<>2 thenif (data=1) or (data mod 2=0) thenanswer:=0
else begin
divisor:=3;
while (divisor<data) and (answer=1) do
if data mod divisor=0 thenanswer:=0
else divisor:=divisor+2end;
if answer=1 then writeln(data,’は素数である’)
else writeln(data,’は素数でない’)
6
end.

program CheckPrime1(input,output);var answer,data,divisor:integer;
begin
構文構造が理writeln(’正の整数を入力してください’);
解できるか？
read(data);
answer:=1;
if data<>2 thenif (data=1) or (data mod 2=0) thenanswer:=0
else begin
divisor:=3;
while (divisor<data) and (answer=1) do
if data mod divisor=0 thenanswer:=0
else divisor:=divisor+2end;
if answer=1 then writeln(data,’は素数である’)
else writeln(data,’は素数でない’)end.

7

program CheckPrime1(input,output);var answer,data,divisor:integer;
変数 answer の役割をbegin理解できるか？
writeln(’正の整数を入力してください’);0 と 1 が代入されていread(data);
る意味は？
answer:=1;
if data<>2 thenif (data=1) or (data mod 2=0) thenanswer:=0
else begin
divisor:=3;
while (divisor<data) and (answer=1) do
if data mod divisor=0 thenanswer:=0
else divisor:=divisor+2
end;
if answer=1 then writeln(data,’は素数である’)
else writeln(data,’は素数でない’)
8end.

program CheckPrime1(input,output);
与えられた尺 4-2
var answer,data,divisor:integer;
度でより良いbegin
プログラムがwriteln(’正の整数を入力してください’); 書ける
与えられた尺度という基準において、候補
read(data);となるプログラム（の構成要素）の中から
answer:=1;上位ないし下位のものを選択する。
if data<>2 thenif (data=1) or (data mod 2=0) then
効率の悪いループ
answer:=0
divisor<data を改善できるか？
else begin
divisor:=3;
while (divisor<=data div 2) and (answer=1) do
if data mod divisor=0 thenanswer:=0
else divisor:=divisor+2
end;
if answer=1 then writeln(data,’は素数である’)
else writeln(data,’は素数でない’)
9end.

N 以下の素因数がある• 整数Ｎが合成数（素数でない）の場合• １でない最小の素因数を p とする

N  p  q （ p  q）

N  pq  p p

N p
10

program CheckPrime1(input,output);var answer,data,divisor:integer;
begin
writeln(’正の整数を入力してください’); 与えられた尺度 4-2
でより良いプロread(data);
グラムが書ける
answer:=1;
if data<>2 thenif (data=1) or (data mod 2=0) thenanswer:=0
整数data に約数があるならばelse begin
data の平方根以下のものがある
divisor:=3;
while (divisor<=sqrt(data)) and (answer=1) do
if data mod divisor=0 thenanswer:=0
else divisor:=divisor+2
end;
if answer=1 then writeln(data,’は素数である’)
else writeln(data,’は素数でない’)
11
end.

program CheckPrime1(input,output);var answer,data,divisor:integer;
begin
writeln(’正の整数を入力してください’);read(data);
answer:=1;｛繰り返し制御のため｝
if data<>2 thenif (data=1) or (data mod 2=0) thenanswer:=0
標準関数を使わずにできることもある
else begin(divisor<=sqrt(data))
divisor:=3;
while (divisor*divisor<=data) and (answer=1) do
if data mod divisor=0 thenanswer:=0
else divisor:=divisor+2
end;
if answer=1 then writeln(data,’は素数である’)
else writeln(data,’は素数でない’)
end.
12素因数分解• 任意の正の整数値が一つ与えられて，その値の素因数分解を求めるプログラムを書きなさい．
• 出力例 376=2*3**3*7• 素数判定プログラムを参考にする
Td
与えられたプログラムを異なる目的に沿って修正できる

2-2 異なる⽬的を達成するために、関連する部分をどのように書き替えるべきかを⾒出す。

13素因数分解• 例えば，２４７４０１の素因数分解はどうなるか？
• 小さい素数から順に割っていく• 求め方は知っているはず！
• それをプログラムとして書けるか？

３ ２４７４０１
３８２４６７３２７４８９７９１６３７１３０９１１１８７
１７２４７４０１＝
３×３×３×７×７×１１×１７14

整数値を変数dataに入力
data>=1

NSチャート
素因数分解

出力(data”の素因数分解＝”)

data>=2

divisor←2
divisor*divisor<=data
power←0dataをdivisorで割ったあまり=0data←data を divisorで割った商
power←power+1
power>=1
出力(divisor)

power>=2

出力(“**” power)
data>1
出力(’*’)

改行
divior=2

divisor ←3
divior ← divisor+2
data≠1出力(data)
次の整数値をdataに入力

出力(’1’)

program PrimeFactorization (input,output);var data,divisor,power:integer;begin
writeln(’正の整数を入力してください’);read(data); write(data,’=’); divisor:=2;
while divisor*divisor<=data do begin
power:=0;
while data mod divisor=0 do begin
data:=data div divisor; power:=power+1
end;
if power>=1 then beginwrite(divisor);
if power>=2 then write(’**’,power);
if data>1 then write(’*’);
end;
if divisor=2 then divisor:=3else divisor:=divisor+2end;
if data<>1 then writeln(data)
end.

16

2-1 与えられたアルゴリズムの動作を説明できる• あるスタイルのアルゴリズム記述を，他のスタイルのアルゴリズム記述に書き直せるか．
– フローチャート表現 → NSチャート表現17

最大公約数を求める
アルゴリズムの流れ図表示
この流れ図で記載されたアルゴリズムをNSチャートで記述せよ

18

連接最大公約数を求める
アルゴリズムのＮＳチャート表示選択

構造化プログラミングの３つの基本形（連接，選択，反復）を明確に表現する反復（ループ）

1973年頃のI. Nassi とB. Shneidermanによる考えをN. Chapinが整理した図式（チャート）19