C++刷题

C++刷题记录

题目集一

C++面向对象程序设计50道编程题

Problem 1

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
#include<iostream>
using namespace std;

class Fract
{
int num, den;
public:
Fract(int a = 0, int b = 1) { num = a; den = b; }
int ged(int m, int n);
Fract add(Fract f);
void show();
};

int Fract::ged(int m, int n)
{
int k = 0;
if(m >= n)
k = n;
else
k = m;
for(; k >= 1; k--)
{
if(m % k == 0 && n % k == 0)
break;
}
return k;
}

Fract Fract::add(Fract f)
{
Fract ff;
int v;
v = ged(f.den, den);
int vv = den / v * f.den;
int uu = vv / den * num + vv / f.den * f.num;
int cc = ged(vv, uu);
if (cc != 1) {vv = vv / cc; uu = uu / cc;}
ff.den = vv;
ff.num = uu;
return ff;
}

void Fract::show()
{
cout << num << '/' << den << endl;
}

int main()
{
Fract f1(1,5), f2(7,20), f3;
f3 = f1.add(f2);
f3.show();
return 0;
}

Problem 2

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
#include<iostream>
using namespace std;

class ARRAY
{
float a[10], b[10];
public:
ARRAY(float t[10])
{
for(int i = 0; i < 10; i++)
a[i] = t[i];
}
void process()
{
for(int i = 0; i < 10; i++)
{
int pre = (i - 1) % 10;
if(pre < 0)
pre = 10 + pre;
int aft = (i + 1) % 10;
b[i] = (a[pre] + a[i] + a[aft]) / 3;
}
}
void print()
{
for(int i = 0; i < 10; i++)
cout << a[i] << ' ';
cout << endl;
for(int i = 0; i < 10; i++)
cout << b[i] << ' ';
}
};

int main()
{
float aa[10] = {0,3,6,9,12,15,18,21,24,27};
ARRAY v(aa);
v.process();
v.print();
return 0;
}

Problem 3

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
#include<iostream>
#include<cstring>
using namespace std;

class ID
{
char s[18], x[11];
int w[17];
public:
ID(char *str){
int i;
for(i = 0; i < 18; i++)
s[i] = '0';
for(i = 0; i < strlen(str); i++){
s[i] = str[i];
}
char x1[] = {'1','0','X','9','8','7','6','5','4','3','2'};
strcpy(x,x1);
int w1[] = {7,9,10,5,8,4,2,1,6,3,7,9,10,5,8,4,2};
for(i = 0; i < 17; i++)
w[i] = w1[i];
}
void fun(){
int i;
for(i = 16; i > 7; i--)
s[i] = s[i - 2];
s[6] = '1'; s[7] = '9';
int sum = 0;
for(i = 0; i < 17; i++){
int temp = s[i] - '0';
sum += temp * w[i];
}
int index = sum % 11;
s[17] = x[index];
}
void print(){
cout << s << endl;
}
};

int main()
{
char *str = "340524800101001";
ID id(str);
id.fun();
id.print();
}

Problem 4

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
61
62
63
64
65
66
67
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>

using namespace std;

class String{
char *str1, *str2;
char *str;
public:
String(char *s1, char* s2){
str1=new char[strlen(s1)+1];
strcpy(str1,s1);
str2=new char[strlen(s2)+1];
strcpy(str2,s2);
str=new char[strlen(s1)+strlen(s2)+1];
strcpy(str,s1);strcat(str,s2);
}
void del(){
char *ptr1 = str;
char *ptr2 = str;
while(*ptr1){
if(*ptr1 != ' '){
*ptr2 = *ptr1;
ptr2++;
}
ptr1++;
}
*ptr2 = '\0';
}
void _sort(){
char *ptr1 = str;
char *ptr2, temp;
while(*ptr1){
for(ptr2 = ptr1; *ptr2; ptr2++){
if(*ptr1 > *ptr2){
temp = *ptr1;
*ptr1 = *ptr2;
*ptr2 = temp;
}
}
ptr1++;
}
}
void show(){
cout << "str1: " << str1 << endl;
cout << "str2: " << str2 << endl;
cout << "str: " << str << endl;
}
~String(){
free(str1);
free(str2);
free(str);
}
};

int main(){
char *s1 = "db a";
char *s2 = "4 1";
String str(s1, s2);
str.del();
str.show();
str._sort();
str.show();
return 0;
}

Problem 5

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
61
62
63
64
65
66
67
68
69
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<math.h>

using namespace std;

class Array{
int *p,k;
float s;
public:
Array(int *ptr, int n){
k = n;
p = new int[k];
for(int i = 0; i < k; i++)
p[i] = ptr[i];
s = 0;
}
int fun(int n);
void sum();
void show();
~Array(){
delete []p;
}
};

int Array::fun(int n){
if(n == 0 || n == 1) return 0;
int i;
for(i = 2; i < n; i++)
{
if(n % i == 0)
return 0;
}
return 1;
}

void Array::sum(){
float sum = 0;
int length = 0;
for(int i = 0; i < k; i++){
if(fun(p[i])){
sum += p[i];
length++;
}
}
s = sum / length;
}

void Array::show(){
cout << k << endl;
int i;
for(i = 0; i < k; i++){
cout << p[i] << '\t';
if(i % 4 ==0 && i != 0)
cout << endl;
}
cout << s;
}

int main(){
int ptr[] = {5,2,7,4,8,23,65,1,40};
int n = 9;
Array arr(ptr, n);
arr.sum();
arr.show();
return 0;
}

Problem 6

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
#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
using namespace std;

class STR{
char s1[80], s2[80];
char s3[160];
public:
STR(char a[], char b[]){
char *ptr1 = s1;
char *ptr2 = s2;
while(*a){
*ptr1 = *a;
ptr1++;
a++;
}
*ptr1 = '\0';
while(*b){
*ptr2 = *b;
ptr2++;
b++;
}
*ptr2 = '\0';
}
void consort();
void show();
};

void STR::consort(){
strcpy(s3, s1);
strcat(s3, s2);
char *ptr1 = s3, *ptr2, temp;
while(*ptr1){
for(ptr2 = ptr1; *ptr2; ptr2++){
if(*ptr2 < *ptr1){
temp = *ptr2;
*ptr2 = *ptr1;
*ptr1 = temp;
}
}
ptr1++;
}
}

void STR::show(){
cout << s1 << endl;
cout << s2 << endl;
cout << s3 << endl;
}

int main(){
char a[] = "pear";
char b[] = "apple";
STR str(a, b);
str.consort();
str.show();
return 0;
}

Problem 7

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
61
62
63
64
65
66
67
68
69
70
71
#include<iostream>
using namespace std;

class RECT{
protected:
double x,y;
public:
RECT(double x1, double y1){
x = x1;
y = y1;
}
virtual double area(){
double are = x * y;
return are;
}
double peri(){
double per = 2 * (x + y);
return per;
}
virtual int isSquare(){
if(x == y)
return 1;
else
return 0;
}
};

class CUB:public RECT{
double height;
public:
CUB(double x1, double y1, double h):RECT(x1,y1){
height = h;
}
double volume();
double area();
int isSquare();
};

double CUB::volume(){
double square = RECT::area();
double v = square * height;
return v;
}

double CUB::area(){
double square = RECT::area();
double result = 2 * square + peri() * height;
return result;
}

int CUB::isSquare(){
if(RECT::isSquare())
return x == height;
else
return 0;
}

int main(){
double a,b,c;
cin>>a>>b>>c;
CUB cu(a,b,c);
RECT *re;
re=&cu;
cout<<"长方体的体积为:"<<cu.volume()<<endl;
cout<<"长方体的表面积为:"<<re->area()<<endl;
if(re->isSquare())
cout<<"该长方体是正方体\n";
else
cout<<"该长方体不是正方体\n";
return 0;
}

Problem 8

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
#include<iostream>

using namespace std;

class ARR{
int n;
int a[100];
public:
ARR(int x[], int size){
n = size;
int i;
for(i = 0; i < n; i++)
a[i] = x[i];
}
void change();
void show();
};

void ARR::change(){
int i = 0, j = n - 1;
for(; i < j; i++){
while(a[i] < 0)
{
if(i == j)
break;
i++;
}
while(a[j] > 0)
{
if(i == j)
break;
j--;
}
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}

void ARR::show(){
for(int i = 0; i < n; i++){
cout << a[i] << ' ';
}
cout << endl;
}

int main(){
int b[10] = {1,-3,-1,3,2,4,-4,5,-5,-2};
ARR arr(b, 10);
arr.show();
arr.change();
arr.show();
}

Problem 9

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
61
62
63
64
65
66
#include<iostream>
using namespace std;

class Base{
protected:
char name[8];
int num;
public:
Base(){
cout << "请输入姓名:";
cin >> name;
}
void print(){
cout << name << endl;
}
virtual int isGood() = 0;
};

class Student:public Base{
public:
Student(){
cout << "请输入成绩:";
cin >> num;
}
int isGood(){
if(num > 90)
return 1;
else
return 0;
}
};

class Teacher:public Base{
public:
Teacher(){
cout << "请输入论文数:";
cin >> num;
}
int isGood(){
if(num > 3)
return 1;
else
return 0;
}
};

int main(){
cout << "学生情况:" << endl;
Student s[2];
cout << "老师情况:" << endl;
Teacher t[2];
Base *p;
int i;
cout << "优秀学生:" << endl;
for(i = 0, p = s; i < 2; i++){
if(p->isGood())
p->print();
p++;
}
cout << "优秀老师:" << endl;
for(i = 0, p = t; i < 2; i ++){
if(p->isGood())
p->print();
p++;
}
}

Problem 10

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
#include<iostream>
using namespace std;
#define M 4

class Array{
int b[M][M];
public:
Array(int (*p)[M]);
void operator+();
friend void operator-(Array &b);
void print();
};

Array::Array(int (*p)[M]){
for(int i = 0; i < M; i++)
for(int j = 0; j < M; j++)
b[i][j] = p[i][j];
}

void Array::operator+(){
int t[M][M];
for(int i = 0; i < M; i++)
for(int j = 0; j < M; j++)
t[i][j] = b[j][M-1-i];
for(int i = 0; i < M; i++)
for(int j = 0; j < M; j++)
b[i][j] = t[i][j];
}

void operator-(Array &b){
int t[M][M];
for(int i = 0; i < M; i++)
for(int j = 0; j < M; j++)
t[i][j] = b.b[M-1-j][i];
for(int i = 0; i < M; i++)
for(int j = 0; j < M; j++)
b.b[i][j] = t[i][j];
}

void Array::print(){
for(int i = 0; i < M; i++)
{
for(int j = 0; j < M; j++)
{
cout << b[i][j] << '\t';
}
cout << endl;
}
cout << '\n';
}

int main(){
int a[][M]={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16};
Array arr(a);
arr.print();
+arr;
arr.print();
-arr;
arr.print();
}

Problem 11

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
#include<iostream>
#include<cstring>
#include<string>
using namespace std;

class String_Integer{
char *s;
public:
String_Integer(char *str);
operator int(){
char *ptr = s;
int num = 0;
while(*ptr){
if(*ptr >= '0' && *ptr <= '9')
{
num = num*10 + *ptr - '0';
}
ptr++;
}
return num;
}
void show();
~String_Integer();
};

String_Integer::String_Integer(char *str){
s = new char(strlen(str) + 1);
strcpy(s, str);
}

void String_Integer::show(){
char *ptr = s;
while(*ptr){
cout << *ptr;
ptr++;
}
cout << endl;
}

String_Integer::~String_Integer(){
delete []s;
}

int main(){
char *s = "ab12 3c00d45ef";
String_Integer str(s);
str.show();
int n = str;
cout << "输出的整数为:" << n;
}

Problem 12

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
61
62
63
64
65
66
67
68
69
70
71
#include<iostream>
using namespace std;
class SET{
int *a;
int len;
public:
SET(int *p, int n);
int operator ==(int m);
friend int operator ==(SET &s1, SET &s2);
void print();
~SET();
};

SET::SET(int *p, int n)
{
len = n;
a = new int(len);
for(int i = 0; i < len; i++)
a[i] = p[i];
}

int SET::operator ==(int m)
{
for(int i = 0; i < len; i++)
if(m == a[i])
return 1;
return 0;
}

int operator ==(SET &s1, SET &s2)
{
if(s1.len != s2.len)
return 0;
else
{
for(int i = 0; i < s1.len; i++)
if(!(s2 == s1.a[i]))
return 0;
}
return 1;
}

void SET::print()
{
for(int i = 0; i < len; i++)
{
cout << a[i] << '\t';
}
cout <<endl;
}

SET::~SET()
{
delete []a;
}

int main()
{
int a[]={1,2,3,4,5},b[]={1,2,3,4,5},c[]={1,2,3,4,5,6},d[]={1,3,5,7,9};
SET s1(a,5),s2(b,5),s3(c,6),s4(d,5);
cout<<"a:\t";s1.print();
cout<<"b:\t";s2.print();
cout<<"c:\t";s3.print();
cout<<"d:\t";s4.print();
if(s1==s2)cout<<"a==b\n";
else cout<<"a!=b\n";
if(s1==s3)cout<<"a==c\n";
else cout<<"a!=c\n";
if(s1==s4)cout<<"a==d\n";
else cout<<"a!=d\n";
}

Problem 13

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
61
62
63
64
65
66
67
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
using namespace std;

class STR
{
char *s;
public:
STR(char *p = 0);
STR& operator =(STR &str);
friend STR& operator +=(STR &str1, STR &str2);
void print();
~STR();
};

STR::STR(char *p)
{
if(p == 0)
s = 0;
else
{
s = new char(strlen(p) + 1);
strcpy(s, p);
}
}

STR& STR::operator =(STR &str)
{
if(s)
delete []s;
s = new char[strlen(str.s) + 1];
strcpy(s, str.s);
return *this;
}

STR& operator +=(STR &str1, STR &str2)
{
char *p = new char[strlen(str1.s) + strlen(str2.s) + 1];
strcpy(p, str1.s);
strcat(p, str2.s);
if(str1.s)
delete []str1.s;
str1.s = new char[strlen(p) + 1];
strcpy(str1.s, p);
return str1;
}

void STR::print()
{
cout << s << endl;
}

STR::~STR()
{
delete []s;
}

int main()
{
STR str1("Shenzhen"),str2(" University"),str3;
str1.print();
str2.print();
str3=str1+=str2;
str3.print();
}

Problem 14

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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include<iostream>
using namespace std;
#define pi 3.14
class container
{
protected:
int radius;
public:
container(int n) {radius = n;}
virtual double square() = 0;
virtual double volume() = 0;
};

class cube:public container
{
public:
cube(int n):container(n){ }
double square()
{
int s = 6 * radius * radius;
return s;
}
double volume()
{
double v = radius * radius * radius;
return v;
}
};

class sphere:public container
{
public:
sphere(int n):container(n){ }
double square()
{
double s = 4 * radius * radius * pi;
return s;
}
double volume()
{
double v = (4 / 3.0) * radius * radius * radius;
return v;
}
};

class cylinder:public container
{
int height;
public:
cylinder(int n, int h):container(n){ height = h;}
double square()
{
double s = 2 * radius * radius * pi + 2 * pi * radius * height;
return s;
}
double volume()
{
double v = radius * radius * pi * height;
return v;
}
};

int main()
{
int radius = 2;
int height = 4;
container *base;
cube c(radius);
sphere s(radius);
cylinder cy(radius, height);
base = &c;
cout << "正方体表面积为:" << base->square() << endl;;
cout << "正方形体积为:" << base->volume() <<endl;
base = &s;
cout << "球体表面积为:" << base->square() << endl;
cout << "球体体积为:" << base->volume() <<endl;
base = &cy;
cout << "圆柱体表面积为:" << base->square() <<endl;
cout << "圆柱体体积为:" << base->volume() << endl;
}

题目集二

王道论坛计算机机试指南

贪心算法

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
#include<iostream>
#include<iomanip>
using namespace std;

int main()
{
int M, N;
cin >> M >> N;
while(M != - 1 && N != -1)
{
int storage = M;
float result = 0.0;
int J[N], F[N];
float rate[N];
for(int i = 0; i < N; i++)
{
cin >> J[i] >> F[i];
rate[i] = float(J[i]) / F[i];
}
while(storage != 0)
{
int index = 0;
float max = 0.0;
for(int i = 0; i < N; i++)
{
if(rate[i] > max)
{
index = i;
max = rate[i];
}
}
if(storage > F[index] && F[index] != 0)
{
result += J[index];
storage -= F[index];
rate[index] = 0;
}
else
{
result += storage * rate[index];
storage = 0;
}
}
cout << fixed << setprecision(3) << result << endl;
cin >> M >> N;
}
}

括号匹配

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
#include<iostream>
#include<stack>
#include<cstring>
using namespace std;

int main()
{
// char str[100];
// cin >> str;
char str[] = ")(rttyy())sss)(";
stack<char> S;
stack<int> index;
int len = strlen(str);
int i;
char result[len];
for(i = 0; i < len; i++)
result[i] = ' ';
for(i = 0; i < len; i++)
{
if(str[i] == '('){
S.push(str[i]);
index.push(i);
}
else if(str[i] == ')')
{
if(S.empty()){
result[i] = '?';
}
else{
S.pop();
index.pop();
}
}
}
result[i] = '\0';
while(!S.empty()){
int top = index.top();
index.pop();
S.pop();
result[top] = '$';
}
cout << result << endl;
}

简易计数器[中缀表达式->后缀表达式]

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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include<iostream>
#include<stack>
#include<cstring>
#include<stdio.h>
using namespace std;

int priority(const char symbol)
{
int grade = 0;
switch(symbol){
case '+': grade = 4;break;
case '-': grade = 4;break;
case '*': grade = 5;break;
case '/': grade = 5;break;
}
return grade;
}

float calculate(const float a, const char symbol, const float b)
{
float result = 0.0;
switch(symbol){
case '+': result = a + b;break;
case '-': result = a - b;break;
case '*': result = a * b;break;
case '/': result = float(a) / b;break;
}
cout << a << ' ' << symbol << ' ' << b << endl;
return result;
}

int main(){
char str[] = "4+2*5-6/3";
stack<char> result;
stack<char> S;
int i;
for(i = 0; i < strlen(str); i++){
if(str[i] >= '0' && str[i] <= '9')
result.push(str[i]);
else if(str[i] == '+' || str[i] == '-' || str[i] == '*' || str[i] == '/'){
while(true){
if(S.empty() || S.top() == '('){
S.push(str[i]);
break;
}
else if(priority(str[i]) > priority(S.top())){
S.push(str[i]);
break;
}
else{
char top = S.top();
result.push(top);
S.pop();
}
}
}
else{
if(str[i] == '(')
S.push(str[i]);
else{
while(S.top() != '('){
char top = S.top();
result.push(top);
S.pop();
}
S.pop();
}
}
}

while(!result.empty()){
char top = result.top();
S.push(top);
result.pop();
}
stack<float> C;
while(!S.empty()){
char top = S.top();
S.pop();
if(top >= '0' && top <= '9'){
C.push(top - '0');
}
else{
float b = C.top();
C.pop();
float a = C.top();
C.pop();
float result = calculate(a, top, b);
C.push(result);
}
}
float num = C.top();
cout << "计算结果:" << num << endl;
}

哈夫曼树

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
#include<iostream>
#include<queue>
#include<stdio.h>
using namespace std;

int main()
{
priority_queue<int, vector<int>, greater<int> > Q;
int n;
while(scanf("%d", &n) != EOF){
while(!Q.empty())
Q.pop();
for(int i = 0; i < n; i++){
int x;
cin >> x;
Q.push(x);
}
int ans = 0;
while(Q.size() > 1){
int a = Q.top();
Q.pop();
int b = Q.top();
Q.pop();
ans += a + b;
Q.push(a + b);
}
cout << ans << endl;
}
}

二叉树遍历[前序+中序->后序]

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
#include<iostream>
#include<cstring>
#include<stdio.h>
using namespace std;

typedef struct TNode {
char data;
TNode *lchild, *rchild;
}*Tree;
char preOrder[] = "FDXEAG", inOrder[] = "XDEFAG";

Tree createTree(){
Tree T = new TNode;
T->lchild = T->rchild = NULL;
return T;
}

void postOrder(Tree T){
if(T->lchild != NULL)
postOrder(T->lchild);
if(T->rchild != NULL)
postOrder(T->rchild);
cout << T->data;
}

Tree BuildTree(int s1, int e1, int s2, int e2){
Tree T = createTree();
T->data = preOrder[s1];
int rootIdx;
for(int i = 0; i < strlen(inOrder); i++)
if(inOrder[i] == preOrder[s1]){
rootIdx = i;
break;
}
if(rootIdx != s2){ //左子树非空
T->lchild = BuildTree(s1 + 1, s1 + (rootIdx - s2), s2, rootIdx - 1);
}
if(rootIdx != e2){ //右子树非空
T->rchild = BuildTree(s1 + (rootIdx - s2) + 1, e1, rootIdx + 1, e2);
}
return T;
}

int main()
{
while(scanf("%s", preOrder) != EOF){
scanf("%s", inOrder);
int len_pre = strlen(preOrder), len_in = strlen(inOrder);
Tree T = BuildTree(0, len_pre - 1, 0, len_in - 1);
postOrder(T);
cout << endl;
}
}

二叉排序树

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
61
62
63
64
#include<iostream>
#include<stdio.h>
using namespace std;

typedef struct TNode{
int data;
TNode *lchild, *rchild;
}*Tree;

void preOrder(Tree T){
if(T != NULL){
cout << T->data << " ";
preOrder(T->lchild);
preOrder(T->rchild);
}
}

void inOrder(Tree T){
if(T != NULL){
inOrder(T->lchild);
cout << T->data << " ";
inOrder(T->rchild);
}
}

void postOrder(Tree T){
if(T != NULL){
postOrder(T->lchild);
postOrder(T->rchild);
cout << T->data << " ";
}
}

Tree Insert(Tree T, int X){
if(!T){
T = new TNode;
T->lchild = T->rchild = NULL;
T->data = X;
}
if(X > T->data)
T->rchild = Insert(T->rchild, X);
else if(X < T->data)
T->lchild = Insert(T->lchild, X);
return T;
}

int main()
{
int n;
while(scanf("%d", &n) != EOF){
Tree T = NULL;
for(int i = 0; i < n; i++){
int num;
scanf("%d", &num);
T = Insert(T, num);
}
preOrder(T);
cout << endl;
inOrder(T);
cout << endl;
postOrder(T);
cout << endl;
}
}

同一二叉搜索树序列

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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;

typedef struct TNode{
int data;
TNode *lchild, *rchild;
}*Tree;

char *str;
char str1[40], str2[40];
int *size;
int size1, size2;

Tree Insert(Tree T, int X){
if(T == NULL){
T = new TNode;
T->data = X;
T->lchild = T->rchild = NULL;
}
if(X < T->data)
T->lchild = Insert(T->lchild, X);
else if(X > T->data)
T->rchild = Insert(T->rchild, X);
return T;
}

void preOrder(Tree T){
if(T != NULL){
str[(*size)++] = T->data + '0';
preOrder(T->lchild);
preOrder(T->rchild);
}
}

void inOrder(Tree T){
if(T != NULL){
inOrder(T->lchild);
str[(*size)++] = T->data + '0';
inOrder(T->rchild);
}
}

void postOrder(Tree T){
if(T != NULL){
postOrder(T->lchild);
postOrder(T->rchild);
str[(*size)++] = T->data + '0';
}
}

int main()
{
int n;
cin >> n;
while(n != 0){
char originTree[20];
cin >> originTree;
for(int i = 0; i < n; i++){
char compareTree[20];
cin >> compareTree;
size1 = 0;
size = &size1;
str = str1;
Tree T1 = NULL;
for(int j = 0; j < strlen(originTree); j++)
T1 = Insert(T1, originTree[j] - '0');
preOrder(T1);
inOrder(T1);
str1[size1] = '\0';
if(strlen(compareTree) != strlen(originTree))
cout << "NO" << endl;
else{
size2 = 0;
size = &size2;
str = str2;
Tree T2 = NULL;
for(int j = 0; j < strlen(compareTree); j++)
T2 = Insert(T2, compareTree[j] - '0');
preOrder(T2);
inOrder(T2);
str2[size2] = '\0';
puts(strcmp(str1, str2) == 0 ? "YES" : "NO");
}
}
cin >> n;
}
}

最大公约数

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
#include<iostream>
#include<cstdio>
using namespace std;

int gcd(int a, int b){
if(b == 0)
return a;
else
gcd(b, a % b);
}

int main()
{
int a, b;
while(scanf("%d %d", &a, &b) != EOF){
cout << gcd(a, b) << endl;;
while(a != 0 && b != 0){
int temp = a;
a = b;
b = temp % b;
}
if(a == 0)
cout << b << endl;
else
cout << a << endl;
}
}

最小公倍数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<iostream>
#include<cstdio>
using namespace std;

int gcd(int a, int b)
{
if(b == 0)
return a;
else
gcd(b, a % b);
}

int main()
{
int a, b;
while(scanf("%d %d", &a, &b) != EOF){
int c = gcd(a, b);
int l = a / c * b;
cout << l << endl;
}
}

列出连通集

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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#include<iostream>
#include<queue>
using namespace std;
#define Vertex int
#define WeightType int
#define MaxVertexNum 1000

bool visited[MaxVertexNum];

typedef struct GNode{
int Gv, Ge;
int vexs[MaxVertexNum];
WeightType G[MaxVertexNum][MaxVertexNum];
}*MGraph;

typedef struct ENode{
Vertex v1, v2;
}*Edge;

MGraph BuildGraph(int VertexNum)
{
MGraph Graph = new GNode;
Graph->Gv = VertexNum;
Graph->Ge = 0;
Vertex v, w;
for(v = 0; v < Graph->Gv; v++)
for(w = 0; w < Graph->Gv; w++)
Graph->G[v][w] = 0;
for(int i = 0; i < Graph->Gv; i++)
Graph->vexs[i] = i;
return Graph;
}

void Insert(MGraph g, Edge e)
{
g->G[e->v1][e->v2] = 1;
g->G[e->v2][e->v1] = 1;
}
void DFS(MGraph g, int i)
{
visited[i] = true;
cout << ' ' << g->vexs[i];
for(int j = 0; j < g->Gv; j++)
if(g->G[i][j] == 1 && !visited[j])
DFS(g, j);
}

void DFSTraverse(MGraph g)
{
for(int i = 0; i < g->Gv; i++)
visited[i] = false;
for(int i = 0; i < g->Gv; i++){
if(!visited[i]){
cout << "{";
DFS(g, i);
cout << " }\n";
}
}
}

void BFSTraverse(MGraph g)
{
int i, j;
queue<int> q;
for(i = 0; i < g->Gv; i++)
visited[i] = false;
for(i = 0; i < g->Gv; i++){
if(!visited[i]){
visited[i] = true;
cout << "{";
cout << ' ' << g->vexs[i];
q.push(i);
while(!q.empty())
{
int k = q.front();
q.pop();
for(j = 0; j < g->Gv; j++)
{
if(g->G[k][j] == 1 && !visited[j])
{
visited[j] = true;
cout << ' ' << g->vexs[j];
q.push(j);
}
}
}
cout << " }\n";
}
}
}

int main()
{
int N;
cin >> N;
MGraph G = BuildGraph(N);
cin >> G->Ge;
if(G->Ge != 0){
for(int i = 0; i < G->Ge; i++){
Edge e = new ENode;
cin >> e->v1 >> e->v2;
Insert(G, e);
}
}
DFSTraverse(G);
BFSTraverse(G);
}

计算智能课程

分油问题

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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include<iostream>
#include<queue>
#include<stack>
#include<cstring>
using namespace std;

typedef struct{
int now[3];
int step;
int pre;
}state;//当前状态,包括油瓶现容量以及上一步操作

int capcacity[3] = {10, 7, 3}; //油瓶的容量
int visit[11][8][4]; //记录当前的操作,避免重复上一步操作
vector<state> path;//记录找到答案时的操作
int index = -1, n = 1;//f记录当前操作的序号

int bfs(state &S, int i, int j){//使用广度优先搜索求解
if(i == j) return 0;
if(S.now[i] == 0) return 0;
if(S.now[j] == capcacity[j]) return 0;
if(S.now[i] + S.now[j] <= capcacity[j]){//倒油
S.now[j] = S.now[j] + S.now[i];
S.now[i] = 0;
}else{
S.now[i] = S.now[i] - (capcacity[j] - S.now[j]);
S.now[j] = capcacity[j];
}
if(visit[S.now[0]][S.now[1]][S.now[2]]) return 0;
else {
visit[S.now[0]][S.now[1]][S.now[2]] = 1;
S.pre = index;
path.push_back(S);
n++;
}
S.step++;
return 1;
}

void print(int i){
stack<state> output;
while(i != -1){//倒序输出
state S;
S.now[0] = path[i].now[0];
S.now[1] = path[i].now[1];
S.now[2] = path[i].now[2];
output.push(S);
i = path[i].pre;
}
printf("A\tB\tC\n");
while(!output.empty()){
state S = output.top();
printf("%d\t%d\t%d\n", S.now[0], S.now[1], S.now[2]);
output.pop();
}
}

int main(){
int end[3] = {5, 5, 0};
int i, j, flag, answer;
queue<state>q;
flag = 0;
memset(visit, 0, sizeof(visit));
state start;//初始状态
start.now[0] = 10;
start.now[1] = 0;
start.now[2] = 0;
start.step = 0;
q.push(start);
start.pre = -1;
path.push_back(start);
while(!q.empty()){
state S = q.front();
index++;
q.pop();
if(S.now[0] == end[0] && S.now[1] == end[1]){//得到目标状态
flag = 1;
answer = index;
S.pre = answer;
path.push_back(S);
break;
}
for(i = 0; i < 3; i++){
for(j = 0; j < 3; j++){
state _S = S;
if(bfs(_S, i, j))
q.push(_S);
}
}
}
print(answer);
return 0;
}

Leetcode

bithub00/Leetcode