實在算不出28,樓主能否給出28的走法,壹下程序根據過河問題原理設計而成,可參考:
/kk0602/blog/item/e9cadb1e1212fdf3e0fe0b03.html
得到最小值是29.
#include<stdio.h>
#ifdef USE_CHINESE
const char* guoqiao ="過橋";
const char* hui ="回";
#else
const char* guoqiao ="go through bridge";
const char* hui ="come back";
#endif
int getShortestTime(int arr[], int n)
{
if(!arr || n < 1) return 0;
if(n<4){
if(n == 3)
{
printf("(1,2) %s;\n", guoqiao);
printf("1 %s; \n", hui);
printf("(1,3) %s;\n", guoqiao);
return (arr[0]+arr[1]+arr[2]);
}
if(n == 2)
{
printf("(1,2) %s;\n", guoqiao);
return arr[1];
}
if(n == 1)
{
printf("1 %s;\n", guoqiao);
return arr[0];
}
}
else{
int a=arr[0], b=arr[1], c=arr[n-2],d=arr[n-1];
if(a+c>2*b)
{
printf("(1,2) %s;\n", guoqiao);
printf("2 %s; \n", hui);
printf("(%d,%d) %s; \n", n-1, n, guoqiao);
printf("1 %s; \n\n", hui);
return (a+d+2*b + getShortestTime(arr, n-2));
}
else
{
printf("(1,%d) %s;\n", guoqiao);
printf("1 %s; \n", hui);
printf("(1,%d) %s;\n", n-1, guoqiao);
printf("1 %s; \n\n", hui);
return (c+d+2*a + getShortestTime(arr, n-2));
}
}
}
void main()
{
int n = 5;
int a[] = {1,2,6,8,12};
printf("The Shortest Time is %d\n", getShortestTime(a, n));
}