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
上传中...
上传图片
插入图片