给1~N的每一个数字标记一种颜色，使得其中任意两个数字A,B，如果A可以整除B，则A和B必须标记不同的颜色，要求所使用的颜色最少，并得到1~N的每一个数字所标记的颜色（用数字表示）。请编写程序解决这个问题。
例子：
输入：（1<= N <=10000）
16
输出：
5
1 2 2 3 2 3 2 4 3 3 2 4 2 3 3 5
这个关键是分析清楚对于一个非质数其颜色为A[i*j] = max(A[i],A[j])+1,质数就为A[1] + 1.
note：
我这里分析的时候是按数组下标为1分析的。程序内面是按0。
其实这题如果是单单只求个数的话，就好弄了。就为sqrt(N*1.0)+1.刚又发现如果pow(2,m)
好了,下面是代码。经过了一定得测试.大家跑跑要是有问题，再说。
|
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define MAX(a,b) (a)>(b)?(a):(b)
int main(int argc, char *argv[])
{
int N;
int i;
int j;
int tmp;
printf("Please input the number you want to count:\n");
scanf("%d",&N);
int sqrt_num = (int)sqrt(N*1.00);
int binary_num = N/2;
int A[N];
A[0] = 1;
for(i=1;i<=N;i++)
A[i] = A[0]+1;
for(i=2;i<=sqrt_num;i++)
for(j=i;j<=binary_num;j++)
{
if(i*j > N)
continue;
tmp = MAX(A[i-1],A[j-1]) + 1;
if(tmp > A[i*j-1])
A[i*j-1] = tmp;
printf("num:%d color:%d\n",i*j, A[i*j-1]);
}
for(i=0;i<N;i++)
printf("%2d ",i+1);
printf("\n");
for(i=0;i<N;i++)
printf("%2d ",A[i]);
system("PAUSE");
return 0;
}
|
阅读(792) | 评论(0) | 转发(0) |
