あるごりの復習。〜〇〇優先〜

2017年7月24日

何もなければ１日に１問。時に２問

まぁ知っていないと困りそうだんぁ〜っていう焦りからですね。
なんとなく、デイリーなワークとしてはじめて見るよ。

ちなみに、ブルゾンの"dirty work"を"daily work"と思っている人がいるらしい。
MV見れば全く"daily"じゃないのに。。。

んで、この本をやってみるのはいいけど、続くかなぁ。基礎的な部分だけでも得られればいいんだよね１区切りついた段階でアップしていく、スタイル？多分。

あと、多分めちゃくちゃフランクに進めていくし、若干本家と違うかもだけど、
あくまで自分が理解できていればいいスタンスなので！

ぶっちゃけ、遊びたい

まぁ遊ぶけど、一人酒に慣れてきて、、、まだ学生だぜ。。。
それでは、

DFS(depth first search)

深さ優先探索ってやつ。昔やった。

要は、あるポイントを見つける。
その状態から繊維できなくなる状態までいってみる
限界迎えたら、１つ前に戻ってみる。

ってことを繰り返して探索するんだけど、つまり再帰関数が得意とする探索で。暗に、スタック(先入れ後出し)を意味しているらしい。へぇ。

計算量O(2^N)。メモリ使用量は再帰関数の深さに比例する。（深く潜る分だけ、浅いところを待たせている。）

//部分話をとく問題
//整数a1~an がgiven (n個)　
//いくつか選んで、合計kにできるか

#include <cstdio>

int a[7] = {1,5,8,3,6,4,3} ;
int n = 3;
int k = 7;

//深さ優先木を作る
//i : 深さ(配列長とみなせる),sum : 
//n : 最大深度
bool dfs(int i, int sum){
	//最大深度に到達したら、その地点での合計とkを比較
	if(i == n) return sum == k;
	//**最大深度でない場合に次の深度へ
	//深度iを使う場合に分岐(分岐先でtrueならこれもtrue,そうでないなら<*>)
	if(dfs(i+1,sum))		return true;
	//深度iを使わない場合に分岐(分岐先でtrueならこれもtrue,そうでないなら<*>)
	if(dfs(i+1,sum+a[i]))	return true;
	//<*>そうでない場合
	return false;
}

void solve(){
	if (dfs(0,0)) printf("Yes\n");
	else printf("No\n");
}


int main(){
	solve();
}

//部分話をとく問題

//整数a1~an がgiven (n個)　

//いくつか選んで、合計kにできるか

#include <cstdio>

int a[7] = {1,5,8,3,6,4,3} ;

int n = 3;

int k = 7;

//深さ優先木を作る

//i : 深さ(配列長とみなせる),sum :

//n : 最大深度

bool dfs(int i, int sum){

//最大深度に到達したら、その地点での合計とkを比較

if(i == n) return sum == k;

//**最大深度でない場合に次の深度へ

//深度iを使う場合に分岐(分岐先でtrueならこれもtrue,そうでないなら<*>)

if(dfs(i+1,sum)) return true;

//深度iを使わない場合に分岐(分岐先でtrueならこれもtrue,そうでないなら<*>)

if(dfs(i+1,sum+a[i])) return true;

//<*>そうでない場合

return false;

}

void solve(){

if (dfs(0,0)) printf("Yes\n");

else printf("No\n");

}

int main(){

solve();

}

んで、もう一個あった。

//大きさN*Mの庭にの中に水たまりを設定
//8近傍に水たまりがあれば、連結とみなし
//何個水たまりが存在するか？
#include <stdio.h>
#include <time.h>
#include <stdlib.h>

//庭の大きさ
const int N = 10;
const int M = 10;

char field[N][M];

//水たまりのランダム作成
void set_input(){
	const char str[] = "W.";	//水：w、土：.
	srand((unsigned int)time(NULL));
	for(int i = 0; i < N; i++){
		for(int j = 0; j < M; j++){
			field[i][j] = str[rand()%2];
			printf("%c",field[i][j]);
		}
		printf("\n");
	}
	printf("\n");
	return;
}

//現在状況出力
void out_put(){
	for(int i = 0; i < N; i++){
		for(int j = 0; j < M; j++){
			printf("%c",field[i][j]);
		}
		printf("\n");
	}
	printf("\n");
	return;
}

//深さ優先木２
//あるポイント(i,j)から手繰れるポイントまで到達してみる。
void dfs(int i,int j){
	//水を土にしていく（到達ポイントは目印として、”.”にする）
	field[i][j] = '.';	
	//(i,j)から８方向に深掘りする
	for(int tmp_i = i-1; tmp_i <= i + 1; tmp_i++){
		for(int tmp_j = j-1; tmp_j <= j + 1; tmp_j++){
			//庭の範囲内確認
			if(tmp_j >= 0 && tmp_j >= 0 && tmp_i <= N && tmp_j <= M){
				if(field[tmp_i][tmp_j] == 'W'){
					//さらに手繰れる場合は次の深度へ
					dfs( tmp_i , tmp_j );
				}
			}
		}
	}
	return;
}

//深さ優先木１
//深さ：座標になる。
void solve(){
	int ans = 0;
	for(int n = 0; n < N; n++){
		for(int m = 0; m < M; m++){
			//水ポイントを発見
			if(field[n][m] == 'W'){
				ans++;
				dfs(n,m);	//そこからできる範囲で土にしていく(深さ優先)
				out_put();	//次なる水ポイントを発見する。
			}
		}
	}
	printf("%d\n",ans);
	return;
}


int main(){
	set_input();
	solve();
}

//大きさN*Mの庭にの中に水たまりを設定

//8近傍に水たまりがあれば、連結とみなし

//何個水たまりが存在するか？

#include <stdio.h>

#include <time.h>

#include <stdlib.h>

//庭の大きさ

const int N = 10;

const int M = 10;

char field[N][M];

//水たまりのランダム作成

void set_input(){

const char str[] = "W."; //水：w、土：.

srand((unsigned int)time(NULL));

for(int i = 0; i < N; i++){

for(int j = 0; j < M; j++){

field[i][j] = str[rand()%2];

printf("%c",field[i][j]);

}

printf("\n");

}

printf("\n");

return;

}

//現在状況出力

void out_put(){

for(int i = 0; i < N; i++){

for(int j = 0; j < M; j++){

printf("%c",field[i][j]);

}

printf("\n");

}

printf("\n");

return;

}

//深さ優先木２

//あるポイント(i,j)から手繰れるポイントまで到達してみる。

void dfs(int i,int j){

//水を土にしていく（到達ポイントは目印として、”.”にする）

field[i][j] = '.';

//(i,j)から８方向に深掘りする

for(int tmp_i = i-1; tmp_i <= i + 1; tmp_i++){

for(int tmp_j = j-1; tmp_j <= j + 1; tmp_j++){

//庭の範囲内確認

if(tmp_j >= 0 && tmp_j >= 0 && tmp_i <= N && tmp_j <= M){

if(field[tmp_i][tmp_j] == 'W'){

//さらに手繰れる場合は次の深度へ

dfs( tmp_i , tmp_j );

}

return;

}

//深さ優先木１

//深さ：座標になる。

void solve(){

int ans = 0;

for(int n = 0; n < N; n++){

for(int m = 0; m < M; m++){

//水ポイントを発見

if(field[n][m] == 'W'){

ans++;

dfs(n,m); //そこからできる範囲で土にしていく(深さ優先)

out_put(); //次なる水ポイントを発見する。

}

printf("%d\n",ans);

return;

}

int main(){

set_input();

solve();

}

今日はここまでだわ。疲れた。

アルゴリ

Posted by tanico.rikudo

若いから四国をめぐる＠0-1日目

jupyterを使った。それだけ１。