[数据结构与算法]算法设计与分析作业（1）

1.怎样用7次比较完成5个元素排序？假设5个元素为a,b,c,d,e,给出该算法的伪代码，加以必要的注释。

输入 a,b,c,d,e

	1.3次
	if(a<b&&c<d){
		if(b<d){//以上4个元素通过两两比较后再将各组中的最大值比较共3次比较，即可得
		//到其中三个元素的全序大小关系及其中一个元素与另一个非上述三元组的元素的大小关系
			then a<b<d && c<d
				triple[3]={a,b,d};
		} else{
			then c<d<b && a<b
				triple[3]={c,d,b};
		}
		2.2次
		then binary_insert(e,triple[3]); //二分插入元素e到定序的三元组中，最多2次比较
		3.2次
		if(a<b<d<e)
			triple[3]={a,b.d};
			then binary_insert(c.triple[3]);
			//这里已知c<d，所以只要在上述三元组中进行二分插入，最多2次比较后即可完成5个元素的排序
	} 
	则总计次数为3+2+2=7次
		
			

2.计算排序数组大小n为2的整数次幂时，自底向上合并排序算法的最少和最多元素比较次数。需要给出计算过程。

1.次数最少

  	令2^n = T,则n=log2(T)
  	T/2+(T/4)*2+(T/8)*4+……+T/(2^n)*2^(n-1)
  =nlog2(n)/2

2.次数最多

  	令2^n = T,则n = log2(T)
  	(T-1)+(T/2-1)*2+(T/4-1)*4+……+(T/2^n-1)*2^n
  =(n+1)T-(2^(n+1)-1)
  =Tlog2(T)+T-2T+1
  =Tlog2(T)-T+1

3.二进制数转换

int num;
cin>>num;
stack<int>s;
while(num){s.push(num%2);num/=2;)}
while(!s.empty()){
	cout<<s.top();
	s.pop();
}

伪代码说明
输入num
初始化栈s
while(num){ //num不为0
s.push(num%2);
num/=2;
}
while(!s){
输出栈顶元素，并出栈
}

基本思路是利用栈的特性将十进制数转为二进制后的每一位数存入栈中，并按先入后出的顺序出栈，则输出流最终的结果就是所要的二进制数。