免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
最近访问板块 发新帖
查看: 1802 | 回复: 5

[算法] 一个用php写的算法 但是估计只有c++的人 愿意帮忙看了 [复制链接]

论坛徽章:
0
发表于 2009-06-16 16:35 |显示全部楼层
目的,将任意字符,数字,组合数用数组的形式描述,不要求排序。
举例 combination('a','b','c')
得到的结果应是
array(
   array('a'),
   array('b'),
   array('a','b'),
   array('a','c'),
   array('b','c'),
   array('a','b','c'),
)
我的算法在命令行模式下执行combination(array(1,2,3,4,5,6,7,8,10,11,12,13,14,15,16)) ;
排列三次时间分别是
0.109853982925 seconds
0.109352827072 seconds
0.109138011932 seconds

希望能帮忙优化到0.05s左右

Done by  0.151807069778 seconds
Done by  0.150317907333 seconds
Done by  0.165793180466 seconds
Done by  0.152053117752 seconds
Done by  0.158030033112 seconds
Done by  0.161707878113 seconds
Done by  0.155565977097 seconds
Done by  0.153033971786 seconds
Done by  0.156593084335 seconds
Done by  0.154980182648 seconds


function combination($arr = array(),$tmp=0){
        if(count($arr) ==2){
                $test =  array(array($arr[0]),array($arr[1]),array($arr[0],$arr[1]));
                return $test;
        }
        else{
                if(is_array($arr[0])){
                        $len = count($arr);
                        for($i=0;$i<$len;$i++){
                                $arrtmp = $arr[$i];
                                array_push($arrtmp,$tmp);
                                $arr[] = $arrtmp;
                        }
                        $arr[] = array($tmp);
                        return $arr;
                }
                else{  
                        $tmp = $arr[count($arr)-1];
                        array_pop($arr);
                        $array = combination($arr);
                        return  combination($array,$tmp);
                }
        }
}

论坛徽章:
0
发表于 2009-06-16 16:38 |显示全部楼层
用c重写

论坛徽章:
0
发表于 2009-06-16 16:45 |显示全部楼层
好久不写c       不见得能写出来了

论坛徽章:
0
发表于 2009-06-16 17:44 |显示全部楼层
看下排列组合的算法吧,我不会

但是觉得从算法上来优化,即使是用php,也能提高一些的

论坛徽章:
0
发表于 2009-06-16 18:55 |显示全部楼层
这种比较快:


  1. #include <iostream>
  2. using namespace std;

  3. int main()
  4. {
  5.         const int N = 16; // N < 32
  6.         int a[N];
  7.         for(int i=0; i<N; ++i)
  8.                 a[i] = i;
  9.                
  10.         for(int i = 1; i < (1<<N); ++i)
  11.         {
  12.                 for(int j = 0; j < N; ++j)
  13.                 {
  14.                         if((1 << j) &i)
  15.                         {
  16.                                 //printf("%d ",a[j]);
  17.                         }
  18.                 }
  19.                 //printf("\n");
  20.         }
  21.         return 0;       
  22. }
复制代码

去除输出
time ./a.out
real        0m0.005s
user        0m0.004s
sys        0m0.000s

论坛徽章:
0
发表于 2009-06-16 19:35 |显示全部楼层
换个好点的机器
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

  

北京盛拓优讯信息技术有限公司. 版权所有 京ICP备16024965号-6 北京市公安局海淀分局网监中心备案编号:11010802020122 niuxiaotong@pcpop.com 17352615567
未成年举报专区
中国互联网协会会员  联系我们:huangweiwei@itpub.net
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP