C语言——习题练习（一）

习题：

现在有两种面值的邮票，一种为8角，一种为6角。你要付n角的邮资（不能多付也不能少付），请给出邮票张数最少的方案。如果没有正好的方案则输出-1。

输入格式:

只有一行，为若干个整数（至少有两个）。这些整数最后一个整数一定是-1（输入结束标志，无需处理），其他整数均大于0，这些大于0的整数代表邮资。

输出格式:

若干行，每行依次对应输入的一个邮资，如果该邮资有正好的方案，则为两个用空格分隔的整数，代表张数最少的方案。前边的数字代表需要的8角的邮票的张数，后边的数字代表6角的邮票的张数；如果该邮资没有正好的方案则输出-1。测试用例保证所有整数均可以用int存储。。

输入样例:

24 14 11 -1

输出样例:

3 0
1 1
-1

代码1如下：

#include <stdio.h>
int main()
{
	int n = 0;
	int x, y;
	while (1)
	{
		again:
		scanf("%d", &n);
		if (n != -1)
		{
			for (x = 0; x <=n/6; x++)
			{
				for (y = 0; y <=n/8; y++)
				{
					if ((6*x + 8*y) == n)
					{
						printf("%d %d\n", y, x);
						goto again;
					}
				}
			}
            printf("-1\n");
		}
		else
		{
			break;
		}
	}
	return 0;
}

运行结果如下：

代码2如下：

#include <stdio.h>
int ba;
int main() {
	int n;
	while (1) {
		scanf("%d", &n);
		if (n == -1)break;
		ba = n / 8;
		int tt = 1;
		while (ba >= 0) {
			if ((n - ba * 8) % 6 == 0) {
				printf("%d %d\n", ba, (n - ba * 8) / 6);
				tt = 2;
				break;
			}
			ba -= 1;
		}
		if (tt == 1)printf("-1\n");
	}
}

运行结果如下：

下面进行代码解读：

代码1：

x代表6角面值，y代表8角面值，n代表总面值，在外层循环中，循环变量x的取值范围是从0到n/6，内层循环中循环变量y的取值范围是从0到n/8。这种按照从小到大的顺序去遍历所有可能的x和y的取值组合，本质上是一种穷举的方式。由于循环是从最小的可能值（也就是0）开始逐步增加，当第一次找到满足6*x + 8*y == n条件的x和y时，它们在当前的穷举顺序下就是使得x + y相对最小的组合。

举例来说，如果n = 24，外层循环x会先取0，然后内层循环y从0开始取值，当y = 3（此时8 * 3 = 24 ，x还是0）时就满足条件了，因为循环从最小开始尝试，所以优先找到的就是数之和相对最小的组合（这里x + y = 0 + 3 = 3），不会出现先找到其他更大和的组合情况，比如x = 4（6 * 4 = 24，此时y = 0，x + y = 4 ）这种相对和更大的情况会在满足条件的更小组合之后才会去尝试到（但因为已经找到组合并输出了，后续更大和的情况就不会再去管了）。

因此应该在x循环下遍历y才能保证最小。

代码2：

外层循环对 ba（y 的取值调整）的控制：代码中首先计算 ba = n / 8，这里是确定了 y（也就是对应 8 的倍数的数量）的初始最大可能值。然后进入 while (ba >= 0) 循环，这个循环会从这个最大可能值开始，逐步递减 ba（也就是 y 的取值逐步减少）。这种从大到小尝试 y 的取值方式是关键所在。因为在尝试用 6 和 8 的倍数组合去凑 n 的过程中，优先考虑让较大的数（这里是 8）尽可能多地参与，这样得到的组合中两个数的和相对会更小。例如，如果 n = 24，一开始 ba = 24 / 8 = 3，此时会先检查 3 个 8 能否满足情况，发现满足（因为 24 - 3 * 8 = 0，0 能被 6 整除），那就直接找到了 y = 3，x = 0 的组合（x + y = 3），这就是数之和最小的组合。如果不先从大的 y 值开始尝试，可能会先找到其他 x、y 值更大的组合来凑 n，比如先从 y = 0 开始尝试，然后不断增加 x 去凑，可能就会先找到 x = 4，y = 0 这样 x + y = 4 的相对更大的组合了。
内层条件判断对 x（(n - ba * 8) % 6 == 0 部分）的确定：在每次 ba（y 的取值）确定后，通过 (n - ba * 8) % 6 == 0 这个条件来判断，剩余的数（也就是 n 减去当前 y 个 8 之后剩下的部分）能否被 6 整除。如果能整除，那就意味着找到了满足 6 * x + 8 * y = n 的 x（即 (n - ba * 8) / 6）和 y（即 ba）的一组值。而且由于外层循环是从大到小递减 y 的取值，一旦找到满足条件的组合，就是按照这种有利于数之和最小的顺序下最先出现的组合，后续即使继续递减 y 再找，得到的组合中两数之和也只会更大（因为优先是让较大数 8 尽可能多地参与凑数了），所以此时找到的组合就是 x + y 最小的组合。