2 scutcoder scutcoder 于 2014.08.23 10:23 提问

问一个算法问题,将一个数变为另一个数的最少步骤

“上上下下左右左右 BABA”中,上用↑表示,下用↓表示,左用←表示,右用→表示,A,
B。先定义一个输入区,模拟 6 位数的输入,输入区有六个位置为(从左到右)第 1 位,第
2 位,第 3 位,第 4 位,第 5 位,第 6 位。有一个指针指向当前操作位置,称其为指针,手
柄上的六个按键分别执行以下操作:
↑:按↑,指针所指向的位置不变,将指针指向位置的数字加 1 (除非它是 9)。例如,如果
指针指向的数字为 6,按↑之后,该数字变为 7;如果该数字是 9,则按↑之后,数字以及
指针位置都不变;
↓:按↓,指针所指向的位置不变,将指针指向位置的数字减 1 (除非它是 0),如果该处数
字为 0,则按↓之后,数字不变,指针所指位置也不变;
←:按←,指针向左移一个位置,如果指针已经指向输入区的第 1 位,则指针位置不变化;
→: 按→, 指针向右移一个位置,如果指针已经指向输入区的第 6 位, 则指针位置也无变化。
A:按 A,指针所指位置不变,输入区第 1 位的数字会和指针所指位置的数字交换。如果指
针指向的是第 1 位,则按 A 键之后,输入区无变化;
B:按 B,指针所指位置不变,输入区第 6 位的数字会和指针所指向的数字与交换。如果指
针指向的是第 6 位数字,则按 B 键之后,输入区无变化;
因为不能直接输入数字, 为了能够达到输入数字的目的, 每次输入目标数字之前, 输入区总
会先随机生成一个 6 位数字,而且指针固定指向第 1 位。当灵活运用手柄上的这六个键, 就
可以得到目标数字,完成输入,最终允许指针指向任何位置。
可以看出,使用这种方案,输入同一个目标数字可能有不种操作方式(按键次数不一) ,但
是存在一种输入方案, 使得需要按键次数最少。 现在请你编写一个程序,求出输入一个目标
数字需要的最少按键次数是多少。

比如说

123456变为654321的最少步骤如下:
B 623451
→ 623451
A 263451
↓ 253451
→ 253451
↑ 254451
→ 254451
↓ 254351
→ 254351
↑ 254361
A 654321
最少按键次数为 11 次

Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
网易笔试编程题:到Fibonacci数最小步数(C++)
题目: Fibonacci数列是这样定义的: F[0] = 0 F[1] = 1 for each i ≥ 2: F[i] = F[i-1] + F[i-2] 因此,Fibonacci数列就形如:0, 1, 1, 2, 3, 5, 8, 13, …,在Fibonacci数列中的数我们称为Fibonacci数。给你一个N,你想让其变为一个Fibonacci数,每一步你可以把
一个无序数组,删除最少的数,使其变得有序
如题,求指导!
输入一个无符号整数,用最少的步骤将该数变为1
输入一个无符号整数n,用最少的步骤将该数变为1,当n为偶数时可以采取的步骤是除2的形式,当n为奇数的时候可以采取加1或者减1的操作。 #include #include using namespace std; int min(int a, int b) { if (a < b) return a; return b; } int get_pow(uint num) { if
hdu 5256 序列变换 求最少改变次数使序列变为递增 最长不下降子序列
题意:我们有一个数列A1,A2…An,你现在要求修改数量最少的元素,使得这个数列严格递增。其中无论是修改前还是修改后,每个元素都必须是整数。 请输出最少需要修改多少个元素。对于任意两个数A[i]A[i],A[j]A[j](i>ji>j) 如果满足A[i]−A[j]≥i−jA[i]-A[j] \geq i-j可以使得[i,j][i,j]区间内的数都是可修改为递增的,可以将上面那个式子转换为A[i]−
25最小操作数问题
题目描述:     给定一个单词集合Dict,其中每个单词的长度都相同。现从此单词集合Dict中抽取两个单词A、B。希望通过若干次操作把单词A变成单词B,每次操作可以改变单词的一个字母,同时,每次操作后,新产生的单词必须是在给定的单词集合Dict中。求所有行得通步数最少的修改方法。    举个例子如下: Given:    A ="hit"    B ="cog"    Dict =[
每天一道LeetCode-----使用最少的操作将一个字符串转换成另一个字符串,只有插入,删除,替换三种操作
原题链接Edit Distance 题目要求,输入两个字符串word1和word2,计算可以将word1转换成word2的最小的操作次数,可以执行的操作如下,每个操作算作1次 将word1的某个字符删除 在word1当前位置插入一个字符 将word1当前位置的字符替换成另一个字符 上面的三个操作每操作一次总操作次数都需要加一,计算最小的操作次数。这是典型的动态规划问题。假设word1的长度为m,
求给定数等于最少的几个完全平方数之和
given an integer ,find 最小长度minlen 的expression of integer, minlen 定义为多少个完全平方数相加?例如 14 = 1 + 4 + 9, minlen = 3int MinExpressionInteger(int i) { int k = sqrt(i); if (k*k == i) return 1;
动态规划求解-将字符串A变换为字符串B 所用的最少字符操作次数
问题描述: 设A 和B 是2 个字符串。要用最少的字符操作将字符串A 转换为字符串B。 这里所说的字符操作包括 (1)删除一个字符; (2)插入一个字符; (3)将一个字符改为另一个字符。 将字符串A变换为字符串B 所用的最少字符操作次数也称为字符串A到B 的编辑距离,记为 d(A,B)。 试设计一个有效算法,对任给的2 个字符串A和B,计算出它们的编辑距离d(A,B)。 思路:
最少交换次数
Problem E: 排序 Time Limit: 1 Sec  Memory Limit: 128 MB Submit: 89  Solved: 39 Description  对于排序算,相信大家都再熟悉不过了,经典的有直接插入排序,快速排序等等。之前小A做过一个和排序相关的问题,给定一个序列,这个序列包含N个不相同的数字,每一个数字属于1到N,要求每次只能交换相邻的两个数字,
一个数是否是另一个数的平方
这个题目肯定不能用sqrt这个函数,如果用了话就违背了本题的考察点。 为了解析这个题目,给出一个数学公式: (n+1)^2=n^2+(2n+1) (n+1)^2=(n-1)^2+[2(n-1)+1]+(2n+1) ..... (n+1)^2=1+(2*1+1)+(2*2+1)+...+[2(n-1)+1]+(2n+1) 可以自己动手验证这个公式的正确性。 下面给出代码:(注:下面的代