1016.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

//////////////////////////////////////////////////////////////////
//Numbers That Count
//
//
//

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

char num[15][100];

int inventory(char *w, char *ans )
{
	int i, j, c[10];
	
	for( i = 0; i < 10; i++ )
		c[i] = 0;
	
	for( ; *w != '\0' ; w++ )
		c[ (*w)-'0' ]++;
	
	for( i = 0, j = 0; i < 10; i++ )
	if( c[i] )
	{
		j += strlen( itoa( c[i], ans+j, 10 ) );
	
		ans[j++] = i + '0';
	}
	ans[j] = '\0';
//	printf("---%s\n",ans);
	return j;
}

int main()
{
	int i, j;
	while(1)
	{
		scanf( "%s", num[0] );
		if( num[0][0] == '-' ) break;
		printf( "%s ", num[0] );

		inventory( num[0], num[1] );

		if( strcmp( num[0], num[1] ) == 0 )
		{
			printf( "is self-inventorying\n" );
			continue;
		}
		
		for( i = 2; i < 16; i++ )
		{
			inventory( num[i-1], num[i] );

			if( strcmp( num[i], num[i-1] ) == 0 )
			{
				printf( "is self-inventorying after %d steps\n", i-1 );
				break;
			}
			
			for( j = 0; j < i; j++ )
			if( strcmp( num[i], num[j] ) == 0 )
			{
				printf( "enters an inventory loop of length %d\n", i-j );
				break;
			}

			if( j < i ) break;
		}
		if( i >= 16 )
			printf("can not be classified after 15 iterations\n");
	}

	return 0;
}