回溯法+递归
【问题描述】
几十年前全世界就流行一种数字游戏，至今仍有人乐此不疲．在中国我们把这种游戏称为“算24点”。您作为游戏者将得到4个1~9之间的自然数作为操作数，而您的任务是对这4个操作数进行适当的算术运算，要求运算结果等于24。
您可以使用的运算只有：+，-，*，/，您还可以使用（）来改变运算顺序。注意：所有的中间结果须是整数，所以一些除法运算是不允许的（例如，(2*2)/4是合法的，2*(2/4)是不合法的）。下面我们给出一个游戏的具体例子：
若给出的4个操作数是：1、2、3、7，则一种可能的解答是1+2+3*7=24。
鉴于各种排序算法经常使用，把上学期c实践课实现冒泡排序，插入排序，快速排序，希尔排序的算法贴出来供参考
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 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 | #include<stdio.h> #include<stdlib.h> #define MAX 200 int a[MAX]; void randsee(); void print(); void bubblesort(); void insertsort(); void quickSort(int a[],int left,int right); int SortGroup(int pnData[], int nLen, int nBegin,int nStep); int ShellSort(int pnData[], int nLen); /*主函数*/ int main() { int num=0; while(1) { system("cls"); printf("1：生成随机数\n2：冒泡排序\n3；插入排序\n4；快速排序\n5；希尔排序\n6：打印随机数\n7：退出\nInput 1-7:\n"); scanf("%d",&num); switch(num) { case 1: system("cls"); randsee(); system("pause"); break; case 2: system("cls"); bubblesort(); system("pause"); system("cls"); break; case 3: system("cls"); insertsort(); system("pause"); system("cls"); break; case 4: system("cls"); quickSort(a,0,MAX-1); system("pause"); system("cls"); break; case 5: system("cls"); ShellSort(a,MAX); system("pause"); system("cls"); break; case 6: system("cls"); print(); system("pause"); system("cls"); break; case 7: exit(0); default: system("cls"); printf("1：生成随机数\n2：冒泡排序\n3；插入排序\n4；快速排序\n5；希尔排序\n6：打印随机数\n7：退出\nInput 1-7:\n"); break; } } system("pause"); return 0; } /*产生随机数组*/ void randsee() { int i; srand(time(0)); for(i=0;i<MAX;i++) { a[i]=1+(rand()%MAX); } } /*打印随机数*/ void print() { int i; for(i=1;i<=MAX;++i) { printf("%5d ",a[i-1]); if(i%10==0) { printf("\n"); } } } /*冒泡排序*/ void bubblesort() { int i,sign,j,temp; for(i=0;i<MAX-2;i++) { sign=1; for(j=MAX-1;j>=i;j--) { if(a[j+1]<a[j]) { temp=a[j+1]; a[j+1]=a[j]; a[j]=temp; sign=0; } } if(sign) { break; } } } /*插入排序*/ void insertsort() { int i,j,c; for(i=1;i<MAX;++i) { c=a[i]; j=i-1; while(j>=0&&a[j]>c) { a[j+1]=a[j]; j--; } a[j+1]=c; } } /*快速排序*/ void quickSort(int a[],int left,int right) { int i,j,temp; i=left; j=right; temp=a[left]; if(left>right) return; while(i!=j) { while(a[j]>=temp && j>i) j--; if(j>i) a[i++]=a[j]; while(a[i]<=temp && j>i) i++; if(j>i) a[j--]=a[i]; } a[i]=temp; quickSort(a,left,i-1); quickSort(a,i+1,right); } int SortGroup(int pnData[], int nLen, int nBegin,int nStep) { int i,j,k,nTemp; for (i = nBegin + nStep; i < nLen; i += nStep) { for (j = nBegin; j < i; j+= nStep) { if (pnData[i] < pnData[j]) { nTemp = pnData[i]; for (k = i; k > j; k -= nStep) { pnData[k] = pnData[k - nStep]; } pnData[j] = nTemp; } } } return 1; } /*希尔排序*/ int ShellSort(int pnData[], int nLen) { int nStep,i; for (nStep = nLen / 2; nStep > 0; nStep /= 2) { for (i = 0 ;i < nStep; ++i) { SortGroup(pnData, nLen, i, nStep); } } return 1; } |
分治法求数组中第k大的元素
思想：用快速排序定位数组中其中一个元素a按从小到大确定它在数组中的位置temp
当temp等于k时，那么这个元素就是我们要找的第k个大的元素
当temp大于k时，说明第k大的元素一定在a元素的左边，向左缩小查找范围
当temp小于k时，说明第k大的元素一定在a元素的右边，向右缩小查找范围
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 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 | #include "stdafx.h" #include <iostream> using namespace std; int quickSort(int *a,int left,int right); int search(int *a,int i,int j,int k); //主函数 int _tmain(int argc, _TCHAR* argv[]) { int n,k_max; int a[100]; cin >> n ; for (int i = 1; i <= n; ++i) { cin >> a[i]; } cin >> k_max; cout << search(a,1,n,k_max)<<endl; return 0; } //一次快速排序，返回被定位元素的位置 int quickSort(int *a,int left,int right) { int i,j,temp; i=left; j=right; temp=a[left]; if(left>right) return -1; while(i!=j) { while(a[j]>=temp && j>i) j--; if(j>i) a[i++]=a[j]; while(a[i]<=temp && j>i) i++; if(j>i) a[j--]=a[i]; } a[i]=temp; return i; } //分治查找第k大的元素 int search(int *a,int i,int j,int k) { int temp; if (j < i) { return -1; } if (i == j) { return a[i]; } //得到第i个元素被定位的下标 temp = quickSort(a,i,j); //相等说明找到第k个大的元素 if (temp == k) { return a[k]; } //比k大，往左缩小查找范围 else if (temp > k ) { return search(a,i,temp-1,k); } //比k大，往右缩小超找范围 else { return search(a,temp+1,j,k-temp); } } |
解决的问题依旧是找出A城市到B城市的最短路径
Bellman-Ford算法，找出各个顶点间的最短路径，路径权值可以是负数，但是不能存在负权回路（在这一回路中存在负权路径）。
而Dijkstra算法，是找出某个顶点到其它顶点的最短路径。当然Dijkstra也可以找出各个顶点间的最短路径，只要做n次Dijkstra就行了。
思路：
对每对顶点i、j，不断缩小i到j的最短路径的权。在i、j中加入顶点k，判断从i到k和k到j路径的和是否小于i到j的路径长度，如果是将k加入，并调整i到j的路径长度。
缩小的条件: a[i][j]>a[i][k]+a[k][j]; （a：每对顶点的路径长度）
下面两组测试数组，前一组没构成负权回路，后一组是负权回路，无法得出正确结果
第一组：
5
1 2 6
2 3 5
3 2 -2
5 3 -3
4 3 7
2 4 -4
5 4 9
1 5 7
4 1 2
2 5 8
0 0 0
第二组：
3
1 2 2
2 3 3
3 1 -8
0 0 0
问题：
从A城市到B城市，中间有n条路径供你选择，每条路径的距离（权值）是不一样的，让你选择一条从A城市（A顶点）到B城市（B顶点）的最短路线，即找出两点间的最短路径。
Dijkstra算法能够为我们解决这一类问题，找出源点s源点到其它顶点的最短路径，但要求每条路径权值必须是非负的。
思路：
设置两个集合分别为集合s，集合t。s存放已找出的最短路径顶点；t，存放待加入顶点。源点为v，从源点到t集合中顶点权值d[t]已经确定，在这些确定的权值里选择最小的一个k，并把k从t移到s中，对u的所有出边进行调整，满足调整的条件：
d[t]>d[k]+c[k][t] (c:顶点k到t之间的权值)
具体实现看下面的代码，注释也写得很清楚了，下面是测试数据：
1 5 7
1 2 10
1 5 100
1 4 30
2 3 50
4 3 20
4 5 60
3 5 10
最新评论