大赛评选结果已出，敬请关注！：PHP编程大赛隆重启动，PHP开发大挑战

renxiao2003

2：用二分法在一个数组中查找你所需元素

1. <?php
   
2.         //二分法
   
3.         function binarySearch($a, $val){
   
4.                 $low = 0;
   
5.                 $high= count($a) - 1;
   
6.                 while($low <= $high){
   
7.                         $mid = intval(($low+$high)/2);
   
8.                         if($a[$mid] == $val) return $mid; //找到相等的就返回所在的位置
   
9.                         if($a[$mid] > $val){  //要查找的在前半截
   
10.                                 $high = $mid - 1;
    
11.                         }else{
    
12.                                 $low = $mid + 1;  //要查找的在后半截
    
13.                         }
    
14.                 }
    
15.                 return -1;
    
16.         }
    
17.         //测试
    
18.     $arr=array(1,3,6,8,10);
    
19.     echo binarySearch($arr,3); //数组从0开始，故返回值是1
    
20. ?>

复制代码

renxiao2003

1：要求在一组数中，插入一个新数，并维护原来的排序方式不变

1. <?php
   
2.     function insertArr($arr,$val){
   
3.             $pos=0;
   
4.             if (sizeof($arr)==0) return array($val); //传入数组没有值
   
5.             if (sizeof($arr)==1){ //传入数组个数为1
   
6.                     return array($val,$arr[0]);
   
7.             }
   
8.             $bfind=false;
   
9.             if ($arr[0]>$arr[sizeof($arr) - 1]){
   
10.                     $bfind=true; //从大到小排序
    
11.             }else{
    
12.                     $bfind=false;//从小到大排序
    
13.             }
    
14.             for($i=0;$i<sizeof($arr);$i++){ //找到要插入值应该插入的位置。
    
15.                     if ($bfind){
    
16.                             if ($arr[$i]<$val){
    
17.                                     $pos=$i;
    
18.                                     break;
    
19.                             }
    
20.                     }else{
    
21.                             if ($arr[$i]>$val){
    
22.                                     $pos=$i;
    
23.                                     break;
    
24.                             }
    
25.                     }
    
26.             }
    
27.             $left_arr=array();
    
28.             $right_arr=array();
    
29.             for ($i=0;$i<sizeof($arr);$i++){ //根据要插入的值把数组分左右两部分。
    
30.                     if ($i<$pos){
    
31.                             $left_arr[]=$arr[$i];
    
32.                     }else{
    
33.                             $right_arr[]=$arr[$i];
    
34.                     }
    
35.             }
    
36.             return array_merge($left_arr,array($val),$right_arr);
    
37.     }
    
38.     //测试
    
39.     $arr=array();
    
40.     print_r(insertArr($arr,10));echo "<br>";
    
41.     $arr=array(1);
    
42.     print_r(insertArr($arr,10));echo "<br>";
    
43.     $arr=array(1,3,8,12,13,15);
    
44.     print_r(insertArr($arr,10));echo "<br>";
    
45.     $arr=array(31,23,18,12,11,1);
    
46.     print_r(insertArr($arr,10));echo "<br>";
    
47. ?>

复制代码

renxiao2003

33、写一个函数，算出两个文件的相对路径
　　如 $a = '/a/b/c/d/e.php';
　　$b = '/a/b/12/34/c.php';
计算出 $b 相对于 $a 的相对路径应该是 ../../c/d将()添上

1. <?php
   
2. $a = '/c/d/d/e.php';
   
3. $b = '/a/c/d/e.php';
   
4. $aArr = explode('/',dirname($a));
   
5. $bArr = explode('/',dirname($b));
   
6. $aLen = count($aArr);
   
7. $bLen = count($bArr);
   
8. $maxLen = max($aLen,$bLen);
   
9. for($i = 1; $i < $maxLen; $i++){
   
10.     if($aArr[$i] != $bArr[$i] && isset($aArr[$i])){
    
11.         if(isset($bArr[$i]))$bUrl[]=$bArr[$i];
    
12.         $relativePath .= "../";
    
13.     }else{
    
14.         $bUrl[]=$bArr[$i];
    
15.     }
    
16. }
    
17. echo $relativePath.implode('/',$bUrl).'/'.basename($b);
    
18. ?>
    

复制代码

renxiao2003

回复 106# dz902


    php关于数组sort函数和rsort函数，还从来没有用过。所以我写的方法就太笨措了。呵呵。

renxiao2003

回复 125# fansekey


    谢谢啊。有些函数我没有用过。谢谢指教。

renxiao2003

回复 110# starzhestarzhe


    有些不一定非得in、out吧。

renxiao2003

回复 146# starzhestarzhe


    最近这几天都没有答题。明天开始再做。

renxiao2003

5：写一个二维数组排序函数，能够具有通用性

1. 
   
2. /**
   
3. * 参数1 array 待排序的苏组
   
4. * 参数2 string 第一项排序关键字
   
5. * 参数3 string 排序方法，升序还是降序("SORT_ASC"|"SORT_DESC")  
   
6. * 参数4 string 排序类型，值有("SORT_REGULAR"|"SORT_NUMERIC"|"SORT_STRING")  
   
7. * 返回值 array   排序后的数组  
   
8. */
   
9. function MultiArraySort($ArrayData,$KeyName1,$SortOrder1 = "SORT_ASC",$SortType1 = "SORT_REGULAR")   
   
10. {   
    
11.   if(!is_array($ArrayData))   
    
12.   {   
    
13.       return $ArrayData;   
    
14.   }   
    
15.   // Get args number.   
    
16.   $ArgCount = func_num_args();   
    
17.   // Get keys to sort by and put them to SortRule array.   
    
18.   for($I = 1;$I < $ArgCount;$I ++)   
    
19.   {   
    
20.       $Arg = func_get_arg($I);   
    
21.       if(!eregi("SORT",$Arg))   
    
22.       {   
    
23.           $KeyNameList[] = $Arg;   
    
24.           $SortRule[]    = '$'.$Arg;   
    
25.       }   
    
26.       else  
    
27.       {   
    
28.           $SortRule[]    = $Arg;   
    
29.       }   
    
30.   }   
    
31.   // Get the values according to the keys and put them to array.   
    
32.   foreach($ArrayData AS $Key => $Info)   
    
33.   {   
    
34.       foreach($KeyNameList AS $KeyName)   
    
35.       {   
    
36.           ${$KeyName}[$Key] = $Info[$KeyName];   
    
37.       }   
    
38.   }   
    
39.   // Create the eval string and eval it.   
    
40.   $EvalString = 'array_multisort('.join(",",$SortRule).',$ArrayData);';   
    
41.   eval ($EvalString);   
    
42.   return $ArrayData;   
    
43. }  

复制代码

renxiao2003

7：设有n 种物品，每种物品有一个重量及一个价值。但每种物品的数量是无限的，同时有一个背包，最大载重量为M，今从n 种物品中选取若干件(同一种物品可以多次选取)，使其重量的和小于等于M，而价值的和为最大。

1. <?php
   
2. /*
   
3. 设有n 种物品，每种物品有一个重量及一个价值。但每种物品的数量是无限的，同时有一个背包，最大载重量为M，今从n 种物品中选取若干件(同一种物品可以多次选取)，使其重量的和小于等于M，而价值的和为最大。
   
4. Input
   
5. 第一行：两个整数，M(背包容量，M<= 200)和N(物品数量，N<= 30)； 第2..N+1 行：每行二个整数Wi,Ui，表示每个物品的重量和价值。
   
6. Output
   
7. 仅一行，一个数，表示最大总价值。
   
8. Sample Input
   
9. 12 4
   
10. 2  1
    
11. 3  3
    
12. 4  5
    
13. 7  9
    
14. Sample Output
    
15. 15
    
16. */
    
17. set_time_limit(30);
    
18. define(’NOWTIME’,time());
    
19. function microtime_float()
    
20. {
    
21.     list($usec, $sec) = explode(” “, microtime());
    
22. $sec=$sec-NOWTIME;
    
23.     return ((float)$usec + (float)$sec);
    
24. }
    
25. //初始化数组
    
26. /*
    
27. $bbw=12;
    
28. $arywp=array();
    
29. $arywp[]=array(’d',2,1);
    
30. $arywp[]=array(’c',3,3);
    
31. $arywp[]=array(’b',4,5);
    
32. $arywp[]=array(’a',7,9);
    
33. */
    
34. $time_start = microtime_float();
    
35. //开始计算
    
36. $wpnum=count($arywp);
    
37. $wpnum=20; //允许的物品类型数量
    
38. $bbw=rand(5*$wpnum,50*$wpnum); //背包允许最大重量
    
39. for($i1=0;$i1<$wpnum;$i1++){ //初始化每个物品类型的重量和价值
    
40. $arywp[$i1][0]=”w”.$i1; //名称
    
41. $arywp[$i1][1]=rand(50,80); //重量
    
42. $arywp[$i1][2]=rand(20,50); //价值
    
43. $arywp[$i1][3]=$arywp[$i1][2]/$arywp[$i1][1];//单位重量的最大价值
    
44. }
    
45. function cmp($a, $b){
    
46. $returnvalue=0;
    
47.     if ($a[3] == $b[3]) {
    
48.   $returnvalue=  0;
    
49.     } else {
    
50.      $returnvalue = ($a[3] > $b[3]) ? -1 : 1;
    
51. }
    
52. return $returnvalue;
    
53. }
    
54. //按单位最大价值排序
    
55. usort($arywp, “cmp”);
    
56. print_r($arywp);
    
57. echo ” <br />\n”;
    
58. //递归函数，计算剩余空间的允许物品最大价值
    
59. function getmaxval($bbw,$arywp){
    
60. //最大单位物品的重量、价值、数量
    
61. $use_w=0;
    
62. $use_v=0;
    
63. $ary_userwp=array();
    
64. //当前空间的允许物品最大价值
    
65. $maxwgt=0;
    
66. $maxval=0;
    
67. $maxuserwp=array();
    
68. 
    
69. $wp = array_shift($arywp);
    
70. $num= floor(($bbw-$use_w)/$wp[1]); //最大单位物品的最大允许个数
    
71. //echo ” countmax : $num * “.$wp[0].”<br/>\n”;
    
72. if(count($arywp)==0 || $bbw-$use_w==$wp[1]*$num){ //没有剩余物品或刚好填满 //递归结束条件
    
73.   if($num>0){
    
74.    $maxwgt+=$wp[1]*$num;
    
75.    $maxval+=$wp[2]*$num;
    
76.    $maxuserwp[$wp[0]]=$num;
    
77.   }
    
78. } else {
    
79.   for($i=0;$i<=$num;$i++){ //计算最大单位物品不同数量时的最大价值
    
80.    $use_w=$wp[1]*$i;
    
81.    $use_v=$wp[2]*$i;
    
82.    $ary_userwp[$wp[0]]=$i;
    
83.    if(($num-$i)*$wp[2]/($bbw-$use_w) < $arywp[0][3]){ //剩余空间的单位价值小于下件物品的单位价值
    
84.     list($subuse_w,$subuse_v,$subusewp)=getmaxval($bbw-$use_w,$arywp);
    
85.    } else {
    
86.     $subuse_w=0;
    
87.     $subuse_v=0;
    
88.     $subusewp=array();
    
89.    }
    
90.    if($use_v+$subuse_v>$maxval || $maxval==0){ //比较最大价值
    
91.     $maxwgt=$use_w+$subuse_w;
    
92.     $maxval=$use_v+$subuse_v;
    
93.     if($i>0){
    
94.      $maxuserwp=array_merge($ary_userwp,$subusewp);
    
95.     } else{
    
96.      $maxuserwp=$subusewp;
    
97.     }
    
98.    }
    
99.   }
    
100.   //print_r($maxuserwp);
     
101.   //echo ” maxwgt : $maxwgt  maxval : $maxval<br/>\n”;
     
102. }
     
103. //返回 使用的重量，最大价值、使用的物品数量数组
     
104. return array($maxwgt,$maxval, $maxuserwp);
     
105. }
     
106. //开始计算
     
107. $arysulte= getmaxval($bbw,$arywp);
     
108. //输出结果
     
109. echo ” bbw “.$bbw.” “;
     
110. print_r($arysulte);
     
111. $time_end = microtime_float();
     
112. $runtime = $time_end – $time_start;
     
113. echo ” runtime : “.$runtime;
     
114. ?>
     

复制代码

renxiao2003

回复 160# 魔法鱼。


    谢谢！