金山程序题2的优化

by davelv Posted on 2009/12/06

前几天把金山公司给的程序题解了下，代码也贴出来了，原文在这里：http://student.csdn.net/space.php?uid=53444&do=blog&id=16634

编程 2

  给定一个数组大小m和一个数组array
  m = 10;  array = {1,2,3,4,5,6,7,8,9,10}
  求从array中任意取得n（n<=m）个数，使得和为m，总共有多少种取法，例如：10 1,9 2,3,5
  方法原型：int  getotalNum (int[] array, int m);

原始代码优化的不是很到位，于是今天早上重写了下。

时间复杂度从O(sigma(1,n,A(i,n)))降低到O(A(n,n))也就是O(n!)。

主要方法是把combine函数改写，把外部调用combine的循环移入combine函数内部，这样减少了combine函数中某些结果重复计算的冗余，从而改进了时间复杂度。

新代码如下

/************************************************************
*名称:    problem02.c                                         *
*描述:    整形数组中取n个元素和等于元素个数m(m&gt;=n)        *
*假设:    不能重复取某个元素                               *
*思路:    从1到m 组和数组元素并求和判断是否等于m           *
*环境:    Code::Blocks & Windows 7 & x86                  *
*备注:    davelv于09-12-06                                 *
*************************************************************/
#include &lt;stdio.h&gt;
#include &lt;stdlib.h&gt;
#include &lt;string.h&gt;
#define BUF_LEN 1024
//比较函数，用于qsort
int compare ( const void *a , const void *b );
//求有几种取法的函数
int  getotalNum (int array[], int m);
//数字组合函数
void combine(int array[], int result[], int m);

int main(void)
{
    int buf[BUF_LEN], m, i;

    printf("Please input NO. of integer(s) no more than %d:", BUF_LEN);
    scanf("%d",&m);
    printf("Please input integer(s):");
    for(i=0; i&lt;m; i++)
    {
        scanf("%d",buf+i);
    }
    printf("Totle %d way(s)/n", getotalNum(buf,m));
    return 0;
}

int compare ( const void *a , const void *b )
{
    return *(int *)a - *(int *)b;
}
//返回值为取法的总数，如果是-1则表示函数失败
int  getotalNum (int array[], int m)
{
    int i, totle;
    int *result;
    qsort(array, m, sizeof(array[0]), compare);//排序
    //排除大于m的数字
    for(i=0; i&lt;m; i++)
    {
        if (array[i] &gt; m)
        {
            m = i;
            break;
        }
    }
    result = (int*)malloc(m * sizeof(int));//为combine函数分配缓存空间
    if (result == NULL)
        return -1;
    combine(array, result, m);
    totle=*result;
    free(result);
    return totle;
}
//array:存储数字，result:存储结果数量,m:数字个数
void combine(int array[], int result[], int m)
{
    int i,t;//计数器,begin变量的中间变量
    static int totle=0,level=0,begin=0,num=0;//已经组合数字和,已递归深度,组合开始元素的下标,符合要求组合的个数

    for (i=begin; i&lt;=m; i++)
    {
        totle += array[i];
        result[level] = array[i];//保存当前数字
        if ( totle &lt; m)//判断当前组合数字和是否已经超出m限制
        {
            //判断当前层数是不是M-1
            if (level &lt; m-1)
            {
                level++;
                t = begin;
                begin = i+1;
                combine(array, result, m);        //下层递归
                begin= t;
                level--;
            }
        }
        else if(totle &gt; m)//超过m则跳出本次循环
        {
            totle -= array[i];
            break;
        }
        else
        {
            int j;
            for(j=0; j&lt;=level; j++)//符合则输出数字
                printf("%d ",result[j]);
            puts("");
            num++;        //计数器加一
        }
        totle -= array[i];
    }

    if (level == 0)
    {
        result[0] = num;
    }
}

利用自己写的测试程序测试新旧两个程序getotleNum()所耗时间结果如下：

E:/cbwork/testc/bin/Release>driver.exe
generate_test_data_file   ok!
run tested programs
data            old(ms)         new(ms)
50              75              2
60              289             5
70              998             15
80              3278            44
90              9409            107
100             26747           261
110             69330           601

gcc (GCC) 3.4.5 (mingw-vista special)，O2开关优化，Win7, Intel 奔腾双核 1.8GHz，1G内存。

排除当时间较少时的噪音干扰，可以得到如下结论。

1、旧程序在数据量每增加10的时候时间增长为原来的约3倍

2、新程序在数据量每增加10的时候时间增长为原来的约2+倍

3、新程序比旧程序在同等数据量的情况下快约100倍。

同时给出测试驱动程序：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

#define PROGRAM_NAME_TYPE "xxx.exe"
#define IN_PIPE "<"

void generate_test_data_file(int from, int to, int step);
void run_programs(int from, int to, int step);
int main()
{
    int from=50,to=110,step=10;
    printf("generate_test_data_file   ");
    generate_test_data_file(from,to,step);
    puts("ok!");
    puts("run tested programs");
    puts("data/t/told(ms)/t/tnew(ms)");
    run_programs(from,to,step);
    return 0;
}
void run_programs(int from, int to, int step)
{
    char cmd[FILENAME_MAX];
    int len;
    for(;from<=to;from+=step)
    {
        len=strlen(PROGRAM_NAME_TYPE)+strlen(IN_PIPE);
        itoa(from,cmd+len,10);
        printf(cmd+len);
        printf("/t/t");
        memcpy(cmd,"old.exe<",strlen("old.exe<"));
        system(cmd);
        printf("/t/t");
        memcpy(cmd,"new.exe<",strlen("new.exe<"));
        system(cmd);
        puts("");
    }
}
void generate_test_data_file(int from, int to, int step)
{
    FILE * fp;
    int i;
    char filename[FILENAME_MAX];
    for(;from<=to;from+=step)
    {
        fp=fopen(itoa(from,filename,10),"w");
        if(fp==NULL)
        {
            puts("generate test data file error!");
            exit(1);
        }
        fprintf(fp,"%d/n",from);
        for(i=0;i<from;i++)
        {
            fprintf(fp,"%d ",i);
        }
        fclose(fp);
    }

}

This entry was posted in 程序设计 and tagged 程序设计. Bookmark the permalink.

23 Responses to 金山程序题2的优化

zydj_2006 says:

2009/12/09 at 10:31

感谢分享，你的文章已经推荐到学生大本营首页。希望你的经验能够帮助更多的同学。

回复
cug_fish_2009 says:

2009/12/12 at 19:26

dfs的算法吧！对于每个元素只有选与不选两种情况,

这样的时间复杂度是o(2^m)。在加里面的优化，复杂度应该比你写的

o(n!)要好吧！

回复
davelv says:

2009/12/12 at 20:24

<div class="quote"><span class="q"><b>中国地质大学（武汉）杨辉鱼(C/C++学生)</b>: dfs的算法吧！对于每个元素只有选与不选两种情况,

这样的时间复杂度是o(2^m)。在加里面的优化，复杂度应该比你写的

o(n!)要好吧！</span></div>我这个就是DFS,仁兄说的DFS如何实现,可以具体一点吗?

回复
cug_fish_2009 says:

2009/12/12 at 21:13

哦，之前没细看你代码，的确是dfs，不过时间复杂度算错了吧！

就是o(2^m)的。

回复
davelv says:

2009/12/12 at 21:20

<div class="quote"><span class="q"><b>中国地质大学（武汉）杨辉鱼(C/C++学生)</b>: 哦，之前没细看你代码，的确是dfs，不过时间复杂度算错了吧！

就是o(2^m)的。</span></div>是个递归.例如当输入数据量是10的时候

最坏情况循环次数就是10*9*8*7*6*5*4*3*2*1=10!

回复
cug_fish_2009 says:

2009/12/12 at 22:37

这样想吧：

假设一个集合S，S里面有n个数，并且和等于m。

那么我们就是求满足这个集合的个数。

对于这n个数，肯定是m个数里面的，所以说可以转换为

这m个数出现在S集合或者不出现。于是就是o(2^m)。

当然里面有剪枝条件可以将复杂度降低很多。

然而你说的n！，明显重复了很多。

比如array<i>先选了，然后在选择array[j];

按照你的算法，选择了array[j]后还会在选array<i>，

这样一来，就重复了很多。

还说得明白点就排列和组合的区别了。

你用的是排列，我用的是组合。

回复
cug_fish_2009 says:

2009/12/12 at 22:38

然而你说的n！，明显重复了很多。

比如array<i>先选了，然后在选择array[j];

按照你的算法，选择了array[j]后还会在选array[j]，

这样一来，就重复了很多。

还说得明白点就排列和组合的区别了。

你用的是排列，我用的是组合。

回复
davelv says:

2009/12/12 at 23:08

<div class="quote"><span class="q"><b>中国地质大学（武汉）杨辉鱼(C/C++学生)</b>: 这样想吧：

假设一个集合S，S里面有n个数，并且和等于m。

那么我们就是求满足这个集合的个数。

对于这n个数，肯定是m个数里面的，所以说可以转换为

这m个数出现在S集合或者</span></div>按照你的说法,m个数在集合s里是否出现,这样只能得到一个结果.

我们要得到是满足这个要求全部集合的个数..

回复
cug_fish_2009 says:

2009/12/13 at 09:59

怎么会呢，假设array[1]+array[2] = 4,也有可能array[3]+array[4] = 4。

回复
davelv says:

2009/12/13 at 10:23

<div class="quote"><span class="q"><b>中国地质大学（武汉）杨辉鱼(C/C++学生)</b>: 怎么会呢，假设array[1]+array[2] = 4,也有可能array[3]+array[4] = 4。</span></div>是我愚笨，麻烦仁兄能给出核心算法吗？伪码也可以的

回复
cug_fish_2009 says:

2009/12/13 at 12:07

我很久没写代码以前就是搞算法的，ACM –pku里。

不过只要你理解我说的就ok了啊。

写出来，也行，不过伪代码就ok。

回复
cug_fish_2009 says:

2009/12/13 at 12:23

没多想过，随手就写了，有错指出啊！

//数组用ar[1-m]表示，个数为m，找n个数的集合S，和为m。

//还有个数组sign[1-m]用于标记ar中元素是否被选中,初始化全为FALSE

//count = 0; 用来计算满足条件的集合数

/*在这之前，像你写的，先对数组清理一下，大于m的数剔除。

将数组非降序排列。*/

void dfs(int k,int u,int sum)//k为数组中第k个元素,u表示S集合里的元素个数，sum之前加的和

{

if(k >= m || u > n)//到数组的末尾或超过n的限制

return ;

if(sum + ar[k] > m)//超过了

return ;

if(sum + ar[k] == m && u == n)

{

count ++ ;

print();//如果满足条件，打印出结果

return ;

}

dfs(k+1, u,sum); //不选此元素

dfs(k+1, u+1, sum +ar[k]); //选此元素

}

回复
cug_fish_2009 says:

2009/12/13 at 12:24

不好意思刚改了改。

//数组用ar[1-m]表示，个数为m，找n个数的集合S，和为m。

//还有个数组sign[1-m]用于标记ar中元素是否被选中,初始化全为FALSE

//count = 0; 用来计算满足条件的集合数

/*在这之前，像你写的，先对数组清理一下，大于m的数剔除。

将数组非降序排列。*/

void dfs(int k,int u,int sum)//k为数组中第k个元素,u表示S集合里的元素个数，sum之前加的和

{

if(k >= m || u > n)//到数组的末尾或超过n的限制

return ;

if(sum > m)//超过了

return ;

if(sum == m && u == n)

{

count ++ ;

print();//如果满足条件，打印出结果

return ;

}

dfs(k+1, u,sum); //不选此元素

sign[k] = TRUE; //做记号

dfs(k+1, u+1, sum +ar[k]); //选此元素

}

回复
cug_fish_2009 says:

2009/12/13 at 12:29

更不好意思了，加有数组优化了一下，lef[]。

//数组用ar[1-m]表示，个数为m，找n个数的集合S，和为m。

//还有个数组sign[1-m]用于标记ar中元素是否被选中,初始化全为FALSE

//在加个数组lef[i-m]表示从第i元素到底m-1元素的和，做优化使用

//count = 0; 用来计算满足条件的集合数

/*在这之前，像你写的，先对数组清理一下，大于m的数剔除。

将数组非降序排列。*/

void dfs(int k,int u,int sum)//k为数组中第k个元素,u表示S集合里的元素个数，sum之前加的和

{

if(k >= m || u > n)//到数组的末尾或超过n的限制

return ;

if(sum > m || sum + lef[k] < m)//超过了或者加上从k开始的全部元素都无法达到m

return ;

if(sum == m && u == n)

{

count ++ ;

print();//如果满足条件，打印出结果

return ;

}

dfs(k+1, u,sum); //不选此元素

sign[k] = TRUE; //做记号

dfs(k+1, u+1, sum +ar[k]); //选此元素

}

回复
davelv says:

2009/12/13 at 13:41

<div class="quote"><span class="q"><b>中国地质大学（武汉）杨辉鱼(C/C++学生)</b>: 更不好意思了，加有数组优化了一下，lef[]。

//数组用ar[1-m]表示，个数为m，找n个数的集合S，和为m。

//还有个数组sign[1-m]用于标记ar中元素是否被选中,初始化全为FAL</span></div>杨兄,我理解了你的算法了,时间复杂度是O(2^n)没错。不过你的n是固定值，而题目要求是随便几个数只要加起来等于m就可以，n是不固定的。

如果外面用一个循环来遍历n的话，这个时间复杂度跟我没有优化前的那个程序基本一致了。而原先那个程序就是用我求组合数的算法修改的。

回复
davelv says:

2009/12/13 at 15:18

<div class="quote"><span class="q"><b>中国地质大学（武汉）杨辉鱼(C/C++学生)</b>: 哦，之前没细看你代码，的确是dfs，不过时间复杂度算错了吧！

就是o(2^m)的。</span></div>其实我也算错了，这个代码的时间复杂度跟优化前的代码是一样的。只是剪枝效果好，所以运行时间短。如果对某些特别坏的数据，运行效率跟原算法差不多的。

题目果然是越讨论越清晰

回复
cug_fish_2009 says:

2009/12/13 at 16:13

哦！n是变的啊，那看来我理解偏了。

这样一来，就是优化效果变差了。

要去掉那个对n约束的剪枝的了。

回复
davelv says:

2009/12/14 at 03:14

<div class="quote"><span class="q"><b>中国地质大学（武汉）杨辉鱼(C/C++学生)</b>: 哦！n是变的啊，那看来我理解偏了。

这样一来，就是优化效果变差了。

要去掉那个对n约束的剪枝的了。</span></div>好消息，利用生成函数的原理+简单多项式乘积的算法，以O(n^2)的时间复杂度基本搞定了该问题。

多亏了TSU的同学的帮助。。。明天开新贴继续讨论

回复
cug_fish_2009 says:

2009/12/14 at 11:21

没听说过呢~

贴出来看看吧！

回复
davelv says:

2009/12/15 at 01:23

<div class="quote"><span class="q"><b>中国地质大学（武汉）杨辉鱼(C/C++学生)</b>: 没听说过呢~

贴出来看看吧！</span></div>已发新帖<a href="http://student.csdn.net/space.php?uid=53444&do=blog&id=18746" target="_blank">http://student.csdn.net/space.php?uid=53444&do=blog&id=18746</a>

回复
caolei19890129 says:

2009/12/26 at 09:48

你写的还不错哦。。继续加油。我会继续关注你的

回复
howlet2 says:

2009/12/28 at 14:59

厉害啊哈哈[e04]

回复
x642458 says:

2010/01/25 at 22:59

看到驱动程序了，强大[e03][e04]

回复

System C.

程序设计=数据结构+算法

金山程序题2的优化

23 Responses to 金山程序题2的优化

发表回复取消回复

近期评论

近期文章

朋友们

分类目录

归档

23 Responses to 金山程序题2的优化

发表回复 取消回复

标签

近期评论

近期文章

朋友们

分类目录

归档

发表回复取消回复