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

t1.全排列poj1256

 描述：

给定一个字符串，按照字典序输出所有排序，并且不区分大小写。

样例输入：

3
aAb
abc
acba

样例输出：

Aab
Aba
aAb
abA
bAa
baA
abc
acb
bac
bca
cab
cba
aabc
aacb
abac
abca
acab
acba
baac
baca
bcaa
caab
caba
cbaa

 思路：

该题的关键就是需要用到STL提供求下一个排列组合的函数next_permutation()。例如3个字符a、b、c组成的序列，next_permutation()能按字典返回6个组合，即：abc,acb,bac,bca,cab,cba。

代码如下：

#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;
}

t2.2的幂次方表示

描述

任何一个正整数都可以用2的幂次方表示。例如：

    137=27+23+20

同时约定方次用括号来表示，即ab可表示为a(b)。由此可知，137可表示为：

    2(7)+2(3)+2(0)

进一步：7=22+2+20（21用2表示）

        3=2+20

所以最后137可表示为：

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

又如：

    1315=210+28+25+2+1

所以1315最后可表示为：

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

输入

一个正整数n（n≤20000）。

输出

一行，符合约定的n的0，2表示（在表示中不能有空格）。

样例输入

137

样例输出

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

思路：

将输入的n和二的次方进行比较使用递归进行比较，有两种解法。

解法一：

将二的次方数存入到一个数组内，由题目所述n≤20000故只要存到2的15次方即可

代码如下：

#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;
}

（本解法有一定局限性，要先知道n的范围，因此可以先把n不断去除2直到小于等一为止，除以2的次数便为2的次方数）

解法二：

自定义一个按位计算的函数，然后使用递归进行比较。

代码如下：

#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;
}

大数据201 liyang

最后

以上就是尊敬树叶为你收集整理的递归：全排列和2的幂次方表达式的全部内容，希望文章能够帮你解决递归：全排列和2的幂次方表达式所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。