算法练习（五）

一、 愚人节的礼物

题目

　　四月一日快到了，Vayko想了个愚人的好办法——送礼物。嘿嘿，不要想的太好，这礼物可没那么简单，Vayko为了愚人，准备了一堆盒子，其中有一个盒子里面装了礼物。盒子里面可以再放零个或者多个盒子。假设放礼物的盒子里不再放其他盒子。

用()表示一个盒子，B表示礼物，Vayko想让你帮她算出愚人指数，即最少需要拆多少个盒子才能拿到礼物。

样例输入

((((B)()))())
(B)

样例输出

4
1

代码

#include<stdio.h>

int main() {
	char c[1000];
	while(scanf("%s",c) != EOF) {
		int n = 0,i;
		for (i = 0; i < sizeof(c) && c[i] != 'B';i++) {
			if (c[i] == '(') {
				++n;
			} else if (c[i] == ')') {
				--n;
			} else {
				break;
			}
		}
		printf("%d
",n);
	}
	return 0;
}

解题思路

从0开始，对数组元素进行比较，如果是“（”，则计数器+1；如果是“）”，则计数器-1；如果是“B”，则退出并输出计数器的值。

---

二、士兵队列训练问题

题目

　　某部队进行新兵队列训练，将新兵从一开始按顺序依次编号，并排成一行横队，训练的规则如下：从头开始一至二报数，凡报到二的出列，剩下的向小序号方向靠拢，再从头开始进行一至三报数，凡报到三的出列，剩下的向小序号方向靠拢，继续从头开始进行一至二报数。。。，以后从头开始轮流进行一至二报数、一至三报数直到剩下的人数不超过三人为止。
　　

样例输入

2
20
40

样例输出

1 7 19
1 19 37

代码

#include<stdio.h>

int main() {
	int n,i,j,t,x,k=2;
	scanf("%d",&n);
	int q[n];
	int a[n][5000];
	for (i = 0; i < n; i++) {
		scanf("%d",&q[i]);
	}
	for (i = 0; i < n; i++) {
		for (j = 0; j < q[i]; j++) {  // 初始化队伍 
			a[i][j] = j+1;
		}
	}
	for (i = 0; i < n; i++) {
		int m = q[i];
		if (q[i] > 3) {
			while(m > 3) {  // 如果剩余人数大于3人，继续筛选 
				t = 0;
				x = m;
				for (j = 0; j < x; j++) {
					if ((j+1) % k != 0) {
						a[i][t++] = a[i][j];  // 将没有被筛选出的人放置到前端 
					} else {
						--m;
					}
				}
			
				if (k == 2) {
					k = 3;
				} else {
					k = 2;
				}
				
				while (m <= 3 && m > 0) {
					printf("%d ",a[i][3-m]);
					--m;
				}
			}
		} else if (q[i] > 2) {
			printf ("1 2 3");
		} else if (q[i] >1) {
			printf("1 2");
		} else {
			printf("1");
		}
		printf("
");
	}
	return 0;
}

解题思路

解决本题的关键在于利用代码表达筛选规则。记录个数再求其是否满足条件，满足则剔除，不满足则向前推进。

附：图

　　　　　　　　　　　　　　　 　　　　——秒速五厘米