アルゴリズムコンテスト入門経典紫書第四章
35369 ワード
ちょっとした問題
素数を判断する点について
グローバル変数を慎重に使用
呼び出しスタック
呼び出しスタックは、関数間の呼び出し関係が複数のスタックフレームから構成され、各スタックフレームは、実行されていない関数スタックフレームに対応して、その関数の戻りアドレスとローカル変数が保存されているため、実行が完了した後に正しい戻りアドレスを見つけることができるだけでなく、また、異なる関数間で異なるスタックフレームに対応するため、異なる関数間の局所変数が互いにコヒーレントでないことも自然に保証される.
針がひっくり返りやすい
これは間違ったプログラムです
このプログラムエラーの原因は、ポインタtが使用される前にtを付与しなければならないことであり、付与する前に不確定である.この不確定な値が表すメモリユニットが適切に書き込まれている場合、このプログラムは正常に動作します.しかし、そうではなく読み取り専用であれば、プログラムがクラッシュする可能性があります.
配列はパラメータとしてひっくり返りやすい
これにはエラーのプログラムがあります.
エラーの原因:sizeof(a)は配列の大きさが得られないため,配列がパラメータとして関数に渡されると,実際には配列のヘッダアドレスのみがポインタとして関数に渡される.関数定義におけるint a[]はint*aに等しい.アドレス情報のみの場合、配列にどれだけの要素があるかを知ることができない正しい方法です.パラメータ、すなわち配列の要素の個数を追加します.
一般に、pがポインタであり、kが正の整数である場合、p+kはポインタpの後ろのk番目の要素であり、p-kはpの前のk番目の要素であり、p 1とp 2がタイプが同じポインタである場合、p 2-p 1はp 1からp 2までの要素の個数である
では、配列和を計算する関数について2つの書き方を用いることができます.1.
上記の2つの書き方はいずれも左閉右開の2つ目の書き方が一般的に配列をポインタとして関数に渡す場合,配列内容は修正可能である.「配列を返す」関数を書く場合は、配列パラメータを追加し、関数で配列の内容を変更できます.
再帰
C言語の関数では、呼び出し自体と他の関数を呼び出すことに本質的な違いはありません.新しいスタックフレームを作成し、パラメータを渡し、現在のコード行を変更します.関数体の実行が完了した後、スタックフレームを削除し、戻り値を処理し、現在のコード行を変更します.
セグメントエラー
コンパイル後に生成された実行可能ファイルには、オペレーティングシステムに関連するコンテンツが保存されています.セグメント.バイナリファイル内の領域を指し、特定のタイプの情報がすべて保存されます.
実行可能ファイルでは、本文セグメントは、初期化されたグローバル変数BSSセグメントを格納するために命令データセグメントを格納するために使用され、割り当てられていないグローバル変数を格納するために必要な空間
呼び出しスタックは実行可能ファイルに格納されず、実行時に呼び出しスタックが作成されるセグメントをスタックセグメントと呼ぶスタックセグメントにも独自のサイズがあり、境界を越えてアクセスできません.そうしないと、セグメントエラーが発生します.
スタックオーバーフローは、再帰呼び出しのたびに呼び出しスタックにスタックフレームを追加し、長い間、境界を越えています.
実行時に、プログラムは動的にスタックセグメントを作成し、呼び出しスタックが格納されるため、関数の呼び出し関係とローカル変数が保存されます.
ローカル変数もスタックセグメント内に格納されます.スタックオーバーフローは必ずしも再帰呼び出しが多すぎるわけではありません.ローカル変数が大きすぎる可能性もあります.そのため、私たちは一般的に大きな配列をmain関数の外に格納します.
例題
例題4-1古いパスワードUVa 1339
qsortはアルゴリズムコンテストではよく使われないsort関数ですここでは「一つの関数をパラメータとして別の関数に渡す」ことを教えるのに役立ちます
例題4-2人斬りゲームUVa 489まず考えてみましょう.プログラム設計の方法は一般的に2種類あります.トップダウンとボトムアップアルゴリズムコンテストでは、トップダウンが一般的です.すなわち、擬似コードを先に書き、実際のコードに変換してメインプログラムを先に書き、関数の呼び出しを含め、関数自体を実現します.
この問題は何の難点もありません.ただ注意すればコードの注釈ができると言っています.私はあまり簡単に書きたくありません.
例題4-3救済金支給UVa 133という注意すべき点がループの扱い方であるこれはジョセフループの進級版とする
例題4-4情報復号UVa 213ブック上のコード:
練習問題
習題4-1 UVa 1589習題4-2 UVa 201習題4-3 UVa 220習題4-4 UVa 253習題4-5 UVa 1590習題4-6 UVa 508習題4-7 UVa 509習題4-8 UVa 12108習題4-9 UVa 1591習題4-10 UVa 815習題4-11 UVa 1588習題4-12 UVa 11809
素数を判断する点について
// ：
// n==1 n
// n int ：
// i=46340 ，i*i=2147395600
// i=46341 ，i*i=2147488281 int ， ，
int is_prime(int n)
{
for (int i = 2; i * i <= n; i++)
{
if (n % i == 0)
return 0;
}
return 1;
}
// ，
//
// ： sqrt(n)
//
int is_prime(int n)
{
if (n <= 1)
return 0;
int m = floor(sqrt(n) + 0.5);
for (int i = 2; i<=m; i++)
{
if (n % i == 0)
return 0;
}
return 1;
}
グローバル変数を慎重に使用
呼び出しスタック
呼び出しスタックは、関数間の呼び出し関係が複数のスタックフレームから構成され、各スタックフレームは、実行されていない関数スタックフレームに対応して、その関数の戻りアドレスとローカル変数が保存されているため、実行が完了した後に正しい戻りアドレスを見つけることができるだけでなく、また、異なる関数間で異なるスタックフレームに対応するため、異なる関数間の局所変数が互いにコヒーレントでないことも自然に保証される.
針がひっくり返りやすい
これは間違ったプログラムです
void swap(int* a, int* b)
{
int* t;
*t = *a;
*a = *b;
*b = *t;
}
このプログラムエラーの原因は、ポインタtが使用される前にtを付与しなければならないことであり、付与する前に不確定である.この不確定な値が表すメモリユニットが適切に書き込まれている場合、このプログラムは正常に動作します.しかし、そうではなく読み取り専用であれば、プログラムがクラッシュする可能性があります.
配列はパラメータとしてひっくり返りやすい
これにはエラーのプログラムがあります.
int sum(int a[])
{
int ans = 0;
for (int i = 0; i < sizeof(a); i++)
{
ans += a[i];
}
return ans;
}
エラーの原因:sizeof(a)は配列の大きさが得られないため,配列がパラメータとして関数に渡されると,実際には配列のヘッダアドレスのみがポインタとして関数に渡される.関数定義におけるint a[]はint*aに等しい.アドレス情報のみの場合、配列にどれだけの要素があるかを知ることができない正しい方法です.パラメータ、すなわち配列の要素の個数を追加します.
一般に、pがポインタであり、kが正の整数である場合、p+kはポインタpの後ろのk番目の要素であり、p-kはpの前のk番目の要素であり、p 1とp 2がタイプが同じポインタである場合、p 2-p 1はp 1からp 2までの要素の個数である
では、配列和を計算する関数について2つの書き方を用いることができます.1.
int sum(int* begin, int* end)
{
int n = end - begin;
int ans = 0;
for (int i = 0; i < n; i++)
{
ans += begin[i];
}
return ans;
}
int sum(int* begin, int* end)
{
int* p = begin;
int ans = 0;
for (int* p = begin; p != end; p++)
{
ans += *p;
}
return ans;
}
上記の2つの書き方はいずれも左閉右開の2つ目の書き方が一般的に配列をポインタとして関数に渡す場合,配列内容は修正可能である.「配列を返す」関数を書く場合は、配列パラメータを追加し、関数で配列の内容を変更できます.
再帰
C言語の関数では、呼び出し自体と他の関数を呼び出すことに本質的な違いはありません.新しいスタックフレームを作成し、パラメータを渡し、現在のコード行を変更します.関数体の実行が完了した後、スタックフレームを削除し、戻り値を処理し、現在のコード行を変更します.
セグメントエラー
コンパイル後に生成された実行可能ファイルには、オペレーティングシステムに関連するコンテンツが保存されています.セグメント.バイナリファイル内の領域を指し、特定のタイプの情報がすべて保存されます.
実行可能ファイルでは、本文セグメントは、初期化されたグローバル変数BSSセグメントを格納するために命令データセグメントを格納するために使用され、割り当てられていないグローバル変数を格納するために必要な空間
呼び出しスタックは実行可能ファイルに格納されず、実行時に呼び出しスタックが作成されるセグメントをスタックセグメントと呼ぶスタックセグメントにも独自のサイズがあり、境界を越えてアクセスできません.そうしないと、セグメントエラーが発生します.
スタックオーバーフローは、再帰呼び出しのたびに呼び出しスタックにスタックフレームを追加し、長い間、境界を越えています.
実行時に、プログラムは動的にスタックセグメントを作成し、呼び出しスタックが格納されるため、関数の呼び出し関係とローカル変数が保存されます.
ローカル変数もスタックセグメント内に格納されます.スタックオーバーフローは必ずしも再帰呼び出しが多すぎるわけではありません.ローカル変数が大きすぎる可能性もあります.そのため、私たちは一般的に大きな配列をmain関数の外に格納します.
例題
例題4-1古いパスワードUVa 1339
//qsort
void qsort(void* base, size_t num, size_t size, int (*comparator)(const void*, const void*))
//qsort
// ：
//
//
//
// ，
int cmp(const void *,const void *) {...}
// ,const void * ：
// ，
// ， ， ：
int cmp(const void* a, const void* b)
{
return *(int*)a - *(int*)b;
}
// ， a b ， cmp ab ，0， 。
qsortはアルゴリズムコンテストではよく使われないsort関数ですここでは「一つの関数をパラメータとして別の関数に渡す」ことを教えるのに役立ちます
例題4-2人斬りゲームUVa 489まず考えてみましょう.プログラム設計の方法は一般的に2種類あります.トップダウンとボトムアップアルゴリズムコンテストでは、トップダウンが一般的です.すなわち、擬似コードを先に書き、実際のコードに変換してメインプログラムを先に書き、関数の呼び出しを含め、関数自体を実現します.
この問題は何の難点もありません.ただ注意すればコードの注釈ができると言っています.私はあまり簡単に書きたくありません.
#include
", rnd);
win = lose = 0;
left = strlen(s);
chance = 7;
for (int i = 0; i < strlen(s2); i++)
{
guess(s2[i]);
if (win || lose)
break;
}
if (win)
printf("You win.
");
else if (lose)
printf("You lose.
");
else
printf("You chickened out.
");
}
return 0;
}
例題4-3救済金支給UVa 133という注意すべき点がループの扱い方であるこれはジョセフループの進級版とする
int go(int p, int d, int t)
{
while (t--)
{
do
{
p = (p + d + n - 1) % n + 1; // 、
}while (a[p] == 0); // 0
}
return p;
}
例題4-4情報復号UVa 213ブック上のコード:
#include
' && ch != '\r')
return ch; //
}
}
//readint 01
int readint(int c) // c ，
{
int v = 0;
while (c--)
{
v = v * 2 + readchar() - '0';
}
return v;
}
int code[8][1 << 8];
int readcodes() // ，
{
memset(code, 0, sizeof(code)); //
code[1][0] = readchar(); //
for (int len = 2; len < 7; len++) //len ，len=2， 00,01，10
{
for (int i = 0; i < (1 << len) - 1; i++) // ， len=2 ， ， (1<
{
int ch = getchar(); //
if (ch == EOF) // ，
return 0;
if (ch == '
' || ch == '\r') //
return 1;
code[len][i] = ch; // 。 01， 2 ， 2 ；10 2 ， 3
}
}
return 1;
}
int main()
{
while (readcodes()) // ，
{
for (;;)
{
int len = readint(3); // ，
if (len == 0) // ， 000
break;
for (;;)
{
int v = readint(len);
if (v == (1 << len) - 1) // 1 ， 。
break;
putchar(code[len][v]);
}
}
putchar('
');
}
return 0;
}
練習問題
習題4-1 UVa 1589習題4-2 UVa 201習題4-3 UVa 220習題4-4 UVa 253習題4-5 UVa 1590習題4-6 UVa 508習題4-7 UVa 509習題4-8 UVa 12108習題4-9 UVa 1591習題4-10 UVa 815習題4-11 UVa 1588習題4-12 UVa 11809