第六章 函数

第一节 函数

1150：求正整数 2 和 n 之间的完全数

代码

#include <bits/stdc++.h>

using namespace std;

bool check(int x) {
    int sum = 0;
    for (int i = 1; i < x; i++)
        if (x % i == 0) sum += i;

    if (sum == x) return true;
    else return false;
}

int main() {
    int n;
    cin >> n;

    for (int i = 2; i <= n; i++) {
        if (check(i)) cout << i << '\n';
    }

    return 0;
}

1151：素数个数

代码

#include <bits/stdc++.h>

using namespace std;

bool is_prime(int x) {
    if (x < 2) return false;
    for (int i = 2; i <= x / i; i++)
        if (x % i == 0) return false;

    return true;
}

int main() {
    int n;
    cin >> n;

    int cnt = 0;
    for (int i = 2; i <= n; i++)
        if (is_prime(i)) cnt++;

    cout << cnt << endl;

    return 0;
}

1152：最大数 max (x,y,z)

代码

#include <bits/stdc++.h>

using namespace std;

double maxn(double a, double b, double c) {
    return max(a,max(b, c));
}

int main() {
    int a, b, c;
    cin >> a >> b >> c;

    double s = double(maxn(a, b, c)) /(maxn(a + b, b, c) * maxn(a, b, b + c));

    printf("%.3lf", s);

    return 0;
}

1153：绝对素数

代码

#include <bits/stdc++.h>

using namespace std;

bool shu(int x) {
    if (x < 2) return false;
    for (int i = 2; i <= x / i; i++)
        if (x % i == 0) return false;

    return true;
}

int main() {
    for (int i = 10; i <= 99; i++) {
        int x = i % 10 * 10 + i / 10;
        if (shu(i) && shu(x)) printf("%d\n", i);
    }

    return 0;
}

1154：亲和数

代码

#include <bits/stdc++.h>

using namespace std;

int f(int x) {
    int s = 0;
    for (int i = 1; i <= x / i; i++) {
        if (x % i == 0) {
            if (i != 1) s += i + x / i;
            else s += 1;
        }
    }

    return s;
}

int main() {
    int x = 2;
    while (1) {
        int a = x;
        int b = f(a);

        if (f(b) == a && a < b) {
            cout << a << ' ' << b << endl;
            break;
        }

        x++;
    }

    return 0;
}

1155：回文三位数

提示

prime，质数

palindrome，回文

代码

#include <bits/stdc++.h>

using namespace std;

bool is_palindrome(int x) {
    int ori = x;
    int t = 0;
    while (x) {
        t = t * 10 + x % 10;
        x /= 10;
    }

    if (ori == t) return true;
    else return false;
}

bool is_prime(int x) {
    if (x < 2) return false;
    for (int i = 2; i <= x / i; i++)
        if (x % i == 0) return false;

    return true;
}

int main() {
    for (int i = 100; i < 1000; i++) {
        if (is_palindrome(i) && is_prime(i)) {
            cout << i << endl;
        }
    }

    return 0;
}

1156：求 π 的值

提示

这个题目，有点饶一点

首先是这两个公式，看不懂。arctanx(x) 是一个多项式

当x取 \(\frac{1}{\sqrt{3}}\) 时，算出来 \(\pi\)

代码

// 求当最后一项小于10?6时π的值。
// 多项式的最后一项，是>=1e-6的
// 小于1e-6就不要加进来

#include <iostream>
#include <cmath>

using namespace std;

double arctanx(double x) {
    double ret = 0.0;

    double fenzi = x;
    int t = -1, fenmu = 1;
    while (true) {
        t *= -1;
        ret += t * fenzi / fenmu;

        fenzi *= x * x;
        fenmu += 2;

        if (fenzi / fenmu < 1e-6) break;
    }

    return ret;
}

int main() {
    printf("%.10lf\n", 6 * arctanx(1.0 / sqrt(3)));

    return 0;
}

1157：哥德巴赫猜想

代码

#include<iostream>

using namespace std;

bool is_prime(int n){
    if (n < 2) return false;
    for (int i = 2; i <= n / i; i++)
        if (n % i == 0) return false;

    return true;
}

int main(){
    for (int x = 6; x <= 100; x += 2){
        bool flag = false;
        for (int i = 2; i <= x; i++){
            int j = x - i;
            if (is_prime(i) && is_prime(j)){
                cout << x << '=' << i << '+' << j << '\n';
                flag = true;
                break;
            }

            if (flag) break;
        }
    }

    return 0;
}

1397：简单算术表达式求值

提示

两位正整数的简单算术运算

注意，两个整数，都是两位数，有了这个前提条件，输入上，才好处理

代码

#include <bits/stdc++.h>

using namespace std;

int a, b;
char c;

int main() {
    scanf("%2d%c%2d", &a, &c, &b);

    if (c == '+') cout << a + b << '\n';
    else if (c == '-') cout << a - b << '\n';
    else if (c == '*') cout << a * b << '\n';
    else if (c == '/') cout << a / b << '\n';
    else cout << a % b << '\n';

    return 0;
}

代码02

// 如果没注意到两个整数的位数，是固定两位的，
// 或者题目就没说几位数的时候
// 那就需要把这一行当成一个字符串输入，然后手动拆出来
// 下面这份代码的写法，要掌握，【必会技能】
#include <bits/stdc++.h>

using namespace std;

string a, b;
char op;

int f(string s) {
    int t = 0;
    for (int i = 0, len = s.size(); i < len; i++)
        t = t * 10 + (s[i] - '0');

    return t;
}

int main() {
    string s;
    getline(cin, s);

    int len = s.size();
    int pos;

    a += s[pos++];
    a += s[pos++];

    while (pos < len && s[pos] == ' ') pos++;

    op = s[pos++];

    while (pos < len && s[pos] == ' ') pos++;

    b += s[pos++];
    b += s[pos++];

    int aa = f(a);
    int bb = f(b);

    //printf("---%d %d\n", aa, bb);
    if (op == '+') cout << aa + bb << endl;
    else if (op == '-') cout << aa - bb << endl;
    else if (op == '*') cout << aa * bb << endl;
    else if (op == '/') cout << aa / bb << endl;
    else if (op == '%') cout << aa % bb << endl;

    return 0;
}

1398：短信计费

代码

#include <bits/stdc++.h>
using namespace std;

double cnt;

double f(double x) {
    double n=0;

    do {
        n+=0.1;
        x-=70;
    } while (x>0);

    return n;
}

int main() {
    int n,m;
    cin>>n;

    for (int i=0; i<n; i++) {
        cin>>m;
        //cout << f(m) << '\n';
        cnt+=f(m);
    }

    printf("%.1lf\n",cnt);

    return 0;
}

1399：甲流病人初筛

代码

#include <bits/stdc++.h>

using namespace std;

int n;
int cnt;
string s;
double degree;
int flag;

int main() {
    cin >> n;
    while (n--) {
        cin >> s >> degree >> flag;
        if (degree >= 37.5 && flag) {
            cnt++;
            cout << s << '\n';
        }
    }
    cout << cnt << '\n';

    return 0;
}

1400：统计单词数

提示

此题对代码能力要求高一点

抠单词是一个基本功

此题，对.find()函数熟悉的，会好写一点

代码

// 这份代码，就是利用抠单词的基本功
// 直接抠就行了
#include<bits/stdc++.h>

using namespace std;

string st1,st2;

void solve() {
    for(int i = 0, len = st1.size(); i < len; i++)
        if(st1[i] >= 'A' && st1[i] <= 'Z') st1[i] += 32;

    for(int i = 0, len = st2.size(); i < len; i++)
        if(st2[i] >= 'A' && st2[i] <= 'Z') st2[i] += 32;
}

int main() {
    int a=0,b=-1;

    getline(cin,st1);
    getline(cin,st2);

    solve();

    for(int i = 0, len = st2.size(); i < len; i++) {
        string s="";
        int j = i;
        while (j < len && st2[j] != ' ') s += st2[j++];

        if(s == st1) {
            a++;
            if(b == -1) b = i;
        }

        while(j < len && st2[j] == ' ') j++;

        i = j - 1;
    }

    if(b == -1) cout<<-1 << '\n';
    else cout<<a<<' '<<b << '\n';

    return 0;
}

代码02

// 这份代码是，利用.find()函数
// .find()函数有一个参数的版本，有两个参数的版本
// 两个参数的，就是指定从哪个位置开始往后找
// 这样就形成了，找到一个，就从这个位置下一个位置开始往后找
// 代码就好写了
#include<iostream>

using namespace std;

string s, s1;

void get_lower(string &s) {
    for (int i = 0, len = s.size(); i < len; i++)
        if (s[i] >= 'A' && s[i] <= 'Z') s[i] += 32;
}

int main() {
    cin >> s;
    getchar();
    getline(cin, s1);

    get_lower(s);
    get_lower(s1);

    s = ' ' + s + ' ';
    s1 = ' ' + s1 + ' ';

    if (s1.find(s) == string::npos) {
        cout << -1 << '\n';
        return 0;
    }

    int tot = 0, fir = s1.find(s);
    int nxt = fir;
    while (nxt != -1) {
        tot++;
        nxt = s1.find(s, nxt + 1);
    }
    cout << tot << ' ' << fir << '\n';

    return 0;
}

1401：机器翻译

代码

// 用到了queue
// 用bool数组，或者map是否在内存里
#include <iostream>
#include <queue>

using namespace std;

int m, n, cnt;
queue<int> q;
bool vis[1010];

int main() {
    cin >> m >> n;
    while (n--) {
        int x;
        cin >> x;

        if (vis[x]) continue;
        cnt++;

        if (q.size() == m) {
            int t = q.front();
            q.pop();
            vis[t] = false;
        }

        q.push(x);
        vis[x] = true;
    }

    cout << cnt << '\n';

    return 0;
}

1402：Vigenère 密码

提示

Helloworld

abcabcabca

Hfnlpyosnd

题面给的数据有误

代码

#include <bits/stdc++.h>

using namespace std;

string K, C;

int main() {
    cin >> K >> C;  // K是密钥，C是密文

    int idx = 0, klen = K.size();
    string s;
    for (int i = 0, len = C.size(); i < len; i++) {
        char c = K[idx]; // 把密钥的字符拿出来, 计算偏移量
        int delta = 0;
        if (c >= 'A' && c <= 'Z') delta = c - 'A';
        if (c >= 'a' && c <= 'z') delta = c - 'a';

        char mc = C[i]; // 把密文的字符拿出来，按偏移量进行操作
        if (mc >= 'A' && mc <= 'Z') s += 'A' + (mc - 'A' - delta + 26) % 26;
        if (mc >= 'a' && mc <= 'z') s += 'a' + (mc - 'a' - delta + 26) % 26;

        // 这里面有+26 %26，是为了防止向左偏移减成负数

        idx++;
        if (idx >= klen) idx = 0; // 这个是用来循环使用密钥的
    }

    cout << s << endl;

    return 0;
}

1403：素数对

提示

先用筛法，把所有质数放到一起

然后捋一遍，看前后是否相差2

这里用的是埃式筛法（以后还要学习一个线性筛法）

代码

#include<bits/stdc++.h>
using namespace std;

bool st[100010];
int primes[100010], cnt, n, maxn = 10010;

void get_primes(int n) {
    for(int i = 2; i <= n; i++) {
        if(st[i]) continue;
        primes[cnt++] = i;
        for(int j = i + i; j <= n; j +=i) {
            st[j] = true;
        }
    }
}
int main() {
    cin >> n;
    get_primes(n);

    bool flag = false;
    for(int i = 1; i < cnt; i++) {
        if (primes[i] - primes[i - 1] == 2) {
            cout << primes[i - 1] <<' '<< primes[i] <<'\n';
            flag = true;
        }
    }

    if (!flag) cout << "empty" << endl;

    return 0;
}

1404：我家的门牌号

代码

#include <bits/stdc++.h>

using namespace std;

int n;

bool check(int x, int y) {
    if (y*(y+1)/2 - 3*x == n) return true;
    else return false;
}

int main() {
    cin >> n;

    int y = 1;
    while (true) {
        for (int i = 1; i <= y; i++)
            if (check(i, y)) {
                cout << i << ' ' << y << '\n';
                return 0;
            }

        y++;
    }

    return 0;
}

1405：质数的和与积

代码

#include <bits/stdc++.h>

using namespace std;

bool is_prime(int x) {
    if (x < 2) return false;
    for (int i = 2; i <= x / i; i++)
        if (x % i == 0) return false;

    return true;
}

int main() {
    int n;
    cin >> n;

    int maxn = -1;
    for (int i = 2; i <= n - 2; i++)
        if (is_prime(i) && is_prime(n - i))
            maxn = max(maxn, i * (n - i));

    cout << maxn << endl;

    return 0;
}

1406：单词替换

提示

这份代码中，有抠单词的操作，用到的是for循环里套了一个while

这种写法，在后续学习算法过程中，是非常重要的代码写法

要好好体会，这个代码思想

另外，在循环内部的最后一行，有一句 i = j - 1;，这句话忘写，会影响答案。你分析分析

代码

#include <bits/stdc++.h>

using namespace std;

string s, a, b;

int main() {
    getline(cin, s);
    cin >> a >> b;

    for (int i = 0, len = s.size(); i < len; i++) {
        string temp;
        int j = i;
        while (j < len && s[j] != ' ') temp += s[j++];

        if (temp == a) cout << b << ' ';
        else cout << temp << ' ';

        // 多余的空格
        while (j < len && s[j] == ' ') j++;
        i = j - 1;
    }

    return 0;
}

1407：笨小猴

代码

#include <bits/stdc++.h>

using namespace std;

int cnt[30];

bool is_prime(int x) {
    if (x < 2) return false;
    for (int i = 2; i <= x / i; i++)
        if (x % i == 0) return false;

    return true;
}

int main() {
    string s;
    cin >> s;

    for (int i = 0, len = s.size(); i < len; i++)
        cnt[s[i] - 'a']++;

    int maxn = -1, minn = 110;
    for (int i = 0; i < 26; i++) {
        if (cnt[i]) {
            maxn = max(maxn, cnt[i]);
            minn = min(minn, cnt[i]);
        }
    }

    if (is_prime(maxn - minn)) {
        cout << "Lucky Word" << endl;
        cout << maxn - minn << endl;
    } else {
        cout << "No Answer" << endl;
        cout << 0 << endl;
    }

    return 0;
}

1408：系数回文数的个数

代码

#include <bits/stdc++.h>

using namespace std;

int primes[1010], idx;
bool st[1010];

void get_primes(int n) {
    for (int i = 2; i <= n; i++) {
        if (!st[i]) primes[idx++] = i;

        for (int j = 0; primes[j] <= n / i; j++) {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) break;
        }
    }
}

bool is_panlindrome(int x) {
    int ori = x;
    int t = 0;
    while (x) {
        t = t * 10 + x % 10;
        x /= 10;
    }

    if (t == ori) return true;

    return false;
}

int main() {
    int n;
    cin >> n;

    get_primes(n);

    int cnt = 0;
    for (int i = 4; i < idx; i++)
        if (is_panlindrome(primes[i])) {
            //cout << primes[i] << endl;
            cnt++;
        }
    cout << cnt << endl;

    return 0;
}

1409：判决素数个数

代码

#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 10;

int primes[N], idx;
bool st[N];

void get_primes(int n) {
    for (int i = 2; i <= n; i++) {
        if (!st[i]) primes[idx++] = i;

        for (int j = 0; primes[j] <= n / i; j++) {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) break;
        }
    }
}

int main() {
    get_primes(N);

    int x, y;
    cin >> x >> y;

    int a = lower_bound(primes, primes + idx, x) - primes;
    int b = upper_bound(primes, primes + idx, y) - primes - 1;

    //cout << a << ' ' << b << endl;
    cout << b - a + 1 << endl;

    return 0;
}

1410：最大质因子序列

代码

#include <bits/stdc++.h>

using namespace std;

bool is_prime(int x) {
    if (x < 2) return false;
    for (int i = 2; i <= x / i; i++)
        if (x % i == 0) return false;

    return true;
}

int solve(int x) {
    for (int i = x; i >= 2; i--) {
        if (x % i == 0 && is_prime(i))
            return i;
    }
}

int main() {
    int x, y;
    cin >> x >> y;

    bool flag = false;
    for (int i = x; i <= y; i++) {
        if (flag) cout << ',';

        cout << solve(i) ;
        flag = true;
    }
}

1411：区间内的真素数

代码

#include <bits/stdc++.h>

using namespace std;

int solve(int x)
{
    int t = 0;
    while (x)
    {
        t = t * 10 + x % 10;
        x /= 10;
    }

    return t;
}

bool is_prime(int x)
{
    if (x < 2) return false;
    for (int i = 2; i <= x / i; i++)
        if (x % i == 0) return false;

    return true;
}

int main()
{
    int x, y;
    cin >> x >> y;

    bool flag = false;
    for (int i = x; i <= y; i++)
    {
        int t = solve(i);
        if (is_prime(i) && is_prime(t)) 
        {
            if (flag) cout << ',';
            cout << i;
            flag = true;
        }
    }

    if (!flag) cout << "No";
    puts("");

    return 0;
}

代码02

// 这份代码，是把质数先筛出来，维护到st数组里(st, state)
// 然后看自己是不是质数，翻转之后的数是不是质数
#include<bits/stdc++.h>

using namespace std;

int m, n, primes[50050], cnt;
bool st[100100], f[100100];

void get_primes() {
    for(int i = 2; i <= 100000; i++) {
        if(st[i]) continue;
        primes[cnt++] = i;
        f[i] = true;
        for(int j = i + i; j <= 100000; j += i) {
            st[j] = true;
        }
    }
}

int change(int n) {
    int x = 0;
    while(n) {
        x = x * 10 + n % 10;
        n /= 10;
    }
    return x;
}

int main() {
    cin >> m >> n;
    bool flag = false;

    get_primes();

    for(int i = m; i <= n; i++) {
        if(f[i] && f[change(i)]) {
            if(flag) cout << ',';
            cout << i;
            flag = true;
        }
    }
    if(!flag) cout << "No";

    return 0;
}

1412：二进制分类

代码

#include<iostream>

using namespace std;

int A, B;

int main() {
    for(int i = 1; i <= 1000; i++) {
        int zero = 0, one = 0;
        int j = i;
        while (j) {
            if (j % 2 == 1) one++;
            else zero++;
            j /= 2;
        }

        //printf("---%d %d %d\n", i, one, zero);
        if (one > zero) A++;
        else B++;
    }

    cout << A << ' ' << B << '\n';

    return 0;
}

代码02

// 这份代码，用的是二进制的思想，需要对二进制有深入理解
#include <bits/stdc++.h>

using namespace std;

bool check(int x) {
    int sum = 0;
    int one = 0;

    for (int j = 0; (1 << j) <= x; j++) {
        if (x & (1 << j)) one++;

        sum++;
    }

    if (one > (sum - one)) return true;

    return false;
}

int main() {
    int A = 0, B = 0;
    for (int i = 1; i <= 1000; i++) {
        if (check(i)) A++;
        else B++;
    }

    cout << A << ' ' << B << endl;

    return 0;
}

1413：确定进制

提示

这个题目，看起来没有什么头绪

要找最小的进制，就从最小的二进制开始枚举吧

如果这个进制成立，那就找到答案了

代码

#include <bits/stdc++.h>

using namespace std;

int work(int x, int y) {
    int sum = 0;
    int t = 1;

    do {
        if (x % 10 >= y) return -1;

        sum += t * (x % 10);
        t *= y;
        x /= 10;
    } while (x);

    return sum;
}

int main() {
    int p, q, r;
    cin >> p >> q >> r;

    bool flag = false;
    for (int i = 2; i <= 40; i++) {
        int pp = work(p, i);
        int qq = work(q, i);
        int rr = work(r, i);

        if (pp == -1 || qq == -1 || rr == -1) continue;

        if (pp * qq == rr) {
            cout << i << endl;
            flag = true;

            break;
        }
    }

    if (!flag) cout << 0 << endl;

    return 0;
}

第二节 递归算法

1158：求 1+2+3+…

提示

问题的边界

求解子问题

代码

#include <bits/stdc++.h>

using namespace std;

int f(int n) {
    //问题的边界
    if (n == 1) return 1;

    //求解子问题
    return f(n - 1) + n;
}

int main() {
    int n;
    cin >> n;

    cout << f(n) << '\n';

    return 0;
}

1159：斐波那契数列

代码

#include <iostream>

using namespace std;

int f(int n) {
    if (n == 1) return 0;
    if (n == 2) return 1;
    return f(n - 1) + f(n - 2);
}

int main() {
    int n;
    cin >> n;

    cout << f(n) << '\n';

    return 0;
}

1160：倒数数

代码

#include <bits/stdc++.h>

using namespace std;

void f(int n) {
    if (n == 0) return ;

    cout << n % 10;
    f(n / 10);
}

int main() {
    int n;
    cin >> n;

    f(n);

    return 0;
}

1161：转进制

代码

#include <bits/stdc++.h>

using namespace std;

int n, m;

string s = "0123456789ABCDEF";

void f(int x) {
    if (x == 0) return;

    f(x / m);
    cout << s[x % m];
}

int main() {
    cin >> n >> m;

    f(n);

    return 0;
}

1162：字符串逆序

代码

#include <bits/stdc++.h>

using namespace std;

void f(string s, int pos) {
    if (pos < 0) return ;

    cout << s[pos];
    f(s, pos - 1);
}

int main() {
    string s;
    cin >> s;

    int len = s.size();

    f(s, len - 2);

    return 0;
}

1163：阿克曼 (Ackermann) 函数

代码

#include<iostream>

using namespace std;

int akm(int m, int n) {
    if (m == 0) return n + 1;

    if (m > 0 && n == 0) return akm(m - 1, 1);
    if (m > 0 && n > 0) return akm(m-1, akm(m, n-1));
}

int main() {
    int m, n;
    cin >> m >> n;

    cout << akm(m, n) << '\n';

    return 0;
}

1164：digit 函数

代码

#include <bits/stdc++.h>

using namespace std;

int f(int n, int k) {
    //printf("---%d %d\n", n, k);
    if (k == 1) return n % 10;

    return f(n / 10, k - 1);
}

int main() {
    int n, k;
    cin >> n >> k;

    cout << f(n, k) << endl;

    return 0;
}

1165：Hermite 多项式

提示

少了条件，保留小数点后2位

代码

//少了条件，保留小数点后2位
#include <bits/stdc++.h>

using namespace std;

double h(int n, double x) {
    if (n == 0) return 1;
    if (n == 1) return x * 2;

    return 2 * x * h(n - 1, x) - 2 * (n - 1) * h(n - 2, x);
}

int main() {
    int n;
    double x;
    cin >> n >> x;

    printf("%.2lf\n", h(n, x));

    return 0;
}

1166：求 f (x,n)

代码

#include <bits/stdc++.h>

using namespace std;

double f(double x, int n) {
    if (n == 1) return sqrt(1 + x);

    return sqrt(n + f(x, n - 1));
}

int main() {
    double x;
    int n;

    cin >> x >> n;

    printf("%.2lf\n", f(x, n));

    return 0;
}

1167：再求 f (x,n)

代码

#include <bits/stdc++.h>

using namespace std;

double f(double x, int n) {
    if (n == 1) return x / (1 + x);

    return x / (n + f(x, n - 1));
}

int main() {
    double x;
    int n;
    cin >> x >> n;

    double res = f(x, n);
    printf("%.2lf\n", res);

    return 0;
}