常见算法实验题整理.doc

实现斐波那契数列的递归算法 1 实现二分检索的递归算法 2 用递归算法求出数组的最大最小元素 4 归并排序算法实现 6 递归快速排序算法实现 9 带期限的作业排序算法 11 二元归并树算法 13 0-1背包问题 16 每对节点之间的最短路径 19 N皇后问题 25 实现斐波那契数列的递归算法 #include iostream using namespace std; //函数声明 int Fibonacci(int n); int main() { int n; cout请输入一个n，将输出Fibonacci前n项数据\nn=; cinn; cout Fibonacci数列的前n项为\n; for (int i=1;i=n;i++) { coutFibonacci(i) ; } coutendl; return 0; } int Fibonacci(int n) { //若为0，输入n不合法，返回0 if (n0) { return 0; } //函数结束条件 if (n==0) { return 1; } if (n==1) { return 1; } //f(n)=f(n-1)+f(n-2); return Fibonacci(n-1)+Fibonacci(n-2); } 实现二分检索的递归算法 #include iostream using namespace std; //二分检索的递归算法，返回为-1，表明查询的数不在查询数组中；否则返回查询数在数组中的下标o int binary_search(int *arr,int low,int high,int target); int main() { //查询数组 int arr[]={11,22,33,44,55,66,77,88,99,110,121}; //查询结果的下标 int flag; //需要查询的数 int n; int len=sizeof(arr)/sizeof(int); cout查询数组中所有的元素为:\n; for (int i=0;ilen;i++) { coutarr[i] ; } cout\n****************************************************************\n; cout请输入一个数n，程序将会判断n是否在查询数组中；输入-1终止程序\n; cinn; while(n!=-1) { flag=binary_search(arr,0,len-1,n); // flag不为-1，表明n在查询数组中 if (flag!=-1) { coutn是查询数组中第flag个元素\n; } else { coutn\n; } cout****************************************************************\n; cout请继续输入需要查询的数据；输入-1终止程序\n; cinn; } return 0; } int binary_search(int *arr,int low,int high,int target) { //没有找到返回-1 if (highlow) { return -1; } //取中间数 int mid=(low+high)/2; //判断是否找到目标数 if (arr[mid]==target) { return mid; } //目标数在左半边 else if (arr[mid]target) { binary_search(arr,low,mid-1,target); } //目标数在右半边 else { binary_search(arr,mid+1,high,target); } } 用递归算法求出数组的最大最小元素 #include iostream #include string using namespace std; //输出数组中元素 void showArray(int *arr,int len,string msg=数组中的元素为:\n); //找到数组中最大元素 int findMaxOfArr(int * arr,int n); //找到数组中最小元素 int findMinOfArr(int *arr,int n); int main() { int arr[]={12,555,133,143,12,13,7,21,3}; int len=sizeof(arr)/s