西南交大机算方法作业

1、算法分析与设计西南交通大学算法设计与分析指导教师：尹治本学院：信息科学与技术学院班级：软件一班姓名：*学号：*2013年11月作业一、8-皇后问题1、实验代码：#include stdio.hint count;int queen10, column20, left20, right20;void prt1()int j;printf(No.%d , +count);for (j = 1; j = 8; j+) printf(%3d, queenj);printf(n);void meun(int i)int j;for (j = 1; j = 8; j+)if (columnj & left

2、i - j + 8 & righti + j)queeni = j; columnj = 0;lefti - j + 8 = 0; righti + j = 0;if (i8) meun(i + 1);else prt1();columnj = lefti - j + 8 = righti + j = 1;void main()int i;for (i = 1; i = 16; i+)columni = lefti = righti = 1;count = 0; meun(1); 2、实验结果 作业二：Quicksort 快速排序算法1、 实验代码：#include#includeusing

3、namespace std;int Partition(int arry,int start,int end) int pivot=arrystart; while(startpivot&startend) end-; arrystart=arryend; while(arrystartpivot&startend) start+; arryend=arrystart; arrystart=pivot; return start;void QSort(int arry,int start,int end) if(startend) int pivotkey=Partition(arry,sta

4、rt,end); QSort(arry,start,pivotkey-1); QSort(arry,pivotkey+1,end); void QuickSort(int arry,int len) QSort(arry,0,len);void main() int arry10; cout输入10个数:endl; for(int i=0;iarryi; coutendl; QuickSort(arry,10); cout排序后：endl; for(int i=0;i10;i+) coutarryi ; coutendl; 2、 实验结果作业三、Heapsort 堆排序算法1、 实验代码：#i

5、nclude #include #define N 10 using namespace std; void BuildMaxHeap(int * array); void HeapSort(int * array); void MaxHeapify(int * array,int n); int HeapSize; int main() int arrayN; cout请输入10个数：; for(int i=0 ; iarrayi; coutendl排序后：endl; HeapSort(array); for(int k=0;kN;k+) coutarrayk ; cout=0 ; i-)

6、int temp = array0; array0 = arrayi; arrayi = temp; HeapSize -= 1; MaxHeapify(array,1); void BuildMaxHeap(int * array) HeapSize = N; for(int i = N/2 ; i=1 ; i-) MaxHeapify(array,i); void MaxHeapify(int * array,int temp) int largest; int l = 2*temp ; int r = 2*temp+1; if(l arraytemp-1) largest = l; el

7、se largest = temp; if(r arraylargest-1) largest = r; if(largest != temp) int t = arraytemp-1; arraytemp-1 = arraylargest-1; arraylargest-1 = t; MaxHeapify(array,largest); 2、 实验结果 作业四：Quicksort like（类似于快速排序的选择算法）找中位数1、 实验代码#include #include #include #include using namespace std;int array = 89,98,45,2

8、6,15,35,48,86,92,65,45;const int size = sizeof array / sizeof *array;int partition(int *array, int left, int right)if (array = NULL)return -1;int pos = right;right-;while (left = right)while (left pos & arrayleft = 0 & arrayright arraypos)right-;if (left = right)break;swap(arrayleft, arrayright);swa

9、p(arrayleft, arraypos);return left;int getMidIndex(int *array, int size)if (array = NULL | size 1;int index = -1;while (index != midPos)index = partition(array, left, right);if (index midPos)right = index - 1; elsebreak;assert(index = midPos);return arrayindex;int main() cout数组元素为：endl; for(int i=0;

10、i9;i+) coutarrayi ; int value = getMidIndex(array, size); coutendlendl; cout 中位数是： value endl; return 0; 2、实验结果作业五：Radixsort基数排序算法1、 实验代码：#include #include #define MAXK 10 int get_int(void); int count_sort (int*array,int n,int d); int get_value(int a,int d); void radix_sort(int* a,int n,int d); int

11、main() int n = 12; int p12 = 1234,3123,2539,5958,4365,3352,6654,7214,7684,9351,4685,3325; radix_sort(p,n,3); for (int i=0;in;i+) printf(%d ,pi); printf(n); return 0; void radix_sort(int* a,int n,int d) for (int i=0;i=d;i+) printf(第%i次n,i+1); count_sort(a,n,i); int count_sort (int *array, int n,int d

12、) int kMAXK = 0; int * temp,*b; int i; temp = (int *) malloc (sizeof (int)*n); b = (int *) malloc (sizeof (int)*n); if (NULL = temp) return 0 ; for (i=0;in;i+) bi = get_value(arrayi,d); for (i=0;in;i+) printf(%d ,bi); printf(n); for (i = 0; i n; i+) kbi+; for (i=0;i10;i+) printf(%d ,ki); printf(n); for (i=1;i=0;i-) temp-kbi=arrayi; for (i=0;in;i+) printf(%d ,tempi); printf(n); for (i = 0; i 0&a0;d-) b/=MAXK; return b%MAXK; int get_int(