代码--算法分析与总结

① 八皇后问题：

#include #include #include

int main(int argc,char *argv[]){ int q[1024]; int i,j,k,c,n; time_t tm; switch(argc){ case 1: n=8; break; case 2: n=atoi(argv[1]); if(i<=0||i>=1024) return 0; break; default: return 0; }

tm=time(0);

for(i=0,c=0,q[0]=0;;){ if(n==q[i]){ if(0==i) break; i--; q[i]++; continue; } for ( j=0; ji++; q[i] = 0; } } else q[i]++; }

printf(\"total:%d,%dsec\\n\ return 0; }

部分运行结果：

② 活动安排问题：

#include

void GreedySelector(int n,int s[],int f[],bool A[]){ A[1]=true; int j=1;

for(int i=2;if[j]){ A[i]=true; j=i; }else{ A[i]=false; } } }

void main(){

int s[12]={0,1,3,0,5,3,5,6,8,8,2,12}; int f[12]={0,4,5,6,7,8,9,10,11,12,13,14}; bool A[11];

GreedySelector(12,s,f,A);

printf(\"最终安排的活动序号为：\\n\"); for(int i=0;i<12;i++){ if(A[i]==true){ printf(\"%d\\n\ } } }

运行结果：

③ 二分法求数组元素的最大值与最小值：

#include

int getMax(int array[12], int i, int j) { int Max1 = 0; int Max2 = 0; if (i == j) { return Max1 = Max2 = array[j]; } else if (i == (j - 1)) { Max1 = array[i]; Max2 = array[j]; return Max1 > Max2 ? Max1 : Max2; } else { int mid = (i + j) / 2; Max1 = getMax(array, i, mid); Max2 = getMax(array, mid, j); return Max1 > Max2 ? Max1 : Max2; } }

int getMin(int array[12], int i, int j) {

int Min1 = 0; int Min2 = 0; if (i == j) { return Min1 = Min2 = array[j]; } else if (i == (j - 1)) { Min1 = array[i]; Min2 = array[j]; return Min1 < Min2 ? Min1 : Min2; } else { int mid = (i + j) / 2; Min1 = getMin(array, i, mid); Min2 = getMin(array, mid, j); return Min1 < Min2 ? Min1 : Min2; } }

void main(){

int a[12]={3,45,67,23,11,100,55,34,46,90,22,33};

printf(\"the max number of array_a is:%d\\n\ printf(\"the min number of array_a is:%d\\n\\n\ }

运行结果：

④ 二分搜索算法核心代码：

template

int BinarySearch(Type a[], const Type& x, int l, int r){ while (r >= l){ int m = (l+r)/2; if (x == a[m]) return m; if (x < a[m]) r = m-1; else l = m+1; }

return -1; } ⑤ 合并排序算法核心代码：

void MergeSort(Type a[], int left, int right){ if (lefttemplate

void Dijkstra(int n,int v,Type dist[],int prev[],Type ** c) {//单元最短路径问题的Dijkstra算法 bool s[maxint];

for(int i=1;i<=n;i++){ dist[i]=c[v][i];s[i]=false; if(dist[i]==maxint) prev[i]=0; else prev[i]=v; }

dist[v]=0; s[v]=true;

for(int i=1;i<=n;i++){ int temp=maxint; int u=v; for(int j=1;j<=n;j++) if(!s[j]&&(dist[j]⑦ 背包问题（贪心算法）的核心代码：

void Knapsack(int n ,float M ,float v[] ,float w[] ,float x[]){ Sort(n,v,w); int i;

for (i=1;i<=n;i++) x[i]=0; float c=M;

for (i=1;i<=n;i++){ if (w[i]>c) break; x[i]=1; c-=w[i]; }

if (i<=n) x[i]=c/w[i]; }