| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 982 人关注过本帖
标题:求聪明的打字员复杂度最低的算法
只看楼主 加入收藏
zorrozzz
Rank: 1
等 级:新手上路
帖 子:22
专家分:0
注 册:2006-10-22
收藏
 问题点数:0 回复次数:5 
求聪明的打字员复杂度最低的算法

聪明的打字员

阿兰是某机密部门的打字员,她现在接到一个任务:需要在一天之内输入几百个长度固定为6的密码。当然,她希望输入的过程中敲击键盘的总次数越少越好。
不幸的是,出于保密的需要,该部门用于输入密码的键盘是特殊设计的,键盘上没有数字键,而只有以下六个键:Swap0, Swap1, Up, Down, Left, Right,为了说明这6个键的作用,我们先定义录入区的6个位置的编号,从左至右依次为1,2,3,4,5,6。下面列出每个键的作用:
Swap0:按Swap0,光标位置不变,将光标所在位置的数字与录入区的1号位置的数字(左起第一个数字)交换。如果光标已经处在录入区的1号位置,则按Swap0键之后,录入区的数字不变;
Swap1:按Swap1,光标位置不变,将光标所在位置的数字与录入区的6号位置的数字(左起第六个数字)交换。如果光标已经处在录入区的6号位置,则按Swap1键之后,录入区的数字不变;
Up:按Up,光标位置不变,将光标所在位置的数字加1(除非该数字是9)。例如,如果光标所在位置的数字为2,按Up之后,该处的数字变为3;如果该处数字为9,则按Up之后,数字不变,光标位置也不变;
Down:按Down,光标位置不变,将光标所在位置的数字减1(除非该数字是0),如果该处数字为0,则按Down之后,数字不变,光标位置也不变;
Left:按Left,光标左移一个位置,如果光标已经在录入区的1号位置(左起第一个位置)上,则光标不动;
Right:按Right,光标右移一个位置,如果光标已经在录入区的6号位置(左起第六个位置)上,则光标不动。
当然,为了使这样的键盘发挥作用,每次录入密码之前,录入区总会随机出现一个长度为6的初始密码,而且光标固定出现在1号位置上。当巧妙地使用上述六个特殊键之后,可以得到目标密码,这时光标允许停在任何一个位置。
现在,阿兰需要你的帮助,编写一个程序,求出录入一个密码需要的最少的击键次数。

输入文件(clever.in)
文件仅一行,含有两个长度为6的数,前者为初始密码,后者为目标密码,两个密码之间用一个空格隔开。

输出文件(clever.out)
文件仅一行,含有一个正整数,为最少需要的击键次数。

输入样例
123456 654321

输出样例
11
希望各位高手能告诉我求解它所使用的复杂度最低的方法

搜索更多相关主题的帖子: 打字员 算法 
2007-07-22 14:50
leeco
Rank: 4
等 级:贵宾
威 望:10
帖 子:1029
专家分:177
注 册:2007-5-10
收藏
得分:0 
测试数据只有一组,BFS即可。
2007-07-23 17:11
zorrozzz
Rank: 1
等 级:新手上路
帖 子:22
专家分:0
注 册:2006-10-22
收藏
得分:0 
回复:(leeco)测试数据只有一组,BFS即可。

不知道怎样剪枝啊(或者用什么处理不用剪枝),时间复杂度太高,能高诉我你的大概思路吗?

2007-07-23 22:07
leeco
Rank: 4
等 级:贵宾
威 望:10
帖 子:1029
专家分:177
注 册:2007-5-10
收藏
得分:0 
不用剪枝,时间复杂度很低,最多有720的结点,哪来什么高复杂度
2007-07-24 01:43
zorrozzz
Rank: 1
等 级:新手上路
帖 子:22
专家分:0
注 册:2006-10-22
收藏
得分:0 
720你怎么排除的啊,我只知道有一种方法可以先将10^6*6*2^6种状态变成720*6*10,但不知到你是怎么处理的,能告诉我你处理的方法么?
2007-07-24 08:41
pimlyb
Rank: 1
等 级:新手上路
帖 子:4
专家分:0
注 册:2007-7-31
收藏
得分:0 
很基础的dp……复杂度最低的算法肯定就是它了……注意每一个状态都很容易按照规则从它之前的状态转移过来……建议lz学下dp……
2007-07-31 22:47
快速回复:求聪明的打字员复杂度最低的算法
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.013894 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved