月: 2017年2月

提出用プロジェクトを作成する。
プロジェクト名は「s16171xx_名前」とする。

0.準備
プロジェクトを作成し、C言語で使用するための設定を行う。

参考：Visual Studio 2012 でC言語を使うための設定

1.メニューを表示するプログラムを作成する。
メニューは0～4の数字で入力する。
0で終了する。

参考：再起呼び出し

(1)階乗 (2)ハノイの塔 (3)ハッシュテーブル (4)リンクリスト (0)終了 : 1
(1)階乗 (2)ハノイの塔 (3)ハッシュテーブル (4)リンクリスト (0)終了 : 2
(1)階乗 (2)ハノイの塔 (3)ハッシュテーブル (4)リンクリスト (0)終了 : 3
(1)階乗 (2)ハノイの塔 (3)ハッシュテーブル (4)リンクリスト (0)終了 : 4
(1)階乗 (2)ハノイの塔 (3)ハッシュテーブル (4)リンクリスト (0)終了 : 0
続行するには何かキーを押してください . . .

2.メニューで1が指定されたら階乗を表示するプログラムが動作するようにする。

参考：再起呼び出し

(1)階乗 (2)ハノイの塔 (3)ハッシュテーブル (4)リンクリスト (0)終了 : 1
整数を入力せよ：3
3の階乗は6です。
(1)階乗 (2)ハノイの塔 (3)ハッシュテーブル (4)リンクリスト (0)終了 : 1
整数を入力せよ：4
4の階乗は24です。
(1)階乗 (2)ハノイの塔 (3)ハッシュテーブル (4)リンクリスト (0)終了 : 0
続行するには何かキーを押してください . . .

3.メニューで2が指定されたらハノイの塔のプログラムが動作するようにする。

参考：再起呼び出し

(1)階乗 (2)ハノイの塔 (3)ハッシュテーブル (4)リンクリスト (0)終了 : 2
ハノイの塔
円盤の枚数: 2
円盤[1]をA軸からB軸へ移動
円盤[2]をA軸からC軸へ移動
円盤[1]をB軸からC軸へ移動
(1)階乗 (2)ハノイの塔 (3)ハッシュテーブル (4)リンクリスト (0)終了 : 2
ハノイの塔
円盤の枚数: 3
円盤[1]をA軸からC軸へ移動
円盤[2]をA軸からB軸へ移動
円盤[1]をC軸からB軸へ移動
円盤[3]をA軸からC軸へ移動
円盤[1]をB軸からA軸へ移動
円盤[2]をB軸からC軸へ移動
円盤[1]をA軸からC軸へ移動
(1)階乗 (2)ハノイの塔 (3)ハッシュテーブル (4)リンクリスト (0)終了 : 0
続行するには何かキーを押してください . . .

4.メニューで3が指定されたらハッシュテーブルのプログラムが動作するようにする。

参考：ハッシュ法

(1)階乗 (2)ハノイの塔 (3)ハッシュテーブル (4)リンクリスト (0)終了 : 3
(1)追加 (2)削除 (3)探索 (4)全削除 (5)ダンプ (0)終了: 1
追加するデータを入力してください。
番号：1
氏名：aaa
(1)追加 (2)削除 (3)探索 (4)全削除 (5)ダンプ (0)終了: 1
追加するデータを入力してください。
番号：2
氏名：bbb
(1)追加 (2)削除 (3)探索 (4)全削除 (5)ダンプ (0)終了: 1
追加するデータを入力してください。
番号：14
氏名：ccc
(1)追加 (2)削除 (3)探索 (4)全削除 (5)ダンプ (0)終了: 5
00
01  → 14 (ccc) → 1 (aaa)
02  → 2 (bbb)
03
04
05
06
07
08
09
10
11
12
(1)追加 (2)削除 (3)探索 (4)全削除 (5)ダンプ (0)終了: 3
探索するデータを入力してください。
番号：1
探索に成功しました。
1 aaa
(1)追加 (2)削除 (3)探索 (4)全削除 (5)ダンプ (0)終了: 0
(1)階乗 (2)ハノイの塔 (3)ハッシュテーブル (4)リンクリスト (0)終了 : 0

5.メニューで4が指定されたら作成したリンクリストが動作するようにする。

参考：線形リスト

(1)階乗 (2)ハノイの塔 (3)ハッシュテーブル (4)リンクリスト (0)終了 : 4
( 1) 先頭にノードを挿入  ( 2) 末尾にノードを挿入  ( 3) 先頭のノードを削除
( 4) 末尾のノードを削除  ( 5) 着目ノードを表示    ( 6) 着目ノードを削除
( 7) 番号で探索          ( 8) 氏名で探索          ( 9) 全ノードを表示
(10) 全ノードを削除      ( 0) 終了 :1
先頭に挿入するデータを入力してください。
番号：1
氏名：aaa
( 1) 先頭にノードを挿入  ( 2) 末尾にノードを挿入  ( 3) 先頭のノードを削除
( 4) 末尾のノードを削除  ( 5) 着目ノードを表示    ( 6) 着目ノードを削除
( 7) 番号で探索          ( 8) 氏名で探索          ( 9) 全ノードを表示
(10) 全ノードを削除      ( 0) 終了 :2
末尾に挿入するデータを入力してください。
番号：2
氏名：bbb
( 1) 先頭にノードを挿入  ( 2) 末尾にノードを挿入  ( 3) 先頭のノードを削除
( 4) 末尾のノードを削除  ( 5) 着目ノードを表示    ( 6) 着目ノードを削除
( 7) 番号で探索          ( 8) 氏名で探索          ( 9) 全ノードを表示
(10) 全ノードを削除      ( 0) 終了 :2
末尾に挿入するデータを入力してください。
番号：3
氏名：ccc
( 1) 先頭にノードを挿入  ( 2) 末尾にノードを挿入  ( 3) 先頭のノードを削除
( 4) 末尾のノードを削除  ( 5) 着目ノードを表示    ( 6) 着目ノードを削除
( 7) 番号で探索          ( 8) 氏名で探索          ( 9) 全ノードを表示
(10) 全ノードを削除      ( 0) 終了 :9
1 aaa
2 bbb
3 ccc
( 1) 先頭にノードを挿入  ( 2) 末尾にノードを挿入  ( 3) 先頭のノードを削除
( 4) 末尾のノードを削除  ( 5) 着目ノードを表示    ( 6) 着目ノードを削除
( 7) 番号で探索          ( 8) 氏名で探索          ( 9) 全ノードを表示
(10) 全ノードを削除      ( 0) 終了 :7
探索するデータを入力してください。
番号：2
2 bbb
( 1) 先頭にノードを挿入  ( 2) 末尾にノードを挿入  ( 3) 先頭のノードを削除
( 4) 末尾のノードを削除  ( 5) 着目ノードを表示    ( 6) 着目ノードを削除
( 7) 番号で探索          ( 8) 氏名で探索          ( 9) 全ノードを表示
(10) 全ノードを削除      ( 0) 終了 :8
探索するデータを入力してください。
氏名：ccc
3 ccc
( 1) 先頭にノードを挿入  ( 2) 末尾にノードを挿入  ( 3) 先頭のノードを削除
( 4) 末尾のノードを削除  ( 5) 着目ノードを表示    ( 6) 着目ノードを削除
( 7) 番号で探索          ( 8) 氏名で探索          ( 9) 全ノードを表示
(10) 全ノードを削除      ( 0) 終了 :6
( 1) 先頭にノードを挿入  ( 2) 末尾にノードを挿入  ( 3) 先頭のノードを削除
( 4) 末尾のノードを削除  ( 5) 着目ノードを表示    ( 6) 着目ノードを削除
( 7) 番号で探索          ( 8) 氏名で探索          ( 9) 全ノードを表示
(10) 全ノードを削除      ( 0) 終了 :9
1 aaa
2 bbb
( 1) 先頭にノードを挿入  ( 2) 末尾にノードを挿入  ( 3) 先頭のノードを削除
( 4) 末尾のノードを削除  ( 5) 着目ノードを表示    ( 6) 着目ノードを削除
( 7) 番号で探索          ( 8) 氏名で探索          ( 9) 全ノードを表示
(10) 全ノードを削除      ( 0) 終了 :0
(1)階乗 (2)ハノイの塔 (3)ハッシュテーブル (4)リンクリスト (0)終了 : 0
続行するには何かキーを押してください . . .

提出は、提出用フォルダ（X:\提出フォルダ\2016\提出\アルゴリズム試験解答）にプロジェクトをそのままコピーする。

プロジェクタが使えないので中央の画面で表示する。
提出用フォルダの下にある「アルゴリズム発表用プログラム」フォルダに学籍番号と名前のフォルダを作成し、そこに作成したプロジェクトをコピーする。
実行ファイルが、プロジェクトの直下の Debug フォルダ内にあるので、発表時はそのexeファイルを起動する。

X:\提出フォルダ\2016\提出\アルゴリズム発表用プログラム\s1617100_名前

発表内容

1. 名前
2. 作成したプログラム名
3. プログラムの説明
4. プログラムを実行してデモを行う
5. 工夫した点、苦労した点、感想など

C++で書かれた2048ゲーム（http://vivi.dyndns.org/tech/games/2048.html）をC言語に書き換えたもの。

コンソールアプリで文字色を変更する処理は省略。

//----------------------------------------------------------------------
//		2048
//		Copyright (C) 2048 by N.Tsuda
//		License: CDDL 1.0 (http://opensource.org/licenses/CDDL-1.0)
//----------------------------------------------------------------------
#include <conio.h>		//	_getch
#include <time.h>			//	time
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define		WALL			-1			//	番人
#define		BOARD_WD		4			//	ボード幅
#define		BOARD_HT		4			//	ボード高さ
#define		CELL_WIDTH	8			//	セル表示幅

#define		KEY_ARROW		0xe0
#define		KEY_UP			0x48
#define		KEY_LEFT		0x4b
#define		KEY_RIGHT		0x4d
#define		KEY_DOWN		0x50

int	g_score = 0;
//int	g_nBlank;		//	空欄箇所数
int	g_board[BOARD_WD+2][BOARD_HT+2];		//	番人付きボード２次元配列


#define swap(a, b) (a += b, b = a - b, a -= b)


//	最上位ビットの位置（0～31）を返す
//		v が0ならば0, 1ならば１，2ならば2, 4ならば3, 8ならば4,... を返す
//		v がマイナスならば -1 を返す
//	int は符号付き32ビット整数と仮定する
int msbPos(int v)
{
	int n = 31;
	int mask;
	if( v == 0 ) return 0;
	if( v < 0 ) return -1;
	mask = 1 << (n-1);
	while( (v & mask) == 0 ) {
		mask >>= 1;
		--n;
	}
	return n;
}
//----------------------------------------------------------------------
void	init_board()
{
	int x, y;
	//g_nBlank = BOARD_WD * BOARD_HT;		//	空欄箇所数
	for (x = 0; x < BOARD_WD+2; ++x) {
		for (y = 0; y < BOARD_HT+2; ++y) {
			if( x == 0 || x == BOARD_WD + 1 ||
				y == 0 || y == BOARD_HT + 1 )
			{
				g_board[x][y] = WALL;
			} else {
				g_board[x][y] = 0;
			}
		}
	}
}
void print_line(int y, int printVal)
{
	int x, v;
	char str[256];
	for (x = 1; x <= BOARD_WD; ++x) {
		str[0] = '\0';
		v = g_board[x][y];
		if( printVal ) {
			if( !v ) {
				strcat_s(str, sizeof(str), "   .   ");
			} else {
				char ss[16];
				sprintf_s(ss, sizeof(ss), "%4d   ", v);
				strcat_s(str, sizeof(str), ss);
			}
		}
		printf("%s", str);
	}
	printf("\n");
}
void print_board()
{
	int y;
	printf("SCORE: %d\n\n", g_score);
	for (y = 1; y <= BOARD_HT; ++y) {
		print_line(y, 0);
		print_line(y, 0);
		print_line(y, 1);
		print_line(y, 0);
		print_line(y, 0);
	}
	printf("\n");
}
int nBlank()
{
	int x, y;
	int nBlank = 0;
	for (y = 1; y <= BOARD_HT; ++y) {
		for (x = 1; x <= BOARD_WD; ++x) {
			if( g_board[x][y] == 0 ) ++nBlank;
		}
	}
	return nBlank;
}
//	空き箇所のどこかに 2(75%) または 4(25%) を配置する
void put_number()
{
	int pos, v, x, y;
	int n = nBlank();
	if( n == 0 ) return;
	pos = rand() % n;
	v = (rand() % 100) < 75 ? 2 : 4;		//	75% の確率で２，25%の確率で４
	for (y = 1; y <= BOARD_HT; ++y) {
		for (x = 1; x <= BOARD_WD; ++x) {
			if( g_board[x][y] == 0 ) {		//	空欄を探す
				if( !pos ) {
					g_board[x][y] = v;
					return;
				}
				--pos;
			}
		}
	}
}
//	盤面左右反転
void hrev_board()
{
	int x, y;
	for (y = 1; y <= BOARD_HT; ++y) {
		for (x = 1; x <= BOARD_WD/2; ++x) {
			swap(g_board[x][y], g_board[BOARD_WD + 1 - x][y]);
		}
	}
}
//	x, y 反転
void swapxy_board()
{
	int x, y;
	for (y = 1; y < BOARD_HT; ++y) {
		for (x = y + 1; x <= BOARD_WD; ++x) {
			swap(g_board[x][y], g_board[y][x]);
		}
	}
}
int move_right()
{
	int y, src, dst, v;
	int moved = 0;
	for (y = 1; y <= BOARD_HT; ++y) {
		dst = BOARD_WD;
		for(src = BOARD_WD; src >= 1; --src) {
			v = g_board[src][y];
			if( v != 0 ) {
				if( src == BOARD_WD ) continue;		//	右端の場合
				if( g_board[dst][y] == 0 ) {		//	移動先が空欄
					if( dst != src ) {
						g_board[src][y] = 0;
						g_board[dst][y] = v;
						moved = 1;
					}
				} else if( g_board[dst][y] == v ) {		//	同じ数字
					g_score += v * 2;
					g_board[src][y] = 0;
					g_board[dst][y] += v;
					--dst;
					moved = 1;
				} else {
					--dst;
					if( dst != src ) {
						g_board[src][y] = 0;
						g_board[dst][y] = v;
						moved = 1;
					}
				}
			}
		}
	}
	return moved;
}
int move_left()
{
	int rc;
	hrev_board();
	rc = move_right();
	hrev_board();
	return rc;
}
int move_up()
{
	int rc;
	swapxy_board();
	hrev_board();
	rc = move_right();
	hrev_board();
	swapxy_board();
	return rc;
}
int move_down()
{
	int rc;
	swapxy_board();
	rc = move_right();
	swapxy_board();
	return rc;
}
int isMovable()
{
	int x, y;
	for (y = 1; y <= BOARD_HT; ++y) {
		for (x = 1; x <= BOARD_WD; ++x) {
			if( g_board[x][y] == 0 ||
				g_board[x][y] == g_board[x+1][y] ||
				g_board[x][y] == g_board[x][y+1] )
			{
				return 1;
			}
		}
	}
	return 0;
}
int g2048()
{
	int moved, c;
	moved = 0;
	srand((int)time(0));
	for (;;) {
		g_score = 0;
		init_board();
		put_number();
		for(moved;;) {
			if( moved )
				put_number();
			print_board();
			if( !isMovable() ) break;
			printf("Type ←↑↓→     ");
			c = _getch();
			if( c == 'q' ) break;
			if( c == KEY_ARROW ) {
				c = _getch();
				switch( c ) {
					case KEY_LEFT:
						moved = move_left();
						break;
					case KEY_RIGHT:
						moved = move_right();
						break;
					case KEY_UP:
						moved = move_up();
						break;
					case KEY_DOWN:
						moved = move_down();
						break;
				}
			}
		}
		printf("Try again ? [y/n]   ");
		for (;;) {
			c = _getch();
			if( c == KEY_ARROW )
				_getch();
			if( c == 'y' || c == 'Y' ||
				c == 'n' || c == 'N' )
			{
				break;
			}
		}
		if( c != 'y' && c != 'Y' ) break;
	}
	return 0;
}

タイプ練習のサンプル

プログラム内に辞書を用意。

#include <conio.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

char *dic[] = {
	"int",
	"short",
	"long",
	"char",
	"float",
	"double",
	"void",
	"unsigned",
	"hello",
	"world",
	"include",
	"time",
	"struct",
	"return",
	"printf",
	"sizeof",
	"while",
	"main",
	"static",
	"extern",
	"switch",
	"case",
	"continue",
	"volatile",
	"default",
	"goto"
};

int typing()
{
	int c;
	int p;
	int size;
	int i;
	time_t start;
	time_t end;
	char buff[256];

	size = sizeof(dic) / sizeof(dic[0]);
	printf("キーを押すとスタート\n");
	c = _getch();
	start = time(NULL);
	srand(start);
	for (i = 0; i < 10; i++) {
		p = rand() % size;
		printf("%s\n", dic[p]);
		while (1) {
			scanf("%s", buff);
			if (strcmp(buff, dic[p])) {
				puts("再入力");
			} else {
				break;
			}
		}
	}
	end = time(NULL);
	printf("%d秒", end - start);
	return 0;
}

オセロゲームのサンプル
人間 VS コンピュータ(AI)対局 7行プログラミング (C言語)

#include <stdio.h>

int put, turn, all, done, pass, count, cur, i;
// 盤状態:横9*縦10で、使用は8*8
// 0:無し 1:1player 2:2player 3:改行
// y*9+xというイメージ。0行目と9行目は番兵
int map[90] = {0};
// 盤を走査する場合、縦横斜め方向に向かうために足されるべき数
int dir[] = { -10, -9, -8, -1, 1, 8, 9, 10 };

// putに駒を置いた場合ひっくり返せる枚数をallに足す
void check() 
{
	if (map[put] == 0) {
		for (i = 0; i < 8; i++) {
			// dir[i]の方向の相手のコマの数を確認
			for (count = 0, cur = put+dir[i]; map[cur] == 3 - turn; cur += dir[i]) {
				count++;
			}
			if (count && map[cur] == turn) {
				// １枚以上存在し、その上端が自分のコマだったら
				all += count;
				cur = put;
				if (done) {
					// doneがtrueの場合は、実際にひっくり返す
					do {
						map[cur] = turn, cur += dir[i];
					} while (map[cur] != turn);
				}
			}
		}
	}
}

// mapに対応するオセロ駒＆改行
char *h = "・○●\n";

int main() {
	// 初期化
	for (i = 1, map[41] = map[49] = 2; i < 10; map[i++*9] = 3) {
		map[40] = map[50] = turn = pass = 1;
	}
	for (;; all = done = 0) { // ループのたびにallとdoneを初期化（セミコロンを１つ削除するため）
		// 盤の表示。今回のデータ構造だとこれで表示できる
		for (put = 9; put < 82; ++put) {
			check();
			printf("%.2s", &h[map[put]*2]);
		}
		if (all) {
			for (done = all = pass = put = 8; all == 8; check()) {
				// コマを置く（人は入力し、コンピュータは左上から順に）
				turn - 2 ? (scanf("%d %d", &put, &i), put+=i*9) : ++put;
			}
		} else if (pass) {
			// コマを置けないのでパス
			pass = 0;
			printf("pass");
		} else {
			break;
		}
		// 交代
		turn = 3 - turn;
	}
	return 0;
}

C言語（またはC++）でコンソールゲームを作成する。
どのゲームを作るのかは、各個人で選択する。
ネット上にあるサンプルを参照しながら作成すること。
例えば、以下のゲームは比較的簡単に作成できる。

• タイプ練習
• トランプゲーム
• オセロ
• 2048
• テトリス
• マインスイーパー

発表：2月21日
提出期限：2月22日

C言語で作成する人は、プロジェクトに対して以下の設定を行うこと。
→ Visual Studio 2012 でC言語を使うための設定

C++で作成する場合は設定不要。

キー入力を待ってその後の動作を決定するプログラムの作成方法。
‘q’が入力されるまで、入力された文字を表示する。

#include <stdio.h>
#include <conio.h>

int main(int argc, char* argv[])
{
	int c;
	while (1) {
		c = _getch();
		if (c == 'q') break;
		putchar(c);
	}
	printf("終了");
	return 0;
}

演習5-6
テキストp.188のList5-6を、軸の名前を数値ではなく名称（A軸・B軸・C軸）で表示するようにプログラムを変更せよ。

元のプログラム

#include <stdio.h>
 
void move(int no, int x, int y) 
{
    if (no > 1)
        move(no - 1, x, 6 - x - y);
    printf("円盤[%d]を%d軸から%d軸へ移動\n", no, x, y);
    if (no > 1)
        move(no - 1, 6 - x - y, y);
}
 
int hmain(void) 
{
    int n;
    printf("ハノイの塔\n円盤の枚数: ");
    scanf("%d", &n);
    move(n, 1, 3);
    return 0;
}

「1軸・2軸・3軸」を「A軸・B軸・C軸」に変更するには？
①「1軸・2軸・3軸」に対応する軸の名前を、文字列の配列で用意する。
②printf()で%dで出力している部分を文字列用の%sに置き換え、
③引数では文字列配列を渡すようにする。

void move(int no, int x, int y) 
{
    char name[3][4] = { "A", "B", "C" };  // ①
    if (no > 1)
        move(no - 1, x, 6 - x - y);
    printf("円盤[%d]を%s軸から%s軸へ移動\n", no, name[x - 1], name[y - 1]); // ②・③
    if (no > 1)
        move(no - 1, 6 - x - y, y);
}