next up previous contents index
Next: メソッド(method) Up: JAVA入門 Previous: 選択(selection)   目次   索引

反復

反復(Loop)

ループとは繰り返し文のことです．俗に反復処理(iteration)と呼ばれていて構造化プログラミングの根幹をなしています．反復処理にはwhile文，do-while文とfor文があります．

その昔，コンピュータの性能が悪かった時代，また，しっかりした制御構造および反復処理がプログラミング言語に用意されたいなっかた時代，多くの人がgoto文と呼ばれるジャンプを使ってプログラムを書いていました．しかし，１９６０年代後半goto文によって書かれたプログラムは，他人にとってわけのわからないプログラム（スパゲッティプログラム）になり，諸悪の根源であると言われ始めました．このことより，ソフトウェアも通常の工業製品と同じように生産管理が必要であるという観点から「ソフトウェア工学」が生まれました．このような流れの中から，分かりやすいプログラムを書くための方法論がダイクストラによって提案され，その中の１つに「構造化プログラミング」があります．

構造化プログラミング(Structured Programming)

構造化プログラミングは，基本的に３つの構造から成り立っています．

連接(sequence):プログラムは上から下に流れる
選択構造（Selection）
反復処理（Iteration）

構造化定理によると，すべてのアルゴリズムはこの３つの構造だけで記述できることが証明されています．

現在，Java言語を学んでいる人は，上記の１，２，３だけでアルゴリズムを書く練習をして下さい．なお，今やプロジェクトの規模が大きくなり，構造化プログラミングを用いても，ある時点からは複雑さがプログラマの管理できる限界を超えてしまっています．そこで生まれたのが，オブジェクト指向という考え方です．Java言語はすでに述べましたがオブジェクト指向言語です．

while文(while Statement)：〜の間〜する

while文の構文は
    while(条件式){
        ステートメント;
    }

の形をとります．while文は条件式が真である限り，その対象の評価を繰り返します．条件式が偽になると，ループを停止します．したがって，while文はステートメントを一つも実行せず，while文を終えることもあります．

例題 4..1   数列の和
\framebox{ \begin{minipage}{13.65cm} $1^2 + 2^2 + 3^2 + 4^2 + 5^2 + \cdots + 100^2$を求めるプログラムを{\rm while}ループを用いて作成しなさい． \end{minipage}}

解答 求める和をsとおくと， $s = \sum_{k=1}^{100}k^{2}$と表せます．$k=1$のとき，$s = 1^{2}$. $k=2$のとき， $s = 1^{2} + 2^{2}$となりますが，$k=1$のとき，$s = 1^{2}$としておくと，$k=2$のとき， $s = s+2^{2}$と表せることに気づいたでしょうか．これが数列の和のコーディングの方法です．

この問題では$j$番目が$j^2$より和は$s=s+j^2$と表せます．これを$j$が１から100まで行えばよいので,擬似コードで書くと，
j $\leftarrow$ 1, s $\leftarrow$ 0;
while (j $<=$ 100) do
s $\leftarrow$ s + $j^{2}$;
j $\leftarrow$ j+1;
となります．これをJava言語に書き直すと，

class SumOfSquares {
  public static void main(String[] args)
  {
    int j = 1, sum = 0;
    while(j <= 100)
    {
      sum += j*j;
      j++;
    }
    System.out.println(sum);
  }
}

実行結果

\begin{figure}\centering \includegraphics[width=7.8cm]{JAVAFIG/SumOfSquares.eps} \end{figure}

一般に，ｊ番目がある関数ｆ(ｊ)で表せるならば，上のステートメントs += j*j;をs += f(j)と書き換えることができます．．

練習問題 4..1   数列の和
$100^2 + 99^2 + 98^2 + 97^2 + 96^2 + \cdots + 1^2$をこの順で求めるプログラムをwhileループを用いて作成しなさい．

例題 4..2   逆数の和
\framebox{ \begin{minipage}{13.65cm} {\rm s = 1 + 1/2 + 1/3 + $\cdots$\ 1/nを求めるプログラムを作成しなさい．ただし，nは逆数の和sが入力されたある整数より大きくなる最初の整数とします．} \end{minipage}}

解答 逆数の和をsumとし，入力された値をboundとすると，
i $\leftarrow$ 0;
while(sum $<$ bound) do
sum $\leftarrow$ sum + 1.0/++i;
で逆数の和が入力された値より大きくなる最初の整数iを求めることができます．Java言語に書き直すと，

class SumOfReciprocal
{
  public static void main(String[] args)
  {
    int bound = Integer.parseInt(args[0]);
    int i = 0;
    double sum = 0.0;
    while(sum < bound)
    {
      sum += 1.0/++i;
    }
    System.out.println("最初の" + i + "項の逆数の和は" + sum);
  }
}

実行結果

\begin{figure}\centering \includegraphics[width=7.8cm]{JAVAFIG/SumOfReciprocal.eps} \end{figure}

練習問題 4..2   逆数の和
sum = 1 + 1/2 + 1/3 + $\cdots$ + 1/1000とrsum = 1/1000 + 1/999 + $\cdots$ + 1をfloatで宣言し求めるプログラムを作成しなさい．sumとrsumの値を比較しなさい．また，どちらが正確か考えなさい．さらに，このとき発生した誤差はなんとよばれるか．

例題 4..3   素因数分解
\framebox{ \begin{minipage}{13.65cm} {\rm 2以上の整数をコマンドラインから入力して，素因数分解するプログラムを作成しなさい．} \end{minipage}}

解答 素因数とは，与えられた数nの約数でかつ素数のことです．素数とは，それ自身と1でしか割れない数です．ただし，1は素数には入れません．例えば，nを120とすると，nの約数は，2,3,5であり，120の素因数分解を行なうと， $120=2 {3}\cdot 3 \cdot 5$となります．

2 120
2 60
2 30
3 15
  5

では，素因数分解をおこなうアルゴリズムを考えてみます．データnを読み取って，2から順に割っていき，ある数mで割れたら商n/mを新たなnとおき，さらにmで割り切れなくなるまで続ける．mで割り切れなくなったらmを1増加し，nを割っていくことを繰り返し，商nが１になるまで続ける．このとき発生した，mが素因数となります．表示するときに，最後の数字のあとには「，」を付けないようにします． では，プログラムを作成しましょう．

class IntFactorization
{
  public static void main(String[] args)
  {
    int input = Integer.parseInt(args[0]);
    int divisor = 2;
    while(input != 1)
    {
      while(input % divisor == 0)
      {
        input /= divisor;
        if(input != 1)
        {
          System.out.print(divisor + "*");
        }
        else
        {
          System.out.println(divisor);
        }
      }
      divisor++;
    }
  }
}

実行結果

\begin{figure}\centering \includegraphics[width=7.8cm]{JAVAFIG/IntFactorization.eps} \end{figure}

練習問題 4..3   素数判定
与えられた数が素数かどうか判定するプログラムを作成しなさい．

do ... while文(do ... while Statement)

do ... while文の構文は
    do {
        ステートメント;
    }while(条件式);
最低一回は必ず実行されます.

例題 4..4   数列の和
\framebox{ \begin{minipage}{13.65cm} {\rm $1^2 + 2^2 + 3^2 + 4^2 + 5^2 + … + 100^2$を求めるプログラムをdo...whileループを用いて作成しなさい．} \end{minipage}}

解答

class SumOfSquares {
  public static void main(String[] args)
  {
    int j = 1, sum = 0;
    while(j <= 100)
    {
      sum += j*j;
      j++;
    }
    System.out.println(sum);
  }
}

実行結果

\begin{figure}\centering \includegraphics[width=7.8cm]{JAVAFIG/SumOfSqRev.eps} \end{figure}

練習問題 4..4   数列の和
$100^2 + 99^2 + 98^2 + 97^2 + … + 1^2$を求めるプログラムをdo...whileループを用いて作成しなさい．

階乗0!,1!,2!,3!,...は次の漸化式により定義されています．

$\displaystyle \left\{\begin{array}{l} 0! = 1\\ n! = n(n-1)! \end{array}\right.$

例えば，$n = 3$のとき，

$\displaystyle 3! = 3(3-1)! = 3(2!) = 3(2)(2-1)! = 3(2) = 6$

となるので，6は3の階乗です．

例題 4..5   階乗数
\framebox{ \begin{minipage}{13.65cm} {\rm 入力された整数までの階乗数を全て求めるプログラムを作成せよ．} \end{minipage}}

解答 階乗$n!$を$f(n)$とすると， $f(n) = nf(n-1)$で与えられる．そこで， $f = f(n-1) = (n-1)!$とおくと，階乗を求める構文は，繰り返しを用いて
f = f * n
となる．この$n$を１から順に増やしていけば，全ての階乗を求めることができる．よって，擬似コードで書くと
入力 bound;
i $\leftarrow$ 1;
f $\leftarrow$ 1;
do
f $\leftarrow$ f $\ast$ (++i);
while(i $<$ 入力);
となる．例題5.2では再帰(recursion)を用いてn!を求めている．

class Factorial
{
  public static void main(String[] args)
  {
    long input = Integer.parseInt(args[0]);
    long f = 1, i= 1;
    do
    {
      f *= ++i;
    System.out.println(f);
    }while(f < input);
  }
}

実行結果

\begin{figure}\centering \includegraphics[width=7.8cm]{JAVAFIG/Factorial.eps} \end{figure}

練習問題 4..5   階乗
${}_{n}C_{r}$を求めるプログラムを作成しなさい．ここで，

$\displaystyle {}_{n}C_{r} = 1\cdot\frac{n-1+1}{1} \cdot \frac{n-2+1}{2} \cdot \frac{n-3+1}{3} \cdots \frac{n-r+1}{r}$

for文(for Statement)

for文の構文は
    for (初期値；条件式；更新){
        ステートメント;
    }

の形をとります．

  1. 初期値はコントロール変数の初期化を行います．2つ以上の初期値を書く場合はカンマで区切る．
  2. 条件が成立するとステートメントは実行されます．条件が成立しなければループを終了．
  3. コントロール変数が更新されます．
  4. 2,3を繰り返す．

例題 4..6   数列の和
$1^2 + 2^2 + 3^2 + 4^2 + 5^2 + … + 100^2$を求めるプログラムをforループを用いて作成しなさい．

解答

class SumOfSqFor
{
  public static void main(String[] args)
  {
    int sum = 0;
    for(int j = 1; j <= 100; j++)
    {
      sum = sum + j*j;
    }
    System.out.println(sum);
  }
}

実行結果

\begin{figure}\centering \includegraphics[width=7.8cm]{JAVAFIG/SumOfSqFor.eps} \end{figure}

練習問題 4..6   forループを用いた数列の和
$1/1^2 + 1/3^2 + 1/5^2 + … + 1/101^2$を求めるプログラムをforループを用いて作成しなさい．

例題 4..7   反復練習
次のような形を表示するプログラムを作成しなさい．

実行結果

\begin{figure}% latex2html id marker 1045 \centering \includegraphics[width=3.3c... ...dai4-12.eps} \includegraphics[width=3.4cm]{CPPPIC/reidai4-12-1.eps} \end{figure}

解答

＜実行結果１＞
System.out.println("*");
で１つのアスタリスクを表示することができます．では*****と表示するにはどうすればよいでしょうか．確かにSystem.out.println("*****");でもできますが，これではアスタリスクを任意の数だけ表示せよとなると，不可能です．そこで，System.out.print("*");を5回実行すると*****が表示できることに気づけばよいでしょう．５回実行させるには，例えばforループを用いるとfor(int i=1;i$<$=5;i++)と書けばよいことを知っています．次に，第１回目には，１つのアスタリスク，第２回目は２つのアスタリスクと増やすにはどうすればよいでしょうか．i$<=$5の5の代わりに，jを用いて，

for(int j=1;j$<$=5;j++){

for(int i=1;i$<$=j;i++){

System.out.print("*");

}

}

と書けば，外側のループが１回終了する間に内側のループがj回実行されることになります．内側のループが終了したら，"
n"で改行します．ではプログラムを作成しましょう．

class AstTree
{
  public static void main(String[] args)
  {
    for(int j = 1; j <= 5; j++)
    {
      for(int i = 1; i <= j; i++)
      {
        System.out.print("*");
      }
      System.out.println();
    }
  }
}

＜実行結果２＞

実行結果１との違いはアスタリスクを右詰めで表示しているところです．そこで，アスタリスクの前にブランクを挿入するコマンドを追加すればよいでしょう．

class AstTreeRight
{
  public static void main(String[] args)
  {
    for(int j = 1; j <= 5; j++)
    {
      for(int i = 1; i <= 5; i++)
      {
        if(i > 5-j)
        {
          System.out.print("*");
        }
        else
        {
          System.out.print(" ");
        }
      }
      System.out.println();
    }
  }
}

練習問題 4..7   反復練習
次のような形を表示するプログラムを作成しなさい．

\begin{figure}% latex2html id marker 1068 \centering \includegraphics[width=3.0cm]{CPPPIC/renshu4-7.eps} \end{figure}

continue文(continue Statement)

break文はループブロックのbreak文以下をスキップし，ループの外の次の文にジャンプします．continue文もbreak文のように，ループブロックをスキップしますが，ループを終了する代わりに，ループの次の反復に移ります．

例題 4..8   continueとbreak文
次のプログラムを実行するとどんな結果が得られるか考えなさい．

class BreakAndContinue
{
  public static void main(String[] args)
  {
    int n = Integer.parseInt(args[0]);
    for(int i = 1; i < n ; i++)
    {
      if(n % 2 == 0)
      {
        System.out.println("ループの中");
        continue;
      }
      if(n % 3 == 0)
      {
        System.out.println("ループの最後");
        break;
      }
    }
    System.out.println("ループの外");
  }
}

解答 2でも3でも割り切れない数を入力すると，2つのif文の条件を満たさないので，"ループの外"が出力されます．2で割り切れる数を入力すると，"ループの中"が出力されcontinueで残りのステートメントをスキップし，ループに戻り，ループの条件が満たされなくなったら"ループの外"を出力します．2で割り切れず3で割り切れる数を入力すると，"ループの最後"を出力しbreak文でループの外に出ます．

実行結果

\begin{figure}\centering \includegraphics[width=7.8cm]{JAVAFIG/BreakAndContinue.eps} \end{figure}

確認問題 4..1  

1. while文の条件式が最初から正しくない（つまり零）場合どうなるか述べなさい．

2. 次のプログラムコードはどこが間違っているか．

while (n <= 100)
sum += n*n;

3. 次のプログラムコードはどこが間違っているか．

class WhatIsWrong
{
  public static void main()
  {
    final double PI;
    int n;
    PI = 3.141592653;
    n = 22;
  }
}

4. break文はどのようにしてループにコントロールをもたらすか述べなさい．

演習問題 4..1  

1. eを式，sを文とするとき，次のforループをwhileループを用いて書き直しなさい．

a. for(;e;)s
b. for ( ; ; e) s

2. 次のforループをwhileループを用いて書き直しなさい．

for (int i=1; i <= n; i++)
    System.out.println(i*i + " ");

3. 次のコードをトレースしなさい．
float x = 4.15;
for (int i = 0; i $<$ 3; i++)
x *= 2;

4. 入力した10進数の数字を反転して出力するプログラムを書きなさい．

5. Euclidの互助法は2つの整数の最大公約数を求めるのに用いることができます．そのアルゴリズムは例えば，210と56の最大公約数ならば，

$\displaystyle 210$ $\displaystyle =$ $\displaystyle 56*3 + 42 \cdots (1)$  
$\displaystyle 56$ $\displaystyle =$ $\displaystyle 42*1 + 14 \cdots (2)$  
$\displaystyle 42$ $\displaystyle =$ $\displaystyle 14*3 + 0 \cdots (3)$  

より，14は（3）の式の両辺の約数です．次に14は（2）の式の両辺の約数です．なぜなら，14は42の約数より，14は56の約数となるからです．最後に14は（1）の式の両辺の約数です．つまり，14は210と56の約数です．また，14より大きな数で，210と56の約数があるとすると，その数は（1）の式より42の約数となります．ということは（2）の式より，14の約数となります．このことから，14は210と56の最大公約数です．

次に，210と56の最大公約数を$(210,56)$と表すと，

$\displaystyle (210, 56) \rightarrow (56,42) \rightarrow (42,14) \rightarrow (14,0)$

となります．このアルゴリズムを実装しなさい．

next up previous contents index
Next: メソッド(method) Up: JAVA入門 Previous: 選択(selection)   目次   索引