算法入门经典-第四章 例题4-3 救济金发放

救济金的问题抽象出来就是几个人围成一个圈坐,给每一个人编号,一个人从1开始,一个人从n开始,从一开始的点到k时,出列一人,n逆时针点人,点到m出列一人。如果我们出列用删除操作,则大大的降低了效率,我们将删除掉的人用0来代替,当我们遇到0时不点人。

     使用两个方法来分别逆时针顺时针点人,如果是0,则跳过

 

n(n<20)个人站成一圈,逆时针编号为1~n。有两个官员,A从1开始逆时针数,B从n开始顺时针数。在每一轮中,官员A数k个就停下来,官员B数m个就停下来(注意有可能两个官员停在同一个人上)。接下来被官员选中的人(1个或者2个)离开队伍。

输入n,k,m输出每轮里被选中的人的编号(如果有两个人,先输出被A选中的)。例如,n=10,k=4,m=3,输出为4 8, 9 5, 3 1, 2 6, 10, 7。注意:输出的每个数应当恰好占3列。

输入: 
10 4 3

输出:

4 8,9 5,3 1,2 6,10,7。 

注意:输出的每个数应当恰好占3列。 

这个题注意在于编写挑选人员的代码,可以单独做一个函数来实现,题目说站成一圈,这里有一个小技巧用n%b来一圈一圈的计算。 

#include<stdio.h>
#define maxn 22
int n, k, m, a[maxn];
int i;

int go(int p, int d, int t) {//步长为d(顺时针走为-1),走t步
    while(t--) {
        do{ p = (p+d+n-1)%n+1;}//重要!
        while(a[p] == 0);//为了略过以输出的0,走到下一个非0的数字
    }
    return p;
}
int main() {
    while(scanf("%d%d%d", &n, &k, &m) == 3 && n) {
        for(i = 1; i <= n; ++i)
            a[i] = i;
        int left = n;//还剩下的人数
        int p1 = n, p2 = 1;
        while(left) {
            p1 = go(p1, 1, k);
            p2 = go(p2, -1, m);
            printf("%3d", p1);
            left --;
            if(p2 != p1) {
                printf("%3d", p2);
                left--;
            }
            a[p1] = a[p2] = 0;//这句话不能省 
            if(left) printf(",");
        }
        printf("
");
    }

    return 0;

分析:

,每一次点相应的人数,这就涉及到我们点到第某人时,某一是0的情况,所以每一次我们点完人,(即某一次点人算数)都要去判断这一次的点人是否有效,也就是是不是点到了正确的人,如果第某次点人,点到的是0,即无效,要向下过滤至有效的一个人。

     转圈,因为一堆人是围着圈坐的,所以当偶们点到最后一个人n时,我们要从新从第一个人开始点名,其中每一次点名都要判断是否我们到达最后一人,同是对于逆时针点人的我们每一次都要判断是否到达队的首端。

 然后做输出。

    在这次的练习中仍然存在的不足有:

    对于vim的分屏操作不熟练,有待加强,对于调试的s,n到底该一次执行一条指令还是多条指令不清楚。调试效率低。

经验:

    对于数数的操作:while(n--)执行的循环次数是n次;

                            当p指向的是当前的位置m时,数k个人后,当前的位置应该是k+m;也就是执行k次循环。

                             当我们点人时从1开始点人的话,点到k人应该是0+k;

                            对于数组的使用我们在实操时往往会选择比题目预设大1;

原文地址:https://www.cnblogs.com/is-Tina/p/7421024.html