程序设计实习MOOC / 程序设计与算法（二）第二周测验(2018春季)

递归算法：

1:全排列

总时间限制: 

1000ms

 

内存限制: 

65536kB

描述

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

输入

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

输出

输出这个字符串的所有排列方式，每行一个排列。要求字母序比较小的排列在前面。字母序如下定义：

已知S = s₁s₂...s_k , T = t₁t₂...t_k，则S < T 等价于，存在p (1 <= p <= k)，使得
s₁ = t₁, s₂ = t₂, ..., s_{p - 1} = t_{p - 1}, s_p < t_p成立。

样例输入

abc

样例输出

abc
acb
bac
bca
cab
cba

答案：

#include <iostream>  
#include <cstring> 
using namespace std;  
int n = 0;  
  
void swap(char *a ,char *b)  
{  
    int m ;  
    m = *a;  
    *a = *b;  
    *b = m;  
}   
   
void perm(char list[],int k, int m )  
{  
    int i;  
    if(k >m)  
    {  
        for(i = 0 ; i <= m ; i++)  
        {  
            cout<<list[i];  
               
        }  
        cout<<"
";  
        n++;  
    }  
    else  
    {  
        for(i = k ; i <=m;i++)  
        {  
            swap(&list[k],&list[i]);  
            perm(list,k+1,m);  
            swap(&list[k],&list[i]);  
        }  
    }  
}  
  
int main()  
{  
    char list[50];
    cin.get(list,50);
    int len=strlen(list) - 1;
    perm(list,0,len);     
    return 0;  
}  

2:2的幂次方表示

总时间限制: 

1000ms

 

内存限制: 

65536kB

描述

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

    137=2⁷+2³+2⁰

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

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

进一步：7=2²+2+2⁰（2¹用2表示）

        3=2+2⁰

所以最后137可表示为：

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

又如：

    1315=2¹⁰+2⁸+2⁵+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复赛 普及组 第一题

答案：

#include<cstdio>  
#include<cstdlib>  
#include<cstring>  
  
void f(int n)  
{  
    if(n==1)  
    {  
        printf("2(0)");  
        return;  
    }  
    if(n==2)  
    {  
        printf("2");  
        return;  
    }  
    int p=1;  
    int s=0;  
    while(p<=n)  
    {  
        p=p*2;  
        s++;  
    }  
    s=s-1;  
    if(n==p/2)  
    {  
        printf("2(");  
        f(s);  
        printf(")");      
    }  
    else  
    {  
        if(p/2==2)  
        {  
            printf("2");  
            printf("+");  
            f(n-p/2);  
        }  
        else  
        {  
            printf("2(");  
            f(s);  
            printf(")+");  
            f(n-p/2);  
        }  
    }  
}  
  
int main()  
{  
    int n;  
    scanf("%d",&n);  
    f(n);  
}