整数变换问题

Love The Way You Lie 2022-02-15 05:23 166阅读 0赞

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

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

整数变换问题。关于整数i的变换f和g定义如下：f(i)=3i；![1771.png][]  
试设计一个算法，对于给定的2 个整数n和m，用最少的f和g变换次数将n变换为m。例如，可以将整数15用4 次变换将它变换为整数4：4=gfgg(15)。当整数n不可能变换为整数m时，算法应如何处理?  
对任意给定的整数n和m，计算将整数n变换为整数m所需要的最少变换次数。

Input

输入数据的第一行有2 个正整数n和m。n≤100000，m≤1000000000。

Output

将计算出的最少变换次数以及相应的变换序列输出。第一行是最少变换次数。第2 行是相应的变换序列。

Sample Input

15 4

Sample Output

4
    gfgg

#include <iostream>
    #include <vector>
    using namespace std;
    
    vector<char> a;
    int k;
    int select(int n, int i) {
    	if (i == 0) {
    		return 3 * n;
    	}
    	else {
    		return n / 2;
    	}
    }
    
    bool dfs(int step, int n, int m) {
    	int num;
    	if (step > k) {
    		return false;
    	}
    	num = n;
    	for (int i = 0; i < 2; i++) {
    		num = select(n, i);
    		if (num == m || dfs(step + 1, num, m)) {
    			if (i == 0) {
    				a.push_back('f');
    			}
    			else {
    				a.push_back('g');
    			}
    			return true;
    		}
    	}
    	return false;
    }
    
    int main() {
    	int n, m;
    	cin >> n >> m;
    	k = 1;
    	while (!dfs(1, n, m)) {
    		k++;
    	}
    	cout << k << endl;
    	for (int i = 0; i < a.size(); i++) {
    		cout << a[i];
    	}
    	cout << endl;
    	return 0;
    
    }

[1771.png]: https://acm.sdut.edu.cn/image/1771.png

发表评论取消回复

表情：

评论列表（有 0 条评论，166人围观）

还没有评论，来说两句吧...

相关阅读

相关整数划分问题

根据n和m的关系，考虑以下几种情况：（1）当 n = 1 时，不论m的值为多少（m > 0 )，只有一种划分即 \{ 1 \}; (...

墨蓝/ 2024年04月18日 16:42/ 0 赞/ 35 阅读

相关整数划分问题

题目描述计算将一个给定的正整数划分为一系列正整数的和的方案数，称为整数的划分问题，例如，当给定正整数为6时，可以有如下划分： 6=6； 6=5+1； 6=4+2=4+

清疚/ 2023年10月18日 12:19/ 0 赞/ 32 阅读

相关整数变换问题

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

傷城~/ 2022年08月02日 11:46/ 0 赞/ 129 阅读

相关整数因子分解问题

问题描述：大于1的正整数n可以分解为n=x1\x2\…\xn。例如，当n=12时，共有以下8种分解方法： 12=12 12=6\2 12

淩亂°似流年/ 2022年08月02日 06:41/ 0 赞/ 176 阅读

相关大整数乘法问题

“大整数乘法问题”的Java重写思路：该问题涉及的主要知识点为一维数组，这个知识点Java和C++几乎没有不同之处，而且一维数组比二维数组还要简单；本文主要讨论内容是左老师

布满荆棘的人生/ 2022年07月24日 10:10/ 0 赞/ 144 阅读

相关整数划分问题

问题描述：将以正整数n表示成一系列正整数之和。输入：整数N 输出：划分方法的总数。 //n为输入的整数，不同划分中最大加数不超过m，返回划分方法的总数。 int q(

小咪咪/ 2022年07月14日 16:13/ 0 赞/ 143 阅读

相关整数变换问题

整数变换问题 Time Limit: 1000 ms Memory Limit: 65536 KiB Problem Description 整数变换问题。关于整数i

Love The Way You Lie/ 2022年02月15日 05:23/ 0 赞/ 167 阅读

相关整数因子分解问题

整数因子分解问题 Time Limit: 1000 ms Memory Limit: 65536 KiB [Submit][] [Statistic][] Probl

柔光的暖阳◎/ 2022年02月15日 02:06/ 0 赞/ 303 阅读

相关图像变换——等距变换，相似变换，仿射变换，投影变换

[https://blog.csdn.net/hailiannanhai/article/details/80742517][https_blog.csdn.net_haili

﹏ヽ暗。殇╰゛Y/ 2022年01月27日 02:45/ 0 赞/ 381 阅读

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

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

女爷i/ 2022年01月11日 07:03/ 0 赞/ 266 阅读