| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 4071 人关注过本帖, 1 人收藏
标题:关于n的倍数,有没有高效的方法?
只看楼主 加入收藏
搬砖
Rank: 2
等 级:论坛游民
帖 子:68
专家分:37
注 册:2016-10-13
收藏
得分:0 
回复 29楼 吹水佬
我以后要认真读题,不过今次也学到了很多
2016-12-24 00:21
九转星河
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:长长久久
等 级:贵宾
威 望:52
帖 子:5023
专家分:14003
注 册:2016-10-22
收藏
得分:0 
回复 31楼 搬砖
21楼是正解,不超时用21楼~的解法~

[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的 就是这样~2018-08-08更~*/[/code]
2016-12-24 03:32
九转星河
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:长长久久
等 级:贵宾
威 望:52
帖 子:5023
专家分:14003
注 册:2016-10-22
收藏
得分:0 
回复 31楼 搬砖
我结合21楼的思考了一下原理,把每个数累加后%N,然后找出相同的余数就行了,题目难度在于时间问题,21楼善于利用表来解决重复出现数字的问题,程序设计很巧妙,原理不算太难理解,但对于初学者来说写这样的也是挺有难度的,要学习一下~

[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的 就是这样~2018-08-08更~*/[/code]
2016-12-24 03:41
吹水佬
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:451
帖 子:10607
专家分:43182
注 册:2014-5-20
收藏
得分:7 
常理算法好理解,也不复杂,主要就两个环节,组统计和打印输出,其他的也就是在转圈。
#include <stdio.h>

void _combine(int *a, int n, int m, int mul)
{
    int i, j, sum;
    for (i=0; i<n-m+1; i++)
    {
            //计算一组
        sum = 0;
        for (j=i; j<i+m; j++)
            sum += a[j];
            //如果这组符合要求就打印输出
        if (sum%mul == 0)
        {
            printf("\n%d\n%d\n", m, i+1);
            for (j=i; j<i+m; j++)
                printf("%d+", a[j]);
            printf("\b \b=%d (%d*%d)\n", sum, sum/mul, mul);
        }
    }
}

main()
{
    int a[]={2,5,6,3,18,7,11,19};
    int n=sizeof(a)/sizeof(int);
    int i;
    for (i=0; i<n; i++)
        printf("%d ", a[i]);
    printf("\nN = %d\n", n);
    for (i=0; i<n; i++)
        _combine(a, n, i+1, n);
}
2016-12-24 07:42
搬砖
Rank: 2
等 级:论坛游民
帖 子:68
专家分:37
注 册:2016-10-13
收藏
得分:0 
回复 34楼 吹水佬
明白
2016-12-24 10:30
搬砖
Rank: 2
等 级:论坛游民
帖 子:68
专家分:37
注 册:2016-10-13
收藏
得分:0 
回复 21楼 azzbcc
这个在cb里编辑不成功
2016-12-24 10:33
azzbcc
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:江西财经大学
等 级:贵宾
威 望:81
帖 子:3293
专家分:12919
注 册:2012-11-4
收藏
得分:0 
这样子写呢?

还不行的话就是空间问题,动态申请内存就行了

程序代码:
#include <stdio.h>

#define MAX 10000

int main()
{
    int N = 8;
    size_t A[MAX] = {2, 5, 6, 3, 18, 7, 11, 19};

    unsigned i, sum = 0, sa[MAX + 1] = {0}, ss[MAX][2] = {1}; // ss 记录sum第一次和第二次出现的位置

    for (i = 0; i < N; ++i)
    {
        sum = (sum + A[i]) % N;

        sa[i + 1] = sum;
        if (ss[sum][1])  continue;
        ss[sum][ss[sum][0] != 0] = i + 2;
    }

    for (i = 0; i < N; ++i)
    {
        if (ss[sa[i]][1])
        {
            printf("%u\n%u\n", ss[sa[i]][1] - ss[sa[i]][0], i + 1);
            break;
        }
    }

    return 0;
}


[fly]存在即是合理[/fly]
2016-12-24 10:56
azzbcc
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:江西财经大学
等 级:贵宾
威 望:81
帖 子:3293
专家分:12919
注 册:2012-11-4
收藏
得分:0 
做极限测试的,也放这里吧

程序代码:
#include <time.h>
#include <stdio.h>
#include <stdlib.h>

#define MAX 10000

#define LEN sizeof(ttt) / sizeof(ttt[0])

unsigned ttt[] = {
        8669, 8677, 8681, 8689, 8693, 8699, 8707, 8713, 8719, 8731, 8737, 8741, 8747, 8753, 8761, 8779, 8783, 8803,
        8807, 8819, 8821, 8831, 8837, 8839, 8849, 8861, 8863, 8867, 8887, 8893, 8923, 8929, 8933, 8941, 8951, 8963,
        8969, 8971, 8999, 9001, 9007, 9011, 9013, 9029, 9041, 9043, 9049, 9059, 9067, 9091, 9103, 9109, 9127, 9133,
        9137, 9151, 9157, 9161, 9173, 9181, 9187, 9199, 9203, 9209, 9221, 9227, 9239, 9241, 9257, 9277, 9281, 9283,
        9293, 9311, 9319, 9323, 9337, 9341, 9343, 9349, 9371, 9377, 9391, 9397, 9403, 9413, 9419, 9421, 9431, 9433,
        9437, 9439, 9461, 9463, 9467, 9473, 9479, 9491, 9497, 9511, 9521, 9533, 9539, 9547, 9551, 9587, 9601, 9613,
        9619, 9623, 9629, 9631, 9643, 9649, 9661, 9677, 9679, 9689, 9697, 9719, 9721, 9733, 9739, 9743, 9749, 9767};

void init(unsigned N, unsigned A[])
{
    unsigned i;

    srand((unsigned int) time(NULL));
    for (i = 0; i < N; ++i)
    {
        A[i] = ttt[rand() % LEN] * ttt[rand() % LEN] + ttt[rand() % LEN];
    }

    for (i = 0; i < N; ++i)
    {
        printf("%u%c", A[i], "\n "[i % 10 < 9]);
    }
    printf("\n\n");
}

void display(unsigned sa[], unsigned ss[][2], unsigned N)
{
    unsigned i, j;

    printf("r ");
    for (i = 0; i <= N; ++i)
    {
        printf("%4u%c", sa[i], "\n "[i < N]);
    }
    for (i = 0; i < 2; ++i)
    {
        printf("%d ", i + 1);
        for (j = 0; j <= N; ++j)
        {
            printf("%4u%c", ss[sa[j]][i], "\n "[j < N]);
        }
    }
    printf("\n");
}

int main()
{
    unsigned N = ttt[rand() % LEN], A[MAX];

    unsigned i, sum = 0, sa[MAX + 1] = {0}, ss[MAX][2] = {1}; // ss 记录sum第一次和第二次出现的位置

    init(N, A);

    for (i = 0; i < N; ++i)
    {
        sum = (sum + A[i]) % N;

        sa[i + 1] = sum;

        if (ss[sum][1]) continue;
        ss[sum][ss[sum][0] != 0] = i + 2;
    }

    display(sa, ss, N);

    for (i = 0; i < N; ++i)
    {
        if (ss[sa[i]][1])
        {
            printf("%u\n%u\n", ss[sa[i]][1] - ss[sa[i]][0], i + 1);
            break;
        }
    }

    return 0;
}


[fly]存在即是合理[/fly]
2016-12-24 11:27
九转星河
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:长长久久
等 级:贵宾
威 望:52
帖 子:5023
专家分:14003
注 册:2016-10-22
收藏
得分:0 
回复 38楼 azzbcc
怎么感觉越写越复杂了,难道这题本来就很难么~

[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的 就是这样~2018-08-08更~*/[/code]
2016-12-24 11:37
azzbcc
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:江西财经大学
等 级:贵宾
威 望:81
帖 子:3293
专家分:12919
注 册:2012-11-4
收藏
得分:0 
回复 39楼 九转星河
没有,我习惯自己写测试数据,上面那个大部分都是测试代码,核心还是那几行


[fly]存在即是合理[/fly]
2016-12-24 11:41
快速回复:关于n的倍数,有没有高效的方法?
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.035831 second(s), 8 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved