剔除相关数
Time Limit:1000MS Memory Limit:32768K
Description:
一个数与另一个数如果含有相同数字和个数的字符，则称两数相关。现有一堆乱七八糟的整数，里面可能充满了彼此相关的数，请你用一下手段，自动地将其剔除。
Input:
每组数据前有一个N(<1000)，表示跟随的整数P(0<P<2^32)个数，若N为0，表示结束。
Output:
按从小到大的顺序输出非相关数，若没有非相关数，则输出None。
Sample Input:
8
213 667 3 213 43 34 677 2
3
322 232 232
0
Sample Output:
2 3 667 677
None
----------------解决方案--------------------------------------------------------
这个题目蛮好的.大家做一下.
----------------解决方案--------------------------------------------------------
有点难度！先改一下再交上来。
[此贴子已经被作者于2006-11-26 20:55:09编辑过]
----------------解决方案--------------------------------------------------------
#define N 1000
void sort(int a[],int n);
void chazhao(int a[],int low,int high);
void chongfu(int n);
main()
{ int n;
scanf("%d",&n);
while(n)
{
chongfu(n);
scanf("%d",&n);
}
}
void sort(int a[],int n)
{int i,j,k;
int temp;
for(i=0;i<n-1;i++)
{
for(j=i+1;j<n;j++)
{
if(a[j]<a[i])
{
temp=a[j];
a[j]=a[i];
a[i]=temp;
}
}
}
}
void chazhao(int a[],int low,int high)
{
int i,j,a1[5],a2[5],k,flag;
for(i=low;i<high-1;i++)
{ if(a[i]!=0)
{
a1[0]=a[i]/10000;
a1[1]=a[i]%10000/1000;
a1[2]=a[i]%1000/100;
a1[3]=a[i]%100/10;
a1[4]=a[i]%10;
sort(a1,5);
flag=0;
for(j=i+1;j<high;j++)
{
a2[0]=a[j]/10000;
a2[1]=a[j]%10000/1000;
a2[2]=a[j]%1000/100;
a2[3]=a[j]%100/10;
a2[4]=a[j]%10;
sort(a2,5);
if(a1[0]==a2[0]&&a1[1]==a2[1]&&a1[2]==a2[2]&&a1[3]==a2[3]&&a1[4]==a2[4])
{a[j]=0; flag=1;}
}
if(flag)
a[i]=0;
}
}
}
void chongfu(int n)
{
int i,j,wei[5]={0,0,0,0,0},a[N];
for(i=0;i<n;i++)
{scanf("%d",&a[i]);
}
sort(a,n);
for(i=0;i<n;i++)
{if(a[i]/10==0)
wei[0]++;
else if(a[i]/100==0)
wei[1]++;
else if(a[i]/1000==0)
wei[2]++;
else if(a[i]/10000==0)
wei[3]++;
else
wei[4]++;
}
for(i=0;i<5;i++)
chazhao(a,0,wei[0]);
chazhao(a,wei[0],wei[0]+wei[1]);
chazhao(a,wei[0]+wei[1],wei[0]+wei[1]+wei[2]);
chazhao(a,wei[0]+wei[2],wei[0]+wei[1]+wei[2]+wei[3]);
chazhao(a,wei[0]+wei[1]+wei[2]+wei[3],n);
j=1;
for(i=0;i<n;i++)
{
if(a[i]!=0)
{j=0;break;}
}
if(j)
{
printf("\nNone");
}
printf("\n");
for(i=0;i<n;i++)
{ if(a[i]!=0)
printf("%-5d ",a[i]);
}
}
不知道行不行？
[此贴子已经被作者于2006-11-26 21:09:34编辑过]
----------------解决方案--------------------------------------------------------
先看了，还没时间想，要睡觉了，下次搞定
----------------解决方案--------------------------------------------------------
关键是如何判断2个数相关:
对一个数如果把其中的数字由大到小排列.如1345 排成5431
4135 排成5431
如果排列后的两个数相等,那么两个数相关.(不知还有没有其他更好的方法)
所以对本题:
(1)把输入的数从小到大排列
(2)把每个数中的数字按从大到小排列.如223 变为322
(2)两两比较是否相关,也就是比较是否相等.
#include <stdio.h>
#include <math.h>
#define N 1000
#define M 10
void Sort(unsigned int *a, int n)
{
int i, j, k, t;
for (i = 0; i < n-1; i++)
{
k = i;
for (j = i + 1; j < n; j++)
if(a[j] < a[k])
k = j;
t = a[k];
a[k] = a[i];
a[i] = t;
}
}
unsigned max(unsigned int num)
{
int index = 0 , i;
unsigned int sum = 0, digit[M];
while (num != 0)
{
digit[index++] = num % 10;
num = num / 10;
}
Sort(digit, index);
for (i = index - 1; i >= 0; i--)
sum = sum * 10 + digit[i];
return sum;
}
int main()
{
unsigned int num[N];
unsigned int temp[N];
int flag[N];
int n;
while (EOF != scanf("%d", &n) && n != 0)
{
int i, j, count;
for (i = 0; i < n; i++)
scanf("%d", &num[i]);
Sort(num, n);
for (i = 0; i < n; i++)
{
flag[i] = 0;
temp[i] = max(num[i]);
}
for (i = 0; i < n; i++)
if (flag[i] == 0)
{
for (j = i + 1; j < n; j++)
if (flag[j] == 0 && temp[i] == temp[j])
{
flag[i] = 1;
flag[j] = 1;
}
}
for (i = 0, count = 0; i < n; i++)
{
if (flag[i] == 0)
{
if (count == 0)
printf("%d",num[i]);
else
printf(" %d",num[i]);
count++;
}
}
if (count == 0)
printf("None");
printf("\n");
}
return 0;
}
----------------解决方案--------------------------------------------------------
struct list{
long num; //要处理的数,如23454322
int a[10]; //处理数的每一个数字的个数,则数组为{0,0,3,2,2,1,0,0,0,0},先初始化为全0.
int len; // 数的位数,8.
}
/*空间浪费较大*/
----------------解决方案--------------------------------------------------------