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 章を参照