C++でソースファイルのclass/field/methodを抜き出したかった
#include <iostream> #include <filesystem> #include <string> #include <vector> #include <algorithm> #include <fstream> using namespace std; using std::filesystem::directory_iterator; using std::filesystem::is_directory; // void fileSearch(string, &ofstream); vector<string> allPath; string fileName = "class_field_methods.txt"; void fileSearch(string path, ofstream &wfile) { vector<string> currentPath; for (const auto& file : directory_iterator(path)) { string tmp = file.path(); cout << tmp << endl; currentPath.push_back(tmp); } sort(currentPath.begin(), currentPath.end()); for (int i = 0; i < currentPath.size(); i++) { string tmp = currentPath[i]; allPath.push_back(tmp); if (tmp.substr(tmp.length()-4, tmp.length()) == ".cpp") { cout << "cpp file: "+tmp << endl; wfile << "cpp file: "+tmp <<endl; fstream mf; mf.open(tmp, ios::in); if (mf.is_open()) { string line; while (getline(mf, line)) { if (!(line == "" || line.at(0) == ' ' || line.at(0) == '{' || line.at(0) == '}')) wfile << line << endl; } wfile << endl; mf.close(); } } if (is_directory(tmp)) fileSearch(tmp, wfile); } } int main() { ofstream wfile; wfile.open(fileName, ios::out); string input = ""; cin >> input; allPath.push_back(input); fileSearch(input, wfile); for (int i = 0; i < allPath.size(); i++) cout << allPath[i] << endl; wfile.close(); return 0; }
cpp file: /〇/△/□/test.cpp #include <iostream> #include <filesystem> #include <string> #include <vector> #include <algorithm> #include <fstream> using namespace std; using std::filesystem::directory_iterator; using std::filesystem::is_directory; // void fileSearch(string, &ofstream); vector<string> allPath; string fileName = "class_field_methods.txt"; void fileSearch(string path, ofstream &wfile) { int main() { cpp file: /〇/△/□/test2.cpp #include <iostream> using namespace std; void print() { int calc(int a, int b) { int main() {
さしあたり
pomato-b.hatenablog.com
これの発展形
・ディレクトリ/ファイル一覧を標準出力
・指定ファイルの左詰めになっている行をファイルへ出力←new!
C++で指定したパス以下のディレクトリ/ファイル名を取得する
#include <iostream> #include <filesystem> #include <string> #include <vector> #include<algorithm> using namespace std; using std::filesystem::directory_iterator; using std::filesystem::is_directory; void fileSearch(string); vector<string> allPath; int main() { string input = ""; cin >> input; allPath.push_back(input); fileSearch(input); for (int i = 0; i < allPath.size(); i++) cout << allPath[i] << endl; return 0; } void fileSearch(string path) { vector<string> currentPath; for (const auto& file : directory_iterator(path)) { string tmp = file.path(); cout << tmp << endl; currentPath.push_back(tmp); } sort(currentPath.begin(), currentPath.end()); for (int i = 0; i < currentPath.size(); i++) { string tmp = currentPath[i]; allPath.push_back(tmp); if (is_directory(tmp)) fileSearch(tmp); } }
さしあたり
ソートしているから見やすくなっているはず...
(c++のはてな記法の ">|あれ|" あれってなんなのだ...
チョウの話
書いた動機
ついこの前、生物分類技能検定の4級を受けてきました。その検定の4級では身近な動植物の知識や高校の生物基礎のような内容を問う問題、それと植物のスケッチが出題されました。
そこで検定を受けて終わりではなく継続的に生物に関わっていこうというのがこの記事、これから書かれるであろう生物に関した記事を書く動機です。
チョウ類の基本的な特チョウ
成虫は翅は2対の4枚でストロー状の口を普段はぺろぺろキャンディのように丸めて持っています。彼らの主食は花の蜜だと思われがちですが樹液や腐った果実などにも集まってきます。
幼虫はその種類に応じた特定の植物の葉を食べます。アゲハであればミカンやサンショウのミカン科の葉を、日本の国蝶であるオオムラサキの幼虫はエノキの葉を好んで食べます。(たいていのチョウの成虫は好き嫌いがないようですが、オオムラサキはクヌギやコナラの樹液を好むそうです。したがって、エノキとクヌギやコナラが同時に多く生えている場所でないと生活できないのです。)
また、幼虫から蛹となり成虫になるという完全変態をすることも特徴の一つです。
チョウの分類
チョウ類はチョウ目の一部なのですが、このチョウ目にはガ類が含まれます。(チョウとガの区別は厳密にはない)
一般的にチョウ類とガ類を見分ける方法として触覚の形が挙げられ、ガ類はふさふさな触覚や糸状の細い触覚を持つのに対し、チョウ類は細い触覚に先端が丸く膨らんでいるものやかぎ状になっているものが多いです。
この記事はチョウ類を扱います。
チョウ目の下には
・アゲハチョウ上科
・アゲハチョウ科
・シロチョウ科
・シジミチョウ科
・タテハチョウ科
・セセリチョウ上科
・セセリチョウ科
・シャクガモドキ上科(1科1属)
・シャクガモドキ科
があり、だいたいどの科のチョウも日常的に見ることができます。(シャクガモドキは知らない)
(チョウ類-アゲハチョウ上科-セセリチョウ上科-シャクガモドキ上科-ガ類の近さらしい)
身近なチョウ
・アゲハ(アゲハチョウ科)
写真準備中
・オオムラサキ(タテハチョウ科)
写真準備中
・モンシロチョウ(シロチョウ科)
写真準備中
これまでに出会ったチョウたち
・ツマグロヒョウモン(タテハチョウ科)
高尾山山頂で撮った写真。
高尾山に登った時の記事↓
・アカボシゴマダラ(タテハチョウ科)
・ヒカゲチョウ(タテハチョウ科)
・チャバネセセリ(セセリチョウ科)
イチモンジセセリと似ているが後翅裏の白い斑点が弧を描いているように見えるのでチャバネセセリだと思われる。
おわりに
今回の記事はチョウについて結構ざっくりとした説明で個々のチョウの特徴などの深いところまで触れられていません。次にチョウについて書くとしたらハチによる寄生やアリとの共生について書いてみたいです。
実は写真を載せて皆さんに見てもらいたいのも記事を書く動機の一つだったりします。
写真がないところはこれから撮ります。
高尾山へ行きました
準備
よく(人生で5回くらい)高尾山には登りに行っていて、その時は自分一人のため革靴とか履いて手ぶらでポンポンポーンみたいに登っていくのですが、今回は友達と二人で登りに行ったため少し準備をしました。
・持ち物
-登山バッグ(多分32L)
-ペットボトル(水500ml*1,ポカリ500ml*1)
-手ぬぐい, タオル, ハンカチ, ポケットティッシュ
-救急セット
-地図
-帽子
-雨具
-カメラ
・装備
-パーカー
-Tシャツ
-登山ズボン(発汗性に優れてるやつ)
-登山靴
服装に関しては長そで長ズボン一択で、高い山ではないけれど一応日よけに帽子
地図とコンパスはセットで持った方がいいかも
ルート
ルートは
稲荷山コース
→山頂
→四号路
→少し登って薬王院
→リフト
→温泉
で行きました。これが最強だと思います。
六号路の川を登るのもいいと考えましたが前日に雨が降ったので安定を取って稲荷山コースにしました。
稲荷山コース(or六号路)を登るから登山靴を用意する必要があったんですね。
山頂ではいろいろな虫さんたちに出会えました。
鳥さんの声は勉強していないので誰がいたかはわかりません(次回リベンジ)
写真
発見当初は成虫のキアシドクガがたくさん飛んでいてこれもキアシドクガだろう(小並)とか思ってたら違うみたいです。
マイマイガの成虫は見られませんでした。
マイマイガの一齢幼虫には毒があるらしい。
キアシドクガの蛹は空になったのにしか出会えませんでしたorz
成虫さんはたくさん飛んでいてきれいでした
キアシドクガに毒はないらしい
タテハチョウ科の前足が退化していて四本に見えるいい写真だあ
山頂にはモンキアゲハやクロアゲハ(カラスアゲハかもしれない)がいっぱい飛んでた
最後に急な長い階段があるので注意
これはいい眺め
展望台の下に羽が破れたアサギマダラがひらひら飛んでいて近くで写真撮りたかったなあ
他にも写真はありますがここまでで
おわりに
めちゃくちゃ楽しかった
一人で行くのもいいけど友達と行くのも感動を共有できるうれしさがあってとてもよかった
高尾山は比較的低く登りやすいのでぜひ(一号路はTシャツ短パンでも登れる)
山頂には高尾山に住んでいる生き物を紹介する施設やうまい蕎麦屋があるので登る価値あり(ふもとにも生き物などを紹介する施設あり)
温泉はいいぞ
登山グッズはJack Wolfskin, モンベルで買ってます
TSPをGAで解いてみようという話
TSP(Traveling Salesman Problem)とは
・日本語で「巡回セールスマン問題」
・N個の都市と都市間の距離が与えられ,それぞれの都市を一回訪れ最初の都市に帰ってきたときの移動距離を最小化する問題
・全巡回経路を列挙して距離を計算して...とやっていると人生が終わってしまう(たしかそこらのpcだと13都市が限界)
wikipedia:巡回セールスマン問題
GA(Genetic Algorithm)とは
・日本語で「遺伝的アルゴリズム」
・解の候補を遺伝子に見立てて操作する手法で,ナップサック問題であればあるものを入れるときは"1"入れない時は"0"としてこれらの組み合わせで解を探す.TSPでは都市に通し番号(激ウマギャグ)をつけて(0,1,...,N)これらの順列を考えることで探索をする.
・あくまで近似解が得られるアルゴリズム
wikipedia:遺伝的アルゴリズム
GAの手順
1.初期化(現世代,次世代)
while(指定回数 or (最適解-近似解)<閾値 or 時間)
2.現世代を評価,近似解を更新
3.現世代から次世代を作成
4.次世代を現世代に代入
5.出力
・現世代から次世代を作成する方法は選択(淘汰)や親それぞれから遺伝子(経路)を引き継ぐ"交叉",突然変異がある
今回の形式
・ファイルから都市の個数とそれぞれの距離を入力する
・評価の方法
-単純に巡回距離
・選択の方法(未定)
・交叉の方法(未定)
・GAの終了条件(未定)
コード
※ファイル入力からグラフ作成,ランダムで現世代を作成,現世代の評価とsortまで実装済み
github.com
※追記:全列挙探索のソース書きました
おわりに
・これから頑張っていきます
C言語でシェルソート
シェルソートとは
・シェルさんが発表したソートアルゴリズムでクイックソートが発見されるまでは最高速のソートアルゴリズムとして知られていたらしい。
・単純なソートアルゴリズムと知られる挿入ソートにひと手間加えて計算量を挿入ソートでは"O(n^2)"だったのを"O(n^(1.25))~O(n^1.5)"まで減らした。
※挿入ソートとは
・バブルソートなどと同じ単純なソートアルゴリズムに数えられる。
イメージは箱の中身をすべて一回出して一つずつ箱に入れていく。その時にすでに入っている箱の中身と比較してしかるべき場所に挿入する。これをn-1回(最初の一つはすでに箱の中に入れているため)繰り返して要素を整列させていく。
最大でn*(n-1)/2回の比較がされるが、すでに整列されているものをソートにかけると(n-1)回で済む。つまり、ソート前の要素が整列されていればその分比較回数が減る。
追記: 交換回数は平均n/2回(多分)
挿入ソートと何が違うのか
・変数hを用いて要素をhの間隔で挿入ソートを行い、その間隔を狭めていき最終的にh=1で挿入ソートを行う。
大まかに挿入ソートを行っていき少しずつ細かくしていくイメージ。ただし、間隔hが常に偶数または奇数の場合比較されるものが変わらないためシェルソートの強みは発揮できない。
何回も挿入ソートを行うのでぱっと見計算量がもとより増えると思うかもしれないが、ある程度ソートされたものをソートしていくのでそれぞれのソートの効率がよく、計算量が減る。
※シェルソートの数学的な解析は完全にはされていないらしい
コード
#include <stdio.h> #include <stdlib.h> void shell_sort(int*, int); //シェルソートのプロトタイプ宣言 //void insertion_sort(int*, int); //挿入ソートのプロトタイプ宣言 void swap(int*, int*); //要素入れ替えのプロトタイプ宣言 int main(void) { int n; //データ数 scanf("%d", &n); //データ数入力 int a[n]; //ソート対象の配列 srand(0); //初期化 for (int i = 0; i < n; i++) { a[i] = rand(); //ランダムに配列の要素を決定 } for (int i = 0; i < n; i++) { //ソート前の配列要素の表示 if(i == 0) printf("%d", a[i]); else printf(" %d", a[i]); } printf("\n"); shell_sort(a, n); //シェルソート for (int i = 0; i < n; i++) { //ソート後の配列要素の表示 if(i == 0) printf("%d", a[i]); else printf(" %d", a[i]); } printf("\n"); return 0; } //シェルソート void shell_sort(int a[], int n) { int h, i, j; for (h = 1; h < n/9; h = h*3+1); //間隔hの決定 for (; h > 0; h /= 3) { //間隔hを狭めていく for (i = h; i < n; i++) { //ここから挿入ソート j = i; while ((j >= h) && (a[j-h] > a[j])) { swap(&a[j], &a[j-h]); j -= h; } } } return; } //挿入ソート /* void insertion_sort(int a[], int n) { int i, j; for (i = 1; i < n; i++) { j = i; while ((j >= 1) && (a[j-1] > a[j])) { swap(&a[j], &j[j-1]); j--; } } return; } */ //入れ替え void swap(int *a, int *b) { int tmp = *a; *a = *b; *b = tmp; return; }
実行結果
20 38 7719 21238 2437 8855 11797 8365 32285 10450 30612 5853 28100 1142 281 20537 15921 8945 26285 2997 14680 38 281 1142 2437 2997 5853 7719 8365 8855 8945 10450 11797 14680 15921 20537 21238 26285 28100 30612 32285
C言語でサイゼリヤナップサック問題-再帰
問題
出せる料金の上限値を決め、それを超えないように摂取カロリーが最大になるように商品を選ぶ
そのときの商品名と料金、摂取カロリーを出力せよ
処理の流れ
- ファイルからメニュー表(商品名,カロリー,値段)を取得
- 商品を端から深さ優先探索で取捨選択していく
- 制約として料金の上限値を超えた場合にはその時点でバックトラックしている(つもり)
- 深さ優先探索ですべての商品を考慮し終わったら、その組み合わせと摂取カロリーをそれぞれ配列と変数に持っておく
- 最終的な解を配列と変数から取得、表示
※これからほかの手法(動的計画法、ビット演算)と計算時間を比較したいので
メニュー表
商品名 カロリー コスト 彩りガーデンサラダ 130 299 小エビのサラダ 115 349 やわらかチキンのサラダ 134 299 わかめサラダ 92 299 イタリアンサラダ 196 299 シーフードサラダ 229 599 半熟卵とポークのサラダ 433 599 コーンクリームスープ 142 149 冷たいパンプキンスープ(季節限定) 105 149 たっぷり野菜のミネストローネ(季節限定) 222 299 削りたてペコリーノチーズ 59 100 ミニフィセル 188 169 ガーリックトースト 252 189 辛味チキン 374 299 アスパラガスのオーブン焼き(季節限定) 221 299 ポップコーンシュリンプ 215 299 エスカルゴのオーブン焼き 256 399 ムール貝のガーリック焼き 164 399 野菜ソースのグリルソーセージ 570 399 チョリソー 393 399 柔らか青豆の温サラダ 213 199 ほうれん草のソテー 138 199 キャベツとアンチョビのソテー 80 199 ポテトのグリル 366 199 セロリのピクルス(季節限定) 52 199 真イカのパプリカソース 138 199 フォッカチオ 214 119 プチフォッカ 214 139 セットプチフォッカ 107 79 フレッシュチーズとトマトのサラダ 203 299 フレッシュチーズとトマトのサラダ(Wサイズ) 406 598 プロシュート 162 399 プロシュート(Wサイズ) 324 798 熟成ミラノサラミ 95 299 熟成ミラノサラミ(Wサイズ) 190 598 マルゲリータピザ 568 399 パンチェッタのピザ 646 399 野菜ときのこのピザ 610 399 やわらかイカのアンチョビのピザ 593 499 バッファローモッツァレラのピザ 575 499 ミラノサラミのピザ 606 499 ほうれん草のグラタン(季節限定) 521 399 シーフードグラタン 537 499 アラビアータ 591 399 ミートソースボロニア風 582 399 半熟卵のミートソースボロニア風 672 468 アーリオ・オーリオ 560 299 キャベツのペペロンチーノ 686 399 タラコソースシシリー風 605 399 スープ入りトマト味ボンゴレ(季節限定) 686 499 パルマ風スパゲッティ 700 399 イカの墨入りスパゲッティ 610 499 カルボナーラ 865 499 アスパラガスとエビのクリームスパゲッティ(季節限定) 711 499 アラビアータ(Wサイズ) 1182 770 ミートソースボロニア風(Wサイズ) 1164 770 アーリオ・オーリオ(Wサイズ) 1120 574 キャベツのペペロンチーノ(Wサイズ) 1372 770 タラコソースシシリー風(Wサイズ) 1210 770 パルマ風スパゲッティ(Wサイズ) 1400 770 イカの墨入りスパゲッティ(Wサイズ) 1220 976 カルボナーラ(Wサイズ) 1730 976 アスパラガスとエビのクリームスパゲッティ(季節限定)(Wサイズ) 1422 976 トッピング半熟卵 90 69 ミラノ風ドリア 542 299 半熟卵のミラノ風ドリア 632 368 セットプチフォッカ付きミラノ風ドリア 649 378 いろどり野菜のミラノ風ドリア 590 399 エビとイカのドリア 624 499 シーフードパエリア 602 599 エビと野菜のトマトクリームリゾット 302 399 ハヤシ&ターメリックライス 638 499 半熟卵のハヤシ&ターメリックライス 728 568 ミックスグリル 823 599 ハンバーグステーキ 514 399 デミグラスソースのハンバーグ 628 499 野菜ソースのハンバーグ(ディアボラ風) 585 499 イタリアンハンバーグ 633 499 焼肉とハンバーグの盛合せ 709 599 若鶏のグリル(ディアボラ風) 541 499 柔らかチキンのチーズ焼き 588 499 パンチェッタと若鶏のグリル 663 599 リブステーキ 621 999 ライス 303 169 ラージライス 454 219 スモールライス 151 119 カプチーノ(アイスケーキ)(季節限定) 114 199 ティラミス(アイスケーキ) 131 199 シナモンフォッカチオ 246 169 プリンとカプチーノの盛合せ 330 399 プリンとティラミスの盛合せ 347 399 ミルクアイスのせシナモンフォッカチオ 346 319 ミルクジェラート 100 199 シチリア産レモンのソルベ 127 199 イタリアンプリン 216 249 チョコレートケーキ 166 299 コーヒーゼリー 162 299 トリフアイスクリーム 164 369
コード
#include<stdio.h> #include<string.h> #include<time.h> #define MAX_N 110 //商品の最大個数 #define MAX_C 1000 //出せる最大金額 typedef struct MENU{ char name[256]; //商品名 int cal; //カロリー int cost; //値段 }M; int ans[MAX_N]={}; //解 int cand[MAX_N]={}; //解候補 M m[MAX_N]; //商品のデータ int N; //読み込んだ商品の種類数 int max_cal=0; //最大カロリー int costy=0; //最大カロリーを実現するためのコスト void knap(int i,int sum_cal,int sum_cos){ //出せる金額を上回った if(sum_cos>MAX_C) return; //すべての品物について考えた if(i==N){ if(sum_cos<=MAX_C && max_cal<sum_cal){ memcpy(ans,cand,sizeof(cand)); max_cal = sum_cal; costy = sum_cos; } return; } //商品iを入れる cand[i] = 1; knap(i+1,sum_cal+m[i].cal,sum_cos+m[i].cost); //商品iを入れない cand[i] = 0; knap(i+1,sum_cal,sum_cos); return; } int main(void){ FILE *fp; char fname[] = "test.txt"; int cnt=0; clock_t start,end; if((fp = fopen(fname,"r"))==NULL){ printf("errer\n"); return -1; }else{ printf("%s file opened\n",fname); } while(fscanf(fp,"%s %d %d",m[cnt].name,&m[cnt].cal,&m[cnt].cost)!=EOF) cnt++; fclose(fp); N = cnt; //メニュー一覧 printf("%d\n",N); for(int i=0;i<N;i++) printf("name:%s\ncal:%d\ncost:%d\n\n",m[i].name,m[i].cal,m[i].cost); printf("\n"); start = clock(); //開始時刻を取得 knap(0,0,0); //再帰ナップ end = clock(); //終了時刻を取得 //最終解 printf("you should order these! (cost<=%d)\n\n",MAX_C); for(int i=0;i<N;i++){ if(ans[i]==1){ printf("name:%s\ncal:%d\ncost:%d\n\n",m[i].name,m[i].cal,m[i].cost); } } printf("SUM_COST:%dyen\n",costy); //かかるコスト printf("MAXI_CAL: %dcal\n\n",max_cal); //摂取カロリー printf("calc_time:%fs\n\n",(double)(end-start)/CLOCKS_PER_SEC); //計算時間 return 0; }
実行結果
※都合上メニュー一覧は表示せず
you should order these! (cost<=1000) name:ポテトのグリル cal:366 cost:199 name:アーリオ・オーリオ(Wサイズ) cal:1120 cost:574 name:ラージライス cal:454 cost:219 SUM_COST:992yen MAXI_CAL: 1940cal calc_time:0.073000s
想定される解は得られたようだ