递归：全排列和2的幂次方表达式

1
2
3
4
3
aAb
abc
acba

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
Aab
Aba
aAb
abA
bAa
baA
abc
acb
bac
bca
cab
cba
aabc
aacb
abac
abca
acab
acba
baac
baca
bcaa
caab
caba
cbaa

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <iostream>
#include<algorithm>
using namespace std;
int cmp(char a, char b)
{
	if (tolower(a) != tolower(b))//tolower 是将大写字母转化为小写字母.
		return tolower(a) < tolower(b);
	else
		return a < b;
}
int main() {
	int t;
	cin >> t;
	while (t--) {
		char str[100];
		cin >> str;
		int len = strlen(str);
		sort(str, str + len, cmp);//比较函数
		do {
			cout << str << endl;
		} while (next_permutation(str, str + len, cmp));//排列组合函数
	}

	return 0;
}

1
137

1
2(2(2)+2+2(0))+2(2+2(0))+2(0)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <iostream>
int a[15];//定义数组用于存放2的0次方到2的15次方
//本题的n<=20000故2的15次方就够了
using namespace std;
void two(int n)//定义函数
{
    int k;
    for (k = 14; k >= 0; --k)
    {
        if (a[k] <= n) break;//先找小于等于n的数
    }
    if (k == 0)  cout << "2(0)";
    else if (k == 1) cout << "2";
    else if (k == 2) cout << "2(2)";//判断k是否等于0、1、2
    else {//如果不是对k通过递归进行分解
        cout << "2(";
        two(k);
        cout << ")";
    }
    if (a[k] < n)
    {
        cout << "+";
        two(n - a[k]);//只要a[k] < n就要将n - a[k]用于计算下一个2的幂次方数
    }
}
int main() {

    a[0] = 1;
    for (int i = 1; i < 15; ++i)
    {
        a[i] = 2 * a[i - 1];//利用循环将2的15个次方分别放入对应次序数组中
    }
    int n;
    cin >> n;
    two(n);

    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <iostream>
using namespace std;
int GetBit(int n, int i)
{
    return (n >> i) & 1;//利用位运算  例如：n >> 2== n / 4 ;
    //再通过与运算得出小于等于n的2的幂次方数
}
void Exp(int n)
{
    bool flag = true;//flag用于判断是否要“+”号
    for (int i = 15; i >= 0; i--)
    {
        if (GetBit(n, i))//如果得到数不为零，便可得到离n最近的2的次方i
        {
            if (!flag)
                cout << "+";
            else
                flag = false;
            if (i == 0)//递归的终止条件  第0位 
                cout << "2(0)";
            else if (i == 1)   // 第一位 
                cout << "2";
            else
            {
                cout << "2(";   //第二位以上先输处"2(” 
                Exp(i);         //压栈 
                cout << ")";
            }
        }
    }
}
int main()
{
    int n;
    cin >> n;
    Exp(n);
    return 0;
}