読者です 読者をやめる 読者になる 読者になる

windowsでwgetの代わりは

Windowswget使いたい場面があったけど、ソフトインストールするのは癪だったので、プログラムちゃちゃっと書いて見ることにした
pythonでやったらほんとにちゃちゃっと終わった
が、出力については要改良BeautifulSoupすごい。prettify()メソッドが勝手に整形してくれた

import sys
import urllib2
from BeautifulSoup import BeautifulSoup as bs4
url = sys.argv[1]
html = urllib2.urlopen(url)
soup = bs4(html.read())
f = open(url[7:]+'.html', 'w')
f.write(str(soup))
f.close()

参考
qiita.com

簡単なgraphの実装

頂点とそれと接続する頂点の情報をもつグラフ表現を書いた
なんとなくprintメソッドが欲しくて書くけど,getメソッドを作ったほうがいいんだろうか

#include <iostream>
#include <vector>

using namespace std;

/*
 * グラフの表現
 */
class graph{
private:
	struct vertex{
		int id;
		vector <vertex*> edge;
	};
public:
	vertex *G;
	int graph_size;
	graph(int size){
		G = new vertex[size];
		graph_size = size;
		for(int i=0; i<size; i++){
			G[i].id = i;
		}
	}

	void append(int target_id, int insert_id){
		// if( find(G[target_id].edge->begin(),G[target_id].edge->end(),&G[insert_id])!=G[target_id].edge->end() ){
		// 	G[target_id].edge->push_back(&G[insert_id]);
		// }
		for(int i=0; i<G[target_id].edge.size(); i++){
			if(G[target_id].edge[i]->id == insert_id) return;
		}
		G[target_id].edge.push_back(&G[insert_id]);

	}

	void print(){
		for(int i=0; i<graph_size; i++){
			cout << "vertex: " << G[i].id << endl << "edge: ";
			for(int j=0; j<G[i].edge.size(); j++){
				cout <<  G[i].edge[j]->id << " ";
			}
			if(G[i].edge.size()==0) cout << "nothing.";
			cout << endl;
		}
	}

};

int main(void){
	int n; cin >> n;
	graph g(n);
	for(int i=0; i<n; i++){
		int id; cin >> id;
		int m; cin >> m;
		for(int j=0; j<m; j++){
			int temp; cin >> temp;
			g.append(id,temp);
		}
	}
	g.print();
	return 0;
}

/*
sample input
5
0 4 1 2 3 4
1 0
2 2 3 4
3 0
4 0


*/

出力結果

続きを読む

union_findの実装

#include <iostream>
#include <cstring>
#include <vector>

using namespace std;

class union_find{
private:
	int *par;
	int *rank;
	int size;
public:	
	union_find(int n){
		par = new int[n];
		rank = new int[n];
		size = n;
		for(int i=0; i<n; i++){
			par[i] = i;
			rank[i] = 0;
		}
	}

	int find(int x){
		if(par[x]==x){
			return x;
		}else{
			return par[x] = find(par[x]);
		}
	}

	void unite(int x, int y){
		x = find(x);
		y = find(y);
		if(x==y) return;

		if(rank[x] < rank[y]){
			par[x]=y;
		}else{
			par[y]=x;
			if(rank[x] == rank[y]) rank[x]++;
		}
	}

	bool same(int x, int y){
		return find(x) == find(y);
	}

	void print(){
		vector <int> t_unit(size);

		int count=0;

		for(int i=0; i<size; i++){
			if(t_unit[i]==0){
				cout << "group " << count++ << endl;
				t_unit[i]=1;
			}else{
				continue;
			}
			for(int j=i; j<size; j++){
				if(same(i,j)){
					cout << j << " ";
					t_unit[j]=1;
				}
			}
			cout << endl;

		}
	}
};

int main(void){
	union_find uf(10);

	uf.print();
	cout << "unite: 0-1" << endl;
	uf.unite(0,1);
	uf.print();
	cout << "unite: 2-3" << endl;
	uf.unite(2,3);
	uf.print();
	cout << "unite: 1-2" << endl;
	uf.unite(1,2);
	uf.print();
	return 0;
}

出力結果

続きを読む

初めての投稿

test

ナップサック問題を解いた

深さ優先探索を用いたものと、漸化式を利用した2重ループを用いた解法の2つ

#include <iostream>
#include <map>
#include <queue>
#include <algorithm>
#include <cstring>

using namespace std;
typedef pair<int,int> P;
int dfs(vector <P> vec, int i, int w, int v, int W){
if(i==vec.size() || w>=W) return 0;
return max( dfs(vec,i+1,w+vec[i].first, v+vec[i].second,W)+v,dfs(vec,i+1,w, v,W));

}
int main(void){
int n; cin >> n;
vector <P> v(n);
for(int i=0; i<n; i++){
int a,b; cin >> a >> b;
v[i] = P(a,b);
}
int w; cin >> w;
// sort(v.begin(), v.end());
cout << dfs(v,0,0,0,w) << endl;

// without dfs only loop

// int** dp = new int*[n+1];
// for(int i=0; i<n+1; i++){
// dp[i] = new int[w+1];
// }
int dp[5][6];
memset(dp,0,sizeof(dp));
for(int i=0; i<n+1; i++){
for(int j=0; j<w+1; j++){
cout << dp[i][j] << " ";
}
cout << endl;
}


for(int i=n-1; i>=0; i--){
for(int j=1; j<w+1;j++){
if(j<v[i].first){
dp[i][j]=dp[i+1][j];
}else{
dp[i][j] = max(dp[i+1][j], dp[i+1][j-v[i].first]+v[i].second);
}
}
}
cout << dp[0][5] << endl;

for(int i=0; i<n+1; i++){
for(int j=0; j<w+1; j++){
cout << dp[i][j] << " ";
}
cout << endl;
}

return 0;

}

/* sample input

4
2 3
1 2
3 4
2 2
5

ans
7
*/

<||