/*在海军节开幕式上，有A、B、C三艘军舰要同时开始鸣放礼炮各n响。
已知A舰每个a秒放一次，B舰每隔b秒放一次，C舰每隔c秒放一次。
假设各炮手对事件的掌握非常准确，请编程计算观众总共可以听到几次炮声。*/
#include<stdio.h>
int main()
{
    int n,a,b,c,i,j,A=0,B=0,C=0,D=0,E=0,z,x,y;
    scanf("%d%d%d%d",&n,&a,&b,&c);
    x=(a>b?a:b)>c?(a>b?a:b):c;/*a,b,c最大值*/
    z=(a>b?b:a)>c?c:(a>b?b:a);/*a,b,c最小值*/
    y=(a>b?b:a)>c?c:((a>b?a:b)>c?c:(a>b?a:b));
    /*利用最小公倍数*/
    for(i=1;i<z*n;i++)
    {
        if(i%x==0&&i%y==0&&i%z==0)
        {
            D+=2;
            continue;
        }
        if(i%x==0&&i%y==0)
            A++;
        if(i%y==0&&i%z==0)
            B++;
        if(i%x==0&&i%z==0)
            C++;
        
    }
    for(j=i;j<=y*n;j++)
    {
        if(j%y==0&&j%z==0)
            E++;
    }
    printf("%d\n",3*n-(A+B+C+D+E));
    return 0;
}

我用另外的方法, 建一个数组, 大小是放炮所需的最长时间, (取a, b, c中最大值乘n), 数组下标代表秒数, 数组初始化为0.
A, B, C在这个时间有放炮就置数组的值为1,
最后统计数组中1的个数,就是听到炮声的次数.

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

#define N 5    // 放炮的次数

int main (void)
{
    int a, b, c;    // 间隔时间
    int *p;         // 数组动态分配
    int i, j, cont = 0;

        scanf("%d%d%d", &a, &b, &c);

        j = (a>b?a>c?a:c:b>c?b:c) * N + 1;  // 求数组的大小, 用a, b, c中的最大值乘次数N, 因为数组下标从0开始, 所以+1.

        p = (int *)calloc(j, sizeof(int));  // 分配内存, 用calloc函数自动初始化数组值为0.
        if (p == NULL)
            exit(1);

        for (i = 1; i <= N; i++)          
            p[a*i] = p[b*i] = p[c*i] = 1;   // 炮声响时置数组值为1
      
        for (i = 0; i < j; i++)             // 统计次数
            if (p[i] == 1) 
                cont++;
        printf("%d\n", cont);

    return 0;
}

 

呵呵，实在不忍再看下去了。这么多天了都在忽视一个条件——“同时开始鸣放礼炮各n响”。

换个说法就是第一响肯定是三炮重叠的。

另外提一句，辗转相除法是作为程序员必须掌握的基础算法之一。

发现了，，我在那篇帖子上已经改了。。哎，，，自己不细心啊。。。

惯性思维了,
这题目的算法能不能说两句?
我之前被楼主的最小倍数搞糊涂了, 现在你又说一个碾转相除法,
我怎么感觉这样也对:

#include <stdio.h>

#define SWAP(p, q, t) t = (p), (p) = (q), (q) = (t)

int main (void)
{
    int n, a, b, c;
    int i, t, cont;

        scanf("%d%d%d%d", &n, &a, &b, &c);
        cont = 1 + 3 * (n-1);
        if (a > b)
            SWAP(a, b, t);
        if (a > c)
            SWAP(a, c, t);
        if (b > c)
            SWAP(b, c, t);

        for (i = 1; i < n; i++) {
            if ((a*i) % b == 0 || (a*i) % c == 0)
                cont--;
            if ((b*i) % c == 0)
                cont--;
        }
        printf("%d\n", cont);

    return 0;
}

只循环n-1次, 比max*n次少多了.

我有点迷糊了, 有不对的地方多多包涵.

[ 本帖最后由 pangshch 于 2014-3-13 16:55 编辑 ]

算法就是求最小公倍数。对a、b、c排下序是应该的，免得总要比较大小。

这里设a < b < c。可以这么想。

首先只考虑间隔为a的船，那n响是没跑的。

再考虑间隔为b的船，第1响之后每隔a、b的最小公倍数的时间会和前一艘重叠1声。那么单独由这船发出的炮声有

n - (n - 1) * a / lcm(a, b) － 1

最后考虑间隔为c的船，第1响之后每隔a、c的最小倍数的时间会和第一艘重叠1声，每隔b、c的最小公倍数会和第二艘重叠1声。注意，这两组里都包含了三艘同时响的次数，所以在计算单独由这艘船发出的炮声时要加回一组。即

n - (n - 1) * a / lcm(a, c) - (n - 1) * b / lcm(b, c) + (n - 1) * a / lcm(a, b, c) - 1

全部加起来就是最后能听到的响声了。下面给出我的示例代码。

提辗转相除法是因为它很简单，却应用的很广泛。这道题的时间复杂度主要就是这个辗转相除法的复杂度，O(log(N))（N是gcd(a, b)或lcm(a, b)里，a、b中最小的那个）

#include <stdio.h>

int lcm(int a, int b)
{
    int ta, tb, r;
    for(ta = a, tb = b; r = ta % tb; ta = tb, tb = r);
    return a / tb * b;
}

int main()
{
    int n, a, b, c, t, ab, ac, bc, abc;
    scanf("%d%d%d%d", &n, &a, &b, &c);
    if(a > b){ t = a; a = b; b = t;}
    if(a > c){ t = a; a = c; c = t;}
    if(b > c){ t = b; b = c; c = t;}
    ab = lcm(a, b);
    ac = lcm(a, c);
    bc = lcm(b, c);
    abc = lcm(ab, ac);
    printf("%d\n", n*3 - (n-1)*a/ab - (n-1)*a/ac - (n-1)*b/bc + (n-1)*a/abc - 2);
    return 0;
}

再不细心，考试铁定挂了