数据结构题目01

1

题目描述

新年快到了,天勤准备搞一个聚会,已经知道现有会员N人,把会员从1到N编号,其中会长的号码是N号,凡是和会长是老朋友的,那么该会员的号码肯定和N有大于1的公约数,否则都是新朋友,现在会长想知道究竟有几个新朋友?请你编程序帮会长计算出来。

输入

第一行是测试数据的组数CN(Casenumber1<CN<10000)CN(Case number,1<CN<10000),接着有CNCN行正整数N(1<n<32768)N(1<n<32768),表示会员人数。

输出

对于每一个NN,输出一行新朋友的人数,这样共有CNCN行输出。

样例输入

1
2
3
2
25608
24027

样例输出

1
2
7680
16016

题解

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
#include <iostream>
using namespace std;
int eular(int n) {
int r = 1;
for (int i = 2; i * i <= n; i++) {
if ( n % i == 0) {
n /= i;
r *= i - 1;
while(n % i == 0){
n /= i;
r *= i;
}
}

}
if (n > 1) r *= n - 1;
return r;
}
int main() {
int CN;
cin >> CN;
for (int i = 0; i < CN; i++) {
int N;
cin >> N;
cout << eular(N) << endl;
}
return 0;
}

2

题目描述

给你一个正整数nn,请问有多少个比nn小的且与nn互质的正整数?
两个整数互质的意思是,这两个整数没有比11大的公约数。

输入

输入包含多组测试数据。每组输入是一个正整数n(n1000000000)n(n \leq 1000000000)。当n=0n=0时,输入结束。

输出

对于每组输入,输出比nn小的且与nn互质的正整数个数。

样例输入

1
2
3
7
12
0

样例输出

1
2
6
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
#include <iostream>
using namespace std;
int eular(int n) {
int r = 1;
for (int i = 2; i * i <= n; i++) {
if ( n % i == 0) {
n /= i;
r *= i - 1;
while(n % i == 0){
n /= i;
r *= i;
}
}

}
if (n > 1) r *= n - 1;
return r;
}
int main() {
int n;
while(cin >> n){
if (n == 0) {
break;
}
cout << eular(n)<<endl;
}
return 0;
}

3

题目描述

nn个人围成一圈,按11nn的顺序编号。从第一个人开始报数(从11mm报数),凡报到mm的人退出圈子,问最后留下的是原来的第几号。

输入

首先输入两个正整数nnmmnn表示nn个人围一个圈子(n2)(n \geq 2)mm表示从11报数到mm的人退出圈子(1m)(1 \leq m)

输出

最后剩下的人的编号。

样例输入

1
2 3

样例输出

1
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
#include <bits/stdc++.h>
using namespace std;
list <int> l;
void init(int n){
for (int i = 1; i <= n; i++) {
l.push_back(i);
}
}
void doJ(int n, int m){
init(n);
list<int> :: iterator it = l.begin();
while(l.size() > 1){
for(int j = 1;j < m; j++){
it ++;
if(it == l.end()){
it = l.begin();
}
}
it = l.erase(it);
if(it == l.end()){
it = l.begin();
}
}
cout << *it << endl;
}
int main() {
int n,m;
cin >> n >> m;
doJ(n, m);
return 0;
}

4

题目描述

编写程序演示把一个1010进制整数转换为RR进制的转换结果。

输入

正整数NNRR,空格分隔
NN是输入的十进制数,RR需要转换的进制数,2R202 \leq R \leq 20

输出

1010进制整数转换为RR进制的转换结果,超过99的数字符号显示为A、B、C……Z等字母。

样例输入

1
10 16

样例输出

1
A

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <bits/stdc++.h>
using namespace std;
string decToR(int n, int r) {
string ans;
string digits = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
while(n > 0){
int m = n % r;
ans = digits[m] + ans;
n /= r;
}
return ans;
}
int main() {
int n, r;
cin >> n >> r;
cout << decToR(n, r);
return 0;
}

5

题目描述

输入两个整数的求和式,比如1+2=,输出求和式和对应结果。请编程实现。

输入

一个求和式,形如a+b=

输出

求和式及对应结果。

样例输入

1
1+2=

样例输出

1
1+2=3

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>
using namespace std;
int stoD(string s){
int a = 0, b = 0;
int i = 0;
while(s[i] != '+'){
a = 10 * a + (s[i] - '0');
i ++;
}
i ++;
while(s[i] != '='){
b = 10 * b + (s[i] - '0');
i ++;
}
return a + b;
}
int main(){
string s;
cin >> s;
cout << s << stoD(s);
return 0;
}

6

题目描述

波兰表达式是一种把运算符前置的算术表达式,例如普通的表达式2 + 3的波兰表示法为+ 2 3。波兰表达式的优点是运算符之间不必有优先级关系,也不必用括号改变运算次序,例如(2 + 3) * 4的波兰表示法为* + 2 3 4。本题求解波兰表达式的值,其中运算符包括+ - * /四个。

输入

输入为一行,其中运算符和运算数之间都用空格分隔,运算数是浮点数。

输出

输出为一行,表达式的值(保留6位小数)。

样例输入

1
* + 11.0 12.0 + 24.0 35.0

样例输出

1
1357.000000

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>
using namespace std;
double operate() {
string s;
cin >> s;
switch (s[0]) {
case '+':
return operate() + operate();
case '-':
return operate() - operate();
case '*':
return operate() * operate();
case '/':
return operate() / operate();
default:
return stold(s);
}
}
int main() {
printf("%.6lf",operate());
return 0;
}

7

题目描述

上体育课的时候,老师已经把班级同学排成了两个队列,而且每个队列都是按照从底到高排好队,现在需要把两个队列合并,合并后需要保证还是从低到高排列。合并队列,你能编程实现吗?

输入

第1行为nn,表示开始排成的每个队列的长度。第2、3行是代表从小到大的nn个整数,每行的整数间有一个空格间隔。

输出

输出占一行,为从小到大的整数,每个整数间间隔一个空格。

样例输入

1
2
3
5
1 3 5 8 15
2 3 4 6 9

样例输出

1
1 2 3 3 4 5 6 8 9 15

题解

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 <bits/stdc++.h>
using namespace std;
queue<int> a,b;
queue<int> merge(queue<int> a,queue<int> b) {
queue<int> c;
while (!a.empty() && !b.empty()) {
if (a.front() < b.front()) {
c.push(a.front());
a.pop();
}
else {
c.push(b.front());
b.pop();
}
}
while (!a.empty()) {
c.push(a.front());
a.pop();
}
while (!b.empty()) {
c.push(b.front());
b.pop();
}
return c;
}
int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
a.push(x);
}
for (int i = 0; i < n; i++) {
int x;
cin >> x;
b.push(x);
}
queue<int> c = merge(a,b);
for(int i = 0; i < 2 * n; i++){
cout << c.front() << ' ';
c.pop();
}
return 0;
}

数据结构题目01
https://ivansnow02.github.io/posts/53823/
作者
Ivan Snow
发布于
2023年5月31日
许可协议