gccによる演習 (1)

progC.pdf progC-s.pdf progC-e.pdf 記事一覧

gcc のダウンロード

progC.pdf の演習用資料 progC-e.pdf の作成を始めました．

参考資料（[n]は本文でも引用, *.pptは未調査）：
[1] 100% 間違いの無料Cコンパイラ探し - sけいし発のホームページたち - FC2
http://skeishi.web.fc2.com/100machigai.html
[2] タダで始めるC/C++プログラミング for Windows - 大八洲.NET
http://www.ooyashima.net/db/prog.htm
[3] GCCを使いたいんですが・・・ GCCコンパイラをダウンロードしたいのです ...
http://detail.chiebukuro.yahoo.co.jp/qa/question_detail/q1412612754
[4] GNUコンパイラコレクション - Wikipedia
http://ja.wikipedia.org/wiki/GNU%E3%82%B3%E3%83%B3%E3%83%91%E3%82%A4%E3%83%A9%E3%82%B3%E3%83%AC%E3%82%AF%E3%82%B7%E3%83%A7%E3%83%B3
[5] Installing GCC: Binaries - GCC, the GNU Compiler Collection
http://gcc.gnu.org/install/binaries.html
[6] Microsoft Visual Studio Express - Wikipedia - ウィキペディア
http://ja.wikipedia.org/wiki/Microsoft_Visual_Studio_Express
[7] ダウンロード | Microsoft Visual Studio 2012
http://www.microsoft.com/visualstudio/jpn/downloads
[8] WideStudio - ウィキペディア
http://ja.wikipedia.org/wiki/WideStudio
[9] WideStudio/MWT Home page
http://www.widestudio.org/ja/
[10] WideStudio 導入編 -vc2ws-
http://www.geocities.jp/ysvc2ws/setup/setup.html

補足：(1) bccdev.exe を愛用しているのですが，気分転換で道具を変えました．
(2) ソフト屋を目指す諸君には Visual Studio がお薦めです．コンソールアプリケーションを選んで printf("Hello, world!\n"); getchar( ); を実行する行をテンプレートに埋め込んだ hello.c は
  #include "stdafx.h"
  int _tmain(int argc, _TCHAR* argv[])
  {
     printf("Hello, world!\n"); getchar( );
     return 0;
  }
のようになりますが，プロジェクト作成時に「プリコンパイル済みヘッダー(P)」をオフにして，hello.cpp の名前を hello.c に変更して
  #include < stdio.h>//HTML対策で' '挿入
  main( )
  {
     printf("Hello, world!\n"); getchar( );
     return 0;
  }
に変え，他の3個のファイルを削除してもビルドは正常に終了します．
(3) WinXP には Visual Studio .NET 2003 をインストールして .NET Framework を更新していますが，Win7 にインストールした Visual C++ 2010 Express と少し挙動が違い，コンソールアプリケーションを選んだときに自動生成されるファイルは３個で，stdafx.h の内容も異なります．
(4) コマンド入力画面の例(2013-10-06追加)：
 

Hello, world!

記事一覧	#include < stdio.h>//HTML対策で' '挿入 int main(void){ char s[64]="Hello, world!"; puts(s); return 0; } printf(・・・)よりこちら？

progC.pdf ではコンソール入出力を printf( ), scanf( ) に限定してＣプログラミングの説明をしましたが，puts( ), gets( ) の方がよかったと反省しています．付言すれば，加減算の前に atoi( )．
※ Turing machine 風にメモリをテープでモデル化すると，x[i] と &x[i] の関係を説明しやすく，ポインタの意味も分かり易かった --- 紙テープの２進パターンはコンピュータでのデータの記憶方法を示すのに効果的．アセンブリ言語の言及不要．

いくつかの関数

progC.pdf progC-s.pdf 記事一覧

標準ライブラリの関数

progC-s.pdf に「D9E%いくつかの関数」を追加しました．

参考資料（$[n]は本文でも引用, *.pptは未調査）：
[1] 標準Cライブラリ - Wikipedia
  http://ja.wikipedia.org/wiki/%E6%A8%99%E6%BA%96C%E3%83%A9%E3%82%A4%E3%83%96%E3%83%A9%E3%83%AA
[2]（再掲）プログラミング言語C―ANSI規格準拠― 第2版
  http://www.kyoritsu-pub.co.jp/bookdetail/9784320026926
全般に参照していますが，作る立場からライブラリ関数を解説しています．
[3] C言語関数辞典 - fread
  http://www.c-tipsref.com/reference/stdio/fread.html
size_t fread(void * restrict ptr, size_t size, size_t nmemb, FILE * restrict stream);
[4] C言語関数辞典 - fwrite
  http://www.c-tipsref.com/reference/stdio/fwrite.html
size_t fwrite(const void * restrict ptr, size_t size, size_t nmemb, FILE * restrict stream);
[5] size_t型
  http://manabu.quu.cc/up/3/e31555.htm
[6] rand - ウィキペディア - Wikipedia
  http://ja.wikipedia.org/wiki/Rand
古いrandの実装が生成する乱数列は、問題があるものがほとんどだったことが指摘されている[2] ・・・詳細は線形合同法#欠点を参照すること。
ライブラリには標準外でより高品質のrandom、rand48等が用意されていることがある。
[7] ボックス＝ミュラー法 - Wikipedia
  http://ja.wikipedia.org/wiki/%E3%83%9C%E3%83%83%E3%82%AF%E3%82%B9%EF%BC%9D%E3%83%9F%E3%83%A5%E3%83%A9%E3%83%BC%E6%B3%95
一様分布に従う確率変数から標準ガウス分布に従う確率変数を生成させる手法。
[8] 時間管理
  http://wisdom.sakura.ne.jp/programming/c/c60.html
[9] Malloc - ウィキペディア - Wikipedia
  http://ja.wikipedia.org/wiki/Malloc
詳細は「動的メモリ確保」を参照
[10] C言語関数辞典 - system
  http://www.c-tipsref.com/reference/stdlib/system.html
[11] Super Technique 講座～可変長引数マクロ
  http://www.nurs.or.jp/~sug/soft/super/vaarg.htm

補足：(1) progC.pdf [#65] で言及した関数に関する補足が中心です．
(2) チェック用のプログラムは
  #include < stdio.h>//HTML対策で' '挿入
  #include < stdlib.h>//HTML対策で' '挿入
  #include < time.h>//HTML対策で' '挿入
  int main( ){
    int bf[4]={0x44434241, 0x46450A0D};
    FILE *fp = fopen("x.dat","wb");
    fwrite(bf,sizeof(bf), 1, fp);
    fclose(fp);
    fp = fopen("x.dat","rb");
    fread(bf, sizeof(bf), 1, fp);
    fclose(fp); printf("%s\n", bf);
  //
    time_t t1, t2; struct tm *p; int k;
    t1 = time(NULL); p = localtime(&t1);
    printf("%s\nk = ", asctime(p));
    scanf("%d", &k); t2 = time(NULL);
    printf("%d, %d, ", t1, t2);
    printf("%f\n", difftime(t2, t1));
  //
    printf("> dir\n"); system("dir");
    return 0;
  }
x.dat のチェックに使ったバイナリエディタは http://www.net3-tv.net/~m-tsuchy/tsuchy/dlpage.htm の TSXBIN.exe

文字列の処理

progC.pdf progC-s.pdf 記事一覧

文字列の編集

progC-s.pdf に「D9A%文字列の処理」を追加しました．

参考資料（[n]は本文でも引用, *.pptは未調査）：
[1] 文字列 - Wikipedia
  http://ja.wikipedia.org/wiki/%E6%96%87%E5%AD%97%E5%88%97
[2] 文字コード - Wikipedia
  http://ja.wikipedia.org/wiki/%E6%96%87%E5%AD%97%E3%82%B3%E3%83%BC%E3%83%89
[3] 文字列探索 - Wikipedia
  http://ja.wikipedia.org/wiki/%E6%96%87%E5%AD%97%E5%88%97%E6%8E%A2%E7%B4%A2
[4] 文字列（string）
  http://www.cc.kyoto-su.ac.jp/~yamada/programming/string.html
文字列のための標準ライブラリ関数
[5] 文字列
  http://www.kis-lab.com/serikashiki/C/C08.html
文字コードの判断
[6] 5. ストリングマッチング 5.1 素朴なアルゴリズム
  http://www2.kobe-u.ac.jp/~ky/da2/haihu01.pdf
[7] クヌース-モリス-プラット法 - Wikipedia
  http://ja.wikipedia.org/wiki/%E3%82%AF%E3%83%8C%E3%83%BC%E3%82%B9-%E3%83%A2%E3%83%AA%E3%82%B9-%E3%83%97%E3%83%A9%E3%83%83%E3%83%88%E6%B3%95
[8] ボイヤー-ムーア文字列検索アルゴリズム - Wikipedia
  http://ja.wikipedia.org/wiki/%E3%83%9C%E3%82%A4%E3%83%A4%E3%83%BC-%E3%83%A0%E3%83%BC%E3%82%A2%E6%96%87%E5%AD%97%E5%88%97%E6%A4%9C%E7%B4%A2%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0
[9] 正規表現 - Wikipedia
  http://ja.wikipedia.org/wiki/%E6%AD%A3%E8%A6%8F%E8%A1%A8%E7%8F%BE
[10] 第7章 正規表現 - Kent Web
  http://www.kent-web.com/perl/chap7.html
[11] 正規表現メモ
  http://www.kt.rim.or.jp/~kbk/regex/regex.html
[12] Regular-Expressions.info - Regex Tutorial, Examples and ...
  http://www.regular-expressions.info/
[13] ライブラリ関数一覧
  http://www9.plala.or.jp/sgwr-t/lib/lib.html
[14] C言語関数辞典 - string.h
  http://www.c-tipsref.com/reference/string.html
strcpy 関数は・・・領域の重なり合うオブジェクト間でコピーが行われるときの動作は未定義です．
※ progC-s.pdf の strcpy は（K&R-2のサンプルと異なり）領域が重ってもコピーできますが src 側が壊れされます．
注意! strcpy 関数はバッファオーバーフロー (buffer over-flow) を発生させやすい関数の 1 つです．

補足：(1) 線形時間で文字列を検索する方法は progC-e.pdf で演習します．正規表現は progC-e.pdf でも扱いません --- sys.pdf[#62]．
(2) string.h にある標準関数を使うときは使用中の領域を壊さないように注意が必要．
  #include < stdio.h>//HTML対策で' '挿入
  #include < string.h>//HTML対策で' '挿入
  int main( ){
    char s1[ ]="abcde", s2[ ]="xyz";
    printf("%p, %p, %s, %s\n", s1, s2, s1, s2);
    strcpy(s2, s1);
    printf("%p, %p, %s, %s\n", s1, s2, s1, s2);
    return 0;
  }
の（BccDevによる）実行結果は
  0012FF84, 0012FF80, abcde, xyz
  0012FF84, 0012FF80, e, abcde
となり，s1[ ]が壊れています．
(3) progC-s.pdf の関数はＣの標準ライブラリ関数とは（名前は同じですが）処理内容は異なります．ポインタpの値を確実に変えたいときは「p = NULL; p="";」．
#include < stdio.h>//HTML対策で' '挿入
int strlen(char *p){
  int k=0;
  while(*p != 0){p++; k++;} return k;
}//'\0' == 0
char *strptr(char *p, char *q){
  int k;
  for( ;p[0] != 0; p++){
    for(k = 0; q[k] != 0; k++){
      if(p[k] != q[k]){break;}
    }
    if(q[k] == 0){return p;}
  } return NULL;
}//無駄な比較が多い．
void strcpy(char *p, char *q){
  int n, k;
  n = strlen(q);
  if(p < q){
    for(k = 0; k < = n; k++){p[k] = q[k];}//HTML対策で' '挿入
  }else while(n >= 0){p[n] = q[n]; n--;}
}//文字列qが使えなくなる場合がある．
int main( ){
  char s1[]="abcde", s2[ ]="pqr", *p1="uvwxyzabc", *p2="xyz";
  //char s2[ ]="pqr", s1[]="abcde", *p1, *p2;
  printf("%p, %p, %p, %p\n", s1, s2, p1, p2);
  printf("%s, %s, %s, %s\n", s1, s2, p1, p2);
  p1 = strptr(p1, p2);
  printf("%p, %d, %s\n", p1, strlen(p1), p1);
//
  p1 = NULL; p1 = "";
  printf("%s, %s, %s, %s\n", s1, s2, p1, p2);
  strcpy(p1, s1);
  printf("%s, %s, %s, %s\n", s1, s2, p1, p2);
  strcpy(p1+strlen(p1), s2);
  printf("%s, %s, %s, %s\n", s1, s2, p1, p2);
//
  strcpy(s2, s1);//実行でき，s1が壊される
  printf("%s, %s, %s, %s\n", s1, s2, p1, p2);
  return 0;
}
/*------------------------------------------------
0012FF84, 0012FF80, 0040A132, 0040A13C
abcde, pqr, uvwxyzabc, xyz
0040A135, 6, xyzabc
abcde, pqr, , xyz
abcde, pqr, abcde, xyz
abcde, pqr, abcdepqr, xyz     //pqr0 abcde0
e, abcde, abcdepqr, xyz       //abcd e0de0
                              //s2[] s1[]
-------------------------------------------------*/

漸近的計算量

progC.pdf progC-s.pdf 記事一覧

べき乗の計算

progC-s.pdf に「D96%漸近的計算量」を追加しました．

参考資料（[n]は本文でも引用）：
[1] アルゴリズム解析と計算量
  http://www.ieice-hbkb.org/files/06/06gun_03hen_01.pdf#page=11
[2] 計算量 - Security Akademeia
  http://akademeia.info/index.php?%B7%D7%BB%BB%CE%CC
[3] 計算複雑性理論 - Wikipedia
  http://ja.wikipedia.org/wiki/%E8%A8%88%E7%AE%97%E8%A4%87%E9%9B%91%E6%80%A7%E7%90%86%E8%AB%96
[4] 分割統治法(マージソートまで)
  http://www.cs.gunma-u.ac.jp/~nakano/Al/note1.html
[5] コンピュータアルゴリズム2 4. 分割統治法
  http://www.logos.t.u-tokyo.ac.jp/~tau/lecture/software/gen/slides/4-divconq.pdf
[6] 高速フーリエ変換 - Wikipedia
  http://ja.wikipedia.org/wiki/%E9%AB%98%E9%80%9F%E3%83%95%E3%83%BC%E3%83%AA%E3%82%A8%E5%A4%89%E6%8F%9B

補足：(1) 計算量には領域計算量と時間計算量がありますが，前者については言及していません．
(2) [%41]の方法を高速フーリエ変換といいます．漸近的計算量がO(N log N)になることを説明するにはもう少し行数が必要です --- ベクトル要素の並び替えや片方の行列にかかっているスカラー倍の扱いの具体化．
(3) [%1]の(m-1+m)「以下」は b(k)=0 のときは乗算不要のため，[%3]の24回「以下」は片方の部分列が空になれば比較しないためです．