▲▲海盗分金币问题▲▲继续求解？

回复人： qiushuiwuhen(秋水无恨) ( ) 信誉：155  2003-1-13 18:07:56  得分:0 
 
 
  
<script>
function t(r,d){
var s,a=[d],b=true,c,f;
for(i=1;i<r;i++){
s=a.concat();
c=i-s.length;
if(b)s[i-1]=0;
b=false;f=0;
for(j=0;j<s.length-1;j++){
if(s[j]==0&&f<d){
s[j]=1;c++;f++;
}else{
s[j]=0;
}
}

if(2*(c+1)>i){
b=true;
s[i]=d-f;
a=s.concat();
document.write(i+1 , "=" , a ,"<br/>");
}
}
if(b)
return a;
else
return null;
}
alert(t(500,100))
</script>  
 

解决方案 »

  1.   

    回复人： llrock(百乐宝||昨夜星辰) ( ) 信誉：100  2003-1-15 17:16:20  得分:0 
     
     
      
    我没有考虑为了活命不要金币投票的人，这下子好了，改了一些地方，速度提高了，并且得出了正确答案。================================================================
    <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
    <HTML>
    <HEAD>
    <TITLE> New Document </TITLE>
    <META NAME="Generator" CONTENT="EditPlus">
    <META NAME="Author" CONTENT="">
    <META NAME="Keywords" CONTENT="">
    <META NAME="Description" CONTENT="">
    </HEAD><BODY>
    计算主进度：<BR><BR>
    显示进度：<BR><BR>
    <BR>
    海盗数<input ID=Pirate_Count value=500>
    金币数<input ID=Gold_Count value=100>
    表决通过率大于<input ID=Pass_Percent value="49.9999" >(对于等于50，使用49.9...，)
    <input type=button value="计算" onclick="Start()">(计算时间与海盗数有关)
    <HR>
    <BR>
    <span ID=stater>...</span>
    <table ID=test style="border:1px solid black;width:100%">
      <tr>
        <td ID=col1 bgcolor="f1f1f1" width=33% valign="top"></td>
        <td  ID=col2 bgcolor="d1d1d1" width=33% valign="top"></td>
        <td  ID=col3 bgcolor="b1b1b1" width=34% valign="top"></td>
      </tr>
    </table>
    <BR>结论：实力和机遇的化身继承财富!<SCRIPT LANGUAGE="JavaScript">
    <!--
    var PirateCount;   //海盗人数 
    var GoldCount;     //金币数
    var PassPercent;   //投票通过率var Pirate;        //海盗数组var PID;           //海盗ID，临时变量
    var DispStr="";    //结果字符串，临时变量function Start(){
       //初始化条件
       if(isNaN(Pirate_Count.value))return alert("请输入数字")
       else PirateCount=Pirate_Count.value;
       if(isNaN(Gold_Count.value))return alert("请输入数字")
       else GoldCount=Gold_Count.value;
       if(Pass_Percent.value>=100||Pass_Percent.value<0||isNaN(Pass_Percent.value)||Pass_Percent.value=="")return alert("请输入0-100的数字")
       else PassPercent=Pass_Percent.value/100;
       
       //创建海盗对象集合，为了方便从1开始
       Pirate=new Array();
       for(i=1;i<=PirateCount;++i)
           Pirate[i]=new TPirate(i);   var num=Math.floor(1/(1-PassPercent))+1
       PID=(PirateCount-num+1);   //初始化进度条
       PB1.Reposition();
       PB2.Reposition();
       PB1.max=PID;
       document.all.stater.innerHTML="正在计算，请稍等...";
       document.all.col1.innerHTML="";
       document.all.col2.innerHTML="";
       document.all.col3.innerHTML="";
       DispStr="";
       Caculate();
    }
    //-----------------------------------------------------------------
    //打印结果
    function OutPut()
    {
       if(PID>PirateCount)
       {
          stater.innerHTML="海盗数："+PirateCount+"| 金币数："+GoldCount+"| 通过率 > "+(PassPercent*100)+"%<BR>";
          return 0;
       }
       //格式输出
       var colcount=Math.ceil(PirateCount/3);
       var str="[Pirate"+Pirate[PID].ID+"]&nbsp;&nbsp;:&nbsp;&nbsp;"
                    +(Pirate[PID].Death?"被投进大海喂鱼了!":Pirate[PID].Gold)+"<BR>";
       if(PID<=colcount)document.all.col1.innerHTML+=str;
       else if(PID>(2*colcount)) document.all.col3.innerHTML+=str;
       else document.all.col2.innerHTML+=str;   PID++;
       PB2.pos++;
       PB2.Update();
       setTimeout("OutPut()",5);
    }
    //-----------------------------------------------------------------
    //从后向前探测
    function Caculate()
    {
       var TreatResult=new Array();   //1、从下一个海盗开始依次听取他们的要求(只是先听听他们上次分得结果)
       for(VisitedID=PID+1;VisitedID<=PirateCount;VisitedID++)
       {   
           //记录被访问过的人ID，此时先不和他们磋商，为了方便放到分配时
       TreatResult.push(VisitedID);
            //每访问一个人就进行一次排序，在这里排序可减少次数
    //根据金币数从小到大排序，相等根据ID序号排序，
       var tmpind=TreatResult.length-1;
           while(tmpind>0&&Pirate[TreatResult[tmpind]].Gold<Pirate[TreatResult[tmpind-1]].Gold)
       {
     var tmp=TreatResult[tmpind];
     TreatResult[tmpind]=TreatResult[tmpind-1];
     TreatResult[tmpind-1]=tmp;
     tmpind--;
    }
    }
       //2、按照TreatResult的顺序分配并获得选票
       Pirate[PID].Allot(TreatResult);
       //3、探测下一个海盗得分配方案,更新进度条
       PID--;
       PB1.pos++;
       PB1.Update();
       //4、知道编号为1的海盗分配结束后，输出结果;否则继续计算
       //为了避免深度的循环嵌套导致浏览器崩溃，使用settimeout，如果可以使用线程盖有多好!
       if(PID<1)
       {   
       PID=1;//PID置为零为输出结果做准备
           PB2.max=PirateCount;
       document.all.stater.innerHTML="计算结束，正在显示，请稍等...";
       PB1.pos=PB1.max;
           PB1.Update();
       OutPut();
       }
       else
       {
          setTimeout("Caculate()",5)
       }   return 0;
    }//------------------------------------------------------------
    //                       海盗类
    //------------------------------------------------------------
    function TPirate(ID)
    {
       this.ID=ID;   //编号从1开始
       this.Gold=0;  //得到的金币数
       this.Death=0; //0:必然死不了，有权利多要金币。1：有可能死，不会要金币就投票
       var count=PirateCount-ID+1;//包括自己在内或者的人数   this.NeedBallot=Math.floor(count*PassPercent);//需要获得的票数，不包括自己投自己的一票
       this.Allot=TPirate_Allot;
       this.Treat=TPirate_Treat;
    }
    //-----------------------------------------------------------------
    //当提议者开始分配时提出自己的要求
    function TPirate_Treat()
    {
       if(this.Death)
       {//如果我有可能死
          this.Gold=0;//只要我免费投当前人一票，他就可以不死
      this.Death=0;//因此我可以不死了
       }
       else
       {//我肯定不死，所以我得多要1块
          this.Gold++;
       }
       return this.Gold;
    }
    //-----------------------------------------------------------------
    //根据别人的要求分配金币
    function TPirate_Allot(TreatResult)
    {
       //1、首先假设可以得到足够选票，测试sumgold的符号判断自己是否可以过关
       var sumgold=GoldCount;
       var ballot=this.NeedBallot;
       var gold,p;
       var ind=0;
       while(ballot>0&&ind<TreatResult.length)
       {//强制测试
           p=Pirate[TreatResult[ind]];
           gold=p.Gold;
       if(!p.Death)gold++;//如果这个人没有可能死，他的要求加1
       sumgold-=gold;
       ballot--;
       ind++;
       }
       //2、根据测试结果进行真实分配
       if(sumgold>=0)
       {//测试结果：通过。按照他们的要求分配  
          this.Gold=GoldCount;
          for(i=0;i<TreatResult.length;++i)
      {
         p=Pirate[TreatResult[i]];
     //海盗开始磋商
     p.Treat();      if(this.NeedBallot>0)
     {//选票不够就买一张
                this.Gold-=p.Gold;
    this.NeedBallot--;
     }
     else
     {//选票够了，就不分给下面的人
        p.Gold=0;
     }
      }
       }
       else
       {//测试结果：死。打进死牢先
          this.Death=1;
      this.Gold=0;
       }
       return 1;
    }
    //-->
    </SCRIPT>
    <!-- ---------------------------以下为进度条----------------------------------- -->
    <SCRIPT LANGUAGE="JavaScript">
    <!--ProgressBar 1.0 llrock.myrice.com
     function TProgressBar(idstr,x,y,w,h,c,bgc,max,min)
     {
       if(!idstr)return alert("I wanna a Name!");
       else this.idstr=idstr;
       this.obj=null;
       this.min=min||0;
       this.max=max||100;
       this.x=x||100;
       this.y=y||100;
       this.width=w||204;
       this.height=h||24;
       this.color=c||"#FF6600";
       this.bgcolor=bgc||"#E1E1E1";
       this.pos=0;
       this.percent=0;
       this.Create=TProgressBar_Create;
       this.Update=TProgressBar_Update;
       this.Reposition=TProgressBar_Reposition;
     }
     function TProgressBar_Update()
     {
        
        this.percent=Math.floor(this.pos/this.max*100);
    if(isNaN(this.percent))this.percent=100;//
    if(this.percent>=100)
    {
      this.percent=100;
      this.obj.width=this.width-4;
    }
    else
    {
          this.obj.width=Math.floor(this.pos/this.max*(this.width-4));
    }
    this.counter.innerHTML=String(this.percent)+"%";  
        
     }
     function TProgressBar_Create()
     {
        var str="";
    str+='<div id="'+this.idstr+'_border" style="position:absolute; left:'+this.x+'px; top:'+this.y+'px; width:'+this.width+'px; height:'+this.height+'px; z-index:1; background-color: #000000;">';
        str+='<div id="'+this.idstr+'_bg" style="position:absolute; left:1px;top:1px;width:'+(this.width-2)+'px; height:'+(this.height-2)+'px; z-index:2; background-color: '+this.bgcolor+';">';
             str+='<div id="'+this.idstr+'_main" style="position:absolute; left:1px; top:1px; width:1p
      

  2.   

    px"></div>';
             str+='<div id="'+this.idstr+'_counter" style="position:absolute;width:10px;height:'+(this.height-4)+'px;left:'+(this.width/2-10)+'px;top:1px;z-index:3">0%</div>';
    str+='</div></div>';
    document.write(str);
    this.obj=document.all[this.idstr+"_main"].style;
    this.counter=document.all[this.idstr+"_counter"];
     }
     function TProgressBar_Reposition()
     {
        this.pos=0;
    //this.max=100;
    this.Update();
     }
     var PB1=new TProgressBar("myPB1",100,5)
     PB1.Create()
     var PB2=new TProgressBar("myPB2",100,40,null,null,"#99FF00")
     PB2.Create()
    //-->
    </SCRIPT>
    </BODY>
    </HTML>