アルゴリズムコンテスト入門経典第2章【読書ノート】

4737 ワード

【学習目標】
01 forループの使い方をマスター(OK)
02 whileサイクルの使い方をマスター(OK)
03学会使用カウンターとアキュムレータ(OK)
04中間結果を出力する方法でデバッグを習得(OK)
05計時関数でプログラム効率をテストすることを学ぶ(よく知らない)
06リダイレクトでファイルを読み書きすることを学ぶ(基本的にはできない)
07 fopenでファイルの読み書きを覚える(基本的にはできない)
08アルゴリズムコンテストのファイルの読み書き方法と命名の厳格性を理解する(うん)
09変数が付与される前の値が不確定であることを覚えておく(OK)
10学会使用条件コンパイル指示フレームワークローカル実行環境(いいえ)
P18
注意浮動小数点数の演算(浮動小数点数を返す関数を含む)に誤差がある可能性があります!
プログラムを作成して出力の数(n<10^9)が完全な平方数であるか否かを判断し、yesを出力し、そうでなければnoを出力する.
#include <stdio.h>
#include <math.h>

int
main(void)
{
	int n;
	double r;

	scanf("%d", &n);
	r = sqrt(n);//or r = sqrt((double)n);
	printf(floor(r+0.5) == r ? "yes
" : "no
"); return 0; }

for (i = 0; i != N; i++)
break;文がループを終了すると、i++は実行されますか?continueは?
#include <stdio.h>
#define N 100

int
main(void)
{
	int i;

	for (i = 0; i != N; i++) {
		if (i == 5)
			continue;
			
		if (i == 10)
			break;
	}
	printf("%d
",i); return 0; }

このプログラムを実行すると、出力は10になり、ループを終了するとi++が実行されないことを示し、continueが実行された後、i++が実行されなければ、必ず無限ループに陥る.だからi++は実行しなければなりません.
循環出口が実行されると、i++は二度と実行されないことがわかります.ループを継続(途中で継続または正常に継続)すると、i++は必ず実行されます.
05計時関数でプログラム効率をテストすることを学ぶ
#include <stdio.h>
#include <time.h>
int
main(void)
{	
	int n, i, j;
	clock_t star, end;
	
	scanf("%d", &n);
	star = clock();
	for (i = 0; i != n; i++)
		for (j = 0; j != n; j++)
			;
	end = clock();
	printf("%lf
", (double)(end-star) / CLOCKS_PER_SEC); //notice! is CLOCKS including 'S' return 0; }

このように書くと入力待ち時間も含めて定数CLOCKS_に注意PER_SECバンド「S」.
linuxでリダイレクト入力はecho 12321|./program_name
06リダイレクトでファイルを読み書きする
これは主に入力出力を1つのテキストに置くことができ、端末でテストデータを入力したり貼り付けたりすることができ、特にいくつかのマトリクスを入力したりするときに省くことができます.
次のデフォルトの入力ファイル名はtest.inで、出力ファイル名はtest.outです.
次に、n*nのマトリクス(n<=100)を入力し、マトリクスの回転マトリクスを出力するプログラムを書きます.
たとえば、
入力:
3
1 2 3
1 2 3
1 2 3
出力:
1 1 1
2 2 2
3 3 3
(注:各行の最後の要素の後ろにスペースがありません)
【通常版】
#include <stdio.h>
#define N 110
int a[N][N];

int
main(void)
{
	int i, j, n;
	
	scanf("%d", &n);
	for (i = 0; i != n; i++)
		for (j = 0; j != n; j++) {
			scanf("%d", &a[i][j]);
		}
	
	for (j = 0; j != n; j++)
		for (i = 0; i != n; i++) {
			printf(i == n-1 ? "%d
" : "%d ", a[i][j]); } return 0; }

【リダイレクトバージョン】
#include <stdio.h>
#define N 110
int a[N][N];

int
main(void)
{
	int i, j, n;

	freopen("test.in", "r", stdin);
	freopen("test.out", "w", stdout);
	
	scanf("%d", &n);
	for (i = 0; i != n; i++)
		for (j = 0; j != n; j++) {
			scanf("%d", &a[i][j]);
		}
	
	for (j = 0; j != n; j++)
		for (i = 0; i != n; i++) {
			printf(i == n-1 ? "%d
" : "%d ", a[i][j]); } return 0; }
リダイレクトバージョンには2行のコードが追加されています.すなわちtest.inの内容を標準入力ストリーム(stdin)として読み出し、標準出力ストリーム(stdout)の内容をtest.outに書き込む.
【fopen版】
#include <stdio.h>
#define N 110
int a[N][N];

int
main(void)
{
	int i, j, n;

	FILE *fin, *fout;//file pointer indicated file name;
	fin = fopen("test.in", "r");
	fout = fopen("test.out", "w");
		
	fscanf(fin, "%d", &n);
	for (i = 0; i != n; i++)
		for (j = 0; j != n; j++) {
			fscanf(fin, "%d", &a[i][j]);
		}
	
	for (j = 0; j != n; j++)
		for (i = 0; i != n; i++) {
			fprintf(fout, i == n-1 ? "%d
" : "%d ", a[i][j]); } fclose(fin); fclose(fout); return 0; }
実はこのバージョンも分かりやすくて、まずファイルを開けて、finはファイルのポインタで、しかもファイルを読むことができて、それからscanf()はfscanf()に変えて、つまりファイルの中から読んで、パラメータも相応に1つプラスして、そして最初の部分でファイルのアドレス(ポインタ)を指定します;書き込みの原理はこのように推定される.
リダイレクトはかなり使いやすい感じですよ!
本書では、ローカル用リダイレクトを紹介し、提出すると「リダイレクト」文を削除し、あまり実用的ではないような気がしますが、勉強してみてください.
10学会使用条件コンパイル指示フレームワークローカル実行環境
#include <stdio.h>
#define N 110
int a[N][N];

int
main(void)
{
	int i, j, n;

#ifdef LOCAL
	freopen("test.in", "r", stdin);
	freopen("test.out", "w", stdout);
#endif
	
	scanf("%d", &n);
	for (i = 0; i != n; i++)
		for (j = 0; j != n; j++) {
			scanf("%d", &a[i][j]);
		}
	
	for (j = 0; j != n; j++)
		for (i = 0; i != n; i++) {
			printf(i == n-1 ? "%d
" : "%d ", a[i][j]); } return 0; }
上記プログラムファイル名test.c
では、コンパイルコマンド:(注意:-DLOCAL)
gcc -g -Wall -DLOCAL test.c -o test
はリダイレクトの2つのコードを実行し、逆に-DLOCALを削除すると実行しません.