轉自：http://www.blog.edu.cn/user2/sempr/archives/2006/1142716.shtml
#include<cstdio>
const int MAX = 10000;
int a[MAX],b[MAX];
int change;
void merge(int p, int q, int r)
{
int i, j = 0;
int begA = p, endA = q, begB = q+1, endB = r;
while(begA <= endA && begB <= endB)
{
if(a[begA] <= a[begB])
b[j++] = a[begA++];
else
{
b[j++] = a[begB++];
change += q - begA + 1;
}
}
while(begA <= endA)
b[j++] = a[begA++];
while(begB <= endB)
b[j++] = a[begB++];
for(i = 0; i < j; i++)
a[p+i] = b[i];
}
void mergeSort(int first, int last)
{
if(first < last)
{
int mid = (first + last) / 2;
mergeSort(first, mid);
mergeSort(mid+1, last);
merge(first, mid, last);
}
}
int main()
{
return 0;
}
posted @
2006-10-11 00:27 beyonlin 閱讀(1085) |
評論 (0) |
編輯 收藏
d[i]用來保存起始點beg到點i的最短路徑。
c[i][j]為邊<i,j>的權。
如果邊<i,j>不存在，則置c[i][j]=INF。
path[i]用來保存最短路徑中點i的前一個頂點。
#include<cstdio>
const int MAX = 10000;
const int INF = 1000000;
int d[MAX];
int c[MAX][MAX];
bool flag[MAX];
//int path[MAX];
int Dijkstra(int beg, int n)
{
int i, j, u, tmp;
for(i = 1; i <= n; i++)
{
d[i] = c[beg][i];
flag[i] = false;
/*if(d[i] == INF)
path[i] = 0;
else
path[i] = beg;*/
}
d[beg] = 0; flag[beg] = true;
for(i = 1; i <= n; i++)
{
tmp = INF; u = beg;
for(j = 1; j <=n; j++)
{
if(!flag[j] && d[j] < tmp)
{
u = j;
tmp = d[j];
}
}
flag[u] = true;
for(j = 1; j <= n; j++)
{
if(!flag[j] && c[u][j] < INF)
{
if(d[u] + c[u][j] < d[j])
d[j] = d[u] + c[u][j];
//path[j] = u;
}
}
}
return 0;
}
int main()
{
return 0;
}
posted @
2006-10-10 00:22 beyonlin 閱讀(3835) |
評論 (0) |
編輯 收藏
d[i][j]保存邊<i,j>的權。
如果邊<i,j>不存在，則置d[i][j]為INF。
#include<cstdio>
const int MAX=10000;
const int INF=1000000;
int d[MAX][MAX];
int floyd (int n)
{
for(int k =1 ; k <= n; k++)
{
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= n; j++)
{
if(d[i][k] + d[k][j] < d[i][j])
d[i][j] = d[i][k] + d[k][j];
}
}
}
????????return 0;
}
int main()
{
return 0;
}
floyd后，如果d[i][j]>=INF，則點i到點j沒有路。
else點i到點j的最短路徑長度為d[i][j]。
posted @
2006-10-09 00:15 beyonlin 閱讀(1629) |
評論 (0) |
編輯 收藏最近發現自己對數論幾乎是一竅不通。
是時候開始學了。
從零開始……
判斷一個數是否為質數：
bool prime(int a)
{
for(int i=2;i<=sqrt(a);i++)
{
if(a%i==0)
return false;
}
return true;
}
posted @
2006-10-08 00:40 beyonlin 閱讀(887) |
評論 (2) |
編輯 收藏轉載自：http://www.shnenglu.com/zerolee/archive/2006/09/12/12335.html
增添于網上的一些書單：
C++/OPP/OOD系列:
層級一：語法/語意(C++)
[Lippman2000] Essential C++
Essential C++,by Stanley B. Lippman Addison Wesley Longman 2000,276 pages
Essential C++ 中文版 ，侯俊杰 譯，282頁
[Andrew Koeing & Barbara MOO] Accelerated C++
Accelerated c++, Andrew Koeing & Barbara MOO, Addison Wesley, 2000
[Eckel2000] Thinking in C++
Thinking in C++ 2/e Bruce Eckel 2000 1470 pages Prentice Hall
C++ 編程思想，劉宗田等 譯，420頁
[Lippman98] C++Primer
C++ Primer,3rd Editoin,by Stanley Lippman and Josee Lajoie
Addison Wesley Longman,1998 1237 pages
C++ Primer 中文版，侯俊杰 譯，1999，1237頁
[Struostrup2000] The C++ Programming Language
The C++ Programming Language,Special Editoin,by Bjarne Stroustrup
Addison Wesley Longman,2000,1017 pages
[ANSI C++] C++規格書 1998.9.1 PDF格式
ANSI C++ 1996 Draft
層級二：專家經驗(C++/OOP)
[Meyers96] More Effective C++
More Effective C++, by Scott Meyers,Addison Wesley,1996,318pages
More Effective C++中文版，侯俊杰，培生 2000. 318頁
[Meyers98] Effective C++
Effective C++, Second Edition,by Scott Meyers,Addison Wesley Longman,1998.256pages
Effective C++ 2/e 中文版,侯俊杰,培生 2000.256頁
Effective C++, Third Edition, by Scott Meyers, Addison Wesley Longman.
[Sutter99] Exceptional C++
Exceptional C++，by Herb Sutter,Addison Wesley Longman,2000.208pages
Exceptional C++中文版，侯俊杰,培生 2000.248頁
[Sutter2001]More Exceptional C++
More Exceptional C++ by Herb Sutter, Addison Wesley Longman, 2001.
[Sutter2004]Exception C++ Style
Exception C++ Style by Herb Sutter, Addison Wesley Longman, 2004.
層級三：底層機制(C++ Object Model)
[Ellis90] The Annotated C++ Reference Manual
The Annotated C++ Reference Manual,by Margaret A.Ellis and Bjarne Stroustrup
Addison Wesley Longman,1990,447 pages.
[Lippman96] Inside the C++ Object Model
Inside the C++ Object Model,by Stanley Lippman,Addison Wesley Longman,1996,280pages
深度探索C++物件模型，侯俊杰 譯
層級四：設計觀念的復用(C++/Patterns)
[Gamma95] Design Patterns：Elements of Reusable Object Oriented Software,
by Erich Gamma,Richard Helm,Ralph Johnson,and John Vlissides,Addison Wesley,1995.395pages
設計模式,李英軍等譯,機械工業出版社,2000.254頁
[Alex2001]Modern C++ Design: Generic Programming and Design Patterns Applied
by Andrei Alexandrescu,Addison-Wesley,2001,352Paper
Genericity/STL系列(與層級二同步）:
第一個境界是使用STL:
[Josuttis99]:The C++ Standard Library －A Tutorial and Reference,by Nicolai M.Josuttis,
Addison Wesley 1999.799pages
第二個境界是了解泛型技術的內涵與STL的學理:
[Austern98]:Generic Programming and the STL -Using and Extending the C++ Standard
Template library,by Matthew H.Austern,Addison Wesley 1998.548page
第三個境界是擴充STL:
[Stepanov2001]:C++ Standard Template Library by P.J.Plauger,Alexander A.Stepanov,
Meng Lee,David R.Musser,Prentice Hall 2001
其他書目：
1. Large-scale C++ software Design, John Lako, Addison Wesley, 1996
2. Effective STL, Scott Meyers, Addison Wesley, 1995
3. C++ FAQs, 2nd, Marshall Cline, Greg Lomow, Mike Girou, Addison Wesley, 1998
4. C++ Gotchas, Stephen Dewhurst, Addison Wesley, 2002
5. C++ templates, the complete Guide, Daveed Vandevoorde & Nicolar M.Josuttis, Addison Wesley, 2002
6. Standard C++ iostreams and Locals, Angelika Langer & Klaus Kreft, Addison Wesley, 2000
7. Design & Evolution of C++, BS, Addison Wesley, 1994
8. Modern C++ Design, Andrie Alexandrescu, Addison Wesley, 2001
9. Generative Programming, Krzysztof Czarnecki & Ulrich Eisencecker, Addison Wesley, 2000
10.Pattern-oriented software architecture, Vol1:A system of patterns, Frank Buschmann, 1996
11. STL 源碼剖析，侯杰
12. C++ Coding Standards 101 Rules Guidelines, Andrie Alexandrescu & Herb Sutter, Addison Wesley, 2005
posted @
2006-09-21 00:13 beyonlin 閱讀(537) |
評論 (0) |
編輯 收藏