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

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# 魔法鱼。


    谢谢！

renxiao2003

8：设随机抽到A的概率为0.1，B的概率为0.2，C的概率为0.3，D的概率为0.4，现在求按此概率随机抽出一个字母的算法，

1. <?php
   
2. /**
   
3. * 根据概率取随机数的算法（仅抽取1个）
   
4. * 用法：
   
5. * $proArr = array(10,20,30,40);
   
6. * $result = pro_rand($proArr);
   
7. * echo '你抽到的$proArr数组索引是'. $result. '，其预设概率数是'. $proArr[$result];
   
8. ** @param array $proArr 概率数组。格式为array('A'=>10, 'B'=>40, 'C'=>50)，或者array(10,40,50)。数组的每个键值（value）必须为大于1的整数；所有数组键值（value）加起来即为其总概率精度
   
9. * @return mixed $result 结果，将返回抽取到的概率数组索引值。
   
10. */
    
11. function pro_rand( $proArr ){
    
12.     $result = '';
    
13. 
    
14.     //概率数组的总概率精度
    
15.     $proSum = array_sum($proArr);
    
16.    
    
17.       foreach ( $proArr as $key => $proCur ){
    
18.         $randNum = mt_rand(1, $proSum);
    
19.         if( $randNum <= $proCur ){
    
20.             $result = $key;
    
21.             break;
    
22.         }else{
    
23.             $proSum -= $proCur;
    
24.         }
    
25.     }
    
26.    
    
27.     return $result;
    
28.    
    
29. }
    
30. 
    

复制代码

renxiao2003

15、 JS下有一个字符串var str = '1|2|3|4|5|6#1|2|3|4#1|2|3|4|5|6|7|8'; 请用“#”号将其分割为数组，再用“|”将其分割为2维数组。可以用例如ary[0][0]这样的各式取出数组中的每个元素。最后输出其中最长数组的编号(1,2,3这样的自然数)，这个数组中元素的个数。以及大数组中每个元素。如图：

1. <script language=javascript>
   
2. var str = '1|2|3|4|5|6#1|2|3|4#1|2|3|4|5|6|7|8';
   
3. var arr=str.split("#");  //分割一维数组
   
4. var arrtwo=new Array();
   
5. for(var i=0;i<arr.length;i++){
   
6.     arrtwo[i]=arr[i].split("|"); //分割二维数组。
   
7. }
   
8. var maxlength=arrtwo[0].length;
   
9. var maxarr=1;
   
10. //求二维数组最大长度和个数
    
11. for (var i=1;i<arrtwo.length;i++){
    
12.     if (maxlength < arrtwo[i].length){
    
13.         maxlength = arrtwo[i].length;
    
14.         maxarr=i+1;
    
15.     }
    
16. }
    
17. document.write("最长的二维数组是："+maxarr);
    
18. document.write("<br>长度为：" + maxlength);
    
19. //打印数组
    
20. for (var i=0;i<arrtwo.length;i++){
    
21.     document.write("<br>");
    
22.     for (var j = 0;j<arrtwo[i].length;j++){
    
23.         document.write(arrtwo[i][j]+",");
    
24.     }
    
25. }
    
26. </script>
    

复制代码

starzhestarzhe

三十四.用写一个类实现会员管理，要求实现：
1）用文件存储会员信息，会员注册输入用户名和电子邮件就行。   
2）用户信息包括：用户名，电子邮件。
3）要求用户可以登录、退出和注销用户。
4）如果用户没有退出，下次登录自动显示用户名。
5）保存用户上次浏览时间。

1. class User {
   
2.         private $error = null;  //出错信息
   
3.         const DATA_FILE = './data.file';  //用户数据文件
   
4.         const SEPARATOR = "\t";   //数据行分隔符
   
5.        
   
6.         public function __construct() {
   
7.                 if(!$this->getIsLogin()) {
   
8.                         if($_COOKIE['user']) { //用户没退出
   
9.                                 $cookie = @unserialize($_COOKIE['user']);
   
10.                                 if(isset($cookie['name']) && isset($cookie['email'])) {
    
11.                                         !$this->login($cookie['name'],$cookie['email']) && $this->logout();
    
12.                                 }
    
13.                         }
    
14.                 }
    
15.         }
    
16.         /**
    
17.          * 用户登陆
    
18.          * @param unknown_type $userName
    
19.          * @param unknown_type $email
    
20.          */
    
21.         public function login($userName,$email) {
    
22.                 if($this->getIsLogin()) {
    
23.                         return true;
    
24.                 }
    
25.                
    
26.                 $find = $this->getUser($userName,$email);//寻找某用户
    
27.                 if(!$find) {
    
28.                         $this->error = 'no user';
    
29.                         return false;
    
30.                 }
    
31.                 $lastView = $find['last_view'];
    
32.                 $content = file_get_contents(self::DATA_FILE);
    
33.                 //更新访问时间
    
34.                 file_put_contents(self::DATA_FILE,str_replace($userName.self::SEPARATOR.$email.self::SEPARATOR.$lastView,$userName.self::SEPARATOR.$email.self::SEPARATOR.time(),$content));
    
35.                 $lastView = $find['last_view'];
    
36.                 $cookie = array();
    
37.                 $cookie['user']['name'] = $_SESSION['user_name'] = $userName;//用session保存登陆用户信息
    
38.                 $cookie['user']['email'] = $_SESSION['email'] = $email;
    
39.                 $_SESSION['last_view'] = $lastView;
    
40.                 setcookie('user',@serialize($cookie),time()+14400);//生成cookie
    
41.                 return true;
    
42.         }
    
43.         /**
    
44.          * 用户注册
    
45.          * @param  $username
    
46.          * @param  $email
    
47.          */
    
48.         public function register($username,$email) {
    
49.                 $this->format($username,$email);
    
50.                 if(!$username || !$email) {
    
51.                         $this->error = 'no user or no email';
    
52.                         return false;
    
53.                 }
    
54.                 if($this->getIsLogin()) {
    
55.                         $this->error = 'has logined';
    
56.                         return false;
    
57.                 }
    
58.                 if($this->getUser($username,$email)) {
    
59.                         $this->error = 'registered by another';
    
60.                         return false;
    
61.                 }
    
62.                 try {
    
63.                         $f = fopen(self::DATA_FILE,'a');
    
64.                         flock($f,LOCK_EX);
    
65.                         fwrite($f,$username.self::SEPARATOR.$email.self::SEPARATOR.time()."\n");//写入一行
    
66.                         flock($f,LOCK_UN);
    
67.                 }
    
68.                 catch (Exception $e) {
    
69.                         fclose($f);
    
70.                         $this->error = $e->getMessage();
    
71.                         return false;
    
72.                 }
    
73.                 fclose($f);
    
74.                 return true;
    
75.         }
    
76.         /**
    
77.          * 寻找用户,找到返回用户信息，找不到返回false;
    
78.          * @param $username
    
79.          * @param $email
    
80.          */
    
81.         public function getUser($username,$email) {
    
82.                 $this->format($username,$email);
    
83.                 try {
    
84.                         $f = fopen(self::DATA_FILE,'r');
    
85.                         if ($f) {
    
86.                             while (!feof($f)) {
    
87.                                 $buffer = fgets($f, 4096);
    
88.                                 list($username1,$email1,$time1) = explode(self::SEPARATOR,$buffer);
    
89.                                 if($username1 == $username && $email1 == $email) {
    
90.                                         return array('user_name'=>$username1,'email'=>$email1,'last_view'=>$time1);
    
91.                                 }
    
92.                             }
    
93.                             fclose($f);
    
94.                         }
    
95.                 }
    
96.                 catch (Exception $e) {
    
97.                         fclose($f);
    
98.                         return false;
    
99.                 }
    
100.                 return false;
     
101.         }
     
102.         /**
     
103.          * 规范化字符串
     
104.          * @param $user
     
105.          * @param $email
     
106.          */
     
107.         public function format(&$user,&$email) {
     
108.                 $username = str_replace(self::SEPARATOR,'',trim($username));
     
109.                 $email = str_replace(self::SEPARATOR,'',trim($email));
     
110.         }
     
111.         /**
     
112.          * 退出：清除session和cookie
     
113.          */
     
114.         public function logout() {
     
115.                 unset($_SESSION['user_name']);
     
116.                 unset($_SESSION['email']);
     
117.                 unset($_SESSION['last_view']);
     
118.                 setcookie('user','',time()-1);
     
119.         }
     
120.         /**
     
121.          * 获取是否登陆
     
122.          */
     
123.         public function getIsLogin() {
     
124.                 if($_SESSION['user_name']) {
     
125.                         return true;
     
126.                 }
     
127.                 return false;
     
128.         }
     
129.         /**
     
130.          * 获取错误信息
     
131.          */
     
132.         public function getError() {
     
133.                 return $this->error;
     
134.         }
     
135. }

复制代码

renxiao2003

后面的不太会做了。呵呵。慢慢来。

angle4

哇， 还有时间阿，  一会过来凑个热闹

angle4

环境：
$ lsb_release -a
No LSB modules are available.
Distributor ID:        Ubuntu
Description:        Ubuntu 10.04.1 LTS
Release:        10.04
Codename:        lucid

$ php --version
PHP 5.3.2-1ubuntu4.5 with Suhosin-Patch (cli) (built: Sep 17 2010 13:41:55)
Copyright (c) 1997-2009 The PHP Group
Zend Engine v2.3.0, Copyright (c) 1998-2010 Zend Technologies

运行方式： $ php -f name.php

第2题

1. 
   
2. <?php
   
3. // search number using binary search
   
4. // the array index from zero to sizeof($array)-1
   
5. function binary_search($list, $num)
   
6. {
   
7.     $low = 0;
   
8.     $high = sizeof($list)-1;
   
9.     $mid = (int)(($low+$high)/2);
   
10.     while ($high >= $low) {
    
11.         if ($num > $list[$mid]) {
    
12.             $low = $mid + 1;
    
13.         } elseif ($num < $list[$mid]) {
    
14.             $high = $mid - 1;
    
15.         } else {
    
16.             return $mid;
    
17.         }   
    
18.         $mid = (int)(($low + $high)/2);
    
19.     }   
    
20.     return -1;
    
21. }
    
22. 
    
23. // read input from in.txt
    
24. $filename = "in.txt";
    
25. $fd = fopen($filename, "r") or exit("Unable open file [$filename]");
    
26. if (!feof($fd)) {
    
27.     $num = (int)fgets($fd);
    
28. }
    
29. if (!feof($fd)) {
    
30.     $list = explode(' ', fgets($fd));
    
31. }
    
32. fclose($fd);
    
33. 
    
34. // get result
    
35. $result = binary_search($list, $num);
    
36. 
    
37. // write result to out.txt
    
38. $filename = "out.txt";
    
39. $fd = fopen($filename, "w") or exit("Unable open file [$filename]");
    
40. fwrite($fd, $result);
    
41. fclose($fd);
    

复制代码

第4题

1. 
   
2. <?php
   
3. function bubble_sort($list)
   
4. {
   
5.     $len = sizeof($list);
   
6.     for ($i = 0; $i < $len; $i++) {
   
7.         for ($j = $i; $j < $len; $j++) {
   
8.             if ($list[$i] > $list[$j]) {
   
9.                 $tmp = $list[$i];
   
10.                 $list[$i] = $list[$j];
    
11.                 $list[$j] = $tmp;
    
12.             }   
    
13.         }   
    
14.     }   
    
15.     return $list;
    
16. }
    
17. 
    
18. function quick_sort($list, $low, $high)
    
19. {
    
20.     $i = $low;
    
21.     $j = $high;
    
22. 
    
23.     if ($low > $high)
    
24.         return;
    
25. 
    
26.     $tmp = $list[$low];
    
27. 
    
28.     while ($i != $j) {
    
29.         while ($list[$j] >= $tmp and $j > $i)
    
30.             $j--;
    
31.         if ($j > $i)
    
32.             $list[$i++] = $list[$j];
    
33. 
    
34.         while ($list[$i] <= $tmp and $j > $i)
    
35.             $i++;
    
36.         if ($j > $i)
    
37.             $list[$j--] = $list[$i];
    
38.     }
    
39.     $list[$i] = $tmp;
    
40.     quick_sort($list, $low, $i-1);
    
41.     quick_sort($list, $i+1, $high);
    
42. }
    
43. 
    
44. $list = array(1, 20, 2, 6, 0, 10);
    
45. print_r(bubble_sort($list));
    
46. print_r(quick_sort($list, 0, sizeof($list)-1));
    
47. ?>
    

复制代码

angle4

第6题

1. 
   
2. <?php
   
3. function sum_iter($list)
   
4. {
   
5.     $result = array();
   
6.     for ($i = 0; $i < sizeof($list); $i++) {
   
7.         for ($j = $i; $j < sizeof($list); $j++) {
   
8.             $result[$i][$j] = $list[$i] + $list[$j];
   
9.         }   
   
10.     }   
    
11.     return $result;
    
12. }
    
13. 
    
14. $list = array(1, 2, 3);
    
15. print_r(sum_iter($list));
    
16. $list = array(1, 2, 3, 4);
    
17. print_r(sum_iter($list));
    
18. ?>
    

复制代码

angle4

第15题

1. 
   
2. <?php
   
3. function getmax($list)
   
4. {
   
5.     $max_so_far = sizeof($list[0]);
   
6.     $index = -1;
   
7.     for ($i = 1; $i < sizeof($list); $i++) {
   
8.         if ($max_so_far < sizeof($list[$i])) {
   
9.             $index = $i;
   
10.             $max_so_far = sizeof($list[$i]);
    
11.         }   
    
12.     }   
    
13.     return $index;
    
14. }
    
15. 
    
16. $str = '1|2|3|4|5|6#1|2|3|4#1|2|3|4|5|6|7|8';
    
17. $arr = explode('#', $str);
    
18. $res = array();
    
19. $length = array();
    
20. for ($i = 0; $i < sizeof($arr); $i++) {
    
21.     $res[$i] = explode('|', $arr[$i]);
    
22.     $length[$i] = sizeof($res[$i]);
    
23. }
    
24. 
    
25. $index = getmax($res);
    
26. $len = sizeof($res[$index]);
    
27. $index++;
    
28. print "最长的二维数组是：$index\n";
    
29. print "长度为：$len\n";
    
30. for ($i = 0; $i < sizeof($res); $i++) {
    
31.     print implode(',', $res[$i]) . "\n";
    
32. }
    
33. ?>
    

复制代码