4 関数 - Bo2SS

コース内容#

関数の基本知識#

関数のカプセル化
- 可読性、美しさ、⭐デバッグ性（関数モジュールごとにデバッグ可能）
関数宣言の三要素（必須）
- 戻り値
  - 戻り値がない場合は void を書く
- 関数名
- 引数宣言リスト
  - 引数の型 + 引数名
関数定義
- 中括弧内の内容

再帰関数#

一種のプログラミングテクニック（for ループ、if 文、再帰）、アルゴリズムではない（再帰的推論）
関数が自分自身を呼び出す
構成要素
- 意味情報：要求に基づいて設計
- 境界条件：再帰の出口を設計し、複数存在することができる
- 再帰式：問題に対して！
- 結果の返却：return だけではない
  - 二つの方法：return で返す、出力引数（ポインタ）
再帰関数が正しいことをどう証明するか？
- 簡単な再帰：中間過程を展開する
  - 下に推論 + 上に戻る
- 複雑な再帰：数学的帰納法
  - 例えば階乗
    - fac (1) が成り立つ
    - fac (k) が正しいと仮定する
    - fac (k+1) が正しいことを証明すればよい

関数ポインタと応用#

関数名をポインタの形式で関数に渡し、関数内で関数名を使って直接関数を使用できる
- 戻り値 (* 関数名)(引数型リスト)
応用
- 分段関数を実現する、上の図のように
- オイラー問題集：EP-45
- 40755 を見つける、同時に三角数、五角数、六角数の数字
  - 次の三角数を見つける、五角数、六角数の条件も満たす
- 二分探索
  - 単調列上の数字列はすべて順序がある
  - 時間効率：O (logn)
- コード

⭐EP-45 には多くのハイライトがあり、主に 6 つの重要な点に注意#

二分探索は必ずしも配列ではなく、マッピング関係のある単調列であればよい
2. 列の特徴に基づいて区間の頭と尾を調整した
対偶論理でインデントを減らし、可読性を向上させる
三角数は六角数を含む：第 2n-1 の三角数＝第 n の六角数
int 型（4 バイト）を使用すると、無限ループに陥る
1. int 型では次に求める数字をカバーできない
2. long long int型（8 バイト）を使用し、制御文字：% lld
固定六角数、スパンが大きく、速度が速く、4 点目から三角数であることがわかる

その他
- temp より小さい右境界または 1 より大きい左境界を使用できるはず
  - ただし O (logn) なので、縮小後の効果はあまり大きくない
- ここで関数ポインタを使用したが、使用しない場合はどれだけ似たような binary_search 関数を書く必要があるか？
  - ただし、マクロを使用して関数の切り替えを行うこともできる
- 図中の赤いバツは誤記で、Hexagonal を Triangle に修正

ユークリッドアルゴリズム#

別名：辗転除法

最大公約数を迅速に計算する
- gcd (a, b) = gcd (b, a % b) = c は、規模を小さくする
- 証明

①c を a、b の最大公約数とし、b、a % b にも公約数 c が存在することを証明する

正の整数 k1、k2、k3 を仮定する
a = k1 * c
b = k2 * c
a % b = a - k3 * b // 取模の本質
したがって a % b= k1 * c - k3 * k2 * c =(k1 - k3 * k2) * c
つまり a % b は c の倍数であり、b も c の倍数である
よって c は両者の公約数である

②c が最大の公約数であることを証明する

b、a % b の他の二つの約数 k2、k1 - k3 * k2 が互いに素であることを証明すればよい
gcd (k2, k1 - k3 * k2)= d（正の整数）とし、d = 1 であることを証明する
正の整数 m、n を仮定し、次のようにする
k2 = m * d
k1 - k3 * k2 = n * d
したがって
k1 =n * d + k3 * k2 =(n + k3 * m) * d
得られる
gcd(k1, k2) >= d
また
gcd(a, b) = c
a = k1 * c
b = k2 * c
したがって
gcd(k1, k2) = 1
したがって
d = 1

コード
再帰関数
- 一行で gcd 関数を実現できる
  - if 文を三項演算子に置き換える
a、b の大小に基づいて順序を交換する必要はない？必要ない
- a ≥ b の場合：gcd () 関数は通常の思考で進む
- a <b の場合：gcd () 関数は二つの変数を交換する
Ctrl+D は前回の出力を繰り返すが、終了しない？
- 【読み込んだ文字数が 0 のときに終了する、例えば int 値以外を入力した場合】
- scanf の戻り値が EOF であるかどうかの判断がないため
- scanf の前に反転 "~" を取るか、後で - 1 の判断を行うことができる

拡張ユークリッドアルゴリズム#

ax+by=1 の整数解の一組を迅速に求める
- gcd (a, b) = C の C が何の値のときに、一組の整数解を求めることができるか
  - C は 1 または > 1 の二つのケースがある

a = nC
b = mC
nCx + mCy = 1
C(nx + my) = 1
nx + my は必ず≥1
C は 1 しか取れない

辗転除法の最後のラウンドで 1、0 だけが残るとき、互いに素であることを示し、整数解が存在する
数学的帰納法
- 流れ
  - f (0) が成り立つ→f (k) が成り立つと仮定する→f (k+1) も成り立つことが得られる→k は任意に成り立つ
  - 上の図、下の表を参考にし、下に推論 + 上に戻る

	a	b	x	y
第 k+1 層（推導）	a	b	y	x - ky
	↓↓↓	↓↓↓	↑↑↑	↑↑↑
第 k 層（仮定）	b	a % b	x	y
...	↓↓↓	↓↓↓	↑↑↑	↑↑↑
第 0 層（成立）	1	0	1	0（任意）

コード

関数入力のアドレスは最初は値がなく、最深部で初めて値が与えられ、戻る
出力の等式の右側は必ずしも 1 ではない
- 実際、拡張ユークリッドアルゴリズムは ax + by = gcd (a, b) の整数解を迅速に求めることができる

可変引数関数#

上記のシーンを通じて学ぶ：

問題は関数をどのように宣言するかではなく、可変引数リストの各引数にどのように位置付けるかである
- 可変引数リスト内の変数の名前がわからない
- 例：教師が張三という生徒の後ろの生徒に質問をさせたいが、名前を忘れてしまった場合、張三の後ろの生徒に直接答えさせることができる
va 一族を通じて実現する <stdarg.h>
- 変数：va_list 型、a 以降の引数リストを取得する

va_list arg;

- 関数
- - va_start：可変引数リストの最初の引数の位置に位置付ける

va_start (arg, n); //n は可変引数リストの前の変数

- - va_arg：次の型に一致する式を返す

va_arg(arg, int);

- - va_end：可変関数の実引数の遍歴を終了し、va_list の空間をクリアする

va_end(arg);

コード
詳細は注釈を参照し、ヘッダーファイル、va_arg 型の一致、最大遍歴回数、va_end のクリア、int の最小値を含む
どのメソッドがどのヘッダーファイルにあるかわからない場合、gcc コンパイルを使用すると、必要なヘッダーファイルを含めるように指示されることがある

ただし、私のマシンの Xshell では - Wall を使用しても表示されず、教師は Mac を使用している

授業中の練習#

コード

負の数の入力を考慮していないが、重要ではない～

コードデモ#

簡易版 printf 関数の実装#

文字を出力する機能を実現する（0 から 1 のステップ）
1. putchar ('x') 関数：標準出力に文字 'x' を出力する
文字列出力機能："hello world" を出力し、成功した印刷文字数を返す機能を持つ

システムは自動的に文字列の末尾に '\0' を追加し、その十進値は 0 である；例：'a'→97
const 修飾子は、渡された文字列リテラルが変更されないようにするためであり、変更できない
- 追加しない場合、C では警告が出ないが、C++ では警告が出ることがある、以下のように：
- さらに：char *const frm
  - frm ポインタを変更できない（例：char *p; frm = p;）、ただしそのポインタが指す内容は変更できる
  - const char * 、char const *、 char *const の違い-CSDN を参照
文字ポインタで文字列の i 番目の値を取得するには、二つの方法がある
- frm[i]
- *(frm + i)

% d を制御文字として有効にし、整数を出力する
1. 画面に '%' を出力する

- switch 構造を使用
- break の前にはカンマではなく、セミコロンが必要
1. 画面に正の整数 123 を出力する
- 二つの while ループを通じて、数字を反転させて再度出力する
  - 反転しない場合、低位から出力することしかできない
- 数字 + 文字 '0'（つまり 48）を使用して、数字を文字に変換して出力する
- ❌整数 0 を出力できない
1. 画面に正の整数 0 を出力する
do...while と while の違い
❌正の整数 1000 の場合、出力は 1 になる
1. 画面に正の整数 1000 を出力する
数字の桁数を記録し、0 値を考慮し、do...while 方式に変更する
二回目の反転は do...while (--digit) を使用できる
- ただし、digit が 0 のときに無限ループに陥るのを避けるため、while (digit--) を先に判断する方が安全
- digit が 0 になることはほとんどない
❌誤ったサンプル
digit-- のとき、数字 1000 を出力すると、桁が一つ多くなる
- --digit では無限ループに陥る可能性があり、無限に 0 を出力する
  - 入力が 0 の場合、記録された数字の桁数は 0（下記参照）となり、--digit は - 1 になる
最初の while ループで 0 の桁数を計算するとき、0 になってしまう、誤り！
❌負の整数の場合、出力に誤りがある！
1. 画面に負の整数 - 123 を出力する
負数の判断を追加するだけでよい
❌INT32_MAX、INT32_MIN の場合、出力に誤りがある！
1. 画面に INT32_MAX (2^31 - 1)、INT32_MIN (-2^31) を出力する
INT32_MAX を反転すると、int 型では表現できない→ブロック反転
- 5 桁ごとに二つの部分に分け→それぞれを反転→それぞれを出力
- 24174 / 83647 →47142 / 74638 →24174 83647
- コード
  - rev_num は temp1 のアドレスを渡すことで、その値を変更できるようにする
  - output_num で行う戻り桁数操作は、digit1、2 から直接得られると思う
  - 高 5 桁、低 5 桁の実際の桁数を修正することを忘れない
  - rev_num と output_num 関数は以下の通り：
    - * output_num内のPUTCは機能しない、コンパイル時にその順序がPUTCの定義の前にあることを考慮する
  - ❌INT32_MIN の場合、出力にまだ誤りがある！
この時点で INT32_MIN の出力はまだ正しくない、なぜなら
INT32_MIN の負数はそれ自体であり、正数は表現できない
- 負数の絶対値は正数より大きい
- INT32_MIN：1000...000
  - →⭐相反数を求める：反転 + 1→0111...111 + 1
  - →1000...000（それ自体）
- コード
  - 符号なし整数型uint32_tを使用して保存すればよい！

% s を制御文字として有効にし、文字列を出力する

とても簡単で、case を一つ追加するだけでよい
- 注意：リテラルは const char * を使用すること

戻り値機能を検証する

追加知識#

K&R スタイルの関数定義
- 引数リスト内の引数の宣言を後ろに置いている
- 古いスタイルの書き方で、理解するだけでよい、使用は推奨しない
% g 制御文字を使用すると、より親しみやすい方法で数字の有効桁を出力できる
配列：展開された関数；関数：圧縮された配列
int と long の違い- 簡書
- 異なるビット数のシステムでサイズが異なる
- long -> 32 ビット：4 バイト；64 ビット：8 バイト
- ただし int はすべて 4 バイト、long long はすべて 8 バイト
アルゴリズムとは？賢い人の仕事の方法
⭐while(~scanf("%d\n", &a))
- while (scanf ("% d\n", &a) != EOF) は while (~scanf ("% d\n", &a)) で置き換えることができる
- ~ はビット反転で、EOF は - 1 であり、ビット反転は 0 になる
undef マクロ定義では、マクロ名を追加するだけで、パラメータは必要ない、例えば：

#define PUTC(a) putchar(a)
#undef PUTC

⭐二進数で相反数を求める：反転 + 1
- 正負に関わらず、互いに逆であり、二回この操作を行うと元に戻る
- -1 と再び反転するのと同じ

思考点#

💡va_arg は型が一致しない場合、どのように処理されるのか？
- 出力には二つの問題がある：
  - 一行目、最初の int 値が取得できないとき、出力は 0.000000 であり、二回目は nan になる？
  - 三行目、入力がすべて int 型であるが、二番目の数字：3.000000 を取得している、実験により、この数字は二行目の 3.000000 に関連しており、va_list がきれいにクリアされていないのか？
- ❓どの型がどれだけの長さのアドレスを後ろに進めて値を取得するのか
  - 例えば double は、後ろに 8 バイトの対応する変数を取得する
- 💡しかし、上書きや未クリアの問題については、説明できない～
- va_list のアドレスを印刷できればさらに良い～

ヒント#

OJ を解いてみる
参考書第 7 章を参照