|
|
2007年6月3日
官方的一个很赞的做法，Divide and Conquer，核心部分：
 void
genfrac(int n1, int d1, int n2, int d2)
   {
  if(d1+d2 > n) /**//* cut off recursion */
 return;
genfrac(n1,d1, n1+n2,d1+d2);
fprintf(fout, "%d/%d\n", n1+n2, d1+d2);
genfrac(n1+n2,d1+d2, n2,d2);
 }
最朴素的做法
/**//*
PROG: frac1
ID: 06301031
LANG: C++
*/
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;
class Fraction {
int gcd(int x, int y);
public:
int numerator;
int denominator;
Fraction(int pa, int pb);
bool reductable();
};
bool compareFrac(const Fraction& f1, const Fraction& f2);
int main() {
ifstream fin("frac1.in");
ofstream fout("frac1.out");
int n;
fin >> n;
vector<Fraction> fracs;
int i, j;
fracs.push_back(Fraction(0, 1));
for (i = 1; i <= n; i++) {
for (j = 1; j <= i; j++) {
Fraction frac(j, i);
if (!frac.reductable()) {
fracs.push_back(frac);
 }
}
}
sort(fracs.begin(), fracs.end(), compareFrac);
vector<Fraction>::iterator iter;
for (iter = fracs.begin(); iter != fracs.end(); iter++) {
fout << iter->numerator << '/' << iter->denominator << endl;
}
return 0;
}
Fraction::Fraction(int pa, int pb) {
numerator = pa;
denominator = pb;
}
bool Fraction::reductable() {
return (gcd(numerator, denominator) != 1);
}
int Fraction::gcd(int x, int y) {
if (x < y) swap(x, y);
if (x % y == 0) return y;
return gcd(y, x % y);
}
bool compareFrac(const Fraction& f1, const Fraction& f2) {
return (long)f1.numerator * (long)f2.denominator < (long)f1.denominator * (long)f2.numerator;
}
USACO上的简单介绍，都快忘了各个术语的中文名了
graph
vertex 顶点 (pl. vertexes / vertices)
edge
edge-weighted 带权图（貌似中文是这么叫的吧）
weight
self-loop 自环
simple graph 简单图，不存在自环或两条（及以上）连接相同两点的边。multigraph 与之相对
degree
adjacent (to)
sparse graph 稀疏图，边数少于最大值（n*(n-1)/2）的图。与之相对的是dense graph。
(un)directed graph (有)无向图
out-degree in-degree 有向图顶点的出度/入度
path
cycle 回路
图的表示：
edge list
adjecency matrix
adjacency list
implict
连通性： connected component 连通分量 strongly connected component 强连通分量 subgraph 子图. The subgraph of G induced by V' is the graph (V', E') bipartite 二分图 complete 任意两点间都有边
1. 关于函数指针
The C++ Programming Language上的一段示例代码：
map<string, int> histogram;
void record(const string& s)
{
histogram[s]++;
}
void print(const pair<const string, int>& r)
{
cout << r.first << ' ' << r.second << '\n\;
}
int main()
{
istream_iterator<string> ii(cin);
istream_iterator<string> eos;
for_each(ii, eos, record);
for_each(histogram.begin(), histogram.end(), print);
}
其中record和print是以函数指针的形式传递给for_each的。感觉这种方法最清晰、直接。
Java似乎更多的是用接口来达到类似的效果的，比如Collections.sort(Comparable)，通常通过匿名内部类来进行自定义元素的比较，从而排序。但是这在语义上已经不是函数了，而是将被排序对象解释为实现了Comparable接口的对象。
另外Java反射机制中也有Mehod方法，觉得也可以通过传递Method类，然后在sort方法中调用这个Method的invoke方法，这应该更接近函数指针的语义。但没看到过这样的实例。
C#则引入了委托的概念，通过delegate关键字声明该方法。多一个关键字感觉就是啰唆了点。 -,-
现在开始对第一次在Thinking in Java中看到的Callback回调机制有了一点感觉。当时看的时候很难理解。
看来在学习某一门语言的时候有一定其他语言的背景进行比较，很容易加深理解。
2. 使用地址传递结构，减少开销
学C++最不适应的就是指针的应用，因为没有C的基础，尽管高中竞赛用的是Pascal，也用指针实现了trie、图的链式表示等比较复杂的数据结构，但是也没有像C++这样指针穿插在整个程序中的，当然C更多。
C++传递结构时默认是先复制一份拷贝，然后函数操作的是该拷贝，而不是Java中的传递引用（当然Java没有结构这一类型）。
C++ Primer Plus中指出要
1) 调用函数时传递地址&myStruct
2) 形参声明为指针MyStruct *
3) 访问成员使用操作符 ->
3. 将引用用于结构
同样，为了节省时空开销，在函数返回值时尽量使用引用。
const MyStruct & use(MyStruct & mystruct)
注意最好将返回的引用声明为const，否则可以使用这样的代码：
use(myStruct).used = 10;
容易产生语义混乱。
但在某些时候必须去掉const关键字。
算法：
进入大学后，对算法这些基础的看法改变了好几次。
高中里认为搞ACM没什么意义，觉得和应试差不多。
但是大学里有意无意的一些接触后，发现它涉及了大量应用数学的知识，对基础的提高十分有用。
保送的时候志愿填了数学系，不就是为了打好数学基础吗？
从功利的角度讲，有ACM的经历以后进IT公司自然可以方便不少。
英语：
从小学到高中，英语一直是强项，考试不需要突击，课本单词不需要刻意背诵，语言点很少复习，高中的英语考试让我对自己的英语过于自信了。
然后进了大学，处处受到强人的打击，上学期拿了B+觉得已经不错了。到现在这个英语班已经成为中等偏下的学生了，无论是词汇量还是听说能力。
sigh，暑假要报个补习班了。
至于其他的应用，asp.net ruby 之类的东西，权且当玩具学学吧，等需要应用的时候再好好看未必来不及，关键要有扎实的基础。
希望这个想法在放假前不会改变。
|