整数变换问题

傷城~ 2022-08-02 11:46 183阅读 0赞

整数变换问题  
问题描述：  
关于整数i的变换f和g定义如下：f(i)=3i；g(i)=i/2。  
现要求对于给定的2个整数n和m，用最少的f和g变换次数将n变换为m。  
例如，可以将整数15用4次变换将它变换为整数4：4=gfgg(15)。当整数n不可能变换为整数m时，算法应如何处理?这里假定每个问题都有解。  
输入：  
有多组输入数据，每行有2个正整数n和m。  
输出:  
对每组输入，如果不可能在至多25次的变换中将n变到m，那么直接输出“No Solution!”，否则输出最少的变换次数以及相应的变换序列。我们约定f比g在先。对两个满足要求的变换序列A=anan-1..a2.a1、B =bnbn-1..b2b1，我们采用字典序，输出最小的那个，但该字典序是从后开始比较的，即从第1个变换a1和b1开始比较，依次考察是否相同，只要有一个不同，那么有f的那个在先。  
输入样例：  
15 4  
4563 22334  
输出样例：  
4  
gfgg

No Solution

#include "stdafx.h"
    #include<vector>
    #include<iostream>
    
    using namespace std;
    typedef unsigned char byte;
    struct  Node
    {
    	vector<byte>path;
    	int current_value;
    };
    Node solution;
    vector<Node>nextnodelist;
    bool integer_trans(int m, int n, vector<Node>&nodelist)//传引用，减少拷贝的时间。nodelist在后面会很大
    {
    	if (nodelist[0].path.size() == 25)
    	{
    		cout << "已达到最大层数，未找到" << endl;
    		return true;
    	}
    	nextnodelist.clear();
    	cout << nextnodelist.size() << endl;
    	int k = 0;
    	while (k < nodelist.size())
    	{
    		if (nodelist[k].current_value % 3 == 0)
    		{
    			Node node;
    			node.path = nodelist[k].path;
    			node.path.push_back(0);
    			node.current_value = nodelist[k].current_value / 3;
    			nextnodelist.push_back(node);
    			if (node.current_value == n)
    			{
    				solution = node;
    				return true;
    			}
    		}
    
    		Node node1;
    		node1.path = nodelist[k].path;
    		node1.path.push_back(1);
    		node1.current_value = nodelist[k].current_value * 2;
    		nextnodelist.push_back(node1);
    		if (node1.current_value == n)
    		{
    			solution = node1;
    			return true;
    		}
    
    		Node node2;
    		node2.path = nodelist[k].path;
    		node2.path.push_back(2);
    		node2.current_value = nodelist[k].current_value * 2+1;
    		nextnodelist.push_back(node2);
    		if (node2.current_value == n)
    		{
    			solution = node2;
    			return true;
    		}
    
    		k++;
    	}
    
    	return false;
    
    }
    
    
    void solve(int m, int n)
    {
    	Node nn;
    	nn.current_value = m;
    	nextnodelist.push_back(nn);
    	bool flag = false;
    	while (!flag)
    	{
    		vector<Node>nodelist(nextnodelist);
    		flag = integer_trans(m, n, nodelist);
    	}
    }
    
    
    
    int _tmain(int argc, _TCHAR* argv[])
    {
    	//solve(4, 15);
            solve(16,73);
    	system("pause");
    	return 0;
    }

从后往前搜索。

每个node存储它之前操作的记录，0代表f，即/3，1代表\*2,2代表\*2+1，value存储当前值。nodelist只存储一层的节点即可。

因为每次对f先进行操作，也先进行存储，所以找到的第一个满足要求的解也是字典序最小的，直接返回即可。

对于m=16，n=73这个问题运行后给出了答案

查看Node solution里存储的值，

current\_value=73，

path里存了15个数，从0开始如下

1 1 1 1 2 0 0 0 2 0 2 0 1 1 2

验证后是正确的。

内存上消耗也不是很大，只有几十M，但可以想见越往后面内存的增长会很厉害的。