精华内容
下载资源
问答
  •  输入整数a和b,输出a/b的循环小数表示以及其循环节长度。例如 a=5 b=43 小数表示为0.(116279069767441860465),循环节长度为21; 分析:  长除法的计算过程  ①mod = a%b;  ②小数 = (mod*10) /...

    问题:

      输入整数a和b,输出a/b的循环小数表示以及其循环节长度。例如 a=5 b=43 小数表示为0.(116279069767441860465),循环节长度为21;

     

    分析: 

      长除法的计算过程

     

        ①mod = a%b;

     

        ②小数 = (mod*10) / b;

     

        ③mod = (mod*10)%b;

     

      循环②③步,当出现重复的余数的时候,也就是循环节出现了

    注意事项:

      当循环上述2、3步骤时,出现余数为零的情况,即计算结果不是循环小数时,直接输出索引值,循环节长度为0。

     

    C++实现:

     1 #include<iostream>
     2 using namespace std;
     3 
     4 int main() {
     5     int a, b, t, k;
     6     cin >> a >> b;
     7     int index = 0;
     8     t = a%b;
     9     if (t ==0) {
    10         cout << index << " " << index << endl;
    11         return 0;
    12     }
    13     int flag[10000] = {0};
    14     memset(flag,-1,1000);
    15     k =0;
    16     int length = 0;
    17     while (true) {
    18         t = (t*10)%b;
    19         if (t == 0) {
    20             index = ++k;
    21             length = 0;
    22             break;
    23         }
    24 
    25         if(flag[t] >= 0) {
    26             index = flag[t];
    27             length = k - index;
    28             break;
    29         }
    30         flag[t]=k;
    31         k++;
    32     }
    33 
    34     cout << index << " " << length << endl;
    35     return 0;
    36 }

     

     

        

    转载于:https://www.cnblogs.com/TonvyLeeBlogs/p/9563915.html

    展开全文
  • 循环节

    千次阅读 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;
    }
    展开全文
  • 对于一个分数(不一定是最简形式),给出它的小树形式,如果小数有循环节的话,把循环节放在一对圆括号中. 例如,1/4 =0.25,1/3=0.3333写成0.(3),1/7= 0.142857142857...写成0.(142857)。如果结果是一种整数xxx,...

     分数化小数

    对于一个分数(不一定是最简形式),给出它的小树形式,如果小数有循环节的话,把循环节放在一对圆括号中.

    例如,1/4 =0.25,1/3=0.3333写成0.(3),1/7= 0.142857142857...写成0.(142857)。如果结果是一种整数xxx,则用xxx.0 等表示整数xxx。

    输入包括一行,包括被空格分隔开的分子N和分母D(第一个是N,第二个是D)。

    输出包括一行,为转换后的小数形式。

    样例输入

    45 56

    样例输出

    0.803(571428)

    分析

    模拟除法的计算过程

    整数部分:a/b

    小数部分:

    ①mod = a%b;

    ②小数 = (mod*10) / b;

    ③mod = (mod*10)%b;

    循环②③步,当出现重复的余数的时候,也就是循环节出现了

    其实这道题的标签是“数论”,推荐队友的博客

    分数化小数 计蒜客(无限循环小数 循环节 欧拉函数 欧拉定理 十进制)

    C++

    #include<bits/stdc++.h>
    using namespace std;
    int main()
    {
        int a,b;
        scanf("%d%d",&a,&b);
        if(a%b==0)
        {
            printf("%d.0\n",a/b);
            return 0;
        }
        map<int,int> m;//标记余数
        vector<int>rem;//余数
        rem.clear();
        vector<int> v;//商数
        v.clear();
        int pos=-1;
        while(true){
            v.push_back(a/b);
            int x=a%b;//余数
            if(x==0)  break;
            if(m[x]) {//map缺省情况下为0
                pos=find(rem.begin(),rem.end(),x)-rem.begin();
                break;
            }
            rem.push_back(x);
            m[x]=1;
            a=x*10;
        }
        printf("%d.",v[0]);
        for(int i=1;i<v.size();i++){
            if(i==pos+1)
                printf("(");
            printf("%d",v[i]);
        }
        if(pos>=0)    printf(")");
        return 0;
    }
    

    Java

    import java.util.List;
    
    import java.util.ArrayList;
    
    import java.util.Scanner;
    
    import java.util.Map;
    
    import java.util.HashMap;
    public class Main {
    	static void f(int a,int b) {
    		ArrayList<Integer> rem=new ArrayList<Integer>();//余数
    		ArrayList<Integer> v=new ArrayList<Integer>();//商数
    		HashMap<Integer,Integer> m=new HashMap<Integer,Integer>();//标记余数
    		
    		int pos=-1;
    		while(true) {
    			v.add(a/b);//商数
    			int x=a%b;//余数
    			if(x==0)	break;
    			if(m.containsKey(x)) {//判断余数是否存在
    				pos=rem.indexOf(x);//查找重复余数所在的位置
    				break;
    			}
    			m.put(x,1);//标记
    			rem.add(x);//将余数添加到动态数组中
    			a=x*10;
    		}
    		System.out.print(v.get(0)+".");
    		for(int i=1;i<v.size();i++) {
    			if(pos+1==i)
    				System.out.print("(");
    			System.out.print(v.get(i));
    		}
    		if(pos>=0)
    			System.out.println(")");
    	}
        public static void main(String[] args) {
    		Scanner cin=new Scanner(System.in);
    		int a=cin.nextInt();
    		int b=cin.nextInt();
    		if(a%b==0) {
    			System.out.println(a/b+".0");
    		}else {
    			f(a,b);
    		}
    		cin.close();
    	}
    }  

     

    展开全文
  • 输入整数a和b(0 ...循环除数加一次,若余数为0,则循环节长度为1,若当前得到的余数已经存在,则有循环节,求出2个相同余数的距离即为循环节长度。  这个主要是怎么寻找循环节,在除法计算的过程

    输入整数a和b(0<=a<=3000,1<=b<=3000),输出a/b的循环小数表示以及循环节长度。例如a=5,b=43,小数表示为

    0.(116279069767441860465),循环节长度为21;  

    思路:分数不能表示无限不循环小数。建立3个数组,一个放商,一个放余数,一个对应下角标的数若是余数则元素为1,即记录余数存在。循环除数加一次,若余数为0,则循环节长度为1,若当前得到的余数已经存在,则有循环节,求出2个相同余数的距离即为循环节长度。

      这个主要是怎么寻找循环节,在除法计算的过程中如何判断一个循环节已经出现了。循环节第二次出现意味着计算过程中的余数已经第二次出现。其实自己在草纸上写一个比如5/7就能发现。当商5的时候(5是循环节的最后一位)余数是5,这和第一次商0的时候(0是循环节前一位)余数也是五。然后用索引存储是否这个余数已经出现过,还有一个数组记录余数对应的商的位置。余数的范围是1~m-1,所以循环节最长是m-1,所以查询数组的大小根据m的值来设定


    1. #include <iostream>  
    2. #include <cstdlib>  
    3. #include <cstring>  
    4. #include <cstdio>  
    5.   
    6. using namespace std;  
    7.   
    8. int r[3003],u[3003],s[3003];  
    9.   
    10. int main()  
    11. {  
    12.     int n,m,t;  
    13.     while (cin >> n >> m) {  
    14.         t = n;  
    15.         memset(r, 0, sizeof(r));  
    16.         memset(u, 0, sizeof(u));  
    17.         int count = 0;  
    18.         r[count ++] = n/m;  
    19.         n = n%m;  
    20.         while (!u[n] && n) {  
    21.             u[n] = count;  
    22.             s[count] = n;  
    23.             r[count ++] = 10*n/m;  
    24.             n = 10*n%m;  
    25.         }  
    26.         printf("%d/%d = %d",t,m,r[0]);  
    27.         printf(".");  
    28.         for (int i = 1 ; i < count && i <= 50 ; ++ i) {  
    29.             if (n && s[i] == n) printf("(");  
    30.             printf("%d",r[i]);  
    31.         }  
    32.         if (!n) printf("(0");  
    33.         if (count > 50) printf("...");  
    34.         printf(")\n");  
    35.         printf("   %d = number of digits in repeating cycle\n\n",!n?1:count-u[n]);  
    36.     }  
    37.     return 0;  
    38. }  

    展开全文
  • 寻找循环节

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

    千次阅读 2017-03-07 21:47:08
    循环节长度 两个整数做除法,有时会产生循环小数,其循环部分称为:循环节。 比如,11/13=6=>0.846153846153..... 其循环节为[846153] 共有6位。 下面的方法,可以求出循环节的长度。 请仔细阅读代码,并...
  • 【KMP算法】【最小循环节】讲解 + 例题 POJ 1961 Period 【给字符串s,求s的具有循环节的前缀,并输出所有前缀长,循环节个数】 摘自 KMP最小循环节 一、定理 假设S的长度为len,若S存在最小循环节...
  • 利用手工除法原理,导出所输入分数的小数形式,并求出小数的循环节(小数的存储结构为单链表)。内含源文件+编译后的文件。开发平台为VC++ 6.0.
  • 八、求循环节

    2020-07-23 15:21:44
    如果采用链表存储各位小数,对于循环节采用循环链表表示,则所有分数均可以表示为如下链表形式。 输入: N M 输出: 整个循环节 要求: 编写一个尽可能高效的查找循环节起始点的函数: NODE * find( NODE * head, ...
  • Java实现有理数的循环节

    万次阅读 多人点赞 2019-07-26 22:39:32
    1/7 = 0.142857142… 是个无限循环小数。 任何有理数都可以表示为无限循环小数的形式。 本题目要求即是:给出一个数字的循环小数表示法。...程序输出两个整数做除法产生的小数或无限循环小数(循环节用...
  • 求分数的循环节和小数表示

    千次阅读 2014-10-12 15:30:00
    这个就是分数的非循环部分的长度,这样偏移后,后面就是循­环部分,直到重复。 代码如下: #include using namespace std; int countBeforeRepeat(int n, int d) { int count5n = 0, count2n = 0; ...
  • 如题: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 …这就是小学题目嘛,对吧看着好简单。 循环节: 其实现在很多题目也要用到同样的方法,...
  • 倒数的循环节

    千次阅读 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
  • 求循环小数循环节

    千次阅读 2018-02-07 15:10:47
    任何有理数都可以表示为无限循环小数的形式。   本题目要求即是:给出一个数字的循环小数表示法。   例如: 输入: 1,5 则输出: 0.2   输入: 1,7 则输出: 0.[142857]   输入: 7...
  • 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可以完全由...
  • JAVA-获取无限循环小数的循环节

    千次阅读 2020-03-27 11:07:03
    JAVA获取无限循环小数的循环节
  • /*这是标志循环节的位置,默认起始位置是0*/ int tag=0; int first=0; void subRecursion(int a,int b) { int divide=0, remainder=0; char ch; divide=a/b; remainder=a%b; ch=divide+'0'; int length=0; ...
  • HDU 5970 (循环节)

    2016-11-06 18:36:54
    题目链接:点击这里打个表...因为(i+kj, j)和(i,j)的辗转次数相等,所以考虑延长循环节,把cj看成是循环节,这样的话就只需要求出循环节内部分,并且重复循环节就行了。在两个循环节之间是等差数列,瞎搞搞就出来了。
  • 求小数的循环节

    2014-11-02 16:44:06
    求小数的循环节
  • 有理数的循环节

    千次阅读 2018-02-22 09:50:01
    任何有理数都可以表示为无限循环小数的形式。 本题目要求即是:给出一个数字的循环小数表示法。 例如: 输入: 1,5则输出: 0.2 输入: 1,7则输出: 0.[142857]输入: 7,6则输出: 1.1[6]用户输入的格式是: 整数,...
  • 循环节问题包括 完全循环 和 不完全循环 完全循环 对于一个具有循环节并且长为n的字符串,其循环节长为 n - n x t [ n - 1 ] ,并且满足n % ( n - n x t [ n - 1 ] ) ==0 ,这里nxt [ ]是KMP算法中的next 数组,...
  • ACM之数列循环节

    千次阅读 2016-03-27 23:45:57
    初次接触这道题,我便想到了原来的写过的斐波拉契数列,便用一个个递推的函数从n一个...下面通过代码解释:接下来这题也是数列循环节的问题 此题便既可以通过程序寻找循环的节点,亦可以同过数学运算得到循环的节点:
  • 输入两个数字m,n,输出m/n的结果,并找出循环节 0,n<=10000
  • kmp求最小循环节及其原理解释

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

    千次阅读 2014-12-10 23:31:25
    11.求循环节 成绩 10 开启时间 2014年11月12日 Wednesday 18:25 折扣 0.8 折扣时间 2014年11月30日 Sunday 23:55 允许迟交 否 关闭时间 2014年12月7日 Sunday ...
  • 求一个分数的循环节

    千次阅读 2019-04-19 18:55:39
    (某年复试真题)编写完整的函数,输入正整数N和D,如果N/D为无限循环小数,输出时小数点后面的第一个循环节用括号括起来,不显示后面的循环;不为循环小数则正常显示。(25分) 如 :3/4=0.75;5/6=0.8(3);10/3=3.(3)...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 121,111
精华内容 48,444
关键字:

如何表示循环节