![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
若田部? 構造化されたプログラミング言語の基本要素を,僕なりに形式・意味の両面から分析し、まとめたもの。 また、コーディングテクニックの域は逸脱するが、問題の見方についても言及する。 若田部/アルゴリズム|アルゴリズムとデータ構造まとめはこちら? 若田部/STL|STLはこちら? 若田部//_プロコン戦記|プログラミングコンテストの記録はこちら?
== ループ==
反復（大局的） †
視点固定（局所的） †
全探索（大局的） †
=*最大最小=
== 量化記号==
全称記号 †
存在記号 †
全称記号(1変数の場合) †
存在記号 †(1変数の場合) [#a33f4556]
== 前進的隣接二項関係から生成されるまとまり== #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;
}
1 2 2 2 2 2 3 4 4 count: 6 == 問題の見方== 要求される情報の量 †
データの見方 †
特性関数の作りやすさ †
=*yes-no=
=*最大最小問題=
境界条件 †
== 再帰関数== 再帰関数の妥当性チェック †
// n!
int frac(int n, int input)
{
if (n == 0)
return 1;
return n - frac(n - 1);
}
再帰関数のデバッグ †#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;
}
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
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演算==
#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;
}
----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 †
a[] = {1, 2, 3, 4, 5};
f(i, a[], b[]) = [0番目からindex個までに対して∑a[b[i]]を確定した場合，0番目からNUM番目に対して∑a[f[i]]が100に最も近づく時の∑a[b[i]]]
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;
}
=*参照による引数渡し=
=*枝刈り=
=*まとめ=
=*コード例= 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 †
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;
}
戻り値なし，実体引数のみの再帰 †
== 2分全探索==
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;
}
|
