妈了个头！！
等老子学好了J2EE，俺也要自己写一个blog程序
真的可以用天差地别来形容啊，基本上差一个数量级
所以现在对C++还是有点留恋的，不舍得完全放弃掉
其实能把C++这么灵活的语言运用的灵活的程序员才是真正有水平的
而且C++在组织很多数据结构上确实比Java要舒服一点
可能是因为C++毕竟是从面向过程的C扩展而来的吧
不知道我这种说话会不会被人喷……
有空还是捡一下C++吧
1 # circuit is a global array
2 find_euler_circuit
3 circuitpos = 0
4 find_circuit(node 1)
5
6 # nextnode and visited is a local array
7 # the path will be found in reverse order
8 find_circuit(node i)
9
10 if node i has no neighbors then
11 circuit(circuitpos) = node i
12 circuitpos = circuitpos + 1
13 else
14 while (node i has neighbors)
15 pick a random neighbor node j of node i
16 delete_edges (node j, node i)
17 find_circuit (node j)
18 circuit(circuitpos) = node i
19 circuitpos = circuitpos + 1
20
1 unsigned long cantor(unsigned long S)
2 {
3 long x=0,i,p,k,j;
4 bool hash[8]={false};
5 for (i=8;i>=2;i--)
6 {
7 k=S>> 3*(i-1);
8 S-=k<<3*(i-1);
9 hash[k]=true;
10 p=k;
11 for (j=0;j<=k-1;j++)
12 if (hash[j])
13 p--;
14 x+=fac[i-1]*p; //fac存的是阶乘 fac[1] = 1, fac[2] = 2, fac[3] = 6
15 }
16 return x;
17 }
其实就是求全排列中，某一个排列的序号
比如321，对应1，2，3的全排列的第6号
上面这个是8禁止存储的，有利于位操作
http://www.csanimated.com/animation.php?t=Bellman-Ford_algorithm
1 procedure BellmanFord(list vertices, list edges, vertex source)
2 // This implementation takes in a graph, represented as lists of vertices
3 // and edges, and modifies the vertices so that their distance and
4 // predecessor attributes store the shortest paths.
5
6 // Step 1: Initialize graph
7 for each vertex v in vertices:
8 if v is source then v.distance := 0
9 else v.distance := infinity
10 v.predecessor := null
11
12 // Step 2: relax edges repeatedly
13 for i from 1 to size(vertices)-1:
14 for each edge uv in edges: // uv is the edge from u to v
15 u := uv.source
16 v := uv.destination
17 if v.distance > u.distance + uv.weight:
18 v.distance := u.distance + uv.weight
19 v.predecessor := u
20
21 // Step 3: check for negative-weight cycles
22 for each edge uv in edges:
23 u := uv.source
24 v := uv.destination
25 if v.distance > u.distance + uv.weight:
26 error "Graph contains a negative-weight cycle"
27
An implementation from wiki
1 #include <limits.h>
2 #include <stdio.h>
3 #include <stdlib.h>
4
5 /* Let INFINITY be an integer value not likely to be
6 confused with a real weight, even a negative one. */
7 #define INFINITY ((1 << 14)-1)
8
9 typedef struct {
10 int source;
11 int dest;
12 int weight;
13 } Edge;
14
15 void BellmanFord(Edge edges[], int edgecount, int nodecount, int source)
16 {
17 int *distance = malloc(nodecount * sizeof *distance);
18 int i, j;
19
20 for (i=0; i < nodecount; ++i)
21 distance[i] = INFINITY;
22 distance[source] = 0;
23
24 for (i=0; i < nodecount; ++i) {
25 int somethingchanged = 0;
26 for (j=0; j < edgecount; ++j) {
27 if (distance[edges[j].source] != INFINITY) {
28 int new_distance = distance[edges[j].source] + edges[j].weight;
29 if (new_distance < distance[edges[j].dest]) {
30 distance[edges[j].dest] = new_distance;
31 somethingchanged = 1;
32 }
33 }
34 }
35 /* if one iteration had no effect, further iterations will have no effect either */
36 if (!somethingchanged) break;
37 }
38
39 for (i=0; i < edgecount; ++i) {
40 if (distance[edges[i].dest] > distance[edges[i].source] + edges[i].weight) {
41 puts("Negative edge weight cycles detected!");
42 free(distance);
43 return;
44 }
45 }
46
47 for (i=0; i < nodecount; ++i) {
48 printf("The shortest distance between nodes %d and %d is %d\n",
49 source, i, distance[i]);
50 }
51
52 free(distance);
53 return;
54 }
55
56 int main(void)
57 {
58 /* This test case should produce the distances 2, 4, 7, -2, and 0. */
59 Edge edges[10] = {{0,1, 5}, {0,2, 8}, {0,3, -4}, {1,0, -2},
60 {2,1, -3}, {2,3, 9}, {3,1, 7}, {3,4, 2},
61 {4,0, 6}, {4,2, 7}};
62 BellmanFord(edges, 10, 5, 4);
63 return 0;
64 }
1 /*************************************************************************
2 * Compilation: javac QuickSort.java
3 * Execution: java QuickSort N
4 *
5 * Generate N random real numbers between 0 and 1 and quicksort them.
6 *
7 * On average, this quicksort algorithm runs in time proportional to
8 * N log N, independent of the input distribution. The algorithm
9 * guards against the worst-case by randomly shuffling the elements
10 * before sorting. In addition, it uses Sedgewick's partitioning
11 * method which stops on equal keys. This protects against cases
12 * that make many textbook implementations, even randomized ones,
13 * go quadratic (e.g., all keys are the same).
14 *
15 *************************************************************************/
16
17 public class QuickSort {
18 private static long comparisons = 0;
19 private static long exchanges = 0;
20
21 /***********************************************************************
22 * Quicksort code from Sedgewick 7.1, 7.2.
23 ***********************************************************************/
24 public static void quicksort(double[] a) {
25 shuffle(a); // to guard against worst-case
26 quicksort(a, 0, a.length - 1);
27 }
28
29 // quicksort a[left] to a[right]
30 public static void quicksort(double[] a, int left, int right) {
31 if (right <= left) return;
32 int i = partition(a, left, right);
33 quicksort(a, left, i-1);
34 quicksort(a, i+1, right);
35 }
36
37 // partition a[left] to a[right], assumes left < right
38 private static int partition(double[] a, int left, int right) {
39 int i = left - 1;
40 int j = right;
41 while (true) {
42 while (less(a[++i], a[right])) // find item on left to swap
43 ; // a[right] acts as sentinel
44 while (less(a[right], a[--j])) // find item on right to swap
45 if (j == left) break; // don't go out-of-bounds
46 if (i >= j) break; // check if pointers cross
47 exch(a, i, j); // swap two elements into place
48 }
49 exch(a, i, right); // swap with partition element
50 return i;
51 }
52
53 // is x < y ?
54 private static boolean less(double x, double y) {
55 comparisons++;
56 return (x < y);
57 }
58
59 // exchange a[i] and a[j]
60 private static void exch(double[] a, int i, int j) {
61 exchanges++;
62 double swap = a[i];
63 a[i] = a[j];
64 a[j] = swap;
65 }
66
67 // shuffle the array a[]
68 private static void shuffle(double[] a) {
69 int N = a.length;
70 for (int i = 0; i < N; i++) {
71 int r = i + (int) (Math.random() * (N-i)); // between i and N-1
72 exch(a, i, r);
73 }
74 }
75
76
77
78 // test client
79 public static void main(String[] args) {
80 int N = Integer.parseInt(args[0]);
81
82 // generate N random real numbers between 0 and 1
83 long start = System.currentTimeMillis();
84 double[] a = new double[N];
85 for (int i = 0; i < N; i++)
86 a[i] = Math.random();
87 long stop = System.currentTimeMillis();
88 double elapsed = (stop - start) / 1000.0;
89 System.out.println("Generating input: " + elapsed + " seconds");
90
91 // sort them
92 start = System.currentTimeMillis();
93 quicksort(a);
94 stop = System.currentTimeMillis();
95 elapsed = (stop - start) / 1000.0;
96 System.out.println("Quicksort: " + elapsed + " seconds");
97
98 // print statistics
99 System.out.println("Comparisons: " + comparisons);
100 System.out.println("Exchanges: " + exchanges);
101 }
102 }
103
# distance(j) is distance from tree to node j
# source(j) is which node of so-far connected MST
# is closest to node j
1 For all nodes i
2 distance(i) = infinity # no connections
3 intree(i) = False # no nodes in tree
4 source(i) = nil
5 treesize = 1 # add node 1 to tree
6 treecost = 0
7 intree(1) = True
8 For all neighbors j of node 1 # update distances
9 distance(j) = weight(1,j)
10 source(j) = 1
11 while (treesize < graphsize)
12 find node with minimum distance to tree; call it node i
13 assert (distance(i) != infinity, "Graph Is Not Connected")
# add edge source(i),i to MST
14 treesize = treesize + 1
15 treecost = treecost + distance(i)
16 intree(i) = True # mark node i as in tree
# update distance after node i added
17 for all neighbors j of node i
18 if (distance(j) > weight(i,j))
19 distance(j) = weight(i,j)
20 source(j) = i
摘要: 留个纪念吧
Code highlighting produced by Actipro CodeHighlighter (freeware)
http://www.CodeHighlighter.com/
--> 1 import java.io.*;
2 import java.util... 阅读全文
# distance(j) is distance from source vertex to vertex j
# parent(j) is the vertex that precedes vertex j in any shortest path
# (to reconstruct the path subsequently)
1 For all nodes i
2 distance(i) = infinity # not reachable yet
3 visited(i) = False
4 parent(i) = nil # no path to vertex yet
5 distance(source) = 0 # source -> source is start of all paths
6 parent(source) = nil
7 8 while (nodesvisited < graphsize)
9 find unvisited vertex with min distance to source; call it vertex i
10 assert (distance(i) != infinity, "Graph is not connected")
11 visited(i) = True # mark vertex i as visited
# update distances of neighbors of i
12 For all neighbors j of vertex i
13 if distance(i) + weight(i,j) < distance(j) then
14 distance(j) = distance(i) + weight(i,j)
15 parent(j) = i
# dist(i,j) is "best" distance so far from vertex i to vertex j
# Start with all single edge paths.
For i = 1 to n do
For j = 1 to n do
dist(i,j) = weight(i,j)
For k = 1 to n do # k is the `intermediate' vertex
For i = 1 to n do
For j = 1 to n do
if (dist(i,k) + dist(k,j) < dist(i,j)) then # shorter path?
dist(i,j) = dist(i,k) + dist(k,j)
|
|
|
随笔：99
文章：-1
评论：17
引用：0
| | 日 | 一 | 二 | 三 | 四 | 五 | 六 |
|---|
| 30 | 31 | 1 | 2 | 3 | 4 | 5 | | 6 | 7 | 8 | 9 | 10 | 11 | 12 | | 13 | 14 | 15 | 16 | 17 | 18 | 19 | | 20 | 21 | 22 | 23 | 24 | 25 | 26 | | 27 | 28 | 29 | 30 | 1 | 2 | 3 | | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|
留言簿(1)
随笔分类
随笔档案
相册
搜索
最新评论
|
|