原创

---

整数变换问题：整数i的两种变换定义为，（向下取整）；设计一个算法求给定两个整数a和b，用最少次数的和变换将整数a变换为b；

例如：4=gfgg(15)

这道题目有两种情况，一种是有解，即n可以通过函数变换成m；另一种是无解，即n无法通过函数变换成m。

第一种情况比较容易，即只需要判断最后的x是否等于m即可。如果x等于m，那么说明n已经被变换成m了，递归返回。

第二种情况，如果在递归的过程，出现了前面计算过的元素，那就说明n是无法转换成m的。

用回溯法解决整数变换问题，用子集树。

import java.util.Scanner;import java.util.ArrayList;class chang{    private int a;    private int bestdept=200;    private int track[]=new int[21];    private int besttrack[]=new int[21];    private ArrayList list=new ArrayList();    private boolean flag=false;    public chang(int a,int b){        this.a=a;        list.add(a);    }    public boolean judge(int a){        for(int i=0;i
     
      20 || t>bestdept){    //最大步数为200            return;        }        if(m==n){            bestdept=t-1;            for(int i=1;i<=20;i++){                besttrack[i]=track[i];            }            flag=true;            return;        }        for(int i=1;i<=2;i++){    //1代表f,2代表g            if(i==1){                if(judge(m*3)){                    list.add(m*3);                    track[t]=i;                    atob(m*3,n,t+1);                    track[t]=0;    //回溯                    list.remove(list.size()-1);                }            }else{                if(judge(m/2)){                    list.add(m/2);                    track[t]=i;                    atob(m/2,n,t+1);                    track[t]=0;                    list.remove(list.size()-1);                }            }                    }    }    public void outPut(){        if(flag==true){            for(int i=20;i>=1;i--){                if(besttrack[i]==0){                    continue;                }else if(besttrack[i]==1){                    System.out.print("f");                }else if(besttrack[i]==2){                    System.out.print("g");                }            }        }else{            System.out.println("no solution");        }        System.out.print("("+a+")");    }}public class changInt {    public static void main(String[] args) {        Scanner reader=new Scanner(System.in);        int a=reader.nextInt();        int b=reader.nextInt();        chang ch=new chang(a,b);        ch.atob(a,b,1);        ch.outPut();    }}
     

18:35:20

2018-11-11