CSP-S 提高级 初赛 模拟试卷（一）

#include <iostream>
using namespace std;
int f(int n) {
    if (n <= 1) return 1;
    return f(n - 1) + f(n - 2);
}
int main() {
    int a = 0;
    for (int i = 1; i <= 5; i++) a += f(i);
    cout << a << endl;
    return 0;
}

#include <iostream>
using namespace std;
int main() {
    int a[] = {5, 2, 8, 1, 9, 3};
    int n = 6, cnt = 0;
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)
            if (a[i] > a[j]) cnt++;
    cout << cnt << endl;
    return 0;
}

#include <iostream>
using namespace std;
int countBits(int x) {
    int c = 0;
    while (x) { x &= (x - 1); c++; }
    return c;
}
int main() {
    int n = 15, ans = 0;
    for (int i = 1; i <= n; i++) ans += countBits(i);
    cout << ans << endl;
    return 0;
}

#include <iostream>
using namespace std;
int binarySearch(int a[], int n, int key) {
    int l = 0, r = n - 1;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (a[mid] == key) return mid;
        else if (a[mid] < key)  ① ;
        else                    ② ;
    }
    return -1;
}

void quickSort(int a[], int l, int r) {
    if (l >= r) return;
    int pivot = a[l], i = l, j = r;
    while (i < j) {
        while (i < j && a[j] >= pivot)  ③ ;
        a[i] = a[j];
        while (i < j && a[i] <= pivot)  ④ ;
        a[j] = a[i];
    }
    a[i] = pivot;
    ⑤ ;   // 递归处理左半部分
    ⑥ ;   // 递归处理右半部分
}