校招季——编程题目（6-7）

￡神魔★判官ぃ 2021-10-30 02:50 306阅读 0赞

2013/08/15，第四天

# 6. 反转单词（题目007） #

**题目：**

将字符串中的每个单词内的字母顺序倒转，其它字符不变

**解答：**

void ReverseString(char *s)
    {
        int n = strlen(s), start = -1, i;
        for (i = 0; i <= n; ++i)
            if (!isalpha(s[i]))
            {
                ReverseWord(&s[start+1], i–start-1);
                start = i;
            }
    }
    void ReverseWord(char *s, int n)
    {
        if (n < 2)
            return;
        int i;
        for (i = 0; i < n/2; ++i)
            Swap(&s[i], &s[n-i-1]);
    }

# 7. 放苹果/和的数量（题目025、题目053） #

**题目：**

题目025：把m个苹果放在n个盘子里，允许有空的盘子或多个苹果的盘子，共有多少种不同的分法？

题目053：输入m，n，从\[1,n\]中取出若干个不相同的数，使其和等于m。打印出各种可能。

**解答：**

令f(m,n)为题目025的解，可知以下几个性质：

1.若n>m，f(m,n)=f(m,m)。

2.f(0,n)=f(m,1)=1。

3.重点来了，f(m,n)=f(m,n-1)+f(m-n,n)。

对第3条的解释：f(m,n)可认为是n个盘子里放m个苹果，如果至少有一个盘子是空的，则此情况等价于n-1个盘子里放m个苹果f(m,n-1)，即将那个空盘子排除掉；如果所有盘子都至少有一个苹果，则此情况等价于每个盘子放一个苹果后n个盘子里放m-n个苹果f(m-n,n)。

题目053与题目025类似，区别在于：

1.终止条件为f(0,n)=f(m,0)=0。

2.在m<n时可直接输出一种结果，但还需要继续寻找其它可能。

3.迭代式为：f(m,n)=f(m-n,n-1)+f(m,n-1)。

对第3条的解释：我们从后向前寻找可能的解，如果n这个数是解的一部分，则此情况等价于f(m-n,n-1)，如果n不是解的一部分，则等价于f(m,n-1)。

025方法1：

直接自顶向下递归进行，代码简洁，但包含大量的重复子问题的计算，速度较慢。

double Func_1(int M, int N)
    {
    	if (M < N)
    		N = M;
    	if (M==0 || N==1)
    		return 1.0;
    	else
    		return Func_1(M - N, N) + Func_1(M, N - 1);
    }

025方法2：

将上面的方法改成动态规划，迭代进行。

double Func_2(int M, int N)
    {
    	if (N > M)
    		N = M;
    	double **data = malloc2d(M + 1, N + 1, sizeof(double));
    	int i, j;
    	for (j = 0; j <= N; ++j)
    		data[0][j] = 1;
    	for (i = 0; i <= M; ++i)
    		data[i][1] = 1;
    	for (i = 1; i <= M; ++i)
    		for (j = 2; j<=N; ++j)
    			if (j > i)
    				data[i][j] = data[i][i];
    			else
    				data[i][j] = data[i][j-1] + data[i-j][j];
    	double ret = data[M][N];
    	free2d(data, M + 1);
    	return ret;
    }

025方法3：

将方法1改为备忘录形式，避免重复计算。

double Func_3(int M, int N)
    {
    	if(N>M)
    		N=M;
    	double **data = (double **)calloc2d(M+1, N+1, sizeof(double));
    	double ret = RealFunc_3(M, N, data);
    	free2d(data,M);
    	return ret;
    }
    double RealFunc_3(int M, int N, double **data)
    {
    	if (M < N)
    		N = M;
    	if (M == 0 || N == 1)
    		return 1.0;
    
    	if (data[M][N] > 0)
    		return data[M][N];
    	else
    		return data[M][N] = RealFunc_3(M-N, N, data) + RealFunc_3(M, N-1, data);
    }

053：

int g_sequence[10000] = {0};
    void PrintSequence(int lenth)
    {
    	int i;
    	for (i = 0; i < lenth - 1; ++i)
    		printf("%d,", g_sequence[i]);
    	printf("%d\n", g_sequence[i]);
    }
    void Find(int m, int n, int pos)
    {
    	if (m < 1 || n < 1)
    		return;
    	if (m < n)
    		n = m;
    	if (m <= n) {
    		g_sequence[pos] = m;
    		PrintSequence(pos + 1);
    	}
    	g_sequence[pos] = n;
    	Find(m - n, n - 1, pos + 1);
    	Find(m, n - 1, pos);	
    }