| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 6645 人关注过本帖
标题:过桥问题..
只看楼主 加入收藏
maxam0128
Rank: 2
等 级:论坛游民
帖 子:37
专家分:10
注 册:2011-10-9
结帖率:75%
收藏
 问题点数:0 回复次数:23 
过桥问题..
漆黑的夜里,n位旅行者来到了一座狭窄而且没有护栏的桥边。如果不借助手电筒的话,大家是无论如何也不敢过桥去的。不幸的是,他们一共只带了一只手电筒,而桥窄得只够让两个人同时过。如果各自单独过桥的话,每人所需要的时间分别是a1、a2、...an分钟;而如果两人同时过桥,所需要的时间就是走得比较慢的那个人单独行动时所需的时间。问题是,如何设计一个方案,让这些人尽快过桥。
#include<stdio.h>
int main()
{
    int n,a[100],i,m=0,s,j,t;
    while(scanf("%d",&n)!=0)
    {
        s=0;
        for(i=0;i<n;i++)
        scanf("%d",&a[i]);
        for(i=0;i<n;i++)
        {
            for(j=1+i;j<n;j++)
            if(a[j]<a[i])
            {
                t=a[i];
                a[i]=a[j];
                a[j]=t;
            }
        }
        if(n%2==0)
        {for(i=n-1;i>=1;i=i-2)
        s=s+a[i];
        s=s+(n-2)*a[1]+a[0]*(n-2)/2;
        printf("%d\n",s);}
        else
        {for(i=n-1;i>=0;i=i-2) s=s+a[i];
        
        s=s+(n-3)*a[1]+a[0]*(n-3)/2+a[1];
        printf("%d\n",s);}   
    }
    return(0);
}
搜索更多相关主题的帖子: 手电筒 护栏 include 旅行者 而且 
2011-11-08 09:20
luchar
Rank: 9Rank: 9Rank: 9
来 自:南京
等 级:蜘蛛侠
帖 子:279
专家分:1263
注 册:2011-11-3
收藏
得分:0 
首先,你的算法不对。有n个人过桥,所需时间最短为除了用时最短的人以外的n-1个人的用时之和,加上用时最短人的时间×(n-2);
其次,用while(scanf("%d",&n)!=0)这句语句的话,最后要输入一个0才能停止。
最后,整个语句在输入界面没有任何提示,不便于外人使用。
以下程序供参考。
程序代码:
#
include<stdio.h>
int main()
{
    int n,a[100]={0},i,s,j,t;
    printf("请输入过桥人数n:");
    scanf("%d",&n);
    if(n!=0)
    {
        s=0;
    printf("请分别输入n个人的过桥所需时间:\n");
        for(i=0;i<n;i++)
        scanf("%d",&a[i]);
        for(i=0;i<n;i++)
        {
            for(j=1+i;j<n;j++)
            if(a[j]<a[i])
            {
                t=a[i];
                a[i]=a[j];
                a[j]=t;
            }
        }
        for(i=n-1;i>0;i--)
        s=s+a[i];
        s=s+(n-2)*a[0];
        printf("共需用时%d分钟。\n",s);    
    }
    else printf("输入错误。\n");
}

之前有点小错误, for(i=n-1;i>0;i--)里面i要大于0,不能等于0。

[ 本帖最后由 luchar 于 2011-11-8 10:23 编辑 ]
2011-11-08 09:53
maxam0128
Rank: 2
等 级:论坛游民
帖 子:37
专家分:10
注 册:2011-10-9
收藏
得分:0 
回复 2楼 luchar
你的算法明显不对,不信你可以测试一下你的算法和我的算法用的总时间...
2011-11-08 10:06
laoyang103
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:内蒙古包头
等 级:贵宾
威 望:19
帖 子:3082
专家分:11056
注 册:2010-5-22
收藏
得分:0 
三个人过河 时间分别为1 2 3 你的程序输出了7 应该是1和2过为2 1再回来 为3  然后1和3过3 1不会来为0

总共用时应该为6
程序代码:
#include<stdio.h>
int main()
{
    int n,a[100]={0},i,s,j,t;
    printf("请输入过桥人数n:");
    scanf("%d",&n);
    if(n!=0)
    {
        s=0;
    printf("请分别输入n个人的过桥所需时间:\n");
        for(i=0;i<n;i++)
        scanf("%d",&a[i]);
        if(1 == n)
        {
            printf("共需用时%d分钟。\n",a[0]);  
            return 0;
        }
        for(i=0;i<n;i++)
        {
            for(j=1+i;j<n;j++)
            if(a[j]<a[i])
            {
                t=a[i];
                a[i]=a[j];
                a[j]=t;
            }
        }
        for(i=1;i<n-1;i++)
            s+=a[i]+a[0];
        s+=a[i];
        printf("共需用时%d分钟。\n",s);   
    }
    else printf("输入错误。\n");
} 


[ 本帖最后由 laoyang103 于 2011-11-8 14:55 编辑 ]

                                         
===========深入<----------------->浅出============
2011-11-08 10:08
luchar
Rank: 9Rank: 9Rank: 9
来 自:南京
等 级:蜘蛛侠
帖 子:279
专家分:1263
注 册:2011-11-3
收藏
得分:0 
回复 4楼 laoyang103
只有一个手电筒,
是1和2或3过去,还要把手电筒送回来,1回来,再和剩下的那个过去

[ 本帖最后由 luchar 于 2011-11-8 10:24 编辑 ]
2011-11-08 10:20
yuccn
Rank: 16Rank: 16Rank: 16Rank: 16
来 自:何方
等 级:版主
威 望:167
帖 子:6815
专家分:42393
注 册:2010-12-16
收藏
得分:0 
回复 2楼 luchar

首先,你的算法不对。有n个人过桥,所需时间最短为除了用时最短的人以外的n-1个人的用时之和,加上用时最短人的时间×(n-2);


就这句话就已经说明你的算法错了。

给你一个面试的题目:

有一家人,晚上要过一个独木桥。但是他们只有一盏灯,而这盏灯只能使用30秒了。要在灯熄灭前过这座桥,他们一家五口人每个人过桥的速度不同。瘦人1秒,小胖3秒,姑娘6秒,大胖8秒,瘸子12秒。 每次只能过两个人。 过去后,对岸要有一个人再把灯送回来。


如果按照你的算法 是不是时间为 12 + 8 + 6 + 3 + 1 * (5 - 2) = 32?
其实这个最短时间是29

你可以通过这个游戏来验证:
http://www.

[ 本帖最后由 yuccn 于 2011-11-8 13:02 编辑 ]

我行我乐
公众号:逻辑客栈
我的博客:
https://blog.yuccn. net
2011-11-08 12:59
wuyijiang07
Rank: 3Rank: 3
等 级:论坛游侠
帖 子:74
专家分:177
注 册:2011-10-21
收藏
得分:0 
看了这么多,有没有人知道正确的算法
2011-11-08 13:22
maxam0128
Rank: 2
等 级:论坛游民
帖 子:37
专家分:10
注 册:2011-10-9
收藏
得分:0 
回复 4楼 laoyang103
我的时间是6,我是这样想得,先把n个人从小到大进行排序,然后,a0,a1过去,a0回来,然后an-1,an-2过去,a1回来,接下来依次类推...
2011-11-08 14:03
maxam0128
Rank: 2
等 级:论坛游民
帖 子:37
专家分:10
注 册:2011-10-9
收藏
得分:0 
回复 6楼 yuccn
你的数字和我的题目的例子是一样的说,他是这样算的,3+1+12+3+3+1+6=29,我的算法跟这差不多...
2011-11-08 14:07
yuccn
Rank: 16Rank: 16Rank: 16Rank: 16
来 自:何方
等 级:版主
威 望:167
帖 子:6815
专家分:42393
注 册:2010-12-16
收藏
得分:0 
回复 9楼 maxam0128
呵呵,如果你的算法算的是29 ,那说明你的算法是对的

我没有测试。^_^

我行我乐
公众号:逻辑客栈
我的博客:
https://blog.yuccn. net
2011-11-08 14:23
快速回复:过桥问题..
数据加载中...
 
   



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

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