整數變換問題(C語言)--回溯法

整數變換問題

題目描述

關于整數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;
}