第二周测验全排列、2的幂次方表示

本是古典何须时尚 2022-05-10 09:52 283阅读 0赞

## 003:全排列 ##

描述

给定一个由不同的小写字母组成的字符串，输出这个字符串的所有全排列。 我们假设对于小写字母有'a' < 'b' < ... < 'y' < 'z'，而且给定的字符串中的字母已经按照从小到大的顺序排列。

输入

输入只有一行，是一个由不同的小写字母组成的字符串，已知字符串的长度在1到6之间。

输出

输出这个字符串的所有排列方式，每行一个排列。要求字母序比较小的排列在前面。字母序如下定义：  
  
已知S = s1s2...sk , T = t1t2...tk，则S < T 等价于，存在p (1 <= p <= k)，使得  
s1 = t1, s2 = t2, ..., sp - 1 = tp - 1, sp < tp成立。

样例输入

abc

样例输出

abc
    acb
    bac
    bca
    cab
    cba

#include<iostream>
    #include<cstring>
    using namespace std;
    char str[10], res[10];
    int mark[10];
    int l;
    void dfs();
    
    
    void print()
    {
    	for(int i = 0; i < l; ++i)
    	{
    		cout << res[i];
    	}
    	cout << endl;
    }
    
    void dfs(int n)
    {
    	if(n == l) 
    	{
    		print();
    		return ;
    	}
    	for(int i = 0; i < l; ++ i)
    	{
    		if(mark[i] == 0)
    		{
    			mark[i] = 1;
    			res[n] = str[i];
    			dfs(n+1);
    			mark[i] = 0;
    		}
    	}
    	return ;
    }
    
    int main()
    {
    	cin >> str;
    	l = strlen(str);
    	dfs(0);
    	return 0;
    }

#include<iostream>
    #include<algorithm>
    #include<cstring>
    #include<string>
    using namespace std;
    const int M = 8;
    char str[M];
    char pl[M];
    bool used[M] = {0};
    int l = 0;
    void PL(int);
    int main()
    {
    	cin >> str;
    	l = strlen(str);
    	PL(0);
    	return 0;
    } 
    void PL(int n)
    {
    	if(n==l)
    	{
    		pl[l] = 0;
    		cout << pl << endl;
    		return ;
    	}
    	for(int i = 0; i < l; ++i)
    	{
    		if(!used[i])
    		{
    			used[i] = true;
    			pl[n] = str[i];
    			PL(n+1);
    			used[i] = false;
    		}
    	}
    }

## 004: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)

来源

NOIP1998复赛 普及组 第一题

> 【分析】137化作二进制形式为 10001001，其中1000 0000 0000 0000 的值为32768, 0100 0000 0000 0000的值为16384,本题n的范围为20000，所以二进制位应该取到16位。
> 
> 137:10001001 等效于 137 = 2^7+2^3+2^0
> 
> 7： 111 等效于 7 = 2^2+2^1+2^0
> 
> 3： 11 等效于 3 = 2^1+2^0
> 
> 因此可以得到：
> 
> 137 = 2^7+2^3+2^0
> 
> = 2^(2^2+2+2^0)+2(2+2^0)+2^0
> 
> =2(2(2)+2+2(0))+2(2+2(0))+2(0)
> 
> 本题需要取n的二进制位，当二进制位为1的时候才需要分解（递归），一直分解到2^2为止，其中要注意2^1和2^0两种特殊情况要单独考虑。

#include<iostream>
    using namespace std;
    int pos[32];
    int GetBit(int n,int i)//取n的第i位
    {
    	return (n >> i) & 1;
    }
    void print(int n)
    {
    	bool first = true;
    	for(int i = 15; i >= 0; --i)
    	{
    		if(GetBit(n,i))//第i位为1时进行递归
    		{
    			if(!first)
    			{
    				cout << "+";
    			}
    			else
    				first = false;
    			if(i == 0)
    				cout << "2(0)";
    			else if(i == 1)
    				cout << "2";
    			else
    			{
    				cout << "2(";
    				print(i);
    				cout << ")";
    			}
    		}
    	}
    }
    int main()
    {
    	int n;
    	cin >> n;
    	print(n);
    	return 0;
    }