金山程序题2的优化

前几天把金山公司给的程序题解了下,代码也贴出来了,原文在这里: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的优化

  1. zydj_2006 says:

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

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

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

    o(n!)要好吧!

  3. davelv says:

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

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

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

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

    就是o(2^m)的。

  5. davelv says:

    <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!

  6. 这样想吧:

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

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

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

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

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

    然而你说的n!,明显重复了很多。

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

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

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

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

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

  7. 然而你说的n!,明显重复了很多。

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

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

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

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

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

  8. davelv says:

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

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

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

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

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

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

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

  10. davelv says:

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

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

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

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

  12. 没多想过,随手就写了,有错指出啊!

    //数组用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]); //选此元素

    }

  13. 不好意思刚改了改。

    //数组用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]); //选此元素

    }

  14. 更不好意思了,加有数组优化了一下,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]); //选此元素

    }

  15. davelv says:

    <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的话,这个时间复杂度跟我没有优化前的那个程序基本一致了。而原先那个程序就是用我求组合数的算法修改的。

  16. davelv says:

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

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

    题目果然是越讨论越清晰

  17. 哦!n是变的啊,那看来我理解偏了。

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

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

  18. davelv says:

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

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

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

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

  19. 没听说过呢~

    贴出来看看吧!

  20. davelv says:

    <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&quot; target="_blank">http://student.csdn.net/space.php?uid=53444&do=blog&id=18746</a&gt;

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

  22. howlet2 says:

    厉害啊 哈哈[e04]

  23. x642458 says:

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

发表评论

邮箱地址不会被公开。 必填项已用*标注