汉扬编程 C语言入门 C语言代码实现周期串问题,算法竞赛入门UVa1225,第六天

C语言代码实现周期串问题,算法竞赛入门UVa1225,第六天

C语言代码实现周期串问题,算法竞赛入门UVa1225,第六天

原题

C语言代码实现周期串问题,算法竞赛入门UVa1225,第六天

原题:A character string is said to have period k if it can be formed by(组成) concatenating(连接) one or more repetitions of (重复)another string of length k. For example, the string ”abcabcabcabc” has period (周期)3, since it is formed by 4 repetitions of the string ”abc”. It also has periods 6 (two repetitions of ”abcabc”) and 12 (one repetition of ”abcabcabcabc”). Write a program to read a character string and determine its smallest periodInput :The first line oif the input file will contain a single integer N indicating (表明)how many test case that your program will test followed by a blank line(空格). Each test case will contain a single character string of up to 80 non-blank characters. Two consecutive input will separated by (用…分开)a blank line.Output :An integer denoting (表示)the smallest period of the input string for each input. Two consecutive(连续) output are separated by a blank line.(一个整数,表示每个输入的输入字符串的最小周期。两个连续输出是用空行隔开)

C语言代码实现周期串问题,算法竞赛入门UVa1225,第六天

Sample Input 1 HoHoHo Sample Output 2题解:如果有个字符串可以由某个长度为k的字符串重复多次得到,则称为该串以k为周期,例如:abcabcabc,是以3为周期(他也是可以以6和12为周期。) 那么现在输入一个长度不超过80的字符串,输出其最小周期。分析:好啦,费了九牛二胡之力终于把题目看懂了,那么下面我们就一起来分析下,程序该如何写吧:

刚开始是想着是,从第二个字符开始和往后如果找到和第一个字符相等的就记录下来,然后开始往后逐次往后比较,但是,这种写法漏洞太多。

于是,回到本质上来,发现问题简单了好多,既然具有周期性,那f(x+T)==f(x),那么,我们就可以循环周期,假设周期为从1开始,然后从f(i+t)和f(i++) 进行比较,如果他们都相等,那么这个周期就找到啦。

PS:在OJ上,这个输出格式要特别注意,刚开始,以为是两个数字用空格隔开,后开看评论才发现除了最后一个,其他的都\\n\\n (两个回车哦)

这个格式也是怕了

在提交了n次之后,终于AC了开心

AC

代码:#include <stdio.h>#include <string.h>#define maxn 85int main(){ char s[maxn]; int T,i,p,flag=0; scanf("%d",&T); while(T–) { scanf("%s",s); for(p=1;p<strlen(s);p++) { if(strlen(s)%p==0) //周期数一定可以被字符串整除 { flag=1; for(i=0;i+p<strlen(s);i++) { if(s[i]!=s[i+p]) flag=0; //说明p不是周期 } if(flag) break ; //周期数找到啦,快跑吧! } } if(flag) { printf("%d\\n",p); if(T!=0) printf("\\n"); } else { printf("%d\\n",strlen(s)); if(T!=0) printf("\\n"); } } return 0;}总结,看到以为大佬写的,用环状序列,来循环,绝得也挺好的: while(N–) { cin>>str; int len=strlen(str); int t=1; while(1) { int c=0; for(int i=0;i<len;++i) //i是周期 { if(str[i]==str[(i+t)%len]) //看一看转几个字符能够恢复原位(环状序列循环公式 // (i++%len)) ++c; } if(c==len) //说明每次都相等,找到周期,快跑! break; ++t; } cout<<t<<endl; if(N!=0) cout<<endl; }收获:想问题要从本质出发思路不能乱常见的发放要熟记于心

本文来自网络,不代表汉扬编程立场,转载请注明出处:http://www.hyzlch.com/cjia/5909.html

汉诺塔问题VB递归算法实现

想要学习编程,都需要什么样的基础?讲的真有道理!

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注

返回顶部