Round and Round We Go POJ 1047

Description

Input

Output

Sample Input

142857
142856
142858
01
0588235294117647

Sample Output

142857 is cyclic
142856 is not cyclic
142858 is not cyclic
01 is not cyclic
0588235294117647 is cyclic

做这个题的时候想法很简单,最笨的办法,直接遍历,但是不知道为什么WA了,求探讨。同时在和人探讨的过程中,也学到了一个新的解法:

#include "stdio.h"
#include "String.h"
#include "malloc.h"
#define nMax 61
int judge(char*str,int i);
void mutiply(char * str,int k,char * newstr);
int roundJudge(char *a,char *b);
void main()
{
	char str[nMax];
	int i,j,k,p,q;
	scanf("%s",str);
	i=strlen(str);
	if(judge(str,i))
		printf("%s is cyclic",str);
	else
		printf("%s is not cyclic",str);
	
}
int judge(char*str,int i)
{
	int j;
	char newstr[nMax];
	for(j=2;j<=i;j++)
	{
		mutiply(str,j,newstr);
		if(!roundJudge(str,newstr))
		{			
			//printf("%d\n",j);
			return 0;
			break;
		}
	}
	return 1;
}
void mutiply(char * str,int k,char * newstr)
{
	int i,j,p,q,*m;
	char kk[3];
	if (k>=10)
	{
		kk[0]=k/10+'0';
		kk[1]=k%10+'0';
		kk[2]='0円';
	}
	else
	{
		kk[0]=k+'0';
		kk[1]='0円';
	}
	i=strlen(str);
	j=strlen(kk);
	m=(int *)malloc(sizeof(int)*(i+j));
	for(p=0;p<(i+j);p++)
		m[p]=0;
	for (p=0;p<i;p++)
	for(q=0;q<j;q++)
		m[p+q+1]+=(str[p]-'0')*(kk[q]-'0');
	for(p=i+j-1;p>=0;p--)
		if(m[p]>=10)
		{
			m[p-1]+=m[p]/10;
			m[p]=m[p]%10;
		}
		p=0;
		while(m[p]==0)
			p++;
			for(q=0;p<i+j;q++,p++)
				newstr[q]=m[p]+'0';
		newstr[q]='0円';
		j=strlen(newstr);
		if(j<i)
			newstr[i]='0円';
			for (p=i-1;p>=0;p--)
			{
				if(p>=(i-j))
					newstr[p]=newstr[p-i+j];
				else
					newstr[p]=0+'0';
			}
		free(m);
}
int roundJudge(char *a,char *b)
{
int ca,cb,i,j,k;
char *c,*temp;
ca=strlen(a);
cb=strlen(b);
if(ca!=cb)
return 0;
else
{
	c=(char*)malloc(sizeof(char)*(2*ca+1));
	temp=(char *)malloc(sizeof(char)*(ca+1));
	for (i=0;i<cb;i++)
	{
		c[i]=b[i];
	}
	for(i=0;i<cb;i++)
	{
		c[strlen(b)+i]=b[i];
	}
	c[2*ca]='0円';
	for (i=0;i<ca;i++)
	{
		for (j=0;j<ca;j++)
		{
			temp[j]=c[i+j];
		}
		temp[ca]='0円';
		if(strcmp(a,temp)==0)
		{
			free(c);
			free(temp);
			return 1;
			break;
		}
	}
	free(c);
	free(temp);
	if(i==ca)
		return 0;
	
}
}

#include<iostream>
#include<string>
#include<map>
using namespace std;
map<string, int> dic;
string sline;
void init(){
	string str[8] = {"142857","0588235294117647","052631578947368421","0434782608695652173913","0344827586206896551724137931",
		"0212765957446808510638297872340425531914893617","0169491525423728813559322033898305084745762711864406779661",
	"016393442622950819672131147540983606557377049180327868852459"};
	for(int i=0;i<8;i++)
		dic[str[i]]=1; 
}
int main(){
 init();
 while(cin>>sline){
 if(dic.count(sline)==1) cout<<sline<<" is cyclic"<<endl;
 else cout<<sline<<" is not cyclic"<<endl;
 }
}

本文来自:CSDN博客

感谢作者:JWMNEU

查看原文:Round and Round We Go POJ 1047

• 编辑
• 预览