life02

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  197 随笔 :: 3 文章 :: 37 评论 :: 0 Trackbacks

题目转自:
http://blog.163.com/ecy_fu/blog/static/444512620098228849190/
 二笔只有三道题,分值分别为30, 30, 40,题分别如下:
1、实现strtol函数,其原型如为int strtol(const char *num_str, char **endptr, int base),num_str存放待转换的字符串,可以是负数也可以是正数;endptr指向第一个非法字符的地址,如果endptr为NULL则不指向第一个非法字符的地址;base用于指示进制,若base为0,则根据num_str的指示来转换。函数必须检查溢出,如果正数溢出,返回INT_MAX;若负数溢出,返回INT_MIN。
2、一亿个数找最大的1000个数,要求效率高占用内存少。函数原型为:find_max_data(int* source_data, int* max_data),其中source_data是存放一亿个数的数组,max_data用于存放其中最大的1000个数。
3、将一个集合拆分成两个不相交的子集,两个子集元素之和相等,如{1, 2, 3, 4, 5, 6, 7},拆分成:
{2, 5, 7}, {1, 3, 4, 6}
给出一个集合,求所有符合上面要求的拆分,效率最高分越高,函数原型为int cal_num(int n);

第三题:
利用回溯剪枝法
空间复杂度:O(n) 栈的最大深度也就是n了
时间复杂度:接近于O(2^n-1), 因为本质上程序时一个遍历树的过程,如果没有剪枝,那么树是一个满二叉树,结点共2^n-1个,也就要遍历2^n-1次。虽然剪枝,但速度估计仍是 2^n次方级别的。
试了下,调用cal_num(104),好久了结果都没有出来。。。

不知用上DP算法会不会好点,不过听说回溯法怎么弄效率都跟不上,最好用递推?
在哪听说的?
http://topic.csdn.net/u/20090922/11/ebc26b48-6581-40c3-afe0-a95ca2d700d5.html

 

/////////////////////////////////////////////////////////////////
//file divide_set.h:

#ifndef __DIVIDE_SET_H__
#define __DIVIDE_SET_H__

// 计算集合set的所有满足下列条件的子集合:子集合元素之和等于value
// 子集合的元素对应的label置1
void divide_set( int set[], int label[], int len, int i_set, int value );

// 对集合{1,2,n}划分
void cal_num( int n );

#endif


/////////////////////////////////////////////////////////////////
//file divide_set.cpp:

#include 
"stdafx.h"
#include 
"divide_set.h"

#include 
<iostream>

using namespace std;

// 查找集合set中,满足元素之和等于value的子集合,结果存于label里
void divide_set( int set[], int label[], int len, int i_set, int value )
{
 
// 输出结果
 if ( value == 0 )
 
{
  cout
<<"";
  
for ( int i=0; i<len; ++i )
  
{
   
if ( label[i] )
   
{
    cout
<<set[i]<<" ";
   }

   
  }

  cout
<<"";
  cout
<<" , { ";
  
for ( int i=0; i<len; ++i )
  
{
   
if ( 0 == label[i] )
   
{
    cout
<<set[i]<<" ";
   }

  }

  cout
<<"";
  cout
<<endl;
  
return;
 }


 
if ( i_set >= len || value <0)
 
{
  
return;
 }


 
// 取第i_set个元素
 label[i_set] = 1;
 divide_set( 
set, label, len, i_set+1, value-set[i_set] );
 
 
// 不取第i_set个元素
 label[i_set] = 0;
 divide_set( 
set, label, len, i_set+1, value );
}


void cal_num( int n )
{
 
int* set = new int[n];
 
int* label = new int[n];

 
// initialize set and label
 int sum_value = 0;
 
for ( int i=0; i<n; ++i )
 
{
  
set[i] = i+1;
  sum_value 
+= set[i]; 
 }

 memset( label, 
0, n*sizeof(int) );

 
// 保证元素总和为偶数
 if( sum_value%2 == 0 )
  divide_set( 
set, label, n, 0, sum_value/2 );

 delete[] 
set;
 delete[] label;
}


 

本文来自CSDN博客,转载请标明出处:http://blog.csdn.net/zdl1016/archive/2009/10/04/4632688.aspx

posted on 2009-10-07 11:08 life02 阅读(482) 评论(1)  编辑 收藏 引用 所属分类: 笔试

评论

# re: 迅雷2010笔试题-成都站 (转)[未登录] 2009-10-07 19:38 vincent
第一题 - -都看不懂..orz
第二题 用一个长度为1000的小头堆..每次拿一个数跟小头堆的头来比..如果大于..就把小头堆的头去掉..然后放进这个数
第三题 这个要看题的范围了吧..dp的话就是背包了..

  回复  更多评论
  


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理