5 配列と前処理コマンド

コース内容#

配列の定義と初期化#

定義：固定サイズの同じ型要素の順序集合を保存する
初期化
- int a[100] = {2, 3}; // a[0] = 2, a[1] = 3
- int a [100] = {0}; // 配列のクリア操作：配列の各要素を 0 で初期化
  - 実際には第 0 要素だけが 0 に定義されるが、他の要素も自動的に 0 に初期化される
その他
- インデックス 0 から始まる
- 配列のサイズ：すべての変数サイズの合計
- ストレージは連続
  - int a[3]

アドレス	0123	4567	89[10][11]
要素	a[0]	a[1]	a[2]

- 上記の定義された配列はすべて静的配列に属する
  - 推奨されない操作：int n; scanf ("% d", &n); int arr (n);
- インデックス - 値のマッピング
  - インデックスが分かれば、値を取得する時間効率は O (1)

素数ふるい#

核心思想：素数を使ってすべての合成数を列挙する

アルゴリズムのフレームワークとして学ぶ、多くの変遷がある
素数：1 とその自身の 2 つの因子のみを持つ
- 1 は素数でも合成数でもない
- 2 は最小の素数
- 素数は必ず奇数である（2 を除く）、奇数は必ずしも素数ではない
配列構造を利用する。配列は3 種類の情報を表すことができる：
- インデックス
- インデックスにマッピングされた値
- 値の正負
アルゴリズムの評価基準とその性能
- 空間計算量：O (N)、N 個の数字があればサイズ N の配列を開放する
- 時間計算量：O (N * logN)、O (N * loglogN)-- 最適化版、O (N) に近づく
  - O (N) ではないのは重複マークの状況があるから
  - 対数の底は誰でも重要ではなく、2 を底にすればすでに非常に小さい
  - どう計算するか：平均化の考え方、時間計算量と確率に基づいて期待値を計算する...
マークを付ける：素数、0；合成数、1
- 配列の 2 つの状態情報を利用する：インデックス→数字、値→マーク
素数ふるいの拡張
- 範囲内のすべての数字の最小、最大素因子を求める
- 例えば 12：2、3

線形ふるい#

オイラーの第 7 問から始める
- 第 10001 個の素数を求める
- 列挙法 O (N * sqrt (N))、素数ふるいを使用できる
- 第 10001 位の素数のサイズはどのくらいになるか？
  - 規則：20 万以内のランキングの素数は、その範囲はランキングの 20 倍を超えない
素数ふるいからの考察
- 6 は何回マークされたか？2 回：2、3
- 30 は何回マークされたか？3 回：2、3、5
- 数字 N の素因数分解式に m 種類の異なる素数が含まれている場合、N は何回マークされるか？m 回
- では、1 回だけマークされることは可能か？👇
線形ふるい
- 空間、時間ともにO(n)
- 整数 M を使って合成数 N をマークする
- M、N の関係は4 つの特性を満たす
  1. N の因子の中で最小の素数は p である
  2. N = p * M
  3. ❗ p は必ずM の最小素因子以下である
    - 七擒孟獲の理論に似て、最後のマークのみに存在する
  4. M * P' （すべての M の最小素数以下の素数集合）を利用して N1、N2、...

【i と iii は少し同等の意味を持つ】

コード
- 核心思想：N = M（↑できるだけ大きく） * p（↓できるだけ小さく）
  - M を列挙し、p の値を徐々に増やし、p の値が終了条件を満たすまで：特性 iii
  - M と比較して、p の方がより良く制御できる！
- 重複を避けるための鍵は第 iii 条の特性である
- 注意：2 重の for ループがあるが、時間計算量は O (N) である。なぜなら、2 重の for ループ内の break により、配列全体が 1 回だけ走査されるからである
- 素数ふるいの初期条件を i * i に最適化することとの違いは？素数ふるいには依然として重複マークの状況がある

二分探索法#

順次探索→二分探索：O (N)→O (logN)
重要な前提：探索列が単調であること
コード
- 主に3 つの部分を示す：①配列内での二分探索 ②関数内での二分探索 ③
- 関数の二分探索実装部分について
  - binary_search_f_i と binary_search_f_d を 1 つの関数に統一できるはず
  - 後の学習に注目し、渡された関数ポインタの戻り値の型を識別できるか
  - しかし、実装部分には違いがあるため、意味はあまりない
- main 関数内でコメントアウトされたコードは、配列と関数内での二分探索の結果をテストしている。以下のように：
- - 関数を利用した二分探索の範囲はより柔軟にできる
- double 型の判定：差が EPSL より小さいかで判断
  - #undef EPSL を忘れずに
- 詳細はコメントを参照
  - 学習の順序：binary_search 👉 binary_search_f_i 👉 binary_search_f_d
再帰版コード
- 関数の引数と反復方法が異なり、探索境界を確定する必要がある

ニュートン反復法#

目的：f (x) = 0 のときの x の値を求める
条件：関数が導関数を持つ；収束する
1 回の反復公式：x2 = x1 - f(x1) / f'(x1)
核心思想：反復するたびに、x2 は x1 よりも要求される x の値に近づき、f (x) の絶対値が EPSL より小さくなるまで
コード
- ⭐ループ終了条件は絶対値を取ることを忘れないで！
- x = n / 2.0 という初期値は固定されているのか？
  - そうではない
  - この値は x の最近の解を想定したもので、解の左右両側に問題はない
  - ただし 0 を取ることはできない、導関数が 0 になると、除数が 0 になる
- ニュートン関数をラッピングして、my_sqrt 関数を得る
- これは二分探索ではない！二分探索には単調性が必要～

前処理命令#

#で始まる命令
- #include <stdio.h> →前処理時に、stdio.h ファイルをそのまま現在位置にコピーする
マクロ定義

定義記号定数：定数→記号。

#define PI 3.1415926
#define MAX_N 1000

値の一括変更を容易にする

バカな式

#define MAX(a, b) (a) > (b) ? (a) : (b)
#define S(a, b) a * b

バカ eg. #define S (a, b) a * b
- S (2 + 3, 4 + 5) → 簡単な置換 → 2 + 3 * 4 + 5 は 2 + (3 * 4) + 5 に等しい
- 置換の過程で何の計算も行わない！

コードセクションの定義（高度）

#define P(a) { \
    printf("%d\n", a); \
}

マクロは 1 行の定義しか受け付けず、改行するにはバックスラッシュ '' （接続子）を使用する
予定義マクロ（システムが封装したもの）
- マクロの両端には 2 つのアンダースコアがある
- DATA、TIME：前コンパイル時の日付、時間、前処理しなければ変更されない
  - 指紋認識のような機能を実現できる？事前保存された関係？
- 非標準マクロ：環境によっては未定義の可能性があり、異なる環境の標準は異なるため、移植性が悪い
  - どう対処するか？条件付きコンパイルを使用する👇
条件付きコンパイル
- #ifdef DEBUG
  - 説明：DEBUG マクロが定義されているかどうか
  - 注意：DEBUG は必ずマクロであり、変数ではない！
    - マクロは前コンパイル後に有効になり、変数はコンパイル後に有効になる
- #ifndef DEBUG 未定義かどうか
- #if MAX_N == 5 マクロ MAX_N が 5 に等しいか
  - ゲーム内でユーザーの携帯版を判断できる
- #elif MAX_N == 4
- #else
- 必ず #endif** で終了すること！！
  - 【コーディング規範】
  - va_start、va_end のように
簡易コンパイルプロセス
- C ソース .c
👇前処理段階（前コンパイル） (gcc -E)：ヘッダーファイルの含有、マクロ置換などの前処理命令、すべての #命令を置換する
- コンパイルソース .c
👇構文チェック、コンパイル (gcc –S)
- アセンブリソース .s、.asm
👇アセンブリ (gcc -c)
- オブジェクトファイル .o（linux 下）または .obj（windows 下）
👇リンク (gcc)
- 実行可能プログラム a.out（linux 下）または a.exe（windows 下）（バイナリファイル）
PS：最後にロードプロセスがあり、主に実行可能ファイル、仮想アドレス、物理アドレスの 3 者のマッピング関係を確立する

文字列#

文字配列
- 定義：char str [size];
- 初期化

char str[] = "hello world";
char str[size] = {'h', 'e', 'l', 'l', 'o'};

Line1
- [] 内でサイズを指定しなくても、システムが自動的に計算する
- システムは自動的に終端文字 '\0' を追加する。文字配列のサイズ：11+1
Line2
- size は少なくとも 6 で、終端文字 '\0' が 1 つのサイズを占めることを考慮する
  - 余分な部分はすべて '\0' で埋められる
- サイズを加えない場合は、配列の最後に文字 '\0' を追加する必要があり、システムは自動的に追加しない
'\0'
- 終端マーク
- 基底に対応する 0 値：false
- '\0' は終端条件として使用できる。例えば：for ループで文字列を読み込む
文字の後に '\0' はあるか？ない、これは文字列の特性である
関連操作
- ヘッダーファイル：<string.h>
- strlen(str)
  - 文字 '\0' のインデックスを返す。長さは '\0' を含まない
  - PS：sizeof () は変数が実際に占有するメモリを考慮し、'\0' も考慮する。単位はバイト
- strcmp(str1, str2);
  - 辞書順で ASCII コードの大小を比較する
    - 最初の位置から始まる
  - 戻り値は差（等しい場合は 0）
- strcpy(dest, src);
- 比較とコピーの終了マーク：文字 '\0' を探す。もし '\0' が失われたら？だから以下のように
- より安全な比較とコピー：strncmp、strncpy
  - '\0' をうっかり失った場合に対処する
  - 最大 n バイトを比較、コピーする
- メモリ関連
  - memset(str, c, n)
  - 文字列操作に限定されず、str はアドレスを指すだけである
    - ここでは配列の操作の例を挙げる
    - memset(arr, 0, sizeof(arr))
      - 初期化し、0 でクリアする
    - memset(arr, 1, sizeof(arr))
      - ここでは各位置を 1 にするわけではない。なぜなら、操作は各バイトに対して行われ、int は 4 バイトを占めるからである
      - 0000...01000...001000....0001...
    - memset(arr, -1, sizeof(arr))
      - 確かに - 1 である。なぜなら - 1 は 1 バイト内で 11111111 であるから
ヘッダーファイル：<stdio.h>
両者を組み合わせることでフォーマットの結合が可能：1 つは入力、もう 1 つは出力
scanf 内の str1 は端末の入力に類似し、それは文字列入力に置き換えられた

授業中の練習#

バグのない MAX マクロを実装する#

思考：①手計算で正しい出力を得る👉②最も簡単なバグのある実装を先に書き、フレンドリーな出力を実現👉③誤った出力に対して順次問題を見つけ、解決する
①正しい出力は図の通り
②最初にバグのあるものを書き、フレンドリーな出力を実現

#define MAX(a, b) a > b ? a : b
#define P(func) { \
    printf("%s = %d\n", #func, func); \
}

Line2-4：フレンドリーな出力表示
- #func はその文字列表現を直接出力する
- #を加えなければその値を呼び出す
③誤った出力に対して順次問題を見つけ、解決する
- （バグ解決の順序も重要だが、ここではバグの順序が良い）
- この時、誤った状況を見てみる
- マクロによるエラーは、前処理後のファイルを見ればわかる
  - gcc -E *.c マクロ置換後のコードを出力する
- 最初の修正
  - 解決：赤枠の部分を括弧で囲んで優先度を上げる

#define MAX(a, b) (a > b ? a : b)

- 2 回目の修正
  - 4 番目の結果は 2 で、思考は上の図の通り
  - 条件演算子 '?:' に注意
    - 優先度は非常に低い：'>' より低い
    - 複数の '?:' が存在する場合、その結合方向は右から左である
  - 解決：各変数を括弧で囲んで優先度を上げる

#define MAX(a, b) ((a) > (b) ? (a) : (b))

- 3 回目の修正
  - a++ が 2 回実行された
    - 実際には a を比較した後に a+1 を行うべきである
  - 解決：++ 演算の前の値を変数に代入し、コードセクション生成の式として定義する

#define MAX(a, b) ({\
    __typeof(a) _a = (a);\
    __typeof(b) _b = (b);\
    _a > _b ? _a : _b;\
})

__typeof (a++) の a++ は実行されるか？
- 表現式の時には実行されず、単にその型を取得する
({}) 表現
- 値は小括弧内の最後の表現の値であり、データ型は最後の表現のデータ型である
- 参考C 言語の小括弧と波括弧の組み合わせ使用 && 複合文-CSDN
- {} や () を取り除くことはできない！
  - () 内にはカンマ式しか置けない
    - カンマ式は最後の式の値を取る
  - {} はコードセクションであり、戻り値がない
    - もし直接マクロ関数として定義した場合
    - 直接 printf 出力すると、MAX が最大値を返す本質を失う
    - ❓戻り値を返すために return を使用する必要がある
      - 宣言が必要
      - しかし、直接表現式を使用して戻り値を表す方が賢い
最終版コード

結果はすべて正しい！

LOG マクロを印刷する実装#

コード
- 仕事を納品する際、ログ情報を省くことができ、条件付きコンパイルを使用する
  - コンパイル時に "gcc -DDEBUG" を使用して DEBUG マクロ定義を渡すことができる
  - #else の後に空のマクロを定義して置き換える
- 可変引数マクロ
  - 可変引数 '...' は名前を取るだけである。eg. args...
- マクロ内の "#"、"##" の使用
  - "#"：文字列を取得する
  - "##"：結合する
    - log マクロに空文字が渡された場合の状況を解決する：空の場合、frm の後の "," は自動的に除去される。前処理結果を参照する👇
    - 参考テキストマクロの置換-cppreference
    - ab と a##b の違い
      - ab は a、b を代入して結合することはない
      - ## で結合する a、b に対応する渡された引数は定義されていなくてもよい
        
        前処理はこれらの未定義の変数名を結合し、結合された変数名が定義されていればよい

亮点ノート#

コードデモ#

素数ふるい#

コード

対偶論理、インデントを制御する
- if continue
prime 配列の前部分は同時にカウントとストレージが可能（全体はマーク付けに使用される）
- 最初は prime [0]、prime [1] は使用されず、空いている
- オーバーテイクの問題は発生しない：偶数は必ず合成数であり、素数は少なくとも 1 つの間隔で出現する
2 番目の for ループの初期条件を最適化できる
- 初期条件：i * 2 → i * i
- 時間効率：O (Nlogn)→O (Nlognlogn)
- なぜなら、i * i より小さい合成数は必ず i より小さい数によってマークされているからである
  - これにより、前の部分の重複マークの回数が減少するが、完全ではない
  - 重複マークを完全に回避するには線形ふるいを使用する必要がある
- 危険な点：i * i は指数的に増加し、int が保存できる最大値をオーバーフローする可能性が高い
  - 事前に判断を加えることはできるか？しかし、より大きな時間をもたらす可能性がある
  - i * i のデータ型をより高い上限のものに変更する

配列#

コード

出力
- 詳細👇

宣言、初期化#

プログラミングのコツ：5 桁多く開くことで、オーバーフローを避け、バグ率を下げる

#define max_n 100
int arr[max_n + 5];

関数内の変数空間はすべてスタック領域に定義される
- スタック領域はバドミントン筒で理解できる。後入れ先出し
- スタック領域のサイズ（デフォルト）：8MB≈800 万バイト
関数内で宣言された配列はクリーンでない可能性があるため、手動で初期化する必要がある
- = {0};
- scanf で読み込む

for (int i = 0; i < max_n; i++) {
scanf("%d",arr + i);
}

- arr + i は &arr [i] と等価である& これは欠かせない！
関数外で宣言された配列
- システムは自動的に 0 でクリアする。これは = {0} 操作に似ている
- 開放できるサイズはコンピュータのメモリに制限され、基本的には無制限である
malloc、calloc、realloc で定義された配列はヒープ領域にあり、関数内で定義されても

使用する空間、アドレス#

sizeof () に対応する制御文字は % lu、符号なし長整数
配列名 arr は配列の先頭アドレスを表し、すなわち & arr [0]

printf ("% p % p\n", arr, &arr [0]); // アドレス値は同じ

アドレス + 1 のオフセットは、アドレスが表す要素のバイト数に依存する

引数の渡し方#

条件：外部と関数内の引数の表現形式が一致すること
- 一次元配列：int arr [100];
  - void func(int *num)
- 二次元配列：int arr2[100][100];
  - void func2 (int **num) は警告を出す
    - num + 1 と arr + 1 の表現形式が一致しない
    - num は int ポインタのポインタを指す
    - num と num + 1 のアドレスは 1 つの【ポインタ】のサイズだけ異なり、64 ビットオペレーティングシステムでは 8 バイトである
    - arr と arr + 1 のアドレスは 1 つの【一次元配列】のサイズだけ異なり、4 * 100 バイトである
  - void func2(int (*num)[100]) 可能である
- 三次元配列：int arr3 [100][100][32]
  - void func3(int (*num)[100][32]) 可能である
  - (*num)[100][32] は num [][100][32] と書くことができる
    - (*num) と num [] の表現形式は同じだが、本質的には異なる
❓q は nil を指している？つまり 0x0

追加の知識点#

配列は3 種類の情報を表すことができる
int arr [100]; //arr を関数に渡すときは、配列の先頭要素のアドレスとして渡される
1 の反転は - 2？推導してみる
- 1： 0000...001
- 反転：1111...110
- 符号ビットは変わらない。反転して 1 を加えると：1000...010
- つまり - 2
- 結論：すべての正の整数のビット反転は、その本体 + 1 の負数である
<math.h> を含むソースファイルでは、コンパイル時に - lm を追加する必要がある。gcc *.c -lm
コーディング習慣、一行は 80 文字を超えない
制御文字 "%X"：大文字の 16 進数

思考点#

関数とマクロ、どちらが強力か？
- マクロは関数を生成でき、マクロは関数の父ではないのか？

ヒント#

vim でヘッダーファイルの自動補完形式を変更する：スペースを追加する
- ~/.vimrc ファイルに入り、SetTitle () 内の対応する形式を変更すればよい
マクロの展開、ネストを自分で探求する
参考書の第 8 章 8.1、8.4 および第 15 章

Bo2SS

5 配列と前処理コマンド

コース内容#

配列の定義と初期化#

素数ふるい#

線形ふるい#

二分探索法#

ニュートン反復法#

前処理命令#

文字列#

授業中の練習#

バグのない MAX マクロを実装する#

LOG マクロを印刷する実装#

亮点ノート#

コードデモ#

素数ふるい#

配列#

宣言、初期化#

使用する空間、アドレス#

引数の渡し方#

追加の知識点#

思考点#

ヒント#

コース速記#