首页 > 代码库 > UVa 263 - Number Chains

UVa 263 - Number Chains

题目:给你一个数字n0。将它的每一个位的数字按递增排序生成数a,按递减排序生成数b,

            新的数字为n1 = a-b,下次依照相同方法计算n1,知道出现循环,问计算了多少次。

分析:数论、模拟。直接模拟计算就可以,利用hash表判重。

说明:注意初始化。

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>

using namespace std;

//hash
typedef struct hash_node
{
	int  		path;
	hash_node* 	next;
}hnode;
hnode* tabel[1002];
hnode  nodeh[1002];
int    hash_size;

void hash_initial()
{
	memset(tabel, 0, sizeof(tabel));
	hash_size = 0;
}

int hash_find(int s)
{
	int v = s%1001;
	for (hnode* p = tabel[v] ; p ; p = p->next)
		if (p->path == s)
			return 1;
	nodeh[hash_size].next = tabel[v];
	nodeh[hash_size].path = s;
	tabel[v] = &nodeh[hash_size ++];
	return 0;
}
//hash end

int buf[11];
int number(int *a, int n)
{
	int value = http://www.mamicode.com/0;"%d",&n) && n) {
		printf("Original number was %d\n",n);
		
		hash_initial();
		sum = 0;
		do {
			hash_find(n);
			sum ++;
			count = 0;
			while (n) {
				buf[count ++] = n%10;
				n /= 10;
			}
			sort(buf, buf+count, cmp2);
			a = number(buf, count);
			sort(buf, buf+count, cmp1);	
			b = number(buf, count);
			printf("%d - %d = %d\n",a,b,n = a-b);
		}while (!hash_find(n));
		printf("Chain length %d\n\n",sum);
	}
    return 0;
}


UVa 263 - Number Chains