LoveSi

自处超然,处人蔼然,无事澄然,遇事斩然,得意淡然,失意泰然

常用链接

统计

最新评论

笔试碰到的算法题

至今笔试都悲剧的被拒,先发几道笔试中遇到的算法题
1.给定一整数序列A1, A2,... An (可能有负数),求A1~An的一个子序列Ai~Aj,使得Ai到Aj的和最大.
例如:整数序列-2, 11, -4, 13, -5, 2, -5, -3, 12, -9的最大子序列的和为21。
int max_sub2(int a[], int size)
{
    
int  max = 0;
    
int temp_sum = 0;
    
for(int i = 0; i < size; i++)
    
{
        temp_sum 
+= a[i];
        
if(temp_sum > max)
            max 
= temp_sum;
        
else if(temp_sum < 0)
            temp_sum 
= 0;
    }

    
return max;
}

2. 任何一个基于"比较"的内部排序的算法,若对6个元素进行排序,则在最坏情况下所需的比较次数至少为____。

   据严蔚敏数据结构,问题等价于给n个不同的砝码和一台天平要称几次能分辨它们的顺序。n个记录的序列可能出现的初始状态有n!个,则描述n个记录排序过程的判定树必有n!个叶子节点,若有n个叶子节点,则二叉树的高度至少为log 2 n,(2为底),也即是说必然存在一条长为log 2 n!的路径,求出来n10,(取上界)

3. 对一个表达式求值时,首先要把表达式转换为后缀表达式,然后在利用栈求值。

posted on 2010-10-10 16:37 LoveSi 阅读(645) 评论(2)  编辑 收藏 引用 所属分类: 面/笔试

评论

# re: 笔试碰到的算法题[未登录] 2010-10-11 15:20 HelloWorld

你这是求的最大和,还不是最大和的子串。
程序改改吧  回复  更多评论   

# re: 笔试碰到的算法题 2010-10-13 09:49 LoveSi

确实,这位同学说的对,应该是求字串,那会只看到例子了,就忘记字串了。@HelloWorld
  回复  更多评论   


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理