2011|08|
2013|10|11|12|
2014|01|02|03|04|05|06|07|08|09|10|11|12|
2015|01|02|03|05|06|07|08|09|10|11|12|
2016|01|03|04|05|06|07|08|09|10|11|12|
2017|01|02|03|04|05|06|07|08|09|10|11|12|
2018|01|02|03|04|05|06|07|08|09|10|11|12|
2019|01|02|03|04|05|06|07|08|09|10|11|12|
2020|01|02|03|04|

2018-03-06 ワーシャル-フロイド法 (経路計算付き) [長年日記]

/*
  gcc -g wf.cpp -o fw
 
  ワーシャル-フロイド法
  (ダイクストラは個別ルートでは早いが、先に全ルート計算しておくなら、
  こっちの方法の法が速いこともある)
 
  参考:ゼオスTTのブログ
  http://zeosutt.hatenablog.com/entry/2015/05/05/045943
 
*/
 
#include <stdio.h>
 
int d[5][5];  // d[i][k]:ノードiからノードkへの距離 
int via[5][5];  // d[i][k]の間にある(少くとも1つの)中継ノード
 
 
// 中継パスの表示ルーチン(再帰呼出し用)
void printPath1_aux(int begin, int end) {
  if (via[begin][end] == begin) {
	if (begin != end)
	  printf("%d -> ", begin);
	return;
  }
  
  printPath1_aux(begin, via[begin][end]);
  printPath1_aux(via[begin][end], end);
}
 
// 中継パスの表示ルーチン
void printPath1(int start, int goal) {
  printPath1_aux(start, via[start][goal]);
  printPath1_aux(via[start][goal], goal);
  printf("%d\n", goal);
}
 
int main(void)
{
 
  // 変数の初期化
  for(int i = 0; i < 5; i++){
	for(int j = 0; j < 5; j++){
	  d[i][j] = 99999999; // 距離の初期化(でっかい値を入力しておく(INT_MAXは足し算の時に桁上がりが起こるので使わない)
	  via[i][j] = i; // ノードiからノードkへの経由値の初期化 
	}
  }
 
 
  // 確認用の表示
  printf("\n[STEP1]\n");
 
  for(int i = 0; i < 5; i++){
	for(int k = 0; k < 5; k++){
	  printf("d[%d][%d]):%d\t",i,k,d[i][k]);
	  printf("via[%d][%d]):%d\n",i,k,via[i][k]);
	}
  }
 
  //// ここからは実際の距離を手書き
 
  for(int i = 0; i < 5; i++){
	d[i][i] = 0; //// 同じノードへの距離は0になるので、上書き
  }
 
  d[0][2] = 1;  // ノード0からノード2までの距離 1 を上書き
  d[2][0] = 1;  // その逆順(さぼってはダメ)
 
  d[0][1] = 2;  // ノード0からノード1までの距離 2 を上書き
  d[1][0] = 2;  // その逆順
 
  d[0][4] = 6;
  d[4][0] = 6;
  
  d[1][2] = 4;
  d[2][1] = 4;
  
  d[2][3] = 4;
  d[3][2] = 4;
 
  d[3][4] = 2;
  d[4][3] = 2;
  
  // 確認用の表示
  printf("\n[STEP2]\n");
 
  for(int i = 0; i < 5; i++){
	for(int k = 0; k < 5; k++){
	  printf("d[%d][%d]):%d\t",i,k,d[i][k]);
	  printf("via[%d][%d]):%d\n",i,k,via[i][k]);
	}
  }
 
  // 経路長計算
  for (int k =0; k < 5; k++){
	for (int i =0; i < 5; i++){
	  for(int j = 0; j < 5; j++){
		if(d[i][j] > d[i][k] + d[k][j]){
		  d[i][j] = d[i][k] + d[k][j];
		  via[i][j] = k; //更新処理
		}
	  }
	}
  }
 
  // 計算結果
  printf("\n[STEP3]\n");
 
  for(int i = 0; i < 5; i++){
	for(int k = 0; k < 5; k++){
	  printf("d[%d][%d]):%d\t",i,k,d[i][k]);
	  printf("via[%d][%d]):%d\n",i,k,via[i][k]);
	}
  }
 
  // 経路パス表示
 
  printf("\n[Path]\n");
  for(int i = 0; i < 5; i++){
	for(int k = 0; k < 5; k++){
	  printf("d[%d][%d]: ",i,k);
	  printPath1(i, k);
	}
  }
}
syntax2html

2018-03-07 ワーシャル-フロイド法(その3) vs ダイクストラ法 [長年日記]

/*
  gcc -g wf3.cpp -o fw3
 
  ワーシャル-フロイド法(その3)
 
  スタックオーバーフローが怖いのと処理が遅くなりそうなので、「再帰呼出し」を使わない方法
  (http://www.kobore.net/diary_techno/?date=20180306)
 
  参考:ゼオスTTのブログ
  http://zeosutt.hatenablog.com/entry/2015/05/05/045943
 
*/
 
#include <stdio.h>
 
int d[5][5];  // d[i][k]:ノードiからノードkへの距離 
int next[5][5];  // ノードi から ノードj への最短経路における i の1つ後のノード
 
int main(void)
{
 
  // 変数の初期化
  for(int i = 0; i < 5; i++){
	for(int j = 0; j < 5; j++){
	  d[i][j] = 99999999; // 距離の初期化(でっかい値を入力しておく(INT_MAXは足し算の時に桁上がりが起こるので使わない)
	  next[i][j] = j; // ノードi から ノードj への最短経路における i の1つ後のノード
	}
  }
 
 
  // 確認用の表示
  printf("\n[STEP1]\n");
 
  for(int i = 0; i < 5; i++){
	for(int k = 0; k < 5; k++){
	  printf("d[%d][%d]):%d\t",i,k,d[i][k]);
	  printf("next[%d][%d]):%d\n",i,k,next[i][k]);
	}
  }
 
  //// ここからは実際の距離を手書き
 
  for(int i = 0; i < 5; i++){
	d[i][i] = 0; //// 同じノードへの距離は0になるので、上書き
  }
 
  d[0][2] = 1;  // ノード0からノード2までの距離 1 を上書き
  d[2][0] = 1;  // その逆順(さぼってはダメ)
 
  d[0][1] = 2;  // ノード0からノード1までの距離 2 を上書き
  d[1][0] = 2;  // その逆順
 
  d[0][4] = 6;
  d[4][0] = 6;
  
  d[1][2] = 4;
  d[2][1] = 4;
  
  d[2][3] = 4;
  d[3][2] = 4;
 
  d[3][4] = 2;
  d[4][3] = 2;
  
  // 確認用の表示
  printf("\n[STEP2]\n");
 
  for(int i = 0; i < 5; i++){
	for(int k = 0; k < 5; k++){
	  printf("d[%d][%d]):%d\t",i,k,d[i][k]);
	  printf("next[%d][%d]):%d\n",i,k,next[i][k]);
	}
  }
 
  // 経路長計算
  for (int k =0; k < 5; k++){
	for (int i =0; i < 5; i++){
	  for(int j = 0; j < 5; j++){
		if(d[i][j] > d[i][k] + d[k][j]){
 
		  d[i][j] = d[i][k] + d[k][j];
		  next[i][j] = next[i][k]; //更新処理
		}
	  }
	}
  }
 
  // 計算結果
  printf("\n[STEP3]\n");
 
  for(int i = 0; i < 5; i++){
	for(int k = 0; k < 5; k++){
	  printf("d[%d][%d]):%d\t",i,k,d[i][k]);
	  printf("next[%d][%d]):%d\n",i,k,next[i][k]);
	}
  }
 
  // 経路パス表示
 
  printf("\n[Path]\n");
  for(int i = 0; i < 5; i++){
	for(int k = 0; k < 5; k++){
	  
	  int cur;
	  printf("d[%d][%d]: ",i,k);
	  
	  for (cur = i; cur != k; cur = next[cur][k]){
        printf("%d -> ", cur);
	  }
	  printf("%d\n", k);
	}
  }
}
syntax2html
■ダイクストラ法
開始時間:82[ms]
終了時間:33139[ms]
 
■ワーシャル-フロイド法(その3)
開始時間:84[ms]
終了時間:91[ms]
 
速度比率 4722.428571 倍
 

2018-03-13 携帯電話 ハンズ フリー [長年日記]

_ 通話中に「アプリ」ボタンを押すと、ハンズフリー になって、スピーカーから相手の声が聞こえるようになる。

_ ハンド ハンズ フリー 手放し


2018-03-14 強化学習(Q-Learning)を理解する為に、中学→高校→大学の学歴を使ってみた [長年日記]

/* 
   gcc -g ql_test.cpp -o ql_test
 
   強化学習(Q-Learning)を理解する為に、中学→高校→大学の学歴を使ってみた
 
*/
 
#include <stdio.h>
#include <stdlib.h>
 
typedef enum period{
  BIRTH = 0, JUNIOR_HIGH = 1, HIGH = 2, COLLEGE = 3, SUPER_COLLEGE = 4
}PERIOD;
 
typedef struct state{
  struct state* future_state[2]; // 未来へのパス(取り敢えず2つほど)
  PERIOD period;
  int q;
}STATE;
 
 
STATE* change_state(STATE* p_state)
{
  if ((double)rand()/RAND_MAX < 0.3){  // ε:0.3
	if ((double)rand()/RAND_MAX < 0.5){ // 半々
	  return p_state->future_state[0];
	}
	else{
	  return p_state->future_state[1];
	}
  }
  else {
	if (p_state->future_state[0]->q > p_state->future_state[1]->q){
	  return p_state->future_state[0];
	}
	else{
	  return p_state->future_state[1];
	}
  }
}
	
void  q_renewal(STATE* p_state)
{
  int dummy_q;
 
  if (p_state->period  == SUPER_COLLEGE){
	p_state->q += 0.1 * (1000- p_state->q); // α:0.1 報酬の源泉:年収1000万円
  }
  else if (p_state->period !=  COLLEGE){
	if (p_state->future_state[0]->q > p_state->future_state[1]->q){
	  dummy_q = p_state->future_state[0]->q;
	}
	else {
	  dummy_q = p_state->future_state[1]->q;
	}
	p_state->q += 0.1 * (0.9 * dummy_q - p_state->q); // α:0.1 γ:0.9
  }
 
  return;
}
	
void q_display(STATE* p_state)
{
  for (int i =0; i < 15 ; i++){
	printf("%d,", p_state->q);
	p_state++;
  }
  printf("\n");
  return;
}
 
 
 
int main()
{
  srand(13);
 
 
  // 初期設定
  //STATE* state;
  STATE state[15];
 
  state[0].period = BIRTH;
  state[0].future_state[0] = &(state[1]);
  state[0].future_state[1] = &(state[2]);
 
  state[1].period = JUNIOR_HIGH;
  state[1].future_state[0] = &(state[3]);
  state[1].future_state[1] = &(state[4]);
 
  state[2].period = JUNIOR_HIGH;
  state[2].future_state[0] = &(state[5]);
  state[2].future_state[1] = &(state[6]);
 
  state[3].period = HIGH;
  state[3].future_state[0] = &(state[7]);
  state[3].future_state[1] = &(state[8]);
 
  state[4].period = HIGH;
  state[4].future_state[0] = &(state[9]);
  state[4].future_state[1] = &(state[10]);
 
  state[5].period = HIGH;
  state[5].future_state[0] = &(state[11]);
  state[5].future_state[1] = &(state[12]);
 
  state[6].period = HIGH;
  state[6].future_state[0] = &(state[13]);
  state[6].future_state[1] = &(state[14]);
 
  state[7].period = COLLEGE;
  state[8].period = COLLEGE;
  state[9].period = COLLEGE;
  state[10].period = SUPER_COLLEGE;
  state[11].period = COLLEGE;
  state[12].period = COLLEGE;
  state[13].period = COLLEGE;
  state[14].period = COLLEGE;
  
  for (int i = 0; i < 15; i++){
	state[i].q = (int)rand() % 100;
  }
 
  printf("誕生,A中学,B中学,C高校,D高校,E高校,F高校,G大学,H大学,I大学,J大学,K大学,L大学,M大学,N大学\n");
 
  STATE* s = state;
  //q_display(s);
  q_display(state);
 
  for (int i = 0; i < 1000; i++){  // 300:学習回数
	STATE* s = state; // 初期値に戻しているだけ
	
	do{ 
	  s = change_state(s);
	  q_renewal(s);
	}while( (s->period != COLLEGE) && (s->period != SUPER_COLLEGE));
 
	q_display(state);
 
  }
 
  printf("\n[after]\n");
  //q_display(s);
  q_display(state);
 
}
syntax2html

2018-03-21 google Mapの座標値から距離を求めるルーチン [長年日記]

/*
  google Mapの座標値から距離を求めるルーチン
  2018-03-21(水) 14:41:31  
 
  gcc -c location_calc.cpp
*/
 
#include <math.h>
 
 
typedef struct location{
  // ちなみに X,Y 軸座標は、→に+  ↑に+
  double longitude; // 経度 東経 139.691 X軸  
  double latitude;  // 緯度 北緯 35.698  Y軸 
} LOCATION;
 
 
#define rad2deg(a) ((a)/M_PI * 180.0) /* rad を deg に換算するマクロ関数 */
#define deg2rad(a) ((a)/180.0 * M_PI) /* deg を rad に換算するマクロ関数 */
 
double distance_km(LOCATION* A, LOCATION* B, double *rad_up)
{
  double earth_r = 6378.137;
 
  double loRe = deg2rad(B->longitude - A->longitude); // 東西
  double laRe = deg2rad(B->latitude - A->latitude); // 南北
 
  double EWD = cos(deg2rad(A->latitude))*earth_r*loRe; // 東西距離
  double NSD = earth_r*laRe; //南北距離
 
  double distance = sqrt(pow(NSD,2)+pow(EWD,2));  
  *rad_up = atan2(NSD, EWD);
 
  return distance;
}
 
LOCATION* new_location(LOCATION* D, double diff_p_x, double diff_p_y) 
{
  double earth_r = 6378.137;
 
  double loRe = diff_p_x / earth_r / cos(deg2rad(D->latitude)); // 東西
  double laRe = diff_p_y / earth_r;  // 南北
  
  double diff_lo = rad2deg(loRe); // 東西
  double diff_la = rad2deg(laRe); // 南北
 
  static LOCATION C;
 
  C.longitude = D->longitude + diff_lo; // 東西
  C.latitude = D->latitude + diff_la; // 南北
  
  return &C;
}
  
double diff_longitude(double diff_p_x, double latitude) 
{
  double earth_r = 6378.137;
  // ↓ これが正解だけど、
  double loRe = diff_p_x / earth_r / cos(deg2rad(latitude)); // 東西
  // 面倒なので、これで統一しよう(あまり差が出ないしね)
  //double loRe = diff_p_x / earth_r / cos(deg2rad(35.700759)); // 東西
  double diff_lo = rad2deg(loRe); // 東西
 
  return diff_lo; // 東西
}
  
double diff_latitude(double diff_p_y) 
{
  double earth_r = 6378.137;
  double laRe = diff_p_y / earth_r;  // 南北
  double diff_la = rad2deg(laRe); // 南北
  
  return diff_la; // 南北
}
syntax2html