ようへいの日々精進XP

よかろうもん

アルゴリズムとプログラミング 「第 4 章 ループの応用」の予習とまとめ

これは

放送大学教養学部の「アルゴリズムとプログラミング」という授業で使われる「アルゴリズムとプログラミング」という教材書籍を自分なりにまとめたものです.

4 章. ループの応用

環境

本メモで利用する環境は以下の通り.

root@0be431eebb77:/work# cat /etc/debian_version
9.5

root@0be431eebb77:/work# gcc -v
Using built-in specs.
COLLECT_GCC=gcc
COLLECT_LTO_WRAPPER=/usr/lib/gcc/x86_64-linux-gnu/6/lto-wrapper
Target: x86_64-linux-gnu
Configured with: ../src/configure -v --with-pkgversion='Debian 6.3.0-18+deb9u1' --with-bugurl=file:///usr/share/doc/gcc-6/README.Bugs --enable-languages=c,ada,c++,java,go,d,fortran,objc,obj-c++ --prefix=/usr --program-suffix=-6 --program-prefix=x86_64-linux-gnu- --enable-shared --enable-linker-build-id --libexecdir=/usr/lib --without-included-gettext --enable-threads=posix --libdir=/usr/lib --enable-nls --with-sysroot=/ --enable-clocale=gnu --enable-libstdcxx-debug --enable-libstdcxx-time=yes --with-default-libstdcxx-abi=new --enable-gnu-unique-object --disable-vtable-verify --enable-libmpx --enable-plugin --enable-default-pie --with-system-zlib --disable-browser-plugin --enable-java-awt=gtk --enable-gtk-cairo --with-java-home=/usr/lib/jvm/java-1.5.0-gcj-6-amd64/jre --enable-java-home --with-jvm-root-dir=/usr/lib/jvm/java-1.5.0-gcj-6-amd64 --with-jvm-jar-dir=/usr/lib/jvm-exports/java-1.5.0-gcj-6-amd64 --with-arch-directory=amd64 --with-ecj-jar=/usr/share/java/eclipse-ecj.jar --with-target-system-zlib --enable-objc-gc=auto --enable-multiarch --with-arch-32=i686 --with-abi=m64 --with-multilib-list=m32,m64,mx32 --enable-multilib --with-tune=generic --enable-checking=release --build=x86_64-linux-gnu --host=x86_64-linux-gnu --target=x86_64-linux-gnu
Thread model: posix
gcc version 6.3.0 20170516 (Debian 6.3.0-18+deb9u1)

1. モンテカルロ法 (Monte Carlo method)

  • 乱数を利用した確率的な数値計算シュミレーションによって問題の近似解等を求める方法
  • モンテカルロ法を用いた有名なプログラムの例として円周率 π を求めるものがある

半径  r が 1 の円とそれを取り囲む変の長さが 2 の正方形がある. 4 分割された円の面積を  A_{circle} とし, 1 x 1 の正方形の面積を  A_{square} とすると, 点が斜面の部分に打たれる確率  p は以下の式で表される.

{ \displaystyle
p = \frac{A_{circle}}{A_{square}} = \frac{\frac{1}{4}\pi r^2}{r^2} = \frac{\pi}{4}
}

この式を変更し  \pi を求めると以下のような式となる.

{ \displaystyle
\pi = 4p = 4\times\frac{A_{circle}}{A_{square}}
}

 p はランダムに打たれた点の数の比率  (A_{circle}\div A_{square}) を計算することによって求めることが出来る.

2. モンテカルロ法による円周率計算のプログラム

点の座標値  (x, y) を乱数として発生させ,  A_{circle} の部分に打たれる点の個数と  A_{square} の部分に打たれる点の個数を求めれば円周率を求めることが出来る.

以下のコードは, モンテカルロ法により円周率  \pi を求めることが出来る.

/* code: ex4-1.c */
#include <stdio.h>
#include <stdlib.h>

#define POINTS 1000

int main()
{
  int i, count, points;
  double x, y, q;
  double pi;
  
  points = POINTS;
  count = 0;
  
  for (i = 0; i < points; i++) {
    x = (double) rand () / ((double) RAND_MAX + 1.0);
    y = (double) rand () / ((double) RAND_MAX + 1.0);
    q = (x * y) + (x * y);
    
    if (q <= 1.00)
      count++;
  }
  
  pi = (double) count / (double) points *(double) 4.00;
  printf ("circle: %d\t", count);
  printf ("square: %d\t", points);
  printf ("PI: %f\n", pi);
  
  return 0;
}
  • 0 以上 RAND_MAX 以下の数値を発生させる rand 関数 (0  \leq rand()  \leq RAND_MAX) を式に代入し, 0 以上 1 未満になるような乱数を発生させている
  • 乱数は 1000 個の点の座標値  (x, y) として使われ,  A_{circle} の部分に打たれる点なのか,  A_{square} の部分に打たれる点なのか判定し, その合計数を求めている

以下の実行例では,  A_{circle} に打たれる点が 829 個,  A_{square} の部分に打たれる点が 1000 個となり, 円周率が 3.316000 と計算される.

root@0be431eebb77:/work# gcc ex4-1.c -o ex4-1
root@0be431eebb77:/work# ./ex4-1
circle: 829     square: 1000    PI: 3.316000

理論的には, シュミレーションに用いる点の個数が増加すれば, 増加するほど精度の高い円周率を得ることが出来る.

以下のコードは, シュミレーションに利用する点の個数を変化させながら円周率を求めるプログラムで for ループを利用して点の数を 10 個から 10 倍ずつ増加させて最終的に 10 億個になるシュミレーションである.

/* code: ex4-2.c */
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int main()
{
  int i, j, count, points;
  double x, y, q;
  double pi;

  for (j = 1; j < 10; j++) {
    points = 1;
    count = 0;
    points = points * pow (10, j);
    for (i = 0; i < points; i++) {
      x = (double) rand () / ((double) RAND_MAX + 1.0);
      y = (double) rand () / ((double) RAND_MAX + 1.0);
      q = (x * y) + (x * y);
      if (q <= 1.00)
        count++;
    }
    pi = (double) count / (double) points *(double) 4.00;
    printf ("circle: %d\t", count);
    printf ("square: %d\t", points);
    printf ("PI: %f (%+f)\n", pi, (pi - M_PI));
  }

  return 0;
}

これをコンパイルして実行すると以下のように出力される. M_PI は, math.h に定義されている円周率の値が定義されており, シュミレーションの値の結果との差分を出力している.

root@0be431eebb77:/work# gcc ex4-2.c -lm -o ex4-2 -g3
root@0be431eebb77:/work# ./ex4-2
circle: 8       square: 10      PI: 3.200000 (+0.058407)
circle: 84      square: 100     PI: 3.360000 (+0.218407)
circle: 835     square: 1000    PI: 3.340000 (+0.198407)
circle: 8533    square: 10000   PI: 3.413200 (+0.271607)
circle: 84543   square: 100000  PI: 3.381720 (+0.240127)
circle: 846860  square: 1000000 PI: 3.387440 (+0.245847)
circle: 8464359 square: 10000000        PI: 3.385744 (+0.244151)
circle: 84655640        square: 100000000       PI: 3.386226 (+0.244633)
circle: 846560173       square: 1000000000      PI: 3.386241 (+0.244648)

教科書の出力だと, 点の数が増えるに従ってより正確な円周率に近づく傾向が見られているが, 手元の環境では点の数が増えても正確な円周率に近づくことはなかった...のは何故だろう... (システムによって乱数生成アルゴリズムが異なるので, 計算結果が異なると記述されている)

おそらく, 上記の疑問に対する答えの一つだと思うが, 上記のコードは rand 関数を利用しているが, 乱数の質はコンパイラの実装に依存している為, 非常に古いコンパイラによっては乱数の質が良くない場合がある為, drand48 (線形合同アルゴリズムと 48 ビット整数演算に基づく) や random 関数 (非線形加法フィードバックに基づく), その他の高品質な疑似乱数生成器 (PRNGs) の利用が望ましい とのこと.

3. 計算量

  • 計算量 (computational complexity) とはアルゴリズムの動作に必要な資源の量を評価するもの
  • 時間計算量 (time complexity) と空間計算量 (space complexity) があり, 通常は単に計算量と言えば, 時間計算量のことを指す
  • 時間計算量では, 計算に必要なステップ数を評価する
  • 評価では複数のアルゴリズムがあり, その評価を行う場合, 計算時間はコンピュータの処理能力によって異なる為, 入力データの大きさに対する基本演算のステップ回数で比較する必要がある
  • 空間計算量は, 領域計算量とも呼ばれることがあり, 計算に必要とされるメモリ量を評価する
  • アルゴリズムの速度比較方法 = ビッグ・オー記法 (big O notation)
  • ビッグ・オー記法によって, データの数と実行時間の関係を表現することが出来る

例えば, 配列の線形探索においては,  n 個のデータに対して, 計算量  O(n) の時間が掛かる. また, 配列の二分探索の場合は計算量  O(\log n) となる.

以下は様々な関数における増加率.

  • 対数時間 (logarithmic time) ...  \log_{2}n,  n\log_{2}n
  • 多項式時間 (polynomial time) ...  n^2,  n^3
  • 指数関数時間 (exponential time) ...  2^n,  n^n,  n!

演習問題

問 4.1

モンテカルロ法について簡単に説明しなさい.

問 4.2

以下のビッグ・オー記法のを関数増加率の大きさで小さい順に並べなさい.  c 定数,  ! は階乗を表し,  n は非常に大きな値とする.

 O(logn),  O(n),  O(nlogn),  O(c), [tex: O(nc)],  O(n!)

以下, 解答より引用.

 O(c) <  O(logn) <  O(n) <  O(nlogn) < [tex: O(nc)] <  O(n!)

問 4.3

C 言語の標準ライブラリ stdlib.h に定義されている rand 関数と srand 関数について調べなさい.

以下, 解答より引用.

関数 詳細
rand 疑似乱数を発生させる
srand rand 関数で返される疑似乱数の乱数種 (seed) を設定する, srand 関数にて同一の乱数種の値で呼び出した場合, rand 関数から同じ疑似乱数列が生成される

以下, rand 関数と srand 関数を用いて疑似乱数を生成するサンプル. C言語関数辞典 - rand より引用させて頂いた. 有難うございます.

/* code: rand-sample.c */
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

/* main */
int main(void) {
    int i, n;

    /* 乱数のシードを与える */
    srand((unsigned)time(NULL));

    for ( i = 0; i <= 9; i++ ) {
        /* 乱数を発生させる */
        n = rand();

        /* 表示 */
        printf("%2d回目 = %3d\n", i + 1, n);
    }
    return EXIT_SUCCESS;
}

これをコンパイルして実行する.

root@0be431eebb77:/work# gcc rand-sample.c -o rand-sample -g3
root@0be431eebb77:/work# ./rand-sample
 1回目 = 1471756858
 2回目 = 1381332833
 3回目 = 1717719774
 4回目 = 1863423450
 5回目 = 1715428247
 6回目 = 799290199
 7回目 = 1453794275
 8回目 = 1058746752
 9回目 = 2001340863
10回目 = 692996476

問 4.3

円周率を求めるアルゴリズムにはどのようなものがあるか調査しなさい.

これら以外に, 級数展開による方法, アレキメデスの方法 (正多角形による方法) 等がある. (解答より引用)

尚, 3月14日は円周率の日!ということで円周率を求めるプログラムを書こう! のコードを実際に試してみたが, 以下のように AGM 法の処理は爆速だった. 有難うございます.

# AGM 法
root@0be431eebb77:/work# time ./pi3
3.14057925052216857509
3.14159264621354283875
3.14159265358979400418
3.14159265358979400418
3.14159265358979400418

real    0m0.004s
user    0m0.000s
sys     0m0.000s

# モンテカルロ法
root@0be431eebb77:/work# time ./pi2
3.200000000
3.120000000
3.156000000
3.166800000
3.138880000
3.141920000
3.140898800
3.141709760
3.141604092

real    0m24.512s
user    0m24.460s
sys     0m0.000s
root@0be431eebb77:/work#

問 4.4

円周率計算を利用して CPU 演算速度を測るソフトウェアがある. 一般的なコンピュータで約 100 万桁の円周率を求めるのにかかる時間を調査しなさい.

EC2 (CentOS 7, t2.micro) で実施した場合, Super Pi では以下のように Segmentation fault で計測出来なった.

$ ./super_pi
./super_pi: 1 行:  1538 Segmentation fault      ./pi $1

TachusPI を利用して計測したところ, 以下のような結果となった.

$ ./tpi -o pi.txt 1000000
Using 790MiB of RAM
Computation to 1000000 digits, formula=Chudnovsky
Output file=pi.txt, format=txt, binary result size=415kB
Binary Splitting
Depth=17
  mem   max  disk   max operation                       compl lv
17.3M 17.3M     0     0 completed                      100.0%  0
  time = 0.352 s
Compute P, Q
16.1M 17.3M     0     0 completed
  time = 0.004 s
Division
17.9M 17.9M     0     0 completed
  time = 0.034 s
Sqrt
17.3M 17.9M     0     0 completed
  time = 0.023 s
Final multiplication
20.0M 20.0M     0     0 completed
  time = 0.017 s
Total time (binary result) = 0.431 s
Base conversion
17.3M 20.0M     0     0 completed
  time = 0.067 s
Total time (base 10 result) = 0.498 s
Writing result to 'pi.txt'

以上

  • アルゴリズムの勉強っぽくなってきたな...ついていけるかな...でも, 面白い章だった
  • Super Pi が EC2 でダウンロード出来なかったり, Segmentation fault したりするのは辛かった

2018 年 10 月 23 日 (火)

ジョギング

  • 山王公園往復
  • 懸垂 5 回, いい感じで 5 回イケるようになった

日課

  • (腕立て x 50 + 腹筋 x 50) x 3

体調

イマイチ. 福岡マラソンまでに整えなければ...

今日のトゥウィート

2018 年 10 月 22 日 (月)

ジョギング

  • 山王公園往復
  • 懸垂 5 回

日課

  • (腕立て x 50 + 腹筋 x 50) x 3

今日のトゥウィート

こんなアイデア, いったい誰が考えるんだろう, 面白い.

2018 年 10 月 21 日 (日)

ジョギング

  • 鴨池運動公園周回コースを 40 分弱
  • 鹿児島県の中学校陸上大会をやっていた, なんか懐かしい気分になった

日課

  • おやすみ

枕崎

ノリばあちゃん (95) に会いに行った.

ノリばあちゃん (95) と。#時間よ止まれ

耳が遠くなっていて, ホワイトボードで筆談しながらおしゃべりしたけど, 手も足も細くなって, 自力で歩行することが出来ないさまを見ていると, ノリばあちゃんと過ごした時間が色々と思い出されて泣けてきた.

枕崎からの帰りに父が気になっていたという川辺のラーメン屋さんで抹茶ラーメンを食べる.

緑茶ラーメン。

帰福

さて、どこに行くんでしょうか? #駅おじさん

エアポートおじさんをパクって SNS にアップしてみたけど, 思ったようなツッコミが無くて残念だった.

2018 年 10 月 20 日 (土)

ジョギング

  • おやすみ

    日課

  • おやすみ

JAWS-UG 鹿児島 Vol.8

  • せっかくの地元での久々の開催だったので参加させて頂いた, ついでに LT までした
  • JAWS-UG 福岡の藤崎さん, 青柳さんも参加するということで, ワイワイな感じで鹿児島まで新幹線で
  • 藤崎さんが市電から降りる時にタラップを踏み外して足を挫くというアクシデントがあった...その後, 終始, 足を引きずっていたけど...心配
  • 会場は現場サポートさんの小洒落たオフィスのセミナーフロアで 20 名程の方が参加されていた
  • 機械学習系のサービスの紹介から, JAWS-UG のトリビア, 新沼さんの受託案件における非機能要件を AWS でどのように満たしていくか的な話はとても勉強になった
  • 懇親会で新沼さんと久しぶりに話が出来て嬉しかった

雑にまとめてしまったけど, 懇親会まですごく楽しい勉強会だっと思う. 企画, 運営に携わった皆さんに感謝.

自宅にて

  • 懇親会を終えて, 自宅で手巻き寿司を肴に家族で一杯

jekyll で作ったペライチページを S3 と CloudFront, ACM, Route53 でサクッと公開出来たのが心地よかったのでメモ

tl;dr

oreno.tools というドメインを酔った勢いで取得して, いつかサイトを公開してみたいなと思っていたので, Jekyll という Ruby 製のサイトジェネレータでペライチページ (ペラ 1 枚)を生成して S3 + CloudFront and more で公開してみたのでメモります.

俺のツールズ

jekyll

Ruby 製のサイトジェネレータで, 導入も簡単だし, コンテンツ自体は Markdown で書くことが出来るので呼吸をする感じで記事を書くことが出来ます.

Jekyll • シンプルで、ブログのような、静的サイト

いい感じのテーマも用意されていて, 記事を書く時間よりもテーマを選ぶ時間のほうが長くなってしまいました.

静的サイトを公開する為の準備

鉄板

Amazon S3 + CloudFront は鉄板だと思います.

ドメイン

可能な限り Route53 で運用することを検討しましょう.

aws.amazon.com

Alias レコードで Zone Apex の指定も可能ですし, 後述の ACM によるサーバー証明書発行の際に DNS 認証を行えるので便利だと思います. Route53 で Hosted Zone を作成し, 払い出されたネームサーバーを某レジストラの管理画面にて登録しました.

サーバー証明書

Amazon Certificate Manager (以後, ACM と記述します) を利用します.

aws.amazon.com

CloudFront と ELB にのみ適用可能な証明書ですが, 今回ようなペライチサイトには十分だと思っています. 証明書を発行してもらうにあたり, メール認証かドメイン認証を行う必要がありますが, Route53 でドメインを管理しているとシームレスに連携 (認証用の CNAME レコードを対象 Hosted zone に挿入してくれます) してくれるので楽ちんです.

S3 + CloudFront

S3 バケットは公開したいドメイン名で作成 (バケットは必ずしもドメイン名で作成する必要はありません) し, CloudFront のオリジンにそのバケットを指定します. 基本的にはこれだけ. サーバー証明書ACM で発行した証明書を指定します.

aws.amazon.com

ただ, OAI (Origin Access Identity) だけは有効にしておきたいところです.

docs.aws.amazon.com

尚, 構築してすぐに対象の URL にアクセスすると HTTP ステータスコード 307 が返ってきてしまいますが, これは少し時間を置くと解消しますのでお茶でも飲んで待ちましょう. 以下, 参考にさせて頂きました. ありがとうございます.

stackoverflow.com

デプロイ

デプロイと言うと大袈裟な感じですが, S3 バケットに Jekyll が書き出した HTML や CSS などのファイルをアップロードします. これは, 以下のようなシェルスクリプトを用意しました.

bundle exec jekyll build
aws s3 sync ./_site/ s3://oreno.tools/ \
   --exclude "jekyll-cayman-theme.gemspec" \
   --exclude "README.md" \
   --exclude "deploy.sh"

詳しく書かれているドキュメントは確認出来ていませんが, ${project}/_site/ 以下のファイル群が実際にアクセスされるコンテンツになるようですので, これらのコンテンツを何らかの方法 (今回は AWS CLI を利用) でアップロードします.

以上

基盤は本当に一瞬と言っていいほど短時間で堅牢なものを準備することが出来ました. 後はそこに載せるコンテンツ次第だと思いますーε≡≡ヘ( ´Д`)ノ

infrataster-plugin-ftp を作ってリリースしました

tl;dr

前回, rspec-ftp を少し触ってみました. rspec に乗っかることで, FTP ユーザーの振る舞いをテスト出来るようにしてみたつもりです.

inokara.hateblo.jp

せっかくなので, infrataster のプラグインも作ってみようということで, fukuoka.rb #110 でもくもくしてみました.

そして, インテグレーションテスト的なものを追加して gem 化してリリースしてみました.

infrataster-plugin-ftp | RubyGems.org | your community gem host

よろしければご利用頂きまして, フィードバック等を頂けると幸いですmm

詳細は

READMEリポジトリ内の spec ディレクトリ以下を参考にして頂くとして, テストコードは以下のように書くことを想定しています.

require 'spec_helper'

describe server(:ftp_server) do
  describe ftp('welcome') do
    it 'check accessible' do
      expect(result.chomp).to eq('230 Login successful.')
    end
  end

  describe ftp('pwd') do
    it 'check `chroot` enabled' do
      expect(result).to eq('/')
    end
  end

  describe ftp('mkdir test_dir') do
    it 'run `mkdir`' do
      expect(result).to include '/test_dir'
    end
  end

  describe ftp('ls') do
    it 'run ls' do
      expect(result).to include 'sample.txt'
    end
  end
end

spec_helper.rb には以下のように FTP サーバーへの接続情報を記述します.

Infrataster::Server.define(
  :ftp_server,
  '192.168.0.6',
  ftp: { user: 'ftpuser', pass: 'supersecret', passive: true },
)

FTP サーバーに対して送信する FTP コマンド (lspwd 等) の挙動をテストするような感じになります. これを実行すると...以下のような結果となります.

$ docker-compose exec rspec-ruby25 rspec

server 'ftp_server'
  ftp:
    check accessible
  ftp:
    check `chroot` enabled
  ftp:
    run `mkdir`
  ftp:
    run ls

Finished in 0.07892 seconds (files took 0.7531 seconds to load)
4 examples, 0 failures

想定するユースケース

自分は FTP サーバーにユーザーを追加した際に, 追加したユーザーがそもそもログイン出来るのか, ユーザーは chroot されているのかをテストしたい場合に利用したいと考えています. その他, 単純に FTP サーバーを構築した後の基本的な動作確認にも利用出来るのではと考えています.

2018 年に FTP を利用するシチュエーションがどれだけあるか判りませんが, FTP クライアントを使って目視で確認という若干アナログな作業を Rspec というフレームワークの上でコード化出来るという意味ではこのプラグインは多少なりとも有用なのではと考えています.

以上

現場からの報告でした!ε≡≡ヘ( ´Д`)ノ

2018 年 10 月 19 日 (金)

ジョギング

  • 山王公園往復
  • 懸垂 5 回, 調子良かった

日課

  • (腕立て x 50 + 腹筋 x 50) x 3

枝豆

  • 今年も兵庫に住んでいる直美おばさんから丹波の黒枝豆が届いた
  • 奥さんが頑張って全部茹でて冷凍保存
  • 茹でたてを食べたけど味が濃くてとても美味しかった

俺のツールズ

Jekyll と Amazon S3 + CloudFront 版に作り変えた.

俺のツールズ

静的サイトの公開は S3 + CloudFront + Route53 + ACM が最高なんではないかと思うくらい, あっという間に公開にこぎつけることが出来た. 一番時間が掛かったのは Jekyll のテーマ選定かな.

明日は

jawsug-kagoshima.doorkeeper.jp

に参加して LT をさせて頂く予定.

今日のトゥウィート

業務と趣味の狭間で作った CLI ツールがいい感じにフィットする作業を淡々と行っていた. 少しは業務に役立って嬉しかった.

2018 年 10 月 18 日 (木)

ジョギング

  • 探検を兼ねて近所をぐるっと 30 分くらい走ってみた
  • 懸垂 5 回
  • 朝の駅南界隈はとにかく人が多いということが判った

日課

  • おやすみ

JAWS-UG 福岡 もくもく会 #13

  • 最も参加者が多い会になったかなー
  • 土曜日の JAWS-UG 鹿児島勉強会で LT やる予定なのでその資料を作ったりした
  • 毎回だけどワイワイいろんな話したり作業したり...いい感じでもくもく出来ていると思う

アルゴリズムとプログラミング 「第 3 章 ループの仕組み」の予習とまとめ

これは

放送大学教養学部の「アルゴリズムとプログラミング」という授業で使われる「アルゴリズムとプログラミング」という教材書籍を自分なりにまとめたものです.

第 3 章では, C 言語のループ処理に関連して for 文や while 文の基本的な内容について触れられています. 課題で gdb を使って繰り返し処理をステップ実行してみました.

尚, 本まとめについては, 以下の Github リポジトリで管理しており, 加筆修正はリポジトリのみ行います.

github.com

1. for ループ

1.1 for 文の形式

for 文は, 初期化 (initialization), 条件文 (condition), 反復文 (counter 又は loop), 本文 (body statement) を記述する.

for ( 初期文; 条件文; 反復文 )
  本文;

以下, サンプル.

/* code: ex3-1.c */
#include <stdio.h>

int main()
{
  int i;
  for (i = 0; i < 10; i++)
    printf ("%d\n", i);

  return 0;
}
  • このプログラムは 0 から 0 までの数字を表示する
  • 初期文は i = 0i という変数の値に 0 が代入されて初期化される
  • 条件文では i < 10 という式があり, 変数 i が 10 より小さい値ならば, printf 関数によって標準出力に変数 i の値が表示される
  • 反復文では i++ という式があり, 変数に値が 1 が加算される
  • for 文で複数の命令を繰り返したい場合には波括弧 {} を利用したブロック文を用いる

上記のコードを実行してみる.

$ gcc ex3-1.c -o ex3-1
$ ./ex3-1
0
1
2
3
4
5
6
7
8
9

以下, % を利用したモジュロ演算のサンプル.

/* code: ex3-2.c */
#include <stdio.h>

int main()
{
  int i;
  for (i = 0; i < 10; i++) {
    printf ("%d", i);
    if (0 != (i % 2))
      printf (" :odd\n");
    else
      printf (" :even\n");
  }

  return 0;
}

上記のコードを実行してみる.

$ gcc ex3-2.c -o ex3-2
$ ./ex3-2

0 :even
1 :odd
2 :even
3 :odd
4 :even
5 :odd
6 :even
7 :odd
8 :even
9 :odd

1.2 for 文の入れ子型ループ

以下のコードは for 文の中にさらに別の for 文のループを含む例. このようなループは入れ子型ループ (nested loop) と呼ばれる.

/* code: ex3-3.c */
#include <stdio.h>

int main()
{
  int i, j;
  for (i = 1; i < 10; i++) {
    for (j = 1; j < 10; j++) {
      printf ("%02d ", i * j);
    }
    printf ("\n");
  }
  return 0;
}

上記のコードを実行してみる.

$ gcc ex3-3.c -o ex3-3
$ ./ex3-3
01 02 03 04 05 06 07 08 09
02 04 06 08 10 12 14 16 18
03 06 09 12 15 18 21 24 27
04 08 12 16 20 24 28 32 36
05 10 15 20 25 30 35 40 45
06 12 18 24 30 36 42 48 54
07 14 21 28 35 42 49 56 63
08 16 24 32 40 48 56 64 72
09 18 27 36 45 54 63 72 81

外側のループでは for 文により変数 i が 1 〜 9 まで増加する, 同様に内側のループでは for 文によって変数 j が 1 〜 9 まで増加する為, 上記の結果は九九表のような表示結果となる.

1.3 for 文の無限ループ

以下のコードは for 文を使った無限ループ (infinite loop) の例. 初期文, 条件文, 反復文に何も記述されていない (又は, 条件文が常に真となる条件) 為, 本文が無限に実行される.

/* code: ex3-4.c */
#include <stdio.h>

int main()
{
  int i;
   
  i = 0;
  for (;;) {
    printf ("%d ", i);
    i++;
  }
  return 0;
}

上記のコードを実行してみる. (今回からコンパイル環境は gcc version 6.3.0 20170516 (Debian 6.3.0-18+deb9u1) でやっていく.)

$ gcc ex3-4.c -o ex3-4 -g3
$ ./ex3-4
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17..... 一瞬で大変なことになる.

放っておいても, ループ内でメモリを消費するようなコードであれば, いずれエラーで停止する.

2. while 文

2.1 while 文の形式

while 文は以下のような形式となる.

while ( 条件文 )
  本文;

以下, コード例. 変数 i に初期値として 0 が代入される. while 文によって条件文 i < 10 が真の間は本文の printf 関数が実行され, 0 から 9 までの値が標準出力で表示される.

/* code: ex3-5.c */
#include <stdio.h>

int main()
{
  int i;

  i = 0;
  while (i < 10) {
    printf ("%d ", i++);
  }
  printf ("\n");
  return 0;
}

このコードをコンパイルして実行してみる.

$ gcc ex3-5.c -o ex3-5 -g3
$ ./ex3-5
0 1 2 3 4 5 6 7 8 9

C 言語の場合, 整数である変数 i の値は, 宣言した場所で自動的に 0 で初期化される為, i = 0; 自体は不要な処理に見えるが, 初期の Pascal 等のプラグラミング言語では 0 等での値での変数初期化保証していない場合もあるので, 変数を利用する前に初期化をすることが望ましいとされている.

コード ex3-5.c は以下のように書き換えることも出来る.

/* code: ex3-6.c */
#include <stdio.h>

int main()
{
  int i;

  i = 0;
  while (i < 10) {
    printf ("%d ", i);
    i++;
  }
  printf ("\n");
  return 0;
}

このコードをコンパイルして実行してみる.

$ gcc ex3-6.c -o ex3-6 -g3
$ ./ex3-6
0 1 2 3 4 5 6 7 8 9

2.2 do-while 文の形式

do-while 文の形式は以下の通り.

do
  本文;
while ( 条件文 );

while 文と異なるのは, 本文が先に実行され, その後に条件文が評価されることで, 本番が少なくとも 1 回は実行される必要があるプログラムを作成する時に便利.

以下, コード例.

/* code: ex3-7.c */
#include <stdio.h>

int main()
{
  int i;

  i = 0;
  do {
    printf ("%d ", i);
    i++;
  } while (i < 10);
  printf ("\n");
  
  return 0;
}

このコードをコンパイルして実行してみる.

$ gcc ex3-7.c -o ex3-7 -g3
$ ./ex3-7
0 1 2 3 4 5 6 7 8 9

2.3 while 文の入れ子ループ

for 文同様に while 文でも入れ子ループは書くことは出来る. 以下のコードは ex3-3.c を while 文で書き換えたもの.

/* code: ex3-8.c */
#include <stdio.h>

int main()
{
  int i, j;
  
  i = 1;
  while (i < 10) {
    j = 1;
    while (j < 10) {
      printf ("%02d ", i * j);
      j++;
    }
    printf ("\n");
    i++;
  }
  return 0;
}

このコードをコンパイルして実行してみる.

$ gcc ex3-8.c -o ex3-8 -g3
$ ./ex3-8
01 02 03 04 05 06 07 08 09
02 04 06 08 10 12 14 16 18
03 06 09 12 15 18 21 24 27
04 08 12 16 20 24 28 32 36
05 10 15 20 25 30 35 40 45
06 12 18 24 30 36 42 48 54
07 14 21 28 35 42 49 56 63
08 16 24 32 40 48 56 64 72
09 18 27 36 45 54 63 72 81

2.4 while 文の無限ループ

以下のコードは while 文による無限ループの例. 条件文が 1 である為, 常に真となり無限ループとなる.

/* code: ex3-9.c */
#include <stdio.h>

int main()
{
  int i;
   
  i = 0;
  while (1) {
    printf ("%d ", i);
    i++;
  }
  return 0;
}

このコードをコンパイルして実行してみる.

$ gcc ex3-9.c -o ex3-9 -g3
$ ./ex3-9
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17..... 一瞬で大変なことになる.

2.5 break 文と continue 文

break 文を利用すると, break 文を使用した場所でループを終了させることが出来る. 以下, コード例.

/* code: ex3-10.c */
#include <stdio.h>

int main()
{
  int i;
   
  i = 0;
  while (1) {
    printf ("%d ", i);
    if (i ==5) {
      i = 0;
      break;
    }
    i++;
  }
  printf ("\n");
  return 0;
}

このコードをコンパイルして実行してみる.

$ gcc ex3-10.c -o ex3-10 -g3
$ ./ex3-10
0 1 2 3 4 5

このコードでは while 文により無限ループとなり変数 i が増加していくが, 変数 i の値が 5 になったところで, 変数 i に 0 が代入され break 文が実行される. これによって, while 文から脱してプログラムが終了する.

continue 文は, continue 文が実行された場所でループ処理が中断し, ループの条件文が評価され, 条件文が真であればループ本文の先頭の命令から実行が行われる. 以下, コード例.

/* code: ex3-11.c */
#include <stdio.h>

int main()
{
  int i;
   
  i = 0;
  while (1) {
    printf ("%d ", i);
    if (i == 5) {
      i = 0;
      continue;
    }
    i++;
  }
  printf ("\n");
  return 0;
}

このコードをコンパイルして実行してみる.

$ gcc ex3-11.c -o ex3-11 -g3
$ ./ex3-11
0 1 2 3 4 5 0 1 2 3 4 5 0 1 2 3 4 5 0 1 2 3... 0 1 2 3 4 5 が繰り返される

このコードでは while 文により無限ループとなり変数 i が増加していくが, 変数 i の値が 5 になったところで, 変数 i に 0 が代入されて continue 文が実行される. ここでループ処理が中断してループの条件文が評価される. 条件文は 1 で常に真であることから, 再びループ本文の先頭から命令が実行される為, 0 1 2 3 4 5 が繰り返し表示される.

3. for 文と while 文の変換

以下, for 文と while 文の形式を比較したもの.

// for 文
for ( 初期文; 条件文; 反復文) {
  本文;
}

// while 文
初期文;
while ( 条件文 ) {
  本文;
  反復文;
}

上記ように, 初期文, 条件文, 反復文の配置を変えることにより for 文, while 文の相互変換が可能となる.

一般的には, ループの処理に入る前に本文の命令を何回繰り返すかが明らかになっているような場合には for 文を, ループの終了条件が本文の命令で決定され, ループの終了の条件が予期しにくい場合には while 文が使われることが多い.

演習問題

問 3.1

以下のコード (コード 3.1) を変更し, 0 から 99 までの数字を表示するようにしなさい.

/* code: ex3-1.c */
#include <stdio.h>

int main()
{
  int i;
  for (i = 0; i < 10; i++)
    printf ("%d ", i);

  return 0;
}

以下, 解答例.

/* code: q3-1.c */
#include <stdio.h>

int main()
{
  int i;
  for (i = 0; i < 100; i++) {
    printf ("%d ", i);
  }

  return 0;
}

コンパイルして実行してみる.

$ gcc q3-1.c -o q3-1 -g3
$ ./q3-1
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99

更にこれを while 文で書き換えてみる.

/* code: q3-1.c */
#include <stdio.h>

int main()
{
  int i;
  
  i = 0;
  while (i < 100) {
    printf ("%d ", i);
    i++;
  }

  return 0;
}

一応, これもコンパイルして実行してみる.

$ gcc q3-1.c -o q3-1 -g3
$ ./q3-1
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99

問 3.2

問 3.1 の q3-1.c を変更して 0 から 9 までの数字を降順に表示するようにしなさい.

以下, 解答例.

/* code: q3-2.c */
#include <stdio.h>

int main()
{
  int i;
  for (i = 9; i >= 0; i--) {
    printf ("%d ", i);
  }

  return 0;
}

これをコンパイルして実行してみる.

$ gcc q3-2.c -o q3-2 -g3
$ ./q3-2
9 8 7 6 5 4 3 2 1 0

先程と同様に while 文でも書いてみる.

/* code: q3-2.c */
#include <stdio.h>

int main()
{
  int i;
  i = 9;
  while (i >= 0) {
    printf ("%d ", i);
    i--;
  }

  return 0;
}

一応, コンパイルして実行してみる.

$ gcc q3-2.c -o q3-2 -g3
$ ./q3-2
9 8 7 6 5 4 3 2 1 0

問 3.3

問 3.1 の q3-1.c を for 文を使ったコードから while 文を使ったコードに変更しなさい.

以下, 解答例.

/* code: q3-3.c */
#include <stdio.h>

int main()
{
  int i;
  
  i = 0;
  while (i < 100) {
    printf ("%d ", i);
    i++;
  }

  return 0;
}

問 3.4

以下のコードの実行した時の出力内容を答えなさい.

/* code: q3-4.c */
#include <stdio.h>

int main()
{
  int i, j, k;
  
  for (i = 0; i < 2; i++) {
    for (j = 0; j < 2; j++) {
      for (k = 0; k < 2; k++) {
        printf ("%d %d %d", i, j, k);
        printf ("\n");
      }
    }
  }
  return 0;
}

普通にコンパイルして実行してみる.

$ gcc q3-4.c -o q3-4 -g3
$ ./q3-4
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1

普通にコンパイルして実行するのは少し学びが無いので gdb でステップ実行してみる.

$ gdb ./q3-4
...
Reading symbols from ./q3-4...done.
(gdb) b main
Breakpoint 1 at 0x708: file q3-4.c, line 8.
(gdb) run
Starting program: /work/q3-4

Breakpoint 1, main () at q3-4.c:8
8         for (i = 0; i < 2; i++) {
(gdb) n
9           for (j = 0; j < 2; j++) {
(gdb) n
10            for (k = 0; k < 2; k++) {
(gdb) n
11              printf ("%d %d %d", i, j, k);
(gdb) n
12              printf ("\n");
(gdb) n
0 0 0
10            for (k = 0; k < 2; k++) {
(gdb) n
11              printf ("%d %d %d", i, j, k);
(gdb) n
12              printf ("\n");
(gdb) n
0 0 1
10            for (k = 0; k < 2; k++) {
(gdb) n
9           for (j = 0; j < 2; j++) {
(gdb) n
10            for (k = 0; k < 2; k++) {
(gdb) n
11              printf ("%d %d %d", i, j, k);
(gdb) n
12              printf ("\n");
(gdb) n
0 1 0
10            for (k = 0; k < 2; k++) {
(gdb)
...

おお.

問 3.5

以下のコードの実行した時の出力内容を答えなさい.

/* code: q3-5.c */
#include <stdio.h>

int main()
{
  int i, j, k;
  
  for (i = 0; i < 2; i++) {
    for (j = 0; j < 2; j++) {
      for (k = 0; k < 2; k++) {
        printf ("%d ", i * j + k);
      }
    }
  }
  return 0;
}

普通にコンパイルして実行してみる.

$ gcc q3-5.c -o q3-5 -g3
$ ./q3-5
0 1 0 1 0 1 1 2

gdb でステップ実行してみる. (上記のコードに改行 ("\n") を追加している)

(gdb) b main
Breakpoint 1 at 0x708: file q3-5.c, line 8.
(gdb) run
Starting program: /work/q3-5

Breakpoint 1, main () at q3-5.c:8
8         for (i = 0; i < 2; i++) {
(gdb) n
9           for (j = 0; j < 2; j++) {
(gdb) n
10            for (k = 0; k < 2; k++) {
(gdb) n
11              printf ("%d ", i * j + k);
(gdb) n
12              printf ("\n");
(gdb) n
0
10            for (k = 0; k < 2; k++) {
(gdb) n
11              printf ("%d ", i * j + k);
(gdb) n
12              printf ("\n");
(gdb) n
1
10            for (k = 0; k < 2; k++) {
...

ふむふむ.

以上

  • for と while の相互変換, 雰囲気掴めた
  • gdb の使い方を勉強せねば...