金山两道程序题(排列和组合)

编程 1  给定一个字符串,输出给定字符串所有的组合的函数,例如:字符串 abc  所有组合 abc  acb  bac b    ca cab  cba六种组合

编程 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);

要求有输入输出,而不是仅仅做一个函数出来..

/************************************************************
*名称:	problem01.c											*
*描述:	给定一个字符串,输出给定字符串所有的组合的函数	*
*假设:	假设字符串中的字母不重复							*
*思路:	对输入字符数组下标全排列再按照排列顺序输出即可	*
*环境:	Code::Blocks & Windows 7 & x86						*
*备注:	davelv于09年光棍节19点								*
*************************************************************/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define BUF_LEN 1024
//排列输出函数
void perm(char *buf, int start, int end);
int main(void)
{
    char buf[BUF_LEN];

    printf("Please input string less than %d letters:", BUF_LEN);
    fgets(buf, BUF_LEN, stdin);

    if (buf[strlen(buf)-1] == '/n')
        buf[strlen(buf)-1] = '/0';//去除控制台附加的/n

    perm(buf, 0, strlen(buf));//排列输出
    system("PAUSE");
    return 0;
}
//buf 待字符串;start 排列开始位置;end 排列结束位置
void perm(char *buf, int start, int end)
{
    int i;
    char temp;

    if (start == end)
    {//当排列到最后一个字符时输出
       puts(buf);
    }
    else
    {//否则继续排列
        for (i=start; i<end; i++)
        {
            //交换
            temp = buf[start];
            buf[start] = buf[i];
            buf[i] = temp;
            //递归排列
            perm(buf, start+1, end);
            //换回原位置
            buf[i] = buf[start];
            buf[start] = temp;
        }
    }
}
/************************************************************
*名称:	problem02.c											*
*描述:	整形数组中取n个元素和等于元素个数m(m>=n)			*
*假设:	不能重复取某个元素									*
*思路:	从1到m 组和数组元素并求和判断是否等于m			*
*改进:	见107行注释											*
*环境:	Code::Blocks & Windows 7 & x86						*
*备注:	davelv于09年光棍节20点								*
*************************************************************/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#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 n);

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<m; i++)
    {
		scanf("%d",buf+i);
	}
	printf("Totle %d way(s)/n", getotalNum(buf,m));
    system("PAUSE");
    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<m; i++)
	{
		if (array[i] > m)
		{
			m = i;
			break;
		}
	}
	result = (int*)malloc(m * sizeof(int));//为combine函数分配缓存空间
	if (result == NULL)
		return -1;
	//循环从1组和到m
	totle=0;
	for(i=1; i<=m; i++)
	{
		combine(array, result, m, i);
		totle += *result;
	}
	free(result);
	return totle;
}
//array:存储数字,result:存储本次结果,m:array长度即组合下标,n:组合上标
void combine(int array[], int result[], int m, int n)
{
    int i,t;//计数器,begin变量的中间变量
    static int totle=0,level=0,begin=0,num=0;//已经组合数字和,已递归深度,组合开始元素的下标,符合要求组合的个数

    for (i=begin; i<=m-n+level; i++)
    {
        if ( totle+array[i] <= m)//判断当前组合数字和是否已经超出m限制
		{
			totle += array[i];
			result[level] = array[i];//保存当前数字
			//判断当前层数是不是N-1
			if (level < n-1)
			{
				level++;
				t = begin;begin = i+1;
				combine(array, result, m, n);  //下层递归
				begin= t;
				level--;
			}
			else
			{
				if(totle == m)//判断当前数字和是否符合要求
				{
					int j;
					for(j=0; j<=level; j++)//符合则输出数字
						printf("%d ",result[j]);
					puts("");
					num++;    //计数器加一
				}
			}
			totle -= array[i];
		}
		else
			break;//超出限制则跳出
			/**************************************************
	*若使用longjmp直接跳回getotalNum可获得更好的性能*
			**************************************************/
    }
    if (level == 0)
	{
		result[0] = num;
		totle = num = 0;//将static变量归零
	}
}
This entry was posted in 程序设计 and tagged . Bookmark the permalink.

18 Responses to 金山两道程序题(排列和组合)

  1. awen_PC says:

    很经典的算法

  2. xy_hhl says:

    自己想了一节课,没想出算法,递归难

  3. davelv says:

    <div class="quote"><span class="q"><b>西安邮电学院 胡海浪(C/C++学生)</b>: 自己想了一节课,没想出算法,递归难</span></div>递归算法要用递归的思想去理解,我现在也是做得不够呢

  4. net613 says:

    代码写的很漂亮[惊讶]

  5. 好啊。。。不错

  6. Marcky says:

    额???居然没要求时间复杂度。。。

  7. davelv says:

    <div class="quote"><span class="q"><b>重庆邮电大学 吴小伟(C/C++学生)</b>: 额???居然没要求时间复杂度。。。</span></div>第一个是O(n!)

    第二个是O(sigama(1,n,A(n,i)))

    第二个题目还可以进一步优化,优化后是O(n!),等会贴新帖子.

  8. awen_PC says:

    等有时间也写一下  试试呵呵

  9. Marcky says:

    <div class="quote"><span class="q"><b>CAS davelv(C/C++学生)</b>: 第一个是O(n!)

    第二个是O(sigama(1,n,A(n,i)))

    第二个题目还可以进一步优化,优化后是O(n!),等会贴新帖子.</span></div>n!这个是不是有点恐怖了哦? 能否优先到n^2?甚至是n, logn……

    能写出n!也相当不错了,楼主继续加油,我们的路都还很长。

  10. woshizhaoy says:

    <div class="quote"><span class="q"><b>CAS davelv(C/C++学生)</b>: 第一个是O(n!)

    第二个是O(sigama(1,n,A(n,i)))

    第二个题目还可以进一步优化,优化后是O(n!),等会贴新帖子.</span></div>第二题用DP试试吧,应该可以达到O(NM2)

  11. davelv says:

    <div class="quote"><span class="q"><b>哈尔滨工业大学 赵昱(C/C++学生)</b>: 第二题用DP试试吧,应该可以达到O(NM2)</span></div>DP是动态规划吧.貌似动态规划只能求得一个解,而不是全部的解.题目要求要计算出全部解的个数,所以,DP在这里不好用.

  12. davelv says:

    <div class="quote"><span class="q"><b>重庆邮电大学 吴小伟(C/C++学生)</b>: n!这个是不是有点恐怖了哦? 能否优先到n^2?甚至是n, logn……

    能写出n!也相当不错了,楼主继续加油,我们的路都还很长。</span></div>今天TSU的朋友让我看MATRIX67的blog上生成函数这一问,他说觉得这个可能对本题有帮助,回去看下,再做总结

  13. [大笑],我通过了

  14. 匿名用户 says:

    [e03]

    哥今天去面试,遇到这题没答上来….[e08]

  15. Lieo says:

    今天逛博客来看看你之前的日志。

    第二题:我刚开始还以为是0/1背包,我还在郁闷你为啥不直接DP。。。后来一看原来是完全背包。。。。

  16. davelv says:

    我对背包也不怎么熟悉,完全是凭感觉去做。优化http://blog.csdn.net/davelv/archive/2009/12/06 /4950605.aspx 进一步优化http://blog.csdn.net/davelv/archive/2009/12/15/5007625.aspx

回复 xy_hhl 取消回复

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