A1158 求1+2+3+...

题意

用递归的方法求1+2+3+……+N的值。

题解

int sum_n(int N) {  
    if (N == 1) {  
        return 1;  
    } else {  
        return N + sum_n(N - 1);  
    }  
}

A1159 斐波那契数列

题意

用递归函数输出斐波那契数列第n项。0,1，1，2，3，5，8，13……

题解

int fibonacci(int n) {
    if (n == 1) {
        return 0;
    } else if(n == 2 || n == 3) {
        return 1;
    } else {
        return fibonacci(n - 1) + fibonacci(n - 2);
    }
}

A1188 菲波那契数列(2)

题意

菲波那契数列是指这样的数列: 数列的第一个和第二个数都为1，接下来每个数都等于前面2个数之和。

给出一个正整数a，要求菲波那契数列中第a个数对1000取模的结果是多少。有n次查询。

题解

递归超时，用递推。

const int maxn = 1e6 + 5;
int a[maxn];
int main() {
    a[1] = 1, a[2] = 1;
    for(int i = 3; i < maxn; i++)
        a[i] = (a[i - 1] + a[i - 2]) % 1000;
    int n;
    cin >> n;
    while(n--) {
        int i;
        cin >> i;
        cout << a[i] << endl;
    }
    return 0;
}

A1160 倒序数

题意

输入一个非负整数，输出这个数的倒序数。例如输入123，输出321。

题解

void reversed(int x) {
    cout << x % 10;
    if(x >= 10)
        reversed(x / 10);
}

A1161 转进制

题意

用递归算法将一个十进制数X转换成任意进制数M（M≤16）。

题解

string toBase(int n, int b) { //将数值n转换为b进制字符串
    if(n == 0)//如果n是0，不输出
        return string("");
    char c;//n%b这一数字对应的字符
    if(n % b >= 10)//将n%b的值以b进制输出
        c = n % b - 10 + 'A';
    else
        c = n % b + '0';
    return toBase(n / b, b) + c;//将n/b的值转为b进制字符串 后面连接c
}
int main() {
    int n, b;
    cin >> n >> b;
    if(n == 0)
        cout << 0 << endl;
    cout << toBase(n, b);
    return 0;
}

A1162 字符串逆序

题意

输入一串以‘！’结束的字符，按逆序输出。

题解

string reversed(string s) {
    if(s[0] == '!')
        return string("");
    char c = s[0];
    s.erase(0, 1);
    return reversed(s) + c;
}
int main() {
    string s;
    cin >> s;
    cout << reversed(s);
    return 0;
}

A1198 逆波兰表达式

题意

求逆波兰表达式的结果。

题解

double exp() {
    char s[20];
    cin >> s;
    switch(s[0]) {
    case '+':
        return exp() + exp();
    case '-':
        return exp() - exp();
    case '*':
        return exp() * exp();
    case '/':
        return exp() / exp();
    default:
        return atof(s);
        break;

    }
}
int main() {
    printf("%f", exp());
    return 0;
}

A1199 全排列

题意

给定一个由不同的小写字母组成的字符串，输出这个字符串的所有全排列。

我们假设对于小写字母有‘a’ <‘b’ < ... <‘y’<‘z’，而且给定的字符串中的字母已经按照从小到大的顺序排列。

题解

时间复杂度$O(n!)$，空间复杂度$O(n)$。

int n;
string a, s;//a为输入，s为输出
bool pos[7];//记录a对应位置的字符是否已用
void Perm(int u) {
    //如果s填满，则输出
    if (u == n) {
        cout << s << endl;
    } else {
        for (int i = 0; i < n; i++) {
            //如果a的位置i还没用
            if (pos[i] == false) {
                s[u] = a[i];//用a[i]填s
                pos[i] = true;//标记a[i]已用
                Perm(u + 1);//填s的下一个位置
                pos[i] = false;//复原，相当于s[u]位置不填a[i]，用于填别的数。
            }
        }
    }
}
int main() {
    cin >> a;
    n = a.size();//用a初始化s，目的是给s初始化空间
    s = a;
    Perm(0);
    return 0;
}

A1205 汉诺塔问题

题意

输入盘子的数目，后面三个字符表示三个杆子的编号。

输出每一步移动盘子的记录。一次移动一行。

题解

void h(int n, char a, char b, char c) {
    if(n == 1) {
        cout << a << "->" << n << "->" << b << "\n";
        return;
    }
    h(n - 1, a, c, b);
    cout << a << "->" << n << "->" << b << "\n";
    h(n - 1, c, b, a);
}
int main() {
    int N;
    char A, B, C;
    cin >> N >> A >> B >> C;
    h(N, A, B, C);
    return 0;
}

A1313 【例3.5】位数问题

题意

在所有的 N 位正整数中，有多少个数中有偶数个数字 3？由于结果可能很大，你只需要输出这个答案对 12345 取余的值。

题解

递归会超时，用递推。

const int mod = 12345;
const int MAXN = 1010;
// a[i]：i位数有多少个数字含偶数个3；
// b[i]：i位数有多少个数字含奇数个3。
int a[MAXN], b[MAXN];
int main() {
    int N;
    cin >> N;
    a[1] = 8, b[1] = 1;
    for(int i = 2; i <= N; i++) {
        a[i] = (9 * a[i - 1] + b[i - 1]) % mod;
        b[i] = (9 * b[i - 1] + a[i - 1]) % mod;
    }
    cout << a[N];
    return 0;
}