24考研王道408数据结构-第三章“栈、队列、数组”-p96课后算法题

第一题：

#include
#include
using namespace std;
bool solution(string s){
	stack<char> st;
	int len=s.length();
	char temp;
	for(int i=0;i<len;i++){
		if(s[i]==')'||s[i]=='}'||s[i]==']'){
			if(st.empty()){//遇到右括号先判断栈是否为空 
				return false;
			}	
			else{
				temp=st.top();
				st.pop();
				if(s[i]==')'&&temp=='('){
					continue;
				}else if(s[i]=='}'&&temp=='{'){
					continue;
				}else if(s[i]==']'&&temp=='['){
					continue;
				}else{
					return false;
				}
			}
		}else{
			st.push(s[i]);
		}
	}
	if(st.empty()){
		return true;
	}else{
		return false;
	}
} 

int main(){
	string s="([{}])";
	bool flag=solution(s);
	if(flag){
		cout<<"true";
	}else{
		cout<<"false";
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

第二题

算法思想：

#include
#include
#include
#define maxSize 5
using namespace std;
char* solution(char str[]){
	stack<char>st;
	char train[maxSize];
	int j=0;
	for(int i=0;i<maxSize;i++){
		if(str[i]=='H'){
			st.push(str[i]);
		}else{
			train[j++]=str[i];
		}
	}
	char temp;
	while(!st.empty()){
		temp=st.top();
		st.pop();
		train[j++]=temp;
	}
	return train;
}
int main(){
	char tr[]="SHSSH";
	char *sortArr=solution(tr);
	for(int i;i<maxSize;i++){
		cout<<sortArr[i];
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

第三题：

#include
using namespace std;
#define maxSize 10
struct stack{
	int n;
	double pnx;
}st[maxSize];//注意需要自定义栈的结构体 

double ans(int n,double x){
	double fv1=1,fv2=2*x;
	int top=-1;
	for(int i=n;i>=2;i--){//越往上n的值越小 
		top++;
		st[top].n=i;
	}
	
	while(top>=0){
		st[top].pnx=2*x*fv2-2*(st[top].n-1)*fv1;
		fv1=fv2;
		fv2=st[top].pnx;
		top--;
	}
	if(n==0){
		return fv1;
	}
	return fv2;
}

int main(){
	double ans1=ans(2,1.0);
	cout<<ans1<<endl;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

第四题：

#include
#include
using namespace std;
void disp(queue<char>&s){
	char c;
	while(!s.empty()){
		c=s.front();
		s.pop();
		cout<<c<<" ";
	}
	cout<<endl;
} 

void ans(){
	queue<char> q;
	queue<char> q1;//客车队列 
	queue<char> q2;//货车队列 
	
	for(int i=0;i<9;i++){
		q1.push('k');
	}
	for(int j=0;j<6;j++){
		q2.push('h');
	}
	int i=0,j=0;//j表示渡船上的总车辆数 
	char temp;
	while(j<10){
		if(!q1.empty()&&i<4){//客车队列不空且未上足四辆 
			temp=q1.front();
			q1.pop();
			q.push(temp);
			i++;//渡船上的客车数+1 
			j++;
		}
		else if(i==4&&!q2.empty()){//客车已经上足四辆 
			temp=q2.front();
			q2.pop();
			q.push(temp);
			j++;
			i=0; 
		}else{//其他情况（客车队列空或货车队列空） 
			while(j<10&&i<4&&!q2.empty()){
				temp=q2.front();
				q2.pop();
				q.push(temp);
				i++; 
			}
			i=0; 
		} 
		if(q1.empty()&&q2.empty()){//货车和客车加起来不足10辆 
			j=11;
		}
	}
	cout<<"渡船队列为"<<endl;
	disp(q);
}

int main(){
	ans();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60