OI

【模拟】三道进制转换（递归）

poj3191转-2进制

直接模拟短除法，用递归实现还是挺漂亮的

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<stdio.h>
typedef long long ll;

void fun(ll n,ll sig){
    int r;
    r=n%2;
    if(n!=0){
      if(r==0)fun(n/2,-sig);
      else if(sig==-1){
          fun(n/2+1,-sig);
      }
      else fun(n/2,-sig);
    }
    if(n!=0)printf("%d",r);
}

int main(){
    ll n,f;
    scanf("%lld",&n);
    f=1;
    if(n<0){n=-n;f=-1;}
    if(n==0)printf("0");
    else fun(n,f);
    return 0;
}

poj1220高精度进制转换

这个高精度本质上是模拟了短除法过程

然后领悟了递归的应用：直接利用递归附加栈回溯的性质一次性倒序输出了；

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include<stdio.h>
#include<string.h>
#define MAX 100005
char num[100]={'0','1','2','3','4','5','6','7','8','9',
'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z',
'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};
int ord[200];
char oric[MAX];
int ori[MAX];
int f;

void fin(int len){
    int i;
    for(i=0;i<len;i++)
      if(ori[i]!=0)return;
    f=1;
}

void fun(int a,int b,int len){
    int i=0,j,r;
    while(ori[i]==0)i++;
    for(;i<len;i++){
        r=ori[i]%b;
        ori[i]/=b;
        ori[i+1]+=r*a;
    }
    fin(len);
    if(!f)fun(a,b,len);
    printf("%c",num[r]);
}


int main(){
    int i,j,k,n,a,b,len;
    scanf("%d",&n);
    for(i='0';i<='9';i++){
      ord[i]=i-'0';
    }
    for(i='A';i<='Z';i++){
      ord[i]=i-'A'+10;
    }
    for(i='a';i<='z';i++){
      ord[i]=i-'a'+36;
    }
    
    for(i=1;i<=n;i++){
        scanf("%d%d",&a,&b);
        scanf("%s",oric);
        len=strlen(oric);
        
        printf("%d ",a);
        puts(oric);
        printf("%d ",b);
        
        for(j=0;j<len;j++)
            ori[j]=ord[oric[j]];
        f=0;
        fun(a,b,len);
        printf("\n\n");
    }
    
    return 0;
}

P1010幂次方

这道题大方向好想，就是求二进制，然后分治到0或1为止

但是输出格式的细节问题挺麻烦，想了很久。最后是借助全局量不是很漂亮的解决了。

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
#include<stdio.h>
int t=0,f[20005]={0};
void fun(int n,int i,int p){
    int r;
    r=n%2;
    if(n/2!=0)
      fun(n/2,i+1,p);
    if(r){
        if(f[p])printf("+");
        if(!f[p])f[p]=1;
        if(i==0)printf("2(0)");
        else if(i==1)printf("2");
        else{
            printf("2(");
            t++;
            fun(i,0,t);
            printf(")");
        }
    }
}

int main(){
    int n;
    scanf("%d",&n);
    fun(n,0,0);
    return 0;
}