- 追加された行はこの色です。
- 削除された行はこの色です。
[[若田部]]
構造化されたプログラミング言語の基本要素を,僕なりに形式・意味の両面から分析し、まとめたもの。
また、コーディングテクニックの域は逸脱するが、問題の見方についても言及する。
[[若田部/アルゴリズム|アルゴリズムとデータ構造まとめはこちら]]
[[若田部/STL|STLはこちら]]
[[若田部//_プロコン戦記|プログラミングコンテストの記録はこちら]]
<comments />
== ループ==
-for (int i = 0; i < NUM; i++)について。
-色んな見方が出来る。
-形式的にはプログラムポインタが順々に回るという見方だけ、これだけでプログラミングするのは相当辛かった。
-ということで、意味的に考えられないかなぁと模索する。
--意味論的考察なので、極めて当然のことを書いているし、整理としては理系的に体系化されたものというより、僕の頭の中の整理ってだけ。
-なお大局的とは、
for (int i = 0; i < NUM; i++) {
[expression]
}
-をfor文の外部から見ることを表し、局所的とは上のうちのexpressionを主体とした時のiの役割を考えていることを表す。
*反復（大局的） [#s8a4dfcd]
-局所的に見ると視点固定。
-i個の動作を全て記述するのが面倒だからfor文を使う、というもの。
-非常に当たり前のfor文の見方。
-簡単な初期化や、Σ、複数の変数への代入など単純なループ。
int i;
int a[10];
for (i = 0; i < 10; i++)
a[i] = i;
*視点固定（局所的） [#s4404d5e]
-大局的に見ると反復、全探索。
-例えば、行列演算を見る。ここでループ変数i, jは行列のうち注目する変数を行列cのi行j列に限定し、視点を固定する役割を持つ。
for (i = 0; i < N; i++) {
for (j = 0; j < N; j++) {
for(k = 0; k < N; k++) {
c[i][j]+=a[i][k]-b[k][j];
}
}
}
--なお、kループ内はi,j固定すれば直感的に分かりやすく、大局的に反復として見る事ができる。
--「Cのi行j列に注目する。この時、内積を取るためにkを動かしながら反復して積を足していく。」という風に読めるようになる。
-この見方が出来ると、上の解釈のように、頭の中で動く変数の数を劇的に抑えられる。
*全探索（大局的） [#w438c455]
-局所的に見ると視点固定。
-「考えられる状態全ての可能性を見る」の見方。
-こんな問題を想定。card[5] = {1, 3, 4, 7, 17};なる数が記載された5枚のカードがある。これから一枚引いて元に戻す操作を4回行い、その和がkになりえるか？
int flag = 0;
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 5; j++) {
for (int h = 0; h < 5; h++) {
for (int k = 0; k < 5; k++) {
if (card[i] + card[j] + card[h] + card[k] == k) {
flag = 1;
break;
}
}
}
}
}
return flag;
--今、4回それぞれにつき5枚のパターンがあったので、探索空間は5^4である。
--外部からは、上のプログラムは「ただその探索空間全てを見るための変数を4個張った」、という見方が出来る。
--「4回引いた時のカードの組み合わせ」状態を4変数で表現しただけに過ぎない。
-この見方ができると、複数のforループを同じ「全探索」一つに見ることができて、強力。
-上にも書いたが、局所的に見ればループ変数i,j,h,kが決まり、視点が固定された世界でif文を行っているようにも解釈できる。
--つまり、「今i, j, h, kの番号のカードが既に置いてある。これを足してkになれば万々歳だねbreak」という見方も出来る。
--しかし、この場合は目的からして全探索として見た方が綺麗だと思う。
=*最大最小=
-全探索の亜種
-最大最小とは、考えられる状態全ての可能性のうち、最も評価値が高いor低いもの、という意味なので全探索として見れる。
-上の問題の条件で、4枚のカードの合計が最も10に近くなるi, j, h, kの組の一つを求めよ、という場合、
int min_i, min_j, min_h, min_k;
int min_ijhk_val = INF;
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 5; j++) {
for (int h = 0; h < 5; h++) {
for (int k = 0; k < 5; k++) {
int ijhk_val = ABS(card[i] + card[j] + card[h] + card[k] - 10);
if (min_ijhk_val > ijhk_val) {
min_ijhk_val = ijhk_val;
min_i = i; min_j = j; min_h = h; min_k = k;
}
}
}
}
}
return flag;
--と、全探索空間を張るi,j,h,kに対応するijhk_val=f(i, j, h, k)の最小化を行えば良い。
-なお、最小最大問題は普通配列などに格納されているものを使うので、以下のように書くと可視性が良くなる。
int min_i, min_j, min_h, min_k;
int min_ijhk_val = INF;
for (int i = 0; i < 5; i++)
for (int j = 0; j < 5; j++)
for (int h = 0; h < 5; h++)
for (int k = 0; k < 5; k++)
if (min_ijhk_val > ABS(card[i] + card[j] + card[h] + card[k] - 10))
min_ijhk_val = ABS(card[min_i = i] + card[min_j = j] + card[min_h = h] + card[min_k = k] - 10);
return flag;
== 量化記号==
-「全てのi, jについてP(i, j)を満たす」(<math>\forall</math>), 「P(i, j)を満たすi, jが存在する」(<math>\exists</math>)の条件式の実装について。
-直感的に実装可能で、かつ可読性の高い実装方法について考える。
*全称記号 [#n4aa1184]
-n変数で<math>\forall a_i P(a_1, a_2, .., a_n)</math>なる条件式を実装する方法について書く。
-<math>\forall \phi = T</math>なので、初期化はfaf = 1とする。
-全探索をかけて、一個でもNGなら全称はNGなので、fafを0にして全部breakする。
--ここで、初めのループではif (!P(a)) の中でbreakすることも出来るけど、他のところとの整合性的な観点から、if文は僕は分けます(下例の16行目と18行目)。
-例, <math>\forall</math> i, j in [1, NUM] (x[i] + y[j]) % 2 == 0
-[https://robotich.ddns.net/svn/tmp/wakatabe/cpractice/forall.cpp https://robotich.ddns.net/svn/tmp/wakatabe/cpractice/forall.cpp]
#include <iostream>
#define NUM 6
int main(int argc, char --argv)
{
int x[NUM] = {1, 2, 3, 4, 5, 6};
int y[NUM] = {1, 2, 3, 4, 5, 6};
/----------------------------------------------------------------------/
// for all i, j in [1, NUM], (x[i] + y[j]) % 2 == 0 ? faf = 1 : faf = 0;
/----------------------------------------------------------------------/
int faf = 1; // for all flag
for (int i = 0; i < NUM; i++) {
for (int j = 0; j < NUM; j++) {
// cont-condition
if (!((x[i] + y[i]) % 2 == 0))
faf = 0;
if (!faf)
break;
}
if (!faf)
break;
}
std::cout << faf << std::endl;
return 0;
}
*存在記号 [#j28f00d5]
-n変数で<math>\exists a_i P(a_1, a_2, .., a_n)</math>なる条件式を実装する方法について書く。
-<math>\exists \phi = F</math>なので、初期化はtef = 0とする。
-全探索をかけて、一個でもOKならOKなので、tefを1にして全部breakする。
--ここで、初めのループではif (P(a)) の中でbreakすることも出来るけど、他のところとの整合性的な観点から、if文は僕は分けます(下例の16行目と18行目)。
-例, <math>\exists</math> i, j in [1, NUM] (x[i] + y[j]) % 3 == 0
-[https://robotich.ddns.net/svn/tmp/wakatabe/cpractice/thereexists.cpp https://robotich.ddns.net/svn/tmp/wakatabe/cpractice/thereexists.cpp]
#include <iostream>
#define NUM 6
int main(int argc, char --argv)
{
int x[NUM] = {1, 2, 3, 4, 5, 6};
int y[NUM] = {1, 2, 3, 4, 5, 6};
/----------------------------------------------------------------------/
// there exists i, j in [1, NUM], (x[i] + y[j]) % 3 == 0 ? tef = 0 : tef = 1;
/----------------------------------------------------------------------/
int tef = 0; // there exists flag
for (int i = 0; i < NUM; i++) {
for (int j = 0; j < NUM; j++) {
// condition
if ((x[i] + y[i]) % 3 == 0)
tef = 1;
if (tef)
break;
}
if (tef)
break;
}
std::cout << tef << std::endl;
return 0;
}
*全称記号(1変数の場合) [#s14c3d0d]
-1変数の場合、より早く実装出来る方法について書く。
-全探索をかけて、一個でもNGならbreakする。
--すると、ループが最後まで回ったかどうかをチェックすることで、fafを判定することができる。
-例, <math>\forall</math> i in [1, NUM] (x[i] + y[i]) % 2 == 0
-[https://robotich.ddns.net/svn/tmp/wakatabe/cpractice/forall_one.cpp https://robotich.ddns.net/svn/tmp/wakatabe/cpractice/forall_one.cpp]
#include <iostream>
#define NUM 6
int main(int argc, char --argv)
{
int x[NUM] = {1, 2, 3, 4, 5, 6};
int y[NUM] = {1, 2, 3, 4, 5, 6};
/----------------------------------------------------------------------/
// for all i in [1, NUM], (x[i] + y[i]) % 2 == 0 ? faf = 1 : faf = 0;
/----------------------------------------------------------------------/
int i;
for (i = 0; i < NUM; i++) {
// cont-condition
if (!((x[i] + y[i]) % 2 == 0))
break;
}
int faf = (i == NUM);
std::cout << faf << std::endl;
return 0;
}
*存在記号 [#b3309d29]
(1変数の場合) [#a33f4556]
-1変数の場合、より早く実装出来る方法について書く。
-全探索をかけて、一個でもOKならbreakする。
--すると、ループが最後まで回ったかどうかをチェックすることで、tefを判定することができる。
-例, <math>\exists</math> i in [1, NUM] (x[i] + y[i]) % 7 == 0
-[https://robotich.ddns.net/svn/tmp/wakatabe/cpractice/thereexists_one.cpp https://robotich.ddns.net/svn/tmp/wakatabe/cpractice/thereexists_one.cpp]
#include <iostream>
#define NUM 6
int main(int argc, char --argv)
{
int x[NUM] = {1, 2, 3, 4, 5, 6};
int y[NUM] = {1, 2, 3, 4, 5, 6};
/----------------------------------------------------------------------/
// there exists i in [1, NUM], (x[i] + y[i]) % 7 == 0 ? tef = 0 : tef = 1;
/----------------------------------------------------------------------/
int i;
for (i = 0; i < NUM; i++) {
// condition
if ((x[i] + y[i]) % 7 == 0)
break;
}
int tef = (i != NUM);
std::cout << tef << std::endl;
return 0;
}
== 前進的隣接二項関係から生成されるまとまり==
#include <stdio.h>
#define NUM 9
// 前進的な隣接二項関係を規定するものとする
// 先を見るイメージで実装
int main(void)
{
int a[NUM] = {1, 2, 2, 2, 2, 2, 3, 4, 4};
int count = 0;
for (int l = 0; l < NUM; l++) {
int tmpl = l;
// 先に進めることが出来て、先に進めるべき時なら
while (l < NUM - 1 && a[l] + 1 == a[l+1])
l++;
for (int i = tmpl; i <= l; i++)
printf("%d ", a[i]);
printf("\n");
count++;
}
printf("count: %d\n", count);
return 0;
}
-output
1 2
2
2
2
2 3 4
4
count: 6
== 問題の見方==
*要求される情報の量 [#fc851606]
-どれくらいの量の情報を求められているのか？
--多ければ、全探索などナイーブなアルゴリズムになりやすい。
--少なければ、色々な同一視を駆使することが出来る。
---プロコンでは、少ない情報しか聞かない問題ほど、全探索では計算が間に合わないものを出してくることが多い。
-yes-no
--相当情報を削ってもいいはず。
--同一視をガンガン考え、他の見方と組み合わせる。
-最大値問題
--全探索や、DPや、逆像的二分探索など。
-解の個数
--全探索や、DPや、逆像的二分探索など。
*データの見方 [#e787d30d]
-操作ステップを引数とした関数
--ステップの前後で変わらない、もしくは何らかの規則性がある(e.g. 0, 1, 0, 1, ...)
--<math>\Sigma a[i]</math>など
-データ列に順序は関係あるか。
--ないならソートしても一般性を失わない。
-<math>\Sigma a[i]</math>なる数列
--a[i] >= 0, a[i] <= 0なら単調性が保証される。
--<math>\Sigma a[i] - \Sigma a[j-1]</math>によって、jからiまで足した数列を得る。
*特性関数の作りやすさ [#md3fb115]
-「このinputはこの問題の答えですか？」というyes-noクエッションに答えられるか？
--少し変形がいるが、かなり基本的な問題である。
=*yes-no=
-全てのinputに対して、「このinputはこの問題の答えですか？」という質問に対して答えられるとする。
--そうすれば、inputの全てを探索することで、yes-noを判別することが出来る。
=*最大最小問題=
-「Pの時、xの最大値を求めよ」という問題に対しても、特性関数が役に立つことがある。
-逆問題として、x<=maxの時は必ずそれに対応するPが存在し、x>maxの時は必ずそれに対応するPが存在しない。
--つまり、「この解の候補xに対応するPを満たすinputが存在しますか？」という質問に対する答えがyesならx<=maxで、noならx>maxである。
-yes-noの時と同様に、解の候補xに対して全てを探索し、上の条件を満たすものが存在する最も大きいものを見つければ、そのxが最大である。
-さらに逆問題の特性関数として、「この解の候補x以上に対応するPを満たすinputが存在しますか？」という問題を考える。
--xに対してmaxの周辺で
P(x): 11111111111111111110000000000000000000
-のように、ある値を境にそれ以前が1, その後が0になるはずである。
-このような特性関数を実装することが出来るのならば、xに対して二分探索を用いることで、xの最大値を計算することが出来る。
--このようなPを選んで二分探索を行うことを、勝手に逆像的二分探索と呼んでいる。
* 境界条件 [#r7e77234]
-特異なinputに対して、そこだけ正しいoutputを吐かない、ということがありえる。
-このようなinputに対応できる能力は、完璧で瀟洒なプログラマには不可欠。
-まずこのような特異入力が発生しうる条件としては、以下のようなものが挙げられる。
--数学的ま場合分け（0で割るなど）
--アルゴリズムの原始的順像における前提
-数学的な場合分けについては、数学の論理をちゃんと展開すればいいのでそんなに問題にはならない。
-アルゴリズムの原始的順像の問題については、問題に対していい加減なアプローチを試す段で、思考が限定されることにより起きる。
--思考が束縛される前に、trivialなinput-outputの組をいくつか考えておいて、それを満たすかを作ったアルゴリズムが対応できているかをCheckする。
--ここで考えられないようなinputが特異になるようでは、アルゴリズムが残念だというスタンス。
-逆に言えば、今考えたtrivialなinputは除外して考えることが出来るということ。
-また、アルゴリズムを見て、何でミスりそうかを考えるのもありだが、これは大変なのでおすすめできない。
--上に書いたことで何とかケリをつけたいですね。
-結局何が言いたいかというと、増えた条件としてのtrivialな条件を境界条件の候補とみなすしかないのでは、ということ。
--これで問題ないとすると、本当であれば関数の一番始めに、思いついたtrivialなinputを門前払いするのが一番安全。
--しかし、全ての思いついた条件を門前払いするのは頭が悪いので、アルゴリズムが実装し終わった後にtrivialなinputで通るかtestするのがいいでしょう。
== 再帰関数==
*再帰関数の妥当性チェック [#p01b64c5]
-再帰関数のテストデータの作り方と、そのデバッグの仕方について。
-再帰関数のテスト関数は、(1) 一回ですぐreturnするもの (2) 一回再帰して返るもの (3) 出来るなら二回以上再帰するもの の三つでチェックする。
// n!
int frac(int n, int input)
{
if (n == 0)
return 1;
return n - frac(n - 1);
}
-この場合、frac(0), frac(1), frac(4)くらいでチェックするのが妥当である。
*再帰関数のデバッグ [#za9c001f]
#include <iostream>
using namespace std;
#define MAP_SIZE 16
int map[MAP_SIZE] = {0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, };
void rm_map_part(int index)
{
if (index < 0 || index >= MAP_SIZE || !map[index])
return;
map[index] = 0;
rm_map_part(index - 1);
rm_map_part(index + 1);
}
int main(void)
{
rm_map_part(3);
for (int i = 0; i < MAP_SIZE; i++)
cout << map[i];
cout << endl;
return 0;
}
-mapを再帰的に、1の帯を全て埋める関数を考える。
--ここの話題とは関係ないが、再帰関数は(1)終端条件(2)操作(3)再帰呼び出しの順に書くとやりやすい。
--再帰呼び出しではあまりゴタゴタとif文を書かず、終端条件で弾いた方が思考回路的に楽。
-このような関数について、例えばどこでどのように操作が行われているのかを知りたいとする。
--しかし、このまま下のように表示すると、意味が分からないことになる。
void rm_map_part(int index)
{
if (index < 0 || index >= MAP_SIZE || !map[index])
return;
map[index] = 0;
cout << "index: " << index << endl;
rm_map_part(index - 1);
rm_map_part(index + 1);
}
mechuser@UoT-IST-Ub:~/tmp$ ./a.out
index: 11
index: 10
index: 9
index: 8
index: 7
index: 6
index: 5
index: 4
index: 3
index: 2
index: 12
index: 13
index: 14
index: 15
index: 16
index: 17
index: 18
index: 19
index: 20
index: 21
index: 22
index: 23
index: 24
-何が分からないかというと、どこのindexをやったあとに、どこのindexが呼ばれたのかが分からない。
--これに対処するために、以下のように再帰関数に一つ引数を追加してやることで、少し見通しのよいログが得られる。
--どこで何が呼ばれているのかがはっきりする。
void rm_map_part(int n, int index)
{
if (index < 0 || index >= MAP_SIZE || !map[index])
return;
for (int i = 0; i < n; i++)
cout << " ";
cout << "index: " << index << endl;
map[index] = 0;
rm_map_part(n + 1, index - 1);
rm_map_part(n + 1, index + 1);
}
mechuser@UoT-IST-Ub:~/tmp$ ./a.out
index: 11
index: 10
index: 9
index: 8
index: 7
index: 6
index: 5
index: 4
index: 3
index: 2
index: 12
index: 13
index: 14
index: 15
index: 16
index: 17
index: 18
index: 19
index: 20
index: 21
index: 22
index: 23
index: 24
== bit演算==
-低位Bitから0, 1, ...と名付けていく。
-基本操作関数
--bit-nをゲットする。(n < sizeofbit)
r = (a >> n) & 1;
--bit-nに1をセットする。(n < sizeofbit)
a |= 1 << n;
--bit-nを0をセットするn < sizeofbit)
a &= ~(1 << n);
-2^nに関する演算
--aを2^nで割った商を取得する。(n < sizeofbit, 負の場合答えが1減る。下の余りと対応している。
r = a >> n;
--aを2^nで割った余りを取得する。(n < sizeofbit, 負の余りも正で出る)
r = a & ~(-1 << n);
-例
#include <iostream>
using namespace std;
void print_bit(int a)
{
for (int i = 8; i >= 0; i--)
cout << (int)((a >> i) & 1);
cout << endl;
}
int main(void)
{
int a, n, r;
// bit-nをゲットする。
cout << "----get bit-n----" << endl;
a = 10, n = 2;
print_bit(a);
r = (a >> n) & 1;
cout << n << "-bit: " << r << endl;
cout << "----get bit-n----" << endl;
a = 10, n = 3;
print_bit(a);
r = (a >> n) & 1;
cout << n << "-bit: " << r << endl;
// bit-nに1をセットする。|=は1の部分を埋めるフィルタ
cout << "----set bit-n 1----" << endl;
a = 0, n = 2;
a |= 1 << n;
print_bit(a);
// bit-nに0をセットする。&=は1の部分だけ通すフィルタ。
cout << "----set bit-n 0----" << endl;
a = 0x04, n = 2;
a &= ~(1 << n);
print_bit(a);
// aを2^nで割った商を取得する。(0 <= n < SIZEOFINTBIT, -1 / 4 = -1など、普通の余りより1大きくなっている。下の余りと対応)
cout << "----/ 2^n----" << endl;
a = 11, n = 2;
r = a >> n;
print_bit(a);
print_bit(r);
cout << a << "/ 2^" << n << " = " << r << endl;
cout << "----/ 2^n----" << endl;
a = -11, n = 2;
r = a >> n;
print_bit(a);
print_bit(r);
cout << a << "/ 2^" << n << " = " << r << endl;
// aを2^nで割った余りを取得する。(0 <= n < SIZEOFINTBIT, 負の余りも正で出る)
cout << "----% 2^n----" << endl;
a = 11, n = 2;
r = a & ~(-1 << n);
print_bit(a);
print_bit(r);
cout << a << "% 2^" << n << " = " << r << endl;
cout << "----% 2^n----" << endl;
a = -13, n = 2;
r = a & ~(-1 << n);
print_bit(a);
print_bit(r);
cout << a << "% 2^" << n << " = " << r << endl;
return 0;
}
-output
----get bit-n----
000001010
2-bit: 0
----get bit-n----
000001010
3-bit: 1
----set bit-n 1----
000000100
----set bit-n 0----
000000000
----/ 2^n----
000001011
000000010
11/ 2^2 = 2
----/ 2^n----
111110101
111111101
-11/ 2^2 = -3
----% 2^n----
000001011
000000011
11% 2^2 = 3
----% 2^n----
111110011
000000011
-13% 2^2 = 3
== BFSとDFS==
-おなじみ幅優先探索と深さ優先探索．これらの構造と具体的な記述方法について
*戻り値ありの再帰によるBFS [#nb0a5050]
-漸化式のアナロジーで記述できる．
-引数を状態（=添字，データ，制限など）と見なして，これをより簡単な状態を用いて表す，というのが基本的な考え方．
-例えば，
a[] = {1, 2, 3, 4, 5};
f(i, a[], b[]) = [0番目からindex個までに対して∑a[b[i]]を確定した場合，0番目からNUM番目に対して∑a[f[i]]が100に最も近づく時の∑a[b[i]]]
-とかすれば，以下のようにfが記述出来る．
int rec(const int- a, int- f, int index)
{
if (index >= NUM) {
int sum = 0;
for (int i = 0; i < NUM; i++)
sum += a[i] - f[i];
return sum;
}
// index番目を取らない
int n = rec(a, f, index + 1);
// index番目を取る
f[index] = 1;
int p = rec(a, f, index + 1);
f[index] = 0;
return (abs(n - 100) > abs(p - 100)) ? p : n;
}
-問題は，これの一般化．
-今回，データ(const int- a)と状態(int i, int- f)について，どのように扱うかについて記述する．
-データは変更されえないので，constで書く．これは問題ない．
-状態は，実体で渡すことも，参照で渡すことも可能である．
--実体で渡す場合は特に気にすることはないが，メモリコピーなどに時間がかかり，どうしても遅くなってしまう．また，記述量も増える．これはやれば出来るので，以下には記述しない．
--indexはint型なので問題ないが，fのような配列を全て毎回コピーするのは骨が折れるかもしれない．
=*参照による引数渡し=
-参照を渡す場合，関数による再帰型であれば，'''子ノードを呼ぶ前に引数のお膳立てするときに気にせず書き換えて，子ノードから返って来たら即刻元の状態に戻す'''ことで参照を再帰に組み込むことが出来る．
--具体的には，//index番目を取るのf[index] = 1;とf[index] = 0;がそれに該当する．
-これによって，ノードの行き来の間，安全に参照を書き換えることが出来る．
=*枝刈り=
-戻り値を持つ再帰関数での枝刈りは少し面倒である．
--というのも，自分が枝刈りされる＝「自分が枝刈り条件に引っかかる」or「自分の子供全てが枝刈り条件に引っかかる」の２つが考えられるからである．
--後者は，stack型や，戻り値のない再帰と違って，親が子供を見放さないことによる性質である．
--すなわち，枝刈りには以下の２つの処理が必要である．
---「一番始めに枝刈り条件を適用して，戻り値として枝刈りされたことを親に知らせる」
---「子ノードを全て呼び終わった後に，それらが全て枝刈りされていれば，自分も枝刈りされたとして，戻り値として枝刈りされたことを親に知らせる」
=*まとめ=
-すなわち，以下のように記述するのが最も機械的，かつ安全に戻り値のある再帰を記述できる．
--(1) 引数を受け取る
--(2) 枝刈りを行い，枝刈りされるのであれば，枝刈りされた印を戻り値として返す．
--(3) 終端ノードであるかどうかを確かめる．終端ノードであれば，そのための処理を行い，戻り値を返す．
--(4) ここからは子ノードの数だけ，以下を呼び出す処理
---(4-a) 親から渡された引数から，子ノードに渡す引数を生成する．親の引数が，実体ならばコピーを作成して，参照ならば改変する．
---(4-b) 子ノードを呼出して，その戻り値をret_iとして保存する．
---(4-c) (4-a)で改変した参照を元に戻す．
--(5) 子ノードが全て枝刈りされていれば，自分も枝刈りされたと親に戻り値として返す．
--(6) ret_iを用いて，何らかの演算を行い，親に自分の返すべき値を返す．
-これらは構造を限定することで，省略可能な手続きが存在する．
--(4-c)は，引数が全て実体のとき，省略することが出来る．
--(5)は，戻り値が存在しない場合，省略することが出来る．
=*コード例=
int rec(const int- a, int- f, int index, int- available)
{
-available = AVAILABLE;
// 終端ノード条件
if (index >= NUM) {
int sum = 0;
for (int i = 0; i < NUM; i++)
sum += a[i] - f[i];
return sum;
}
// 枝刈り条件
int nsum = 0;
for (int i = 0; i < index; i++)
nsum += a[i] - f[i];
if (nsum > 100) {
-available = NOT_AVAILABLE;
return NOT_FOUND;
}
// index番目を取らない
int nav;
int n = rec(a, f, index + 1, &nav);
// index番目を取る
f[index] = 1;
int pav;
int p = rec(a, f, index + 1, &pav);
f[index] = 0;
// 子供が枝刈りされる時の条件
if (nav == NOT_AVAILABLE && pav == NOT_AVAILABLE) {
-available = NOT_AVAILABLE;
return NOT_FOUND;
}
if (n > 100 && p > 100)
return NOT_FOUND;
else if (n > 100)
return p;
else if (p > 100)
return n;
else
return max(p, n);
}
*stackとqueueによるDFSとBFS [#y06229d6]
-stackとqueueはDFSとBFSにそれぞれ対応している．
-特にstackは「全ての引数を実体で渡す，戻り値なしの再期関数」と同値な記述が可能である．
--上で記述したように，(4-c)(5)が省略され，すっきり書くことが出来る．
--むしろこっちの性質の方が僕の主張したいことである．
-こんな感じで記述する．枝刈りが一回しかなく，n.f[n.index]=1の後に=0と戻しておらず，戻り値でNOT_FOUNDが出てこないためコードが短くなっていることに注意．
class Node {
public:
int index;
int a[NUM];
int f[NUM];
Node(int index, int -a, int -f);
};
Node::Node(int index, int -a, int -f) {
this->index = index;
for (int i = 0; i < NUM; i++) {
this->a[i] = a[i];
this->f[i] = f[i];
}
}
int main(int argc, char-- argv)
{
int a[NUM] = {97, 2, 3, 4, 5, 6, 7, 8, 9, 10};
int f[NUM] = {};
queue<Node> st;
Node firstnode = Node(0, a, f);
st.push(firstnode);
int ret = 0;
while (!st.empty()) {
Node n = st.front(); st.pop();
// 枝刈り
int nsum = 0;
for (int i = 0; i < n.index; i++)
nsum += n.a[i] - n.f[i];
if (nsum > 100)
continue;
// 終端ノード
if (n.index >= NUM) {
int sum = 0;
for (int i = 0; i < NUM; i++)
sum += n.a[i] - n.f[i];
ret = (abs(100 - ret) > abs(100 - sum)) ? sum : ret;
continue;
}
// 取らない
Node no
de_n = Node(n.index + 1, n.a, n.f);
st.push(node_n);
// 取る
n.f[n.index] = 1;
Node node_p = Node(n.index + 1, n.a, n.f);
st.push(node_p);
}
cout << ret << endl;
return 0;
}
-ちなみに，これはDFSだが，vimを開いて以下のように打つだけでBFSとなる．
%s/stack/queue/g
%s/top/front/g
-DFSとBFSの違いは，FIFOかFILOかの違いだけなのだが，この辺はどこの教科書を見ても書いてあるので，書く意味はない．
*戻り値なし，実体引数のみの再帰 [#g8890797]
-これは，上のstackと全く同じ構造となる．
-オブジェクトや配列のコピーが存在する代わりに，枝刈り条件や戻り値の条件や参照の管理が必要なくなる点で楽である．
== 2分全探索==
-int型が2進数であることを利用して，以下のように「n個の中から任意個数の選択」を記述できる．
--本当に簡単に記述できるのでお勧め．上の再帰のものと全く同じ機能のプログラムだが，相当記述量が抑えられている．
int main(int argc, char-- argv)
{
int a[NUM] = {99, 2, 3, 4, 5, 6, 7, 8, 9, 10};
int maximum = 0;
for (int i = 0; i < round(pow(2, NUM)); i++) {
int sum = 0;
int tmpi = i;
for (int j = 0; j < NUM; j++, tmpi /= 2) {
if (!(tmpi & 1))
continue;
sum += a[j];
}
maximum = (abs(maximum - 100) > abs(sum - 100)) ? sum : maximum;
}
cout << maximum << endl;
return 0;
}
![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
