[数据结构与算法]C++小白学习笔记（6）

1、TOWER OF HANOI（汉诺塔）

//递归分治
#include<iostream>
using namespace std;
void hanoi(int, char, char, char);
int count = 0;//计数

int main(){
	int n;
	cin>>n;
	hanoi(n,'A','B','C');
	cout<<count;//2^n - 1
	
	return 0;。
}
void hanoi(int n, char from, char assist, char to){
	if(n==1){
		cout<<from<<"->"<<to<<endl;
		count++;
		return ;
	}
	hanoi(n - 1, from, to, assist);
	cout<<from<<"->"<<to<<endl;
	
	hanoi(n - 1, assist, from, to);
}

//快速排序
枢轴

#include<iostream>
using namespace std;
void quickSort(int*,int,int);
int partition(int*,int,int);
void exchange(int*,int,int);

int main(){
	int n;
	cout<<"请输入个数："<<endl; 
	cin>>n;//个数 
	int a[n+1];
	cout<<"请输入数据："<<endl; 
	for(int i =1; i <= n; i++) 
		cin>>a[i];
	quickSort(a, 1, n); 
	cout<<"排序结果为："<<endl; 
	for(int i =1; i <= n; i++) 
		cout<<a[i]<<endl;
}

void quickSort(int* a,int low,int high){
	if(low<high){
		int pivotLoc
		=partition(a,low,high);
		quickSort(a,low,pivotLoc-1);
		quickSort(a,pivotLoc+1,high);
	}
}

int partition(int* a,int low,int high){
	while(low<high){
		while(low<high&&a[low]<=a[high]) high--;
		exchange(a,low,high);
		while(low<high&&a[low]<=a[high]) low++;
		exchange(a,low,high);
	}
	return low;
}

void exchange(int* a,int i,int j){
	int temp=a[i];
	a[i]=a[j];
	a[j]=temp;
}

//优化 不移动枢轴 
#include<iostream>
using namespace std;
void quickSort(int*,int,int);
int partition(int*,int,int);
void exchange(int*,int,int);

int main(){
	int n;
	cout<<"请输入个数："<<endl; 
	cin>>n;//个数 
	int a[n+1];
	cout<<"请输入数据："<<endl; 
	for(int i =1; i <= n; i++) 
		cin>>a[i];
	cout<<"原数据排序："<<endl; 
	for(int i =1; i <= n; i++) 
	cout<<a[i]<<"   ";
	quickSort(a, 1, n); 
	cout<<endl<<"排序结果为："<<endl; 
	for(int i =1; i <= n; i++) 
		cout<<a[i]<<"   ";
}

void quickSort(int* a,int low,int high){
	if(low<high){
		int pivotLoc
		=partition(a,low,high);
		quickSort(a,low,pivotLoc-1);
		quickSort(a,pivotLoc+1,high);
	}
}

int partition(int* a,int low,int high){
	a[0] = a[low]; 
	while(low<high){
		while(low<high&&a[0]<=a[high]) high--;
			a[low] = a[high];
		while(low<high&&a[low]<=a[0]) low++;
			a[high] = a[low];
	}
	a[low] = a[0];
	return low;
}

//幂乘
#include<iostream>
using namespace std;
int calc(int a, int m);

int main()

{
	int a, n;
	cout<<"求幂乘数的底数是："<<endl;
	cin>>a;
	cout<<"求幂乘数的幂是："<<endl;
	cin>>n;
	cout<<"该数幂乘的结果为："<<endl;
	cout<<calc(a, n)<<endl;

	return 0;
}

int calc(int a, int n)
{
	int count = 0;
	if(n == 1) 
		return a;
	int m =calc(a, n / 2);
	m *= m;
	count++;//乘法计步器 
	if(n%2)
	{
		 m*=a;
		 count++;
	}
	return m;
}

//二分法求一组数的极大极小值 

#include<iostream>
using namespace std;
void maxMin(int *, int, int, int *, int *);

int main()
{
	int n;
	cout<<"请输入个数："<<endl; 
	cin>>n;
	int a[n-1];
	cout<<"请输入数据："<<endl; 
	for (int i = 0; i < n; i++)
		cin>>a[i];
	
	int max, min;
	maxMin(a, 0, n-1, &max, &min);
	cout<<max<<"  "<<min<<endl;
	
	return 0;
}

void maxMin(int *a, int begin, int end, int *pmax, int *pmin)
{
	if(begin == end)
	{
		*pmax = *pmin = a[begin];
		return ;
	}
	int mid = (begin + end)	/ 2;
	int lmin, lmax, rmin, rmax;
	maxMin(a, begin, mid, &lmax, &lmin);
	maxMin(a, mid + 1, end, &rmax, &rmin);
	//合并解 
	*pmax = lmax > rmax?lmax:rmax; 
	*pmin = lmin < rmin?lmin:rmin; 
}

//二分法求一组数的第二大的值 （第一第二都要求出来） 
//最小问题规模的解 
#include<iostream>
using namespace std;
void maxNext(int *a, int begin, int end, int *pmax1, int *pmax2);

int main()
{
	int n;
	cout<<"请输入个数："<<endl; 
	cin>>n;
	int a[n-1];
	cout<<"请输入数据："<<endl; 
	for (int i = 0; i < n; i++)
		cin>>a[i];
	
	int max1, max2;
	maxNext(a, 0, n-1, &max1, &max2); 

	
	return 0;
}

void maxNext(int *a, int begin, int end, int *pmax1, int *pmax2)
{
	if(begin == end)
	{
		*pmax1 =  a[begin];
		*pmax2 = unsigned(-1)/2+1; //极小值（不会影响最后的结果） 
		return ;
	}
	int mid = (begin + end)	/ 2;
	int lmax1, lmax2, rmax1, rmax2;
	maxNext(a, begin, mid, &lmax1, &lmax2);
	maxNext(a, mid + 1, end, &rmax1, &rmax2);
	
	if(lmax1 > rmax1)
	{
		*pmax1 = lmax1;
		*pmax2 = lmax2 > rmax1?lmax2:rmax1;
	}
	else 
	{
		*pmax1 = rmax1;
		*pmax2 = rmax2 > lmax1?rmax2:lmax2;
	}
	cout<<*pmax1<<"  "<<*pmax2;
}
//注意：该代码有误！！！！！