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) ではないのは重複マークの状況があるため
  - log の底は誰でも重要ではなく、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 である
- 注意：二重の for ループがあるが、時間計算量は O (N) である。なぜなら、二重の 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' で埋められる
- size を加えない場合、配列の最後に文字 '\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 マクロを印刷する実装#

亮点ノート#

コードデモ#

素数ふるい#

配列#

宣言、初期化#

使用スペース、アドレス#

引数渡し#

追加知識点#

思考点#

ヒント#

コース速記#