BIT-CS-2001年复试机试(A)（约瑟夫环链表法）

1、编写程序，计算下列分段函数 y=f(x)的值。

y= -x+2.5，0<= x <2

y=2-1.5(x-3)(x-3)，2<= x <4

y=x/2-1.5，4<= x <6。

#include<iostream>
using namespace std;
int main() {
    int n;
    cin >> n;
    if (0 <= n&&n < 2)
        cout << 2.5 - n;
    else if (n >= 2 && n < 4)
        cout << 2 - 1.5*(n - 3)*(n - 3);
    else if (n <= 4 && n < 6)
        cout << n*0.5 - 1.5;
    system("pause");
    return 0;
}

2、编写程序，读入一个整数 N。若 N 为非负数，则计算 N 到 2N 之间的整数和；若 N 为一个负数，则求 2N 到 N 之间的整数和。

#include<iostream>
using namespace std;
int main() {
    int n;
    cin >> n;
    long long int sum;
    if (n >= 0)
        sum = (n+1)*(n + 2 * n) / 2;
    else
        sum = (1-n)*(n + 2 * n) / 2;
    cout << sum;
    system("pause");
    return 0;
}

3、设 N 是一个四位数，它的 9 倍恰好是其反序数（例如：1234 的反序数是 4321），求 N 的值。

#include<iostream>
using namespace std;
int main() {
    for (int n = 1000; n <= 9999; n++) {
        long int m = n * 9;
        int a = n / 1000;
        int b = n / 100 - a * 10;
        int c = n / 10 - a * 100 - b * 10;
        int d = n % 10;
        int aa = m / 1000;
        int bb = m / 100 - aa * 10;
        int cc = m / 10 - aa * 100 - bb * 10;
        int dd = m % 10;
        if (a == dd&&b == cc&&c == bb&&d == aa)
            cout << n << endl;
    }
    system("pause");
    return 0;
}

4、N 个人围成一圈顺序编号，从 1 号开始按 1、2、 3 顺序报数，报 3 者退出圈外，其余的人再从 1、2、 3 开始报数，报 3 的人再退出圈外，依次类推。请按退出顺序输出每个退出人的原序号。要求使用环形链表编程。
即约瑟夫环问题。

#include<iostream>
using namespace std;
struct lnode {
    int num;
    lnode *next;
};
int main() {
    lnode *temp,*p;
    lnode *head = new lnode;    //初始化链表
    head->num = 1;
    p = head;
    p->next = NULL;
    int n;
    cin >> n;
    for (int i = 2; i <= n; i++) {
        temp = new lnode;
        temp->num = i;
        p->next = temp;
        p = temp;
        p->next = NULL;
    }
    p->next = head;  //成环
    p = head;
    int i = 1;
    while (n != 0) {
        if (i % 3 == 0) {
            cout << p->num << " ";
            head->next = p->next;
            i = 1;
            p = head->next;
            n--;
        }
        i++;
        head = p;
        p = p->next;
    }

    system("pause");
    return 0;
}