今日の表計算ソフトを使った演習では、下記のサンプルファイルを練習に使うので、Teamsで参照してください。

• 2024-06-21-Excelサンプル.xlsx

前回課題の答え合わせ

前回のレポートでは、sin(83度)_(例)といった数値の有効数字を考えるというものを考えてもらったので、この有効数字をどう記載すべきか考えてみる。

課題を示す Excel ファイルでは、75度～89度あたりの角度で出題をするようにしてあった。注意しないといけない点は、sinは90度に近づくほど、1に近づく。このため、0.99…といった数値が求まるが、角度がちょっと変化しても、0.99といった部分はほぼ変化しない。だから、83が有効数字2桁ということで、0.99 といった有効数字2桁の書き方では、ちょっと不十分かもしれない。

そこで、83度(有効数字2桁)が小数点以下を丸められた数値と仮定する。この場合、元の数値は 82.5度～83.5度 の可能性がある。これらの値のsinを計算すると、0.9914から0.9935の間であり、小数点以下3桁目は、1～3 の値であり、結果を 0.992 (有効数字3桁) と記載しても良いかもしれない。

 sin(82.5°) = 0.991444861
 sin(83.0°) = 0.992546152
 sin(83.5°) = 0.993571856

表計算ソフトの使い方

情報制御基礎では、プログラムで計算する所を、Excel のような表計算ソフトを用いて検証してもらったりする予定なので、Excel で計算式を使う方法を説明する。

セルの場所と簡単な式

簡単な、品名・単価・個数・価格の表を考える。以下の表のように、列の名前と、品名・単価・個数まで入力した後、単価と個数をかけた価格を求めるとする。

Excel では、表の列には左から、A,B,C,D… , 表の行には上から1,2,3,4,5 と番号が振られていて、特定の列・特定の行のデータを表す時には、列行を組み合わせ、A1に品名、B3に￥80、C5に4 が入っている。

例えば、D2 に、ノート単価120円、ノート個数3個をかけた値を入れたい場合は、D2の場所に、

=B2*C2

を書き込めば、その場所には360が表示される。

先頭の”=”を入力した後、該当する”B2″の場所をクリックするなりカーソルを操作すると、カーソルのセルの場所”B2″が自動的に入力される。さらに”*”を入力した後、”C2″の場所をクリックすれば”C2″が入力される。

Excelでは、入力する文字列の先頭が”=”の場合は、残り部分は計算式として扱われる。

D3には、”=B3*C3″を入力すれば、160 が表示される。しかし、この様な式を何度も入力するのは面倒である。

この場合、セル・カーソルを、D2 に合わせ、[右ボタン]-[コピー]を行い、D3 で[右ボタン]-[貼り付けオプション]-[貼り付け]を行えば、”=B3*C3″が入力される。

ここで注意しないといけないのが、式を張り付ける場合には、貼り付け先のセルの場所が一つ下の行なので、行番号を表す2の部分が1つ下の行番号3に書き換えられて、貼り付けが行われる。(相対参照)

関数式

例えば、下左図のような、数字とその平方根の表を作る場合、A2 に 1、B2に =sqrt( A2 ) を入力、A3 に =A2+1 を入力したあと、B2の式をB3にコピー＆ペーストし、A3,B3　を A4～A6にペーストすればいい。

B2に入力したような、sqrt( A2 ) のようなものは、関数式と呼ばれる。

また、A3,B3 といった複数の行・列をまとめた範囲を示す時は、A3:B3 といった表記方法であらわす。

絶対参照と相対参照

最初の例に戻って、単価と個数の積で今度は税率を加えて計算する例を考える。また、税率は後で変化するかもしれないので、B1 のセルに税率を記入しておく場合を考える。

この場合、D3 には、” =B3*C3*(1+B1) ” を入力すればいい。

ただ、このように式を入力すると、D3 の計算式を、D4,D5,D6 にコピーすると、セル D4 には =B4*C4*(1+B2) が入力されてしまい、B2 には単価という文字が記載されているため、正しい結果が求まらない。

こういった場合には、絶対参照を用いる。D3 に記入する式を

=B3*C3*(1+$B$2)

とし、この D3 の式を D4 にコピー＆ペーストすると、列記号、行番号の前に$がついた部分の式は、貼り付け場所に応じて変化しない。

このような、$B$2 といったセルの参照は、絶対参照と呼ぶ。これに対し、B2 といったセル参照は、貼り付け場所に応じて書き換えられるので、相対参照と呼ぶ。

絶対参照と相対参照が混ざった、$B2, B$2 といった書き方もある。
式の入力時に[F4ボタン]を押す度に、B2→$B$2→B$2→$B2→B2 と変化する

$B2 は、式をコピーすると列部分はBのまま、行部分は場所に合わせて変化する。

B$2 は、式をコピーすると列部分は場所に合わせて変化し、行部分は2のままとなる。

レポート課題(第5回)

Excel で、xを0〜180度まで変化させたときのsin(x),位相をyとした時のsin(x+y)の値の表を作り、グラフ機能で表示せよ。A列は角度・B列はsin(x)・C列はsin(x+y)の値とし、yの値は”C1″に保存されているものとする。

この時、計算式の入力をどのように行なったのか(相対参照や絶対参照をどのように使ったのか)説明を、グラフの下に入力欄を設け記入せよ。

なお、Excel の sin() 関数は、引数がラジアンで入力する必要があるので、計算式には注意せよ。

そして出来上がった Excel のファイルを、Teams のこちらのフォルダに提出せよ。

実数型(float / double)

実数型は、単精度実数(float型)と、倍精度実数(double型)があり、それぞれ32bit,64bitでデータを扱う。

指数表現は、大きい値や小さい値を表現する場合に使われ、物理などで1.2345×10^-4といった、仮数×基数^指数で表現する方法。数学や物理では基数に10を用いるが、コンピュータの世界では基数を2とすることが多い。

単精度型(float)では、符号1bit,指数部8bit,仮数部23bitで値を覚え、数値としては、以下の値を意味する。

符号✕ 1.仮数部 ✕ 2^{(指数数部-127)}

符号部は、正の値なら0, 負の値なら1 を用いる。

仮数部が23bitなので、有効桁(正しい桁の幅)は約7桁となる。

例えば、float型で扱える最大数は、以下のようになる。

0,1111,1111,111,1111,1111,1111,1111,1111 = 1.1111…×2¹²⁸ ≒ 2¹²⁹ ≒ 10³⁸

float 型は、計算精度が低いので 通常の数値計算のプログラミングではあまり使われることはない。一方で、ゲームなどの3次元座標計算などでは、精度は必要もないことから、GPU(グラフィックス専用のプロセッサ)では float 型を使うことも多い。また、最近の機械学習のプログラミングでは、神経の動きをまねた計算(ニューラルネットワークプログラミング)が行われるが、これも精度はあまり高くなくてもいいので float 型を使うことも多く、グラフィックス用の GPU で float 型で機械学習の計算を行うことも多い。

倍精度型(double)では、符号1bit,指数部11bit,仮数部52bitで値を覚え、数値としては、以下の意味を持つ。

符号✕ 1.仮数部 ✕ 2^{(指数部-1023)}

これらの実数で計算を行うときには、0.00000001011×2¹⁰といった値の時に、仮数部に0が並んだ状態を覚えると、計算の精度が低くなるので、1.01100000000×2²のように指数部の値を調整して小数点の位置を補正しながら行われる。

double型の場合、52bit=10進数16桁相当の有効桁、最大数で、1.1111…×2¹⁰²⁴≒10³⁰⁸

倍精度型を使えば、正しく計算できるようになるかもしれないが、実数型はただの加算でも仮数部の小数点の位置を合わせたりする処理が必要で、浮動小数点専用の計算機能を持っていないような、ワンチップコンピュータでは整数型にくらべると10倍以上遅い場合もある。

実数の注意点

C言語でプログラムを作成していて、簡単な数値計算のプログラムでも動かないと悩んだことはないだろうか？解らなくて友達のプログラムを真似したら動いたけど、なぜ自分のプログラムは動かなかったのか深く考えたことはあるだろうか？

単純な合計と平均

整数を入力し、最後に合計と平均を出力するプログラムを以下に示す。
しかし、C言語でこのプログラムを動かすと、10,10,20,-1 と入力すると、合計(sum)40,件数(cnt)3で、平均は13と表示され、13.33333 とはならない。

小数点以下も正しく表示するには、どうすればいいだろうか？
ただし、変数の型宣言を “double data,sum,cnt ;” に変更しないものとする。

// 入力値の合計と平均を求める。
#include <stdio.h>

int main() {
   int data ;
   int sum = 0 ;
   int cnt = 0 ;
   for(;;) {
      printf( "数字を入力せよ。-1で終了¥n" ) ;
      scanf( "%d" , &data ) ;
      if ( data < 0 )
         break ;
      cnt = cnt + 1 ;
      sum = sum + data ;
   }
   printf( "合計 %d¥n" , sum ) ;
   printf( "平均 %d¥n" , sum / cnt ) ;
}

C言語では、int型のsum / int型のcnt の計算は、int 型で計算を行う(小数点以下は切り捨てられる)。このため、割り算だけ実数で行いたい場合は、以下のように書かないといけない。

   printf( "平均 %lf¥n" , (double)sum / (double)cnt ) ;
   // (double)式 は、sum を一時的に実数型にするための型キャスト

まずは動く例

以下のプログラムは、見れば判るけど、th を 0度〜360度まで5度刻みで変化させながら、y = sin(th) の値を表示するプログラム。

// sin の値を出力
#include <stdio.h>
#include <math.h>

int main() {
    double th , y ;
    for( th = 0.0 ; th <= 360.0 ; th += 5.0 ) {
        y = sin( th / 180.0 * 3.1415926535 ) ;
        printf( "%lf %lf¥n" , th , y ) ;
    }
    return 0 ;
}

動かないプログラム

では、以下のプログラムはどうだろうか？

// case-1 ---- プログラムが止まらない
#define PI 3.1415926535
int main() {
    double th , y ;
    // 0〜πまで100分割でsinを求める
    for( th = 0.0 ; th != PI ; th += PI / 100.0 ) {
        y = sin( th ) ;
        printf( "%lf %lf¥n" , th , y ) ;
    }
    return 0 ;
}

// case-2 ---- y の値が全てゼロ
int main() {
    int    th ;
    double y ;
    for( th = 0 ; th <= 360 ; th += 5 ) {
        y = sin( th / 180 * 3.1415926535 ) ;
        printf( "%d %lf¥n" , th , y ) ;
    }
    return 0 ;
}

どちらも、何気なく読んでいると、動かない理由が判らないと思う。そして、元のプログラムと見比べながら、case-1 では、「!=」を「<=」に書き換えたり、case-2 では、「int th ;」を「double th ;」に書き換えたら動き出す。

では何が悪かったのか…
回答編

数値と誤差

コンピュータで計算すると、計算結果はすべて正しいと勘違いをしている人も多い。ここで、改めて誤差について考える。特に、計器で測定した値であれば、測定値自体に誤差が含まれている。

こういった誤差が含まれる数字を扱う場合注意が必要である。例えば実験値を手書きで記録する場合、12.3 と 12.300 では意味が異なる。測定値であやふやな桁を丸めたのであれば、前者は 12.2500〜12.3499… の間の値であり有効数字3桁である。後者は、12.2995〜12.300499… の間の値であり、有効数字5桁である。このため、誤差が含まれる数字の加算・減算・乗算・除算では注意が必要である。

加減乗除算の場合

加減算であれば小数点の位置を揃え、誤差が含まれる桁は有効桁に含めてはいけない。

上記の計算では、0.4567の0.0567の部分は意味がないデータとなる。(情報落ち)

乗除算であれば、有効桁の少ない値と有効桁の多い値の計算では、有効桁の少ない方の誤差の影響が計算結果に出てくるため、通常は、有効桁5桁と2桁の計算であれば、乗除算結果は少ない2桁で書くべきである。

桁落ち

有効桁が大きい結果でも、減算が含まれる場合は注意が必要である。

例えば、以下のような計算では、有効桁7桁どうしでも、計算結果の有効桁は3桁となる。

このような現象は、桁落ちと呼ばれる。

演習問題(4回目)

こちらのフォルダに示す、Excel の表で、有効桁を考えてもらうための演習問題(ランダムに値が作られます)を有効数字を考えながら計算し、答えをレポートにまとめてください。例を以下に示す。

レポートは、こちらのひな型をベースに作成し(手書きノートをキャプチャした資料でもOKです)、同じフォルダに提出してください。

学際科目の情報制御基礎において、プログラムの基本としてフローチャートと基本的な処理を説明し、数値型の注意点を説明。

フローチャートの基本

プログラムの処理の順序を理解するには、初心者であればフローチャート(流れ図)を使う。

処理の1つ1つを箱で表し、流れを箱の間の矢印で示すことでアルゴリズム(プログラムの考え方)や処理順序を表現する。処理単位の箱は、命令の種類によって箱の書き方が決まっている。

上図右側のフローチャートの例では、以下の説明のように実行され、0,1,2,…,9 が表示され、最終的に変数 i が10以上になり処理を停止する。

(1) 変数 i に 0 を保存
(2) 変数 i は10未満なら(3)、10以上なら終了
(3) 変数 i を表示
(4) i = i + 1 右辺の計算結果を、左辺に代入。iが0から1に変化
(5) 処理(2)から繰り返し。

上記のようなプログラムは、C言語であれば以下のようになる。

#include <stdio.h>                 | 入出力関数を使うための準備

int main() {                       | 最初に main() という関数が呼び出される。
   int i ;                         | 変数 i の入れ物を準備
   for( i = 0 ; i < 10 ; i++ ) {   | 最初に i = 0 を行い、i < 10 の条件を満たす間繰り返し、
                                   |       繰り返しの度に i を1つ増やす
      printf( "%d\n" , i ) ;       |    i の値を表示
   }
   return 0 ;                      | 正しく終わったら0を返す。
}

• Paiza.ioで動作確認1

練習問題1

以下のフローチャートの処理A,処理B,処理C,処理Dの実行結果を答えよ。

• 電気電子工学科,電子情報工学科の学生は、出席番号が偶数は処理C,奇数は処理Dについて回答せよ。
• それ以外の学科の学生は、出席番号が偶数は処理A,奇数は処理Bの結果について回答せよ。
• このプログラムではどういった意味の値を求めようとしているのか答えよ。

情報量の単位

データを覚える最小単位は、0と1の2通りで表される1bit (ビット)と呼ぶ。単位として書く場合には b で表す。さらに、その1bitを8個組み合わせると、256通りの情報を保存できる。256通りあれば一般的な英数字などの記号を1文字保存する入れ物として便利であり、この単位を 1byte (バイト) と呼ぶ。単位として書く場合には B で表す。

通信関係の人は8bit=1byteを1オクテットと呼ぶことも多い。日本語を表現するには、かなや漢字を使うため16bit = 2byte = 1word(ワード) で表現することが多い。(ただしワードは32bitを意味することもあるので要注意, double word=32bit, quad word=64bit という呼び方もある。)

物理では単位が大きくなると、10³=kキロ,10⁶=Mメガ,10⁹=Gギガ,10¹²=Tテラ を使うが、コンピュータの世界では、10³≒2¹⁰=1024 なので、1kB(キロバイト)というと1024Bを意味することが多い。明確に区別する時は、1024B(バイト)=1KiB(キビバイト), 1024²B=1MiB_{(メビバイト)}, 1024³B=1GiB_{(ギビバイト)} などと記載する。

2進数,8進数,16進数

プログラムの中で整数値を覚える場合は、2進数の複数桁で記憶する。例えば、2進数3桁(3bit)であれば、000, 001, 010, 011, 100, 101, 110, 111 で、10進数であれば 0～7 の8通りの値が扱える。(8進数)

2進数4桁(4bit)であれば、0000, 0001, 0010, 0011, 0100, 0101, 0110, 0111, 1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111 の16通りを表現できる(16進数)。これを1桁で表現するために、0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F を使って表現する。

例  8進数    16進数
    0123    0x123     ※C言語では、
  +  026   + 0xEA      8進数を表す場合、先頭に0をつけて表す。
 -------- --------     16進数を表す場合、先頭に0xをつけて表す。
    0151    0x20D      0x3+0xA = 0xD
                       0x2+0xE = 2+14 = 16 = 0x0 + 桁上がり
                       0x1+桁上がり = 0x2

整数型と扱える値の範囲

コンピュータの開発が進むにつれ計算の単位となるデータ幅は、8bit, 16bit, 32bit, 64bit と増えていった。整数型データには、正の値しか覚えられない符号無し整数と、2の補数で負の数を覚える符号付き整数に分けられる。

プログラムを作るためのC言語では、それぞれ 8bitの文字型(char)、16bitの short int型、32bitの int 型、64bitの long int 型(^※C言語では long int で宣言すると32bitの環境も多いので要注意)があり、それぞれに符号なし整数(unsigned), 符号あり整数(signed: C言語の宣言では書かない)がある。

符号付きのデータは、負の数は2の補数によって保存され、2進数の最上位bit(符号ビット)は負の数であれば1、正の数であれば0となる。

整数型で扱える数

(例) 符号なしの1byte(8bit)であれば、いくつの数を扱えるであろうか？

符号なしの N bit の整数であれば2^N通りの値を表現でき、0～(2^N-1) までの値が扱える。

符号付きの N bit の整数であれば、2の補数表現では最上位ビットが符号を表すために使われる。

正の数なら残りの(N-1)bitで扱うため 0〜2^N-1-1を表現できる。負の数は2^N-1通りを表現できるので、N bit の符号つき整数は、-2^N-1 〜0〜 2^N-1-1の範囲の値を覚えられる。

2の べき乗 の概算

プログラムを作る場合、2のべき乗がだいたいどの位の値なのか知りたいことが多い。この場合の計算方法として、2つの方法を紹介する。

• 2³² = 2² × (2¹⁰)³ = 4 × 1024³ ≒ 4,000,000,000
• 2³²をN桁10進数で表すとすれば なので、両辺のlog₁₀を求める。
  
    (つまり、bit数に0.3をかければ10進数の桁数が求まる。)

数値の範囲の問題で動かないプログラム

この話だけだと、扱える数値の上限について実感がわかないかもしれないので、以下のプログラムをみてみよう。(C言語の詳細は説明していないので、問題点がイメージできるだけでいい。)

組み込み系のコンピュータでは、int 型で宣言される変数でも、16bitの場合もある。以下のプログラムは期待した値が計算できない例である。以下の例では、16bit int型として short int で示す。

// ✳️コード1
#include <stdio.h>
#include <math.h>

int main() { // 原点から座標(x,y)までの距離を求める
   short int x  = 200 ;
   short int y  = 200 ;
   short int r2 = x*x + y*y ;  // (x,y)までの距離の2乗
   short int r  = sqrt( r2 ) ; // sqrt() 平方根
   printf( "%d\n" , r ) ;      // 何が求まるか?
   return 0 ;                  // (例) 200√2 = 282ではなく、120が表示された。
}

• Paiza.ioで動作確認2

コンピュータで一定時間かかる処理を考えてみる。

// コード2.1
// 1 [msec] かかる処理が以下のように書いてあったとする。
short int i ;
for( i = 0 ; i < 1000 ; i++ )
   NOP() ; // NOP() = 約1μsecかかる処理とする。

// ✳️コード2.2
// 0.5 [sec]かかる処理を以下のようにかいた。
short int i ;
for( i = 0 ; i < 500000 ; i++ )
   NOP() ;
// でもこの処理は16bitコンピュータでは、1μsecもかからずに終了する。なぜか？

上記の例は、性能の低い16bit コンピュータの問題で、最近は32bit 整数型のコンピュータが普通だし、特に問題ないと思うかもしれない。でも、32bit でも扱える数の範囲で動かなくなるプログラムを示す。

OS(unix) では、1970年1月1日からの経過秒数で時間(unix時間)を扱う。ここで、以下のプログラムは、正しい値が計算できなかった有名な例である。(2004年1月11日にATMが動かなくなるトラブルの原因だった)

// ✳️コード3.1
int t1 = 1554735600 ; // 2019年4月09日,00:00
int t2 = 1555340400 ; // 2019年4月16日,00:00

// この2日の真ん中の日を求める。
//  t1       |        t2
//  |--------+--------|
//  |      t_mid      |
//  以下のプログラムは、正しい 2019年4月12日12:00 が求まらない。なぜか？
int t_mid = (t1 + t2) / 2;  // (例) 1951年03月25日 08:45 になった。

// コード3.2
//  以下のプログラムは正しく動く。　time_t 型(時間処理用の64bit整数)を使えば問題ない。
time_t t1 = 1554735600 ; // 2019年4月09日,00:00
time_t t2 = 1555340400 ; // 2019年4月16日,00:00

// time_t型が32bitであったとしても桁溢れない式
time_t t_mid = t1 + (t2 - t1) / 2 ;

• Paiza.ioで動作確認3

練習問題2

以下の整数の範囲を具体的な値で答えよ。
出席番号・自分の誕生日(の日にち)に合わせて該当する2問について答えること。

1. 7bitの符号なし整数で扱える数値の範囲 (出席番号が偶数)
2. 12bitの符号あり整数で扱える数値の範囲 (出席番号が奇数)
3. 20bitの符号なし整数で扱える数値の範囲 (誕生日の日づけが偶数)
4. 24bitの符号あり整数で扱える数値の範囲 (誕生日の日づけが奇数)

練習問題3

先に示した数値の範囲が原因で動かないプログラム(コード1,コード2.2,コード3.1)の中から1つを選んで、計算結果が正しく求まらない原因を、具体的な値を示しながら説明せよ。

練習問題1,練習問題2,練習問題3について、レポートとして提出せよ。

Teamsのこちらの共有フォルダに、回答記入用のひな型がおいてあるので、この書式を参考に各自レポートにまとめ、同フォルダに提出してください。

基本的なガイダンス

情報構造論のシラバスを、ここに示す。プログラムを作成する上で、どのような考え方で作れば処理速度が速いのかを議論する。基本的に、4回のテストのたびに、レポート課題を実施する。各テスト毎の評価は、テスト素点と、「テスト素点×60%+レポート評価×40%」の良い方とする。テストに自信のない人は、レポート課題をきちんと提出すること。

• 情報構造論の講義録は、すべてこの BLOG に残します。
• 過去のテスト問題は、こちらにすべて残ってます。

プログラムを評価する3つのポイント

まずは以下を読む前に、質問。

• あなたが”良い”プログラムを作るために何を考えて作りますか？ ※1
  • ここまでの段階で3つの要点を考えメモしてください。

具体的な言葉で要点を考えると、いろいろなものがでてくるだろうが、端的なポイントにまとめると、次の3つに分類できるはずである。

• プログラムの速度
• プログラムのわかり易さ
• メモリの使用量

プログラムを作る場合、この３要素がトレードオフの関係にある。プログラムの速度を優先すると、プログラムが分かり難くなったり、メモリを大量浪費するものだったりする。

メモリの使用量の影響

メモリを大量に使用すると、どういった影響がでるのか？ OSの機能を知らないと、メモリ(主記憶)を使い果たしたら、プログラムが動かないと思うかもしれないけど、最近のOSは仮想メモリ機能があるため、主記憶がメモリが足りなければ待機状態のプロセスのメモリを補助記憶に保存することで、プログラムを動かすことはできる。(仮想記憶)

しかし、プロセスが切り替わる度に、補助記憶への読み書きが発生するため、処理性能は低下する。(スワッピング)

int 型のメモリ使用量は？

int 型は、プログラムで扱う一般的な整数を扱うのに十分なデータ型。

32bit の0/1情報の組み合わせで、2³²通りの情報が表現でき、負の数も扱いたいことから2の補数表現を用いることで、-2³¹～0～2³¹-1 の範囲を扱うことができる。2³¹ = 2×2¹⁰×2¹⁰×2¹⁰ ≒ 2×1000³

32bit = 4byte

ソフトウェアとアルゴリズムとプログラム

用語として、ソフトウェア、アルゴリズム、プログラムという表現があるが、この違いは何か？

• アルゴリズム – 計算手順の考え方。
• プログラム – アルゴリズムを特定のプログラム言語によって記述したもの。
• ソフトウェア – プログラムと、その処理に必要なデータ。
  (日本語を変換するプログラムは、日本語の辞書データが無いと動かない/役に立たない)
• パラダイム – プログラムをどう表現すると分かりやすいか？

トレードオフ関係をプログラムで確認

例えば、配列の中から、目的データを探すプログラムの場合、最も簡単なプログラムは以下の方法であろう。

// ((case-1))
// 単純サーチ O(N)
#define SIZE 1024
int main() {
   int a[ SIZE ] = {
      52 , 14 , 82 , 62 , 15
   } ; // 配列
   int size =  5 ;      // 実際のデータ数(Nとする)
   int key  = 62 ;      // 探すデータ
   for( int i = 0 ; i < size ; i++ ) // 先頭から1つづつ比較、シンプル
      if ( a[i] == key ) {
         printf( "Find %d¥n" , key ) ;
         break ;
      }
   }
}

import java.util.*;

public class Main {
   public static void main(String[] args) throws Exception {
      int a[] = {
         52 , 14 , 82 , 62 , 15
      } ;
      int key = 62 ;
      for( int i = 0 ; i < a.length ; i++ ) {
          if ( a[i] == key ) {
             System.out.println( "Find " + key ) ;
             break ;
          }
      }
   }
}

// import java.util.Arrays;  // こういった正当なJavaのプログラムでは、
// public class Main {       // データ件数が大きくなった時の挙動がわからない
//    public static void main( String[] args ) {
//       Integer a[] = {
//          52 , 14 , 82 , 62 , 15    // Integer型 int 型は何が違うの？
//       } ;
//       if ( Arrays.asList( a ).contains( 62 ) ) {
//          System.out.println("配列内に値が存在しています。");
//       }
//    }
// }

しかし、もっと早く探したいのであれば、2分探索法を用いるだろう。でも、このプログラムは、case-1 のプログラムよりは分かり難い。(速度⇔わかり易さ)

// ((case-2))
// 2分探索法 O(log N)
// 速いけど、プログラムは分かりにくく(複雑に)なった
int main() {
   int a[] = {
      14 , 15 , 52 , 62 , 82  // データはあらかじめ昇順に並べておく
   } ; 
   int L=0 , R= 5 ; 
   while( L != R ) {
      int M = (L + R) / 2 ;
      if ( a[M] == key )
         break ;
      else if ( a[M] < key )
         L = M + 1 ;
      else
         R = M ;
   }
}

import java.util.*;

public class Main {
   public static void main(String[] args) throws Exception {
      int a[] = {
         14 , 15 , 52 , 62 , 82  // データはあらかじめ昇順に並べておく
      } ;
      int key = 62 ;
      int L = 0 ;
      int R = a.length ;
      while( L != R ) {
         int M = (L + R) / 2 ;
         if ( a[M] == key )
            break ;
         else if ( a[M] < key )
            L = M + 1 ;
         else
            R = M ;
      }
   }
}

でももっと速いプログラムとしたければ、大量のメモリを使えば一発でデータを探せる。(速度⇔メモリ使用量)

// ((case-3))
// 添字がデータ O(1)
// 探すデータが電話番号 272925 のような 6 桁ならば、データを以下の様に保存すればいい。
int a[ 1000000 ] ;
a[ 272925 ] = 272925 ;
：
// データを探したければ a[ 電話番号 ] で探せばいい
printf( "%d\n" , a[ 621111 ] ) ;
// 処理速度はクソ速いけど、メモリは大量消費

良いプログラムを作るとは

プログラムを作る時には、メモリが大量に使えるのなら、速いものを使えばいい。だけど実際には、そのシステムには限られた予算があるだろう。

実際には、限られた予算からメモリやCPUが決まり、その会社の人員やら経験やらでプログラム開発に使える時間がきまる。プログラムをデザインするとは、限られた条件の中で、適切な速度のコンピュータ、適切な量のメモリでコンピュータを用意し、限られた納期の中でシステムを完成させることである。

皆さんも、ゲームを買った時、処理速度が遅くてキャラクターがカクカク動いたら幻滅するでしょ？ゲームがバグですぐに変な動きしたらキレるでしょ！(参考) 発売日の予定どおりに買えなかったらさみしいでしょ!!プログラムがでかすぎてローディングに時間がかかったら、寝ちゃうでしょ!!!