| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 4073 人关注过本帖, 1 人收藏
标题:关于n的倍数,有没有高效的方法?
只看楼主 加入收藏
搬砖
Rank: 2
等 级:论坛游民
帖 子:68
专家分:37
注 册:2016-10-13
收藏
得分:0 
回复 37楼 azzbcc
成功了,上面不成功好像是用了c99mode

2016-12-24 11:53
九转星河
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:长长久久
等 级:贵宾
威 望:52
帖 子:5023
专家分:14003
注 册:2016-10-22
收藏
得分:0 
我也重新做了一下~用自己的思路做了一遍,和21楼的写得有点像,虽然比21楼的写得繁琐一点,但感觉理解上来应该比较容易一点~感觉第二次出现的数字下标可以用选择法选择出最小值,这里还可以优化~

程序代码:
#include <stdio.h>
#define S(a) sizeof (a)
#define Max 10000
typedef struct Node
{
    int time1;
    int time2;
}Node;
Node Count[Max+1]={0};
int main()
{
    int a[]={2,3,4,5,6,7,8,9};
    int n=S(a)/S(int);
    int N=8;
    int i=0;
    int sum=0;
    int flag=0;
    int SS=1;
    
    if ((a[0]%=N)==0)
        flag=1;

    for (;i<n-1&&flag==0;i++)
    {
        a[i+1]=(a[i+1]+a[i])%N;
        if (a[i+1]==0)
        {
            SS=i+2;
            flag=1;
            break;
        }
    }

    for (i=0;i<n&&flag==0;i++)
    {
        if (Count[a[i]].time1==0)
            Count[a[i]].time1=i+1;
        else if (Count[a[i]].time2==0)
            Count[a[i]].time2=i+1;
    }

    if (flag)
        printf("%d\n1\n",SS);

    for (i=1;i<n+1&&flag==0;i++)
        if (Count[a[i-1]].time2)
        {
            printf("%d\n%d\n",Count[a[i-1]].time2-Count[a[i-1]].time1,i+1);
            break;
        }

    if (i==n+1)
        printf("No Solution\n");
    return 0;
}


[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的 就是这样~2018-08-08更~*/[/code]
2016-12-24 21:42
xzlxzlxzl
Rank: 15Rank: 15Rank: 15Rank: 15Rank: 15
来 自:湖北
等 级:贵宾
威 望:125
帖 子:1091
专家分:5825
注 册:2014-5-3
收藏
得分:0 
回复 37楼 azzbcc
这算法妙!基本思想应该是:余数相等的两个数差值能被整除。
不过注释掉显示部分的的“break;”语句后显示所有连续的被整除数据段,发现有部分数据不符,情况如下:
起点  个数  符合性
1     4     符合
2     4     符合
3     6     符合
5     4     不符合,和为55
6     4     不符合,没有4个数,和为37

不知道是不是我对程序算法理解有误
2016-12-24 23:29
azzbcc
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:江西财经大学
等 级:贵宾
威 望:81
帖 子:3293
专家分:12919
注 册:2012-11-4
收藏
得分:0 
回复 43楼 xzlxzlxzl
怎么说呢,5 4其实就是1 4啊,因为第5个余数前面已经出现过了,所以有这种情况,避免的办法是sa数组不要重复,存入时加一个条件判断,但是这是没必要的,因为如果无解,就一定不重复,如果重复,早就break了


[fly]存在即是合理[/fly]
2016-12-25 08:00
搬砖
Rank: 2
等 级:论坛游民
帖 子:68
专家分:37
注 册:2016-10-13
收藏
得分:0 
回复 43楼 xzlxzlxzl
我也查到了,这是抽屉原理
2016-12-25 15:27
快速回复:关于n的倍数,有没有高效的方法?
数据加载中...
 
   



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

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