大家来讨论一道题目吧

令狐

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

10072130666

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

stpchina

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

stpchina

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

10072130666

#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

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

乃不

omg!
外行路过~

10072130666

此题数据不大，基本思路是以空间换取时间，把所有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个数替换原来的基础值，再不断的求，直到所有差值的距离全部求出。为了去掉重复时间，只要已经存在距离值得差值不再做计算。

令狐

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

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

stpchina

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

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

stpchina

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

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

stpchina

令狐 发表于 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),否则你直接查数组就行了。

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

令狐

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

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

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

stpchina

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

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

彭云晖

程序还算看懂了点……

彭云晖

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