大家来讨论一道题目吧

令狐 · 发表于 2011-8-29 16:45:36

给定两个整数a和b，这两个数的取值均在【-2000,2000】区间中。把对a进行一系列操作得到b的过程称为a到b的路径
，可选操作包括：加12、减 12、加7、减7、加5、减5。例如-5至19的的一条路径为（-5,7,19）。现要求编写程序，
对任何a和b，求a至b的最短路径。

10072130666 · 发表于 2011-8-29 17:12:22

本帖最后由 10072130666 于 2011-8-29 17:24 编辑

这个要动态规划了。。。慢慢想想。。。。

stpchina · 发表于 2011-8-29 18:00:15

应为求的是最短路径，所以LZ只需要考虑[-12,12]之间的各种情况，因为在这区间之外的都能通过移动12，转化为[-12,12]之间的情况，这样一来问题规模就缩小很多了

stpchina · 发表于 2011-8-29 18:01:56

问题规模还有可能缩小，反正思路我给出了，剩下的LZ自己想吧。

10072130666 · 发表于 2011-8-29 18:23:51

#include<stdio.h>
int dis[8005],op[7],done[8005],done_nxt[8005];

int main()
{
int done_n,done_c=6,dis_n=2,pot_n,total=6,i,j;
int a,b;
op[1]=-12;op[2]=-7;op[3]=-5;op[4]=5;op[5]=7;op[6]=12;
for(i=1;i<=6;i++)
{
done[i]=op[i]+2000;
dis[done[i]]=1;
}
while(1)
{
done_n=0;
for(i=1;i<=done_c;i++)
{
for(j=1;j<=6;j++)
{
pot_n=done[i]+op[j];
if(pot_n>=0&&pot_n<=8000&&dis[pot_n]==0)
{
dis[pot_n]=dis_n;
done_nxt[++done_n]=pot_n;
}
}
}
total+=done_n;
if(total>=8000)
break;
done_c=done_n;
for(i=1;i<=done_n;i++)
done[i]=done_nxt[i];
dis_n++;
// for(i=1;i<=done_n;i++)
// printf("%d ",done[i]-2000);
// printf("\n");
}
while(scanf("%d %d",&a,&b)!=EOF)
{
if(a>b)
{
a=a^b;
b=b^a;
a=a^b;
}
printf("%d\n",dis[b-a+2000]);
}
return 0;
}

10072130666 · 发表于 2011-8-29 18:24:28

程序我给出来了，你可以运行测试，输入a和b回车就能得出结果。

乃不 · 发表于 2011-8-29 18:29:57

omg!
外行路过~

10072130666 · 发表于 2011-8-29 18:30:31

此题数据不大，基本思路是以空间换取时间，把所有ab只差的距离求出即可。首先初始化是相差+12，+7，+5，-5，-7，-12这些数，相差这些值的数距离为1，把这些基础值分别经过这6种运算，得到第二批的基础值：-24，-19，-17，0，-14，-2，-10，2，10，17，14，19，24这13个数，相差这些值得ab距离为2，将这13个数替换原来的基础值，再不断的求，直到所有差值的距离全部求出。为了去掉重复时间，只要已经存在距离值得差值不再做计算。

令狐 · 发表于 2011-8-29 22:18:52

stpchina 发表于 2011-8-29 18:00
应为求的是最短路径，所以LZ只需要考虑[-12,12]之间的各种情况，因为在这区间之外的都能通过移动12，转化为 ...

你这个算法肯定不能保证路径最小。
其实这个问题还是很复杂的，找一条路径很容易，找最短路径不是那么容易的事

stpchina · 发表于 2011-8-30 10:32:37

令狐发表于 2011-8-29 22:18
你这个算法肯定不能保证路径最小。
其实这个问题还是很复杂的，找一条路径很容易，找最短路径不是那么容 ...

有什么路径会比每次走最长距离的路径短，你走进死胡同了，自己好好想想吧。

stpchina · 发表于 2011-8-30 10:35:26

令狐发表于 2011-8-29 22:18
你这个算法肯定不能保证路径最小。
其实这个问题还是很复杂的，找一条路径很容易，找最短路径不是那么容 ...

我突然发现你所说的路径，和我讨论的路径不是同一个概念，我所说的是路径是其移动步数，不知道你所需要的是不是这个概念

stpchina · 发表于 2011-8-30 11:58:58

令狐发表于 2011-8-29 22:18
你这个算法肯定不能保证路径最小。
其实这个问题还是很复杂的，找一条路径很容易，找最短路径不是那么容 ...

我再进一步提醒一下吧，你可以参考一下图论中求最短路径的算法，我们先找出对应距离为1~12的最短距离分别是7,8,4,4,1,6,1,5,3,2,5,1,。然后如果你要计算距离为13的最短路径，我们肯定无法一步达到，则我们必定需要通过形式上的两步走完这段距离，如2-11,5-8.......我们前面已经找出了1-12的最短距离，那么将其存入一个数组中，取头尾指针从两头遍历该数组，找出距离和最小的一个，就是13的最短路径，我们可以找出3-10与5-8都是13的最短路径，长度为6,。至于14,15,16.。。。。。。的距离不用我再说了吧。
最后进行复杂性分析：如果你没有足够的内存来储存一个4000维的整数数组，那么从13开始算时间代价为O(n^2),否则你直接查数组就行了。

我说的够多了，不用我再做正确性证明了吧

令狐 · 发表于 2011-8-30 20:16:25

stpchina 发表于 2011-8-30 11:58
我再进一步提醒一下吧，你可以参考一下图论中求最短路径的算法，我们先找出对应距离为1~12的最短距离分别 ...

我举个例子吧，
比如 28走到0的最短路径应该是 28->21->14->7->0

按你的想法28->16->4 然后再寻找4->0的最短路径，这样肯定比上一种方法步数更多

stpchina · 发表于 2011-8-30 21:05:03

本帖最后由 stpchina 于 2011-8-30 21:09 编辑

令狐发表于 2011-8-30 20:16
我举个例子吧，
比如 28走到0的最短路径应该是 28->21->14->7->0

你做错了，我们首先算出的是14，最短路径是7-7，然后算出的是21最短路径是7-14,28的时候是7-21。我的想法是以1-12为基础，逐步扩充数组，可能说的有点急，但我还是希望LZ耐心的看。

彭云晖 · 发表于 2011-8-31 16:22:46

程序还算看懂了点……

彭云晖 · 发表于 2011-8-31 16:25:51

输入-12和12，得到的结果是2……

		自动登录	找回密码
密码			注册账号

大家来讨论一道题目吧

本帖子中包含更多资源