整数变换问题(C语言)--回溯法

女爷i 2022-01-11 07:03 313阅读 0赞

## ***整数变换问题*** ##

**题目描述**  
关于整数i的变换f和g定义如下：f(i)=3i；g(i)=i/2。  
现要求对于给定的2个整数n和m，用最少的f和g变换次数将n变换为m。

**具体代码实现**

#include<stdio.h>
    #define MAX 100 
    #define MAXVALUE 32767
    int m,n;
    int a[MAX]={0};	//记录变换数组 
    int b[MAX];		//记录最少变换数组 
    int mincount=MAXVALUE;	//记录最少变换次数 
    int tempcount=0;		//记录交换次数 
    
    //向文件读入一个字符 
    void fileWriteChar(char c){
    	FILE *fp;
    	fp = fopen("i:\\算法\\回溯法\\output.txt", "a");
    	
    	if (fp == NULL) {			//若打开文件失败则退出
            printf("不能打开文件！\n");
            return ;
        }
    	
    	fprintf(fp,"%c",c); 
    	
    	fclose(fp);	
    }
    
    //向文件读入一个数字 
    void fileWriteInt(int i){
    	FILE *fp;
    	fp = fopen("i:\\算法\\回溯法\\output.txt", "a");
    	
    	if (fp == NULL) {			//若打开文件失败则退出
            printf("不能打开文件！\n");
            return ;
        }
    	
    	fprintf(fp,"%d\n",i); 
    	
    	fclose(fp);	
    }
    
    //从文件读取m,n
    void fileRead(){
    	FILE *fp;
    	fp = fopen("i:\\算法\\回溯法\\input.txt", "r");
    	if (fp == NULL) {			//若打开文件失败则退出
            printf("不能打开文件！\n");
            return ;
        }
        
     	//从文件中读入m,n
        fscanf(fp,"%d",&m);
        fscanf(fp,"%d",&n);
    	
    	fclose(fp);	
    } 
    
    void traceback(int t)
    {
    	
    	if(t==n)    
    	{
    		if(tempcount<mincount)
    		{
    			mincount=tempcount;
    			for(int i=1;i<=mincount;i++)
    			{
    				b[i]=a[i];		
    			}
    		}
    		return;
    	}
    	else{
    		tempcount++;
    		if(tempcount<mincount && t>n)
    		{
    			a[tempcount]=2;
    			traceback(t/2);
    		} 
    		tempcount--;
    		
    		tempcount++;
    		if(tempcount<mincount && t>0 && t<n)
    		{
    			a[tempcount]=1;
    			traceback(t*3);	
    		}
    		tempcount--;
    	}
    	
    	
    	
    }
    
    int main(){
    	fileRead();
    	traceback(m);
    	fileWriteInt(mincount);	//最少变换次数 
    	for(int i=mincount;i>0;i--){
    		if(a[i]==2)
    			fileWriteChar('g');
    		else
    			fileWriteChar('f');
    	}
    	
    	return 0;
    }