西南交大机算方法作业
- 格式：doc
- 大小：224.00 KB
- 文档页数：12
算法分析与设计
西南交通大学
《算法设计与分析》
指导教师：尹治本
学院：信息科学与技术学院
班级：软件一班
姓名：***
学号：***
2013年11月
算法分析与设计
作业一、8-皇后问题
1、实验代码：
#include "stdio.h"
int count;
int queen[10], column[20], left[20], right[20];
void prt1()
{
int j;
printf("No.%d ", ++count);
for (j = 1; j <= 8; j++) printf("%3d", queen[j]);
printf("\n");
}
void meun(int i)
{
int j;
for (j = 1; j <= 8; j++)
if (column[j] && left[i - j + 8] && right[i + j])
{
queen[i] = j; column[j] = 0;
left[i - j + 8] = 0; right[i + j] = 0;
if (i<8) meun(i + 1);
else prt1();
column[j] = left[i - j + 8] = right[i + j] = 1;
}
}
void main()
{
int i;
for (i = 1; i <= 16; i++)
column[i] = left[i] = right[i] = 1;
count = 0; meun(1);
}
2、实验结果 算法分析与设计
算法分析与设计
作业二：Quicksort 快速排序算法
1、 实验代码：
#include
#include
using namespace std;
int Partition(int arry[],int start,int end)
{
int pivot=arry[start];
while(start
{
while(arry[end]>pivot&&start
end--;
arry[start]=arry[end];
while(arry[start]
start++;
arry[end]=arry[start];
}
arry[start]=pivot;
return start;
}
void QSort(int arry[],int start,int end)
{
if(start
{
int pivotkey=Partition(arry,start,end);
QSort(arry,start,pivotkey-1);
QSort(arry,pivotkey+1,end);
}
}
void QuickSort(int arry[],int len)
{
QSort(arry,0,len);
}
void main()
{
int arry[10];
cout<<"输入10个数:"<
for(int i=0;i<10;i++)
{
cin>>arry[i];
}
cout<
QuickSort(arry,10);
cout<<"排序后："<
for(int i=0;i<10;i++)
{
cout<
}
cout<
}
2、 实验结果
算法分析与设计
作业三、Heapsort 堆排序算法
1、 实验代码：
#include
#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 array[N];
cout<<"请输入10个数：";
for(int i=0 ; i
{
cin>>array[i];
}
cout<
HeapSort(array);
for(int k=0;k
{
cout<
}
cout<
return 0;
}
void HeapSort(int * array)
{
BuildMaxHeap(array);
for(int i=N-1 ; i>=0 ; i--)
{
int temp = array[0];
array[0] = array[i];
array[i] = temp;
HeapSize -= 1;
MaxHeapify(array,1);
}
}
void BuildMaxHeap(int * array)
{
HeapSize = N; 算法分析与设计
