新书推介：《语义网技术体系》
作者：瞿裕忠，胡伟，程龚
   XML论坛     W3CHINA.ORG讨论区     >>计算机科学论坛<<     SOAChina论坛     Blog     开放翻译计划     新浪微博  
 
  • 首页
  • 登录
  • 注册
  • 软件下载
  • 资料下载
  • 核心成员
  • 帮助
    		•   Add to Google

    >> 研友的交流园地，讨论关于计算机考研的方方面面。
    [返回] 计算机科学论坛 → 计算机理论与工程 → 『 计算机考研交流 』 → [求助]一道PV原语的题目求解？吸烟者问题或者说是酒吧听音乐问题 ◇查看新帖 ◇ 用户列表 ◇

      发表一个新主题  发表一个新投票  回复主题  (订阅本版) 您是本帖的第 10292 个阅读者浏览上一篇主题  刷新本主题   树形显示贴子　浏览下一篇主题
     * 贴子主题： [求助]一道PV原语的题目求解？吸烟者问题或者说是酒吧听音乐问题 举报  打印  推荐  IE收藏夹 
       本主题类别:     
     kidd 美女呀，离线，快来找我吧！
      
      
      等级：大一新生
      文章：4
      积分：66
      门派：XML.ORG.CN
      注册：2006/11/8

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给kidd发送一个短消息 把kidd加入好友 查看kidd的个人资料 搜索kidd在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看kidd的博客楼主
    发贴心情 [求助]一道PV原语的题目求解？吸烟者问题或者说是酒吧听音乐问题

    吸烟者问题（Patil, 1971)
    
    三个吸烟者在一间房间内，还有一个香烟供应者。为了制造并抽掉香烟，每个吸烟者需要三样东西：烟草、纸和火柴。供应者有丰富的货物提供。三个吸烟者中，第一个有自己的烟草，第二个有自己的纸，第三个有自己的火柴。供应者将两样东西放在桌子上，允许一个吸烟者进行对健康不利的吸烟。当吸烟者完成吸烟后唤醒供应者，供应者再放两样东西（随机地）在桌面上，然后唤醒另一个吸烟者。试为吸烟者和供应者编写程序解决问题。
    
    这个和酒吧的问题是一样的，但是这道题到底应该怎么解啊～～～

       收藏   分享  
    顶(0)
      




    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/11/8 22:48:00
     
     ychj 帅哥哟，离线，有人找我吗？
      
      
      等级：大二期末(C++考了100分!)
      文章：58
      积分：440
      门派：XML.ORG.CN
      注册：2006/8/9

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给ychj发送一个短消息 把ychj加入好友 查看ychj的个人资料 搜索ychj在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看ychj的博客第2楼
    发贴心情 
    这跟酒吧那个问题有点不一样。
    我们已经讨论过酒吧的问题了。只是当时帖子上的那个算法，有点小问题：即如果爱好者队列是有限队列，则可能导致死锁。
    你这个问题由于三个吸烟者不断的吸，可以完全参照那个算法。
    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/11/9 1:27:00
     
     kidd 美女呀，离线，快来找我吧！
      
      
      等级：大一新生
      文章：4
      积分：66
      门派：XML.ORG.CN
      注册：2006/11/8

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给kidd发送一个短消息 把kidd加入好友 查看kidd的个人资料 搜索kidd在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看kidd的博客第3楼
    发贴心情 
    这是引用那个讨论音乐问题的贴子有一位朋友提供的答案。
    parbegin (表示方法各书不同,大致差不多)
    p1: begin
          repeat
            p(b1)
            p(m1)
            b=b-1
            c=c-1
    v(m1)
    listening
    v(s)
    until......
    end:
    p2:begin
    repeat
    p(b2)
    p(m2)
    a=a-1
    c=c-1
    v(m2)
    listeing......
    v(s)
    until.....
    end;
    p3(和p1p2差不多,就不写了)
    老板p4:begin
    repeat parbegin
    begin
    p(s)
    p(m1)
    b=b+1
    c=c+1
    v(m1)
    v(b1)
    end
    begin...(下面还有两个分支和这个一样,不过是分别ac和ab加一,然后v相应的信号量)


    [此贴子已经被作者于2006-11-15 19:12:54编辑过]
    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/11/9 21:39:00
     
     kidd 美女呀，离线，快来找我吧！
      
      
      等级：大一新生
      文章：4
      积分：66
      门派：XML.ORG.CN
      注册：2006/11/8

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给kidd发送一个短消息 把kidd加入好友 查看kidd的个人资料 搜索kidd在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看kidd的博客第4楼
    发贴心情 
    求救啊～～～
    可不可以有简单一点的啊？
    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/11/15 19:25:00
     
     Supremgoooo 帅哥哟，离线，有人找我吗？
      
      
      等级：大四下学期(考上研究生啦!)
      文章：201
      积分：1872
      门派：XML.ORG.CN
      注册：2006/4/9

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给Supremgoooo发送一个短消息 把Supremgoooo加入好友 查看Supremgoooo的个人资料 搜索Supremgoooo在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看Supremgoooo的博客第5楼
    发贴心情 
    你写的真和天书一样。。。。

    这个题前面有帖子已经讨论过，carroty给的算法完全正确，你去看下吧。

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/11/16 17:37:00
     
     runningwulf 帅哥哟，离线，有人找我吗？
      
      
      等级：大一(高数修炼中)
      文章：33
      积分：201
      门派：XML.ORG.CN
      注册：2006/5/20

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给runningwulf发送一个短消息 把runningwulf加入好友 查看runningwulf的个人资料 搜索runningwulf在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看runningwulf的博客第6楼
    发贴心情 
    carroty的帖子找了半天也没有找到，惭愧啊。。。。。
    这里是我写的关于这个问题的解答，请大牛们过目评判一下吧！我觉得我写的是不适太简单了，可是又察觉不出哪里有问题。

    分析思想：
    1） 供应者seller随即产生两样东西，提供它们，这里用普通变量来表示
    2） 吸烟者进程smoker根据其排号不同，拥有不同的一件东西。假设1号吸烟者拥有烟草tobacco，2号吸烟者拥有纸paper，3号吸烟者拥有火柴match。其他号码错误返回。
    3） 吸烟者的序号代表他们拥有的东西，用他们的序号和供应者产生的两样东西比较，如果都不相等，则说明他拥有的东西和供应者产生的东西匹配，它可以吸烟。如果其中一个相等，则推出，继续排队。
    4） mutex信息量代表一个只能进入的门，每次只有一个吸烟者可以进入进行比较和吸烟。
    5） 每个吸烟者在吸烟完毕之后出门之前要叫醒供应者，调用seller进程。

    信息量：
    mutex:=1 ——互斥信息量，表示吸烟者进入的门

    解法：
    #typedef int semaphore
    semaphore mutex=1;
    int thing1,thing2;

    void seller(){
     Randomize;
     int i = random(2);  //产生0-2的随机数
     thing1 = ((i-1)%3)+1; //将thing赋值为0-2种不等于i的两个数+1
     thing2 = ((i+1)%3)+1; 
    }
    void smoker(int i){
     if((i<=0)||(i>3))  //i值应为1-3
      return false;
     while(true){
      P(mutex)
      if((i!=thing1)&&(i!=thing2)){ //所拥有的物品与供应者放出的物品不一样
       吸烟;
       seller();   //唤醒供应者
       V(mutex);
      }
      else{
       V(mutex)
      }//end if
     }//end while
    }

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/12/2 10:27:00
     
     lalala 帅哥哟，离线，有人找我吗？
      
      
      等级：大一新生
      文章：1
      积分：61
      门派：XML.ORG.CN
      注册：2006/9/12

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给lalala发送一个短消息 把lalala加入好友 查看lalala的个人资料 搜索lalala在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看lalala的博客第7楼
    发贴心情 
    [color=#FF0033]
    以下是引用runningwulf在2006-12-2 10:27:00的发言：
    carroty的帖子找了半天也没有找到，惭愧啊。。。。。
    这里是我写的关于这个问题的解答，请大牛们过目评判一下吧！我觉得我写的是不适太简单了，可是又察觉不出哪里有问题。

    分析思想：
    1） 供应者seller随即产生两样东西，提供它们，这里用普通变量来表示
    2） 吸烟者进程smoker根据其排号不同，拥有不同的一件东西。假设1号吸烟者拥有烟草tobacco，2号吸烟者拥有纸paper，3号吸烟者拥有火柴match。其他号码错误返回。
    3） 吸烟者的序号代表他们拥有的东西，用他们的序号和供应者产生的两样东西比较，如果都不相等，则说明他拥有的东西和供应者产生的东西匹配，它可以吸烟。如果其中一个相等，则推出，继续排队。
    4） mutex信息量代表一个只能进入的门，每次只有一个吸烟者可以进入进行比较和吸烟。
    5） 每个吸烟者在吸烟完毕之后出门之前要叫醒供应者，调用seller进程。

    信息量：
    smoke:=0 ——互斥信息量，表示卖烟者已准备好卖烟
    解法：
    #typedef int semaphore
    semaphore smoke=0, next=0;
    int thing1,thing2;

    void seller(){
      while(true){
        Randomize;
        int i = random(2);  //产生0-2的随机数
        thing1 = ((i-1)%3)+1; //将thing赋值为0-2种不等于i的两个数+1
        thing2 = ((i+1)%3)+1;
        v(smoke);  //准备好卖
        p(next);    //能否进行下一次卖烟
      }
    }
    void smoker(int i){
      if((i<=0)||(i>3))  //i值应为1-3
       return false;
      while(true){
       p(smoke);     //有烟可吸？
       if((i!=thing1)&&(i!=thing2)){ //所拥有的物品与供应者放出的物品不一样
        吸烟;
        v(next); //唤醒供应者进行下一次卖烟
       }
       else{
        V(smoke);
       }//end if
      }//end while
    }


    [/color]
    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/12/5 16:04:00
     
     GoogleAdSense
      
      
      等级：大一新生
      文章：1
      积分：50
      门派：无门无派
      院校：未填写
      注册：2007-01-01
    给Google AdSense发送一个短消息 把Google AdSense加入好友 查看Google AdSense的个人资料 搜索Google AdSense在『 计算机考研交流 』 的所有贴子 访问Google AdSense的主页 引用回复这个贴子 回复这个贴子 查看Google AdSense的博客广告
    2024/5/2 22:20:04

    本主题贴数7，分页： [1]

    管理选项： 修改tag | 锁定 | 解锁 | 提升 | 删除 | 移动 | 固顶 | 总固顶 | 奖励 | 惩罚 | 发布公告
    W3C Contributing Supporter! W 3 C h i n a ( since 2003 ) 旗 下 站 点
    苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》
    		 5,421.875ms