精华内容
下载资源
问答
  • 循环节长度以及循环节

    千次阅读 2019-07-24 13:17:34
    循环节长度 两个整数做除法,有时会产生循环小数,其循环部分称为:循环节。 比如,11/13=6=>0.846153846153….. 其循环节为[846153] 共有6位。 这是一道蓝桥杯的题目,试卷上是一个填空题,思路就是不断的对...

    循环节长度

    两个整数做除法,有时会产生循环小数,其循环部分称为:循环节。 
    比如,11/13=6=>0.846153846153….. 其循环节为[846153] 共有6位。 
     

    这是一道蓝桥杯的题目,试卷上是一个填空题,思路就是不断的对除数取余,然后乘10后再取余,直到余数在之前出现过或者为0 结束。

    为什么是这样的呢: 我来试着解释一下:

    首先我先对上面写的思路模拟一下,好更好的明白我在说的是什么:

           n = 11%13    商 0 余 11

           n = 110%13  商 8 余 6

           n = 60%13    商 4 余 8

           n = 80%13    商 6 余 2

           n = 20%13    商 1 余 7

           n = 70%13    商 5 余 5

           n = 50%13    商 3 余 11

           看到上面的余数为11,就又回到了第一次取余的余数结果。 另外注意上面每次取余运算获得的商,连起来就是0.846153 小数部分就是循环节,可以用计算器除以下看是不是循环节。

    那么为什么,这样就能算出来呢?

           由题知,循环节存在于小数部分,不含整数部分,而在做除法的时候,小数部分是由余数除以除数产生的。这样的话只要取出余数就取出了小数部分,然后要做的就是从小数部分中取出循环节,怎末取?

    假设x是m/n的小数部分,那么x*n就是余数,而((x*n)*10)/n 的商部分就是小数部分的第一位取出来了,然后循环,如果发现余数出现过了,那么就说明下面要重复循环了。

    这是题目的代码:

    public static int f(int n, int m)
    {
        n = n % m;	
        Vector v = new Vector();
    
        for( ; ; )
        {
            v.add(n);   # 每次把余数加进去
            n *= 10;    
            n = n % m;  # 算出下次循环的余数
            if(n==0) return 0;  # 说明没有循环节,有循环节不会出现整除的
            if(v.indexOf(n)>=0) _________________________________ ; //填空
        }
    }
    
    #  横线上填:  return v.size() 

    如果要求出循环节是什么:

    public static int f(int n, int m)
    {
        n = n % m;	
        Vector v = new Vector();
        Vector w = new Vector();
    
        for(;;)
        {
            v.add(n);   # 每次把余数加进去
            n *= 10;    
            n = n % m;  # 算出下次循环的余数
            tem = n / m
            if(n==0) return 0;  # 说明没有循环节,有循环节不会出现整除的
            if(v.indexOf(n)>=0) _________________________________ ; //填空
            w.add(tem)   # 容器w里装的就是循环节
        }
    }
    
    #  横线上填:  return v.size() 
    展开全文
  • 循环节

    千次阅读 2018-08-11 16:10:22
    经典问题 : 给出一个由某个循环节构成的字符串,要你找出最小的循环节,例如 abababab 最小循环节当是 ab ,而类似 abab 也可以成为它的循环节,但并非最短。   分析 : 对于上述问题有两个结论  如果对于next...

    转自https://www.cnblogs.com/Rubbishes/p/7564992.html

    经典问题 : 给出一个由某个循环节构成的字符串,要你找出最小的循环节,例如 abababab 最小循环节当是 ab ,而类似 abab 也可以成为它的循环节,但并非最短。

     

    分析 :

    对于上述问题有两个结论 

    如果对于next数组中的 i, 符合 i % ( i - next[i] ) == 0 && next[i] != 0 , 则说明字符串循环,而且

    循环节长度为:    i - next[i]

    循环次数为:       i / ( i - next[i] )

    水平有限,用自己的语言描述怕有差错,给出一个参考博客  ==>  http://www.cnblogs.com/jackge/archive/2013/01/05/2846006.html

     

    再抛一个问题 : 有没有想过对于一个不完整的循环串要补充多少个才能使得其完整?

    答案是==>(循环节长度) - len%(循环节长度) 即 (len - next[len]) - len%(len - next[len])

    为什么? (以下胡扯,看不懂就掠过吧.........)

    首先考虑整串就是循环节构成的情况,类似 abcxabcx 观察构造出来的next值显然满足上式,得出答案 0

    那现在考虑不完整的情况,例如 abcabca 、其 next 值为 -1 0 0 0 1 2 3 4 。现在考虑末尾的 a,若没有它,而是将 c 作为末尾则会在 len 失配的时候会回溯道下一个循环节的末尾即 abca , 那现在多了一个a,那么回溯当然也应该是(循环节长度 + 1) 即 abcab,故 len 那里无论是否刚好为循环节的末尾,只是个"残"的末尾,未圆满的循环节,len-next[len]也是循环节长度,那需要补多少个呢?现在就很显然了!下面相关题目的 ① 就是这样的一个问题。

     

    相关题目 : 

    ① HDU 3746 Cyclic Nacklace

    题意 : 给出一个字符串,问你最少补充多少个字母才能使得字符串由两个或者以上的循环节构成

    分析 : 由结论可知,如果字符串循环,那么最小循环节的长度为 len - next[len] ,并且这个字符串总长能被循环节长度整除说明字符串已经循环,否则 len % (len - next[len]) 则为多出来的部分,例如 abcabcab ==> len - next[len] = 3,而 len % 3 == 2 很明显就是余出来两个,这两个应当是循环节的头两个字母,对于其他串也可以自己模拟看看,所以需要补充的就是 循环节长度 - 多余出来的长度

    复制代码

    #include<stdio.h>
    #include<string.h>
    using namespace std;
    const int maxn = 1e5 + 10;
    char mo[maxn];
    int Next[maxn], moL, nCase;
    inline void GetNext()
    {
        int i = 0, j = -1;
        Next[i] = j;
        while(i < moL){
            while( j!=-1 && mo[i]!=mo[j]) j = Next[j];
            Next[++i] = ++j;
        }
    }
    int ans()
    {
        GetNext();
        if(Next[moL] == 0) return moL;
    
        int Period_len = moL - Next[moL];
        int Remain = moL % Period_len;
    
        if(Remain == 0) return 0;
        return Period_len - Remain;
    }
    int main(void)
    {
        scanf("%d", &nCase);
        while(nCase--){
            scanf("%s", mo);
            moL = strlen(mo);
            printf("%d\n", ans());
        }
        return 0;
    }

    复制代码

     

    ② POJ 1961 Period

    题意 : 给出一个字符串,叫你给出这个字符串存在的不同循环节长度以及个数 ( 循环节构成的不一定是整个字符串,也有可能是其子串 )

    分析 : 根据以上的结论,我们只要让构造出字符串的next数组,而后一个for循环判断当前长度和当前最小循环节长度是否是倍数关系,即 i % ( i - next[i] ) == 0 && next[i] != 0,就能判断是否为一个循环节了,循环节的长度自然是 i / (i-next[i])

    复制代码

    #include<stdio.h>
    using namespace std;
    const int maxn = 1e6 + 10;
    char mo[maxn];
    int Next[maxn], moL;
    inline void GetNext()
    {
        int i = 0, j = -1;
        Next[i] = j;
        while(i < moL){
            while( j!=-1 && mo[j]!=mo[i] ) j = Next[j];
            Next[++i] = ++j;
        }
    }
    inline void PrintAns()
    {
        GetNext();
        int Period;
        for(int i=1; i<=moL; i++){
            if(Next[i] != 0){
                Period = i - Next[i];
                if(i % Period == 0){
                    printf("%d %d\n", i, i/Period);
                }
            }
        }puts("");
    }
    int main(void)
    {
        int Case = 1;
        while(~scanf("%d", &moL) && moL){
            scanf("%s", mo);
            printf("Test case #%d\n", Case++);
            PrintAns();
        }
        return 0;
    }

    复制代码

     

    ③ HUST 1010  The Minimum Length

    题意 : 假设 A 是一个循环字符串,现在截取 A 的某一段子串 B 出来,给出 B 问你构成 A 的循环节的最小长度是多少?

    分析 : 既然是循环串当中截取出来的,那么只要根据结论公式算出最小循环节长度即是答案,可以证明证明这样做永远是最优的。以下代码由于HUST OJ崩了,所以不知道结果

    复制代码

    #include<stdio.h>
    #include<string.h>
    #include<iostream>
    using namespace std;
    const int maxn = 1e6 + 10;
    int Next[maxn], moL;
    char mo[maxn];
    inline void GetNext()
    {
        int i = 0, j = -1;
        Next[i] = j;
        while(i < moL){
            while(j!=-1 && mo[i]!=mo[j]) j = Next[j];
            Next[++i] = ++j;
        }
    }
    int Ans()
    {
        GetNext();
        if(Next[moL] == 0) return moL;
        else return moL - Next[moL];
    }
    int main(void)
    {
        while(~scanf("%s", mo)){
            moL = strlen(mo);
            printf("%d\n", Ans());
        }
        return 0;
    }

    复制代码

     

    ④ POJ 2406 Power String

    题意 : 给你一个字符串,问你它由多少个相同的字符串拼接而成

    分析 : 直接找算出最小循环节长度,如果字符循环,则答案为 len / (循环节长度) ,而对于 len % (循环节长度) != 0 和 next[len] == 0 的情况答案就是 1 了

    复制代码

    #include<string.h>
    #include<stdio.h>
    using namespace std;
    const int maxn = 1e6 + 10;
    int Next[maxn], moL;
    char mo[maxn];
    inline void GetNext()
    {
        int i = 0, j = -1;
        Next[i] = j;
        while(i < moL){
            while(j!=-1 && mo[i]!=mo[j]) j = Next[j];
            Next[++i] = ++j;
        }
    }
    int Ans()
    {
        GetNext();
        if(Next[moL] == 0) return 1;
        int Period = moL - Next[moL];
        if(moL % Period != 0) return 1;
        return moL / Period;
    }
    int main(void)
    {
        while(scanf("%s", mo) && mo[0]!='.'){
            moL = strlen(mo);
            printf("%d\n", Ans());
        }
        return 0;
    }

    复制代码

     

    ⑤ POJ 2752 Seek the Name, Seek the Fame

    题意 : 给出一个字符串,问你所有关于这个字符串的前缀和后缀相同的长度,比如 abcab 有 1 "a"、2 "ab"、5 "abcab"

    分析 : 这里就要巧妙利用到 next 数组的性质了,根据next数组定义可以知道 next[len] 表示一个从头开始长度为 next[len] 的前缀和相同长度的后缀相等,那么next[ next[len] ]呢?next[ next[ next[len] ] ]呢?这里的一层层嵌套实际上都是一个长度为 next[ next[len] ] 或者 长度 next[ next[ next[len] ] ]的前缀和后缀相等,自己构造个数组画画图也能得出来这个规律,那么到此,这个问题是不是被圆满的解决了呢!

    复制代码

    #include<string.h>
    #include<stack>
    #include<stdio.h>
    using namespace std;
    const int maxn = 4e5 + 10;
    char mo[maxn];
    int Next[maxn], moL;
    inline void GetNext()
    {
        int i = 0, j = -1;
        Next[i] = j;
        while(i < moL){
            while(j!=-1 && mo[j]!=mo[i]) j = Next[j];
            Next[++i] = ++j;
        }
    }
    inline void PrintAns()
    {
        moL = strlen(mo);
        GetNext();
        int tmp = Next[moL];
        stack<int> ans;///根据题目要求需要递增输出长度,而我们得出的答案顺序正好相反,所以利用栈存储
        while(tmp != -1){///直到头为止
            ans.push(tmp);
            tmp = Next[tmp];
        }
        while(!ans.empty()){
            int Top = ans.top(); ans.pop();
            if(Top) printf("%d ", Top);
        }
        printf("%d\n", moL);
    }
    int main(void)
    {
        while(~scanf("%s", mo)){ PrintAns(); }
        return 0;
    }
    展开全文
  • 循环节长度

    千次阅读 2017-03-25 20:49:39
    循环节长度 ps:2015年蓝桥杯Java语言B组第三题 两个整数做除法,有时会产生循环小数,其循环部分称为:循环节。 比如,11/13=6=>0.846153846153..... 其循环节为[846153] 共有6位。 下面的方法,可以求出循环节...
    循环节长度
    

    ps:2015年蓝桥杯Java语言B组第四题


    两个整数做除法,有时会产生循环小数,其循环部分称为:循环节。
    比如,11/13=6=>0.846153846153.....  其循环节为[846153] 共有6位。
    下面的方法,可以求出循环节的长度。


    请仔细阅读代码,并填写划线部分缺少的代码。

    public static int f(int n, int m) {
    		n = n % m;
    		Vector<Integer> v = new Vector<Integer>();
    
    		for (;;) {
    			v.add(n);
    			n *= 10;
    			n = n % m;
    			if (n == 0)
    				return 0;
    			if (v.indexOf(n) >= 0)
    			__________________ ;  //填空
    		}
    	}



    注意,只能填写缺少的部分,不要重复抄写已有代码。不要填写任何多余的文字。


    因为在一个循环节中,可能会有重复的数字,比如3/17,所以不能根据小数点后的数字来分析。
    本题是通过看每次计算的余数是否与之前相等,来判断循环节长度的。因为余数一旦相等,乘以十后除以除数也必然相等。


    答案:return v.size()-v.indexOf(n);

    展开全文
  • 寻找循环节

    千次阅读 2013-11-15 18:59:18
    碰到递推大数再取模的问题,如果MOD不是特别大的情况下,而且f[i]的值比较连续的情况下可以考虑采用寻找循环节的方法解题,当然为了提高程序的效率,递推的过程可以采用矩阵快速幂(请参考矩阵快速幂II);...

    链接:http://acm.hrbust.edu.cn/index.php?m=ProblemSet&a=showProblem&problem_id=1100


    碰到递推大数再取模的问题,如果MOD不是特别大的情况下,而且f[i]的值比较连续的情况下可以考虑采用寻找循环节的方法解题,当然为了提高程序的效率,递推的过程可以采用矩阵快速幂(请参考矩阵快速幂II;


    寻找循环节的方法如下:


    #include <stdio.h>
    #define MOD 10007  //宏定义;


    int f[20016] = {1,2,4};  //对数组的声明及前三项初始化;


    int main()
    {
    int n, t;
    for (int i=3; ; i++) {
    f[i] = (f[i-1] + f[i-2] + 1) % MOD;  //递推表达式,及每次取模;
    /*
    if (f[i]==2 && f[i-1]==1) {  //寻找循环节;
                printf("%d\n", i);
    break;
    }
    */
    }
    while(scanf("%d", &t) != EOF) {
    while(t--) {
    scanf("%d", &n);
    printf("%d\n", f[n%20016]);  //因为n的范围很大,所以在输出f[n]之前先对n进行循环节取模;
    }
    }
    return 0;
    }


    矩阵快速幂的递推法:


    #include<stdio.h>

    #include<math.h>

    const int MAX=10007;

    int A[1][3];

    int B[3][3]={0,1,0,1,1,0,0,1,1};

    int C[3][3];

    void mul(int a[][3],int b[][3],intc[][3]){//功能,求出a*b存在c里

       int i,j,h;

       for(i=0;i<3;i++)

           for(j=0;j<3;j++){

                c[i][j]=0;

               for(h=0;h<3;h++)

                    c[i][j]+=a[i][h]*b[h][j];

               c[i][j]%=MAX;

           }

    }

    void qiu(int x,int a[][3]){//求出 B 的x次方,存在a里(二分

       int i,j;

       int b[3][3];

       if(x==1){//x等于1时,直接把B存在a里

           for(i=0;i<3;i++)

               for(j=0;j<3;j++)

                    a[i][j]=B[i][j];

           return;

        }

       if(x%2==0){

           qiu(x/2,b);

           mul(b,b,a);

        }

       else{

           qiu(x-1,b);

           mul(b,B,a);

        }

    }

    int main(){

       int c[3][3];

       int i,j,h,l,p,n,N;

       while(scanf("%d",&N) != EOF)

       while(N--){

           scanf("%d",&p);

           A[0][0]=0;A[0][1]=1;A[0][2]=1;

           qiu(p+1,C);//表示求f[n];

           mul(A,C,c);

           n = c[0][0]%MAX;

           printf("%d\n", n);

        }

       return 0;

    }


    展开全文
  • C语言求循环节

    千次阅读 2019-03-04 19:42:48
    C语言求分数的循环节题目代码实现测试结果 题目 输入一些分数,输出该分数的循环节。 比如: input:1/3 1/6 6/11 output:0.(3) output:0.1(6) output:0.(54) 思路就是模仿小数除法的过程,通过将每一次除法...
  • 输入整数a和b(0 ...循环除数加一次,若余数为0,则循环节长度为1,若当前得到的余数已经存在,则有循环节,求出2个相同余数的距离即为循环节长度。  这个主要是怎么寻找循环节,在除法计算的过程
  • 哈哈,题目是这样的给你一下小数,然后请告诉我分别告诉我这个小数的循环节的循环次数、循环节以及循环节长度 输入 输入包括多组测试数据每组测试数据1行,包括一个小数,小数的长度不超过200,小数大于0小于100 ...
  • 循环节的长度

    千次阅读 2019-03-18 17:20:56
    循环节长度 两个整数做除法,有时会产生循环小数,其循环部分称为:循环节。 比如,11/13=6=>0.846153846153..... 其循环节为[846153] 共有6位。 下面的方法,可以求出循环节的长度。 请仔细阅读代码,并填写...
  • 最小循环节

    千次阅读 2013-07-20 12:13:23
    hdu 3746(KMP) 最小循环节 分类: 数据结构 2013-04-05 20:01 157人阅读 评论(0) 收藏 举报 ACM算法数据结构KMP最小循环节 http://acm.hdu.edu.cn/showproblem.php?pid=3746 /* 通过KMP中的 next ...
  • 八、求循环节

    2020-07-23 15:21:44
    要求: 编写一个尽可能高效的查找循环节起始的函数: NODE * find( NODE * head, int * n ) 。函数的返回值为循环节的起点(即图中的指针p),n为循环节的长度。 说明:提交程序时请同时提交将分
  • 字符串最短循环节

    千次阅读 2019-09-28 10:55:27
    循环节与最短循环节: 若某个字符串是由某个子串循环构成的,那么就称该子串为原串的循环节,长度最短的循环节就是最短循环节。 如abababab,abab和ab都是原串的循环节,而最短循环节是ab。 结论: 如果字符串 s 有...
  • python再计算无限循环小数的循环节

    千次阅读 2017-05-01 23:02:00
    循环节: 如果无限小数的小数点后,从某一位起向右进行到某一位止的一节数字循环出现,首尾衔接,称这种小数为循环小数,这一节数字称为循环节。 #寻找1000以内的n,使得1/n的循环小数节长度最长#问题化简,首先...
  • 如何利用KMP的next求字符串的循环节

    万次阅读 2017-05-23 20:19:36
    利用KMP算法中的next值可以求出字符串的循环节,如ababab的循环节为ab,abcd的循环节为abcd,具体做法如下:假设字符串的长度为len,next[len]为字符串的最后一个字符的下一个字符的next值(下标从0开始),如果len ...
  • 字符串循环节

    千次阅读 2015-11-21 14:27:26
    字符串若存在循环节,则必有最小循环节,其余循环节均为最小循环节的倍数。 字符串看成一个映射i->s[i] 这样这个问题就类似于函数的周期性... 证明: 若X,Y是字符串的循环节则有 s[i]=s[i+x]=s[i+y] x=gcd*p y=gcd...
  • 最长循环节模版

    千次阅读 2018-09-16 16:27:15
    //则存在一个循环节,求&lt;=n的数中,倒数循环节长度最长的那个数, //假如存在多个最优的答案,输出所有答案中最大的那个数。  /* *如果1&lt;=b&lt;a,a没有2或5的质因子,并且a与b互质,那么b/a 的...
  • Java实现有理数的循环节

    万次阅读 多人点赞 2019-07-26 22:39:32
    1/7 = 0.142857142… 是个无限循环小数。 任何有理数都可以表示为无限循环小数的形式。 本题目要求即是:给出一个数字的循环小数表示法。...程序输出两个整数做除法产生的小数或无限循环小数(循环节用...
  • 如题:1035 最长的循环节 基准时间限制:1 秒 空间限制:131072 KB 分值: 20 难度:3级算法题正整数k的倒数1/k,写为10进制的小数如果为无限循环小数,则存在一个循环节,求&lt;=n的数中,倒数循环节长度...
  • 循环节 - 【数论】

    千次阅读 2019-07-30 10:15:28
    循环节 引言: 小学的规律题大家不陌生吧,经常跟取余数挂钩的那种,其实挺简单的。比如给你一个序列1 3 5 7 9 1 3 5 7 9 1 3 …这就是小学题目嘛,对吧看着好简单。 循环节: 其实现在很多题目也要用到同样的方法,...
  • 循环节(SDUT 2747)

    千次阅读 2014-06-16 13:21:34
    循环节 Time Limit: 1000ms Memory limit: 65536K 有疑问?这里^_^ 题目描述 X最近爱上了一种奇怪的游戏,就是找出一个字符串中的最小循环节。 对于最小循环节的定义:对于字符串A存在字串B,使得...
  • java实现第六届蓝桥杯循环节长度

    万次阅读 多人点赞 2019-07-29 12:43:22
    循环节长度 两个整数做除法,有时会产生循环小数,其循环部分称为:循环节。 比如,11/13=6=>0.846153846153..... 其循环节为[846153] 共有6位。 下面的方法,可以求出循环节的长度。 请仔细阅读代码,并填写...
  • kmp求最小循环节

    千次阅读 多人点赞 2017-08-21 19:19:41
    KMP最小循环节、循环周期: 定理:假设S的长度为len,则S存在最小循环节循环节的长度L为len-next[len],子串为S[0…len-next[len]-1]。 (1)如果len可以被len - next[len]整除,则表明字符串S可以完全由...
  • 求循环小数循环节

    千次阅读 2018-02-07 15:10:47
    任何有理数都可以表示为无限循环小数的形式。   本题目要求即是:给出一个数字的循环小数表示法。   例如: 输入: 1,5 则输出: 0.2   输入: 1,7 则输出: 0.[142857]   输入: 7...
  • 蓝桥杯-循环节长度

    千次阅读 2018-03-14 11:40:15
    题目如下:循环节长度两个整数做除法,有时会产生循环小数,其循环部分称为:循环节。比如,11/13=6=&gt;0.846153846153..... 其循环节为[846153] 共有6位。下面的方法,可以求出循环节的长度。请仔细阅读代码...
  • 倒数的循环节

    千次阅读 2016-11-08 16:26:53
    单位分数指分子为1的分数。分母为2至10的单位分数的十进制表示如下所示:1/2= 0.5 ...1/10= 0.1这里0.1(6)表示0.166666…,括号内表示有一位循环节。可以看出,1/7有六位循环节。找出正整数d < 100
  • JAVA-获取无限循环小数的循环节

    千次阅读 2020-03-27 11:07:03
    JAVA获取无限循环小数的循环节
  • C语言实现小数转分数,包括带循环节的小数
  • HDU1358KMP求循环节

    千次阅读 2020-07-12 18:26:30
    直接说结论吧,KMP算法的前提是预处理一个next数组,一个字符串长度为len,那么这个字符串的最小循环节就是len-nxt[len]。 因此有: 判断一个字符串是否完全循环可以用 (len%(len-nxt[len]))==0,并且nxt[len]!=0 ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 196,290
精华内容 78,516
关键字:

循环节的点怎么点