首页 > ACM题库 > HDU-杭电 > HDU 4148-Length of S(n)[解题报告]HOJ
2015
04-16

HDU 4148-Length of S(n)[解题报告]HOJ

Length of S(n)

问题描述 :

A number sequence is defined as following:
S(1)=1,
S(2)=11,
S(3)=21,
S(4)=1211,
S(5)=111221,
S(6)=312211,
……
Now, we need you to calculate the length of S(n).

输入:

The input consists of multiple test cases. Each test case contains one integers n.
(1<=n<=30)
n=0 signal the end of input.

输出:

The input consists of multiple test cases. Each test case contains one integers n.
(1<=n<=30)
n=0 signal the end of input.

样例输入:

2
5
0

样例输出:

2
6

/*

分析:

    表示下面的规律不是自己发现的- -I。

  摘:
    解题思路:看过题就知道是要找规律的,而从下列式子中不轻易发明,

                       S(1)=1,           //在s(n)从左往右看
                       S(2)=11,          s(1)中有1个1;
                       S(3)=21,          s(2)中有2个1;
                       S(4)=1211,       s(3)中有1个2和1个1;
                       S(5)=111221,   s(4)中有1个1、1个2和2个1;
                       S(6)=312211,   s(5)中有3个1、2个2和1个1;
                       &#8230;&#8230;

                                                   2012-05-04
*/

#include"stdio.h"
#include"string.h"
int main()
{
	char str[31][5000];
	int len[31];
	int num[30],k_temp;
	int i,l;
	int count,k;
	int n;


	memset(str,0,sizeof(str));
	str[1][0]=1;
	len[1]=1;
	for(i=2;i<=30;i++)
	{
		count=1;
		k=0;
		for(l=1;str[i-1][l-1];l++)
		{
			if(str[i-1][l]!=str[i-1][l-1])
			{
				k_temp=0;
				while(count)
				{
					num[k_temp]=count%10;
					count/=10;
					k_temp++;
				}


				k_temp--;
				while(k_temp>=0)
				{
					str[i][k]=num[k_temp];
					k++;
					k_temp--;
				}
				str[i][k]=str[i-1][l-1];
				k++;


				count=1;
				continue;
			}
			count++;
		}
		len[i]=k;
	}


	while(scanf("%d",&n),n)
	{
		printf("%d\n",len[n]);
	}
	return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/ice_crazy/article/details/7535969


  1. 很高兴你会喜欢这个网站。目前还没有一个开发团队,网站是我一个人在维护,都是用的开源系统,也没有太多需要开发的部分,主要是内容整理。非常感谢你的关注。

  2. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。