| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 1260 人关注过本帖, 3 人收藏
标题:华为面试题,大家讨论下!
只看楼主 加入收藏
ybjkl
Rank: 2
等 级:论坛游民
帖 子:86
专家分:85
注 册:2011-6-21
结帖率:95.65%
收藏(3)
已结贴  问题点数:10 回复次数:12 
华为面试题,大家讨论下!
求组合数: 求n个数(1....n)中k个数的组合....
如:combination(5,3)
要求输出:543,542,541,532,531,521,432,431,421,321

给定一个数组,这个数组中既有正数又有负数,找出这个数组中的子数组,此子数组的和最大!



搜索更多相关主题的帖子: 华为面试 
2011-09-04 19:52
laoyang103
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:内蒙古包头
等 级:贵宾
威 望:19
帖 子:3082
专家分:11056
注 册:2010-5-22
收藏
得分:0 
程序代码:
#include <stdio.h>
int data[100] = {5,4,3,2,1};
bool foot[100] = {0};
int cool = 0;
void com(int n,int k,int mem[],int depth,int begin)
{
    int i,j;
    if(k == depth)
    {
        for(i = 0;i<k;i++)
            printf("%d ",mem[i]);
        cool++;
        printf("\n");
        return ;
    }
    for(i = 0;i<n;i++)
    {
        if(!foot[i])
        {
            foot[i] = true;
            mem[begin] = data[i];
            com(n,k,mem,depth+1,begin+1);
            foot[i] = false;
        }
    }
}
int main()
{
    int mem[100] = {0};
    com(5,3,mem,0,0);
    return 0;
}
以上程序完成 A(m,n)并且将其打印出来

                                         
===========深入<----------------->浅出============
2011-09-04 20:43
laoyang103
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:内蒙古包头
等 级:贵宾
威 望:19
帖 子:3082
专家分:11056
注 册:2010-5-22
收藏
得分:0 
程序代码:
#include <stdio.h>
int data[100] = {5,4,3,2,1};
bool foot[100] = {0};
int cool = 0;
void com(int n,int k,int mem[],int depth,int begin,int pos)
{
    int i,j;
    if(k == depth)
    {
        for(i = 0;i<k;i++)
            printf("%d ",mem[i]);
        cool++;
        printf("\n");
        return ;
    }
    for(i = pos;i<n;i++)
    {
        if(!foot[i])
        {
            foot[i] = true;
            mem[begin] = data[i];
            com(n,k,mem,depth+1,begin+1,i+1);
            foot[i] = false;
        }
    }
}
int main()
{
    int mem[100] = {0};
    com(5,3,mem,0,0,0);
    return 0;
}
上面程序完成了 C(m,n)并且将其打印出来

[ 本帖最后由 laoyang103 于 2012-3-23 21:27 编辑 ]

                                         
===========深入<----------------->浅出============
2011-09-04 20:44
laoyang103
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:内蒙古包头
等 级:贵宾
威 望:19
帖 子:3082
专家分:11056
注 册:2010-5-22
收藏
得分:0 
仔细观察两个程序的递归 全排列的递归为无序生成子树 也就是每次都要从0一直到n来寻找

没有使用过的数  求解组合数时使用有序递归生成子树 也就是每次从上一次递归的下一个位置开始即i+1

这样就可以生成组合数  其实只是全排列稍稍改动一下

                                         
===========深入<----------------->浅出============
2011-09-04 20:47
laoyang103
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:内蒙古包头
等 级:贵宾
威 望:19
帖 子:3082
专家分:11056
注 册:2010-5-22
收藏
得分:0 
程序代码:
#include<stdio.h>
int main()
{
    int i,j,k;
    int b,c,n;
    while(EOF != scanf("%d",&n))
    {
        if(0 == n)
            break;
        int a[10001] = {0};
        int max[10001] = {0};
        int begin = 0,end = 0,tempmax = -1;
        int tempbegin = 0;
        for(i = 1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            if(1 == i)
            {
                max[i] = a[i];
                tempmax = max[i];
                tempbegin = begin = end = i;
            }
            else
            {
                if(max[i-1]>=0)
                {
                    max[i] = max[i-1]+a[i];
                }
                else
                {
                    max[i] = a[i];
                    tempbegin = i;
                }
                if(tempmax < max[i])
                {
                    tempmax = max[i];
                    end = i;
                    begin = tempbegin;
                }
            }
        }
        for(i = 1;i<=n;i++)
            if(a[i]>=0)
                break;
        if(i > n)
            printf("0 %d %d\n",a[1],a[n]);
        else
            printf("%d %d %d\n",tempmax,a[begin],a[end]);
    }
    return 0;
}

                                         
===========深入<----------------->浅出============
2011-09-04 20:54
laoyang103
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:内蒙古包头
等 级:贵宾
威 望:19
帖 子:3082
专家分:11056
注 册:2010-5-22
收藏
得分:7 
上面题是我在OJ上面做过的一道题 解法为动态规划  状态转移方程为

max[i] = max{max[i-1]+a[i],a[i]} 其实仔细看如果max[i-1]大于等于0那么一定是max[i-1]+a[i]

如果小于0 那么一定是a[i]所以可以写成 max[i] = max[i-1]>=0 ? max[i-1]+a[i]:a[i];

然后再从0到n去遍历max数组 找到那个最大值就可以了 题目网址http://acm.tzc.

应该能符合你的要求了吧

                                         
===========深入<----------------->浅出============
2011-09-04 20:59
韩54521风
Rank: 4
等 级:业余侠客
帖 子:75
专家分:212
注 册:2011-6-11
收藏
得分:0 
楼上经典,佩服,实在是厉害啊!
2011-09-04 22:02
laoyang103
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:内蒙古包头
等 级:贵宾
威 望:19
帖 子:3082
专家分:11056
注 册:2010-5-22
收藏
得分:0 
其实排列 组合这些算法都是递归的基础应用  递归更深的应用是搜索

                                         
===========深入<----------------->浅出============
2011-09-04 22:06
czsbc
Rank: 10Rank: 10Rank: 10
等 级:青峰侠
帖 子:469
专家分:1700
注 册:2008-12-13
收藏
得分:3 
第一题我也做了一下。
程序代码:
#include<stdio.h>
void combination(int n,int k);

static path[100]={0};
int cnt=0;

void main()
{
    combination(5,3);
}

void combination(int n,int k)
{
    if(n>=k)
    {
        if(n==k)
        {
            for(int i=n;i!=0;--i)
                path[cnt++]=i;
            for(i=0;i<cnt;i++)
                printf("%d",path[i]);
            printf(" ");
            cnt-=n+1;
            return;
        }
        if(k==0)
        {
            for(int i=0;i<cnt;i++)
                printf("%d",path[i]);
            printf(" ");
            cnt--;
            return;
        }
        if(k==1)
        {
           
            for(int i=n;i!=0;--i)
            {
                path[cnt++]=i;
                combination(i,0);
            }
            cnt--;   
        }
        else
        {
            path[cnt++]=n;
            combination(n-1,k-1);
            combination(n-1,k);
        }
    }
    else
        printf("data error!\n");
}
第二个是不是只要找出所有正数就可以了呢?
2011-09-04 22:31
pangding
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:北京
等 级:贵宾
威 望:94
帖 子:6784
专家分:16751
注 册:2008-12-20
收藏
得分:0 
回复 9楼 czsbc
第二个不是找正数就行了。因为它应该是要这个数列的一个连续的部分,否则就完全没有考的意义了。

不过就从语言描述上看,子数组这个词确实有待商榷。
数学的数列是有子列的概念的,那个可没要求连着取,只要原来在前面的项还在前面就行了(就是说项的先后顺序不能换,其它的不关心)。


另外老杨经验丰富的很,给的答案很有参考价值。
2011-09-04 23:20
快速回复:华为面试题,大家讨论下!
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.056202 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved