首页计算机科学408数据结构

# 1

# 题目描述

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

# 输入

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

# 输出

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

# 样例输入

2
25608
24027

# 样例输出

7680
16016

# 题解

#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(n≤1000000000)n(n \leq 1000000000)。当n=0n=0 时，输入结束。


# 输出


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


# 样例输入


7
12
0
# 样例输出


6
4
# 题解


#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 个人围成一圈，按11 到nn 的顺序编号。从第一个人开始报数（从11 到mm 报数），凡报到mm 的人退出圈子，问最后留下的是原来的第几号。


# 输入


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


# 输出


最后剩下的人的编号。


# 样例输入


2 3
# 样例输出


2
# 题解


#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 进制的转换结果。


# 输入


正整数NN 和RR，空格分隔

NN 是输入的十进制数，RR 需要转换的进制数，2≤R≤202 \leq R \leq 20


# 输出


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


# 样例输入


10 16
# 样例输出


A
# 题解


#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+2=
# 样例输出


1+2=3
# 题解


#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 位小数)。


# 样例输入


* + 11.0 12.0 + 24.0 35.0
# 样例输出


1357.000000
# 题解


#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 个整数，每行的整数间有一个空格间隔。


# 输出


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


# 样例输入


5
1 3 5 8 15
2 3 4 6 9
# 样例输出


1 2 3 3 4 5 6 8 9 15
# 题解


#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;
}