注意:只是为了抬头,这不是我学校的任务,因为我自己甚至不知道哪所学校写了这个问题.希望没有误会.
我发现这个关于更衣室的有趣问题:
Rec的更衣室有N个储物柜,标有1,2,.... ..,N.
每个储物柜都已锁定,但可以使用其唯一的钥匙打开.
每个储物柜钥匙的副本都在其相邻的储物柜内; 即,储物柜钥匙的副本i被放置在储物柜i + 1和i-1中(储物柜1的钥匙仅在储物柜2中,储物柜N的钥匙仅在储物柜N-1中).
T网球在T个不同的储物柜内(你知道他们在哪个储物柜里).您将获得M个储物柜的钥匙,您的目标是通过打开最少数量的储物柜来收集所有网球.
我必须向一些新生提出这个问题,但我想先确定我自己已经预先得到了正确的答案.
我在想的是:
需要逐一检查球.因此,对于每个球(忽略其他球),每个球必须通过遍历指定的球来访问.对于每个键,计算访问球所需的步骤.最小的结果存储在称为"总步数"的变量中.
对下一个球做这个确切的事情,当我得到当前球的最小步数.我将此值添加到"总步骤".
如果钥匙上方有一个球,则应用特殊条件,然后键开始从i + 1和i-1移动.
我的问题是:我是对的吗？我不想将错误的算法分享给其他人,因为它不专业.期待任何意见,建议和意见.
izo*_*ica 16
您的算法不会产生最少的步骤数.你不能独立考虑球.让我们考虑以下情况:你只有一把钥匙用于1号储物柜,而球放在储物柜12,10,8,6,4,2中.如果按照我给出的顺序考虑球,最终会得到总步数等于11 + 9 + 7 + 5 + 3 + 1,虽然你可以通过11个步骤的单程解决问题.您不应该忽略前面步骤中访问过的框.