Monthly Archives: October 2014

子问题完整性

处理递归问题时,将原问题切割成若干子问题,即要保证完整又要避免重叠。

找零钱问题:
Given an infinite number of quarters (25 cents), dimes (10 cents), nickels (5 cents)
and pennies (1 cent), write code to calculate the number of ways of representing n
cents.

如下切割将导致子问题重叠:
f(n) = f(n-25) + f(n-10) + f(n-5) + f(n-1)

f(0) = 1: {}
f(5) = 2: {5}, {1,1,1,1,1}
f(9) = 2: {5,1,1,1,1}, {1,1,1,1,1,1,1,1,1}
f(10) = f(0) + f(5) + f(9) = 1 + 2 + 2 = 5,这是错误的

f(10) = 4: {10}, {5, 5}, {1,1,1,1,1,5}, {1,1,1,1,1,1,1,1,1,1}
这是组合问题不是排列问题,{1,1,1,1,1,5}和{5,1,1,1,1,1}是重复的
组合问题要用“计数“的方法来将原问题切割成子问题。
排列问题要用“顺序”的方法来切割,如跳台阶问题: f(n)=f(n-1)+f(n-2),表示从上一步跳到这一步是经过1个台阶或者2个台阶。

正确的切割方法是:
f(n, 25) = sum{f(n-i*25, 10)}, 0<=i<=n/25 f(n, 10) = sum{f(n-i*10, 5)}, 0<=i<=n/10 f(n, 5) = sum{f(n-i*5, 1)}, 0<=i<=n/5 f(n, 1) = 1 f(n,25)表示将原问题切割成(n/25+1)个子问题 使用0个25分硬币, 1个25分硬币,2个25分硬币,3个25分硬币 .... n/25个25分硬币 这样切割是完整的,而且不重叠。

/* Copyleft: Ming Lin <minggr@gmail.com> */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/* Wrong */
int all_ways(int n)
{
	int total = 0;
	int ways[26];
	int i;
	int k;
	
	for (i = 1; i <= n; i++) {
		if (i < 5)
			ways[i] = 1;
		else if (i == 5)
			ways[i] = ways[i-1] + 1;
		else if (i < 10)
			ways[i] = ways[i-1] + ways[i-5];
		else if (i == 10)
			ways[i] = ways[i-1] + ways[i-5] + 1;
		else if (i < 25)
			ways[i] = ways[i-1] + ways[i-5] + ways[i-10];
		else if (i == 25)
			ways[i] = ways[i-1] + ways[i-5] + ways[i-10] + 1;
		else {
			total = ways[1] + ways[5] + ways[10] + ways[25];
			k = 25;
			while (k >= 2) {
				ways[k] = ways[k-1];
				k–;
			}
			ways[k] = total;
		}
	}

	return total;
}

/* Wrong */
int all_ways2(int n)
{
	int *table = malloc(sizeof(int) * n);
	int total;
	int i;

	for (i = 0; i < 5; i++)
		table[i] = 1;

	for (i = 5; i < 10; i++)
		table[i] = 2;

	for (i = 10; i < 25; i++)
		//table[i] = table[i-10] + table[i-5] + table[i-1];
		table[i] = 4;

	for (i = 25; i < n; i++)
		table[i] = table[i-25] + table[i-10] + table[i-5] + table[i-1];

	for (i = 0; i < n; i++)
		printf(“table[%02d]: %d\n”, i, table[i]);

	total = table[n-1];
	free(table);

	return total;
}

/* Correct */
int makeChange(int n, int denom) {
	int next_denom = 0;
	int ways = 0;
	int i;

	switch (denom) {
	case 25:
		next_denom = 10;
		break;
	case 10:
		next_denom = 5;
		break;
	case 5:
		next_denom = 1;
		break;
	case 1:
		return 1;
	}

	for (i = 0; i * denom <= n; i++) {
		ways += makeChange(n – i * denom, next_denom);
	}
	return ways;
}

int main()
{
	int n = 30;

	printf(“n=%d, total %d ways\n”, n, all_ways(n));
	printf(“n=%d, total %d ways\n”, n, all_ways2(n));
	printf(“n=%d, total %d ways\n”, n, makeChange(n, 25));
	return 0;
}