首页 > ACM题库 > HDU-杭电 > HDU 4161-Iterated Difference-递推-[解题报告]HOJ
2015
05-23

HDU 4161-Iterated Difference-递推-[解题报告]HOJ

Iterated Difference

问题描述 :

You are given a list of N non-negative integers a(1), a(2), … , a(N). You replace the given list by a new list: the k-th entry of the new list is the absolute value of a(k) – a(k+1), wrapping around at the end of the list (the k-th entry of the new list is the absolute value of a(N) – a(1)). How many iterations of this replacement are needed to arrive at a list in which every entry is the same integer?

For example, let N = 4 and start with the list (0 2 5 11). The successive iterations are:

2 3 6 11
1 3 5 9
2 2 4 8
0 2 4 6
2 2 2 6
0 0 4 4
0 4 0 4
4 4 4 4
Thus, 8 iterations are needed in this example.

输入:

The input will contain data for a number of test cases. For each case, there will be two lines of input. The first line will contain the integer N (2 <= N <= 20), the number of entries in the list. The second line will contain the list of integers, separated by one blank space. End of input will be indicated by N = 0.

输出:

The input will contain data for a number of test cases. For each case, there will be two lines of input. The first line will contain the integer N (2 <= N <= 20), the number of entries in the list. The second line will contain the list of integers, separated by one blank space. End of input will be indicated by N = 0.

样例输入:

4
0 2 5 11
5
0 2 5 11 3
4
300 8600 9000 4000
16
12 20 3 7 8 10 44 50 12 200 300 7 8 10 44 50
3
1 1 1
4
0 4 0 4
0

样例输出:

Case 1: 8 iterations
Case 2: not attained
Case 3: 3 iterations
Case 4: 50 iterations
Case 5: 0 iterations
Case 6: 1 iterations

给出一串数,这串数的下一个状态的每一位都由上个状态的后一位的绝对值减这一位的绝对值得到,求经过多少次状态这串数均变成0;

//Time : 203MS	
//Memory : 224K
#include <stdio.h>
int sum=-1;
int dif(int a[],int n)
{
	int i,s=0;
	bool zero=true;
	sum++;
	for(i=0;i<n-1;i++)
	{	if(a[i]<0)
			a[i]=0-a[i];
		if(a[i+1]<0)
			a[i+1]=0-a[i+1];
		a[i]=a[i+1]-a[i];
		if(a[i]!=0)
			zero=false;
		s+=a[i];
	}
	a[n-1]=s;
	if(s==0 && zero)
		return sum;
	if(sum>1000)
		return -1;
	dif(a,n);
}
int main()
{
	int a[21];
	int n,temp=1;
	while(scanf("%d",&n)!=EOF && n)
	{
		sum=-1;
		for(int i=0;i<n;i++)
			scanf("%d",&a[i]);
		int num=dif(a,n);
		printf("Case %d: ",temp);
		if(num==-1)
			printf("not attained\n");
		else
			printf("%d iterations\n",num);
		temp++;
	}
	return 0;
}

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

参考:http://blog.csdn.net/winkloud/article/details/7841027