第38次编程比赛第一题题目 — 编程爱好者社区

主题：第38次编程比赛第一题题目

liangbch [专家分：1270] 发布于 2006-08-18 12:16:00

在N以内(小于等于N)找出一个数，要求：
1.这个数的约数的个数达到最大，
2.如果有好几个数满足条件1，仅取最小的那个数

说明：
1) 1<N<=[color=FF0000]2^32-1[/color]，每个N的时限是1000ms。内存限制256M,注意使用适当数据类型，以免溢出。

函数原型：
// n: 范围
// result:结果，存放符合条件的那个数
// count:存入存放符合条件的那个数的约数的个数
// arr:存放那个数的所有约数，按照从小到大的顺序
void Search(unsigned long n, unsigned long *result,int *count,unsigned long arr[]);

例：
n=100，则 result=60,
在100以内，60和90的约数个数同为12个，达到这个范围内所有整数中，其约数个数的最大值，但60比90小，所有正确答案为60。60共有12个约数：1,2,3,4,5,6,10.12.15.20.30,60.所以count应该存入12，从arr[0]开始，应该依次写入1,2,3,4,5,6,10.12.15.20.30,60。

本帖地址： http://bbs.pfan.cn/post/187657.html

回复列表（共47个回复）

沙发

liangbch [专家分：1270] 发布于 2006-08-18 12:17:00

test

板凳

linxuanxu [专家分：9360] 发布于 2006-08-18 12:46:00

long arr[]); //传过来的是多大的数组？

3 楼

joekings [专家分：550] 发布于 2006-08-18 14:55:00

void Search(unsigned long n, unsigned long *result,int *count,unsigned long arr[])
{
    unsigned long i,j,k,sqrtn,temparr[200];//temparr取和arr同样大小
  //实际上，当n值为80000的时候，count也才120，所以200绝对够用，甚至有点浪费
    int test;
    *result=2;
    *count=2;
    for(i=n/2+1;i<=n;i++)
    {
        test=0;
        sqrtn=sqrt(i);
        for(j=1;j<sqrtn;j++)
        {
            if(i%j==0)
            {
                temparr[test]=j;
                test++;
            }
            continue;
        }
        if(test>*count||(test==*count&&sqrtn*sqrtn==i))
        {
            *count=test;
            *result=i;
            for(k=0;k<test;k++)
                arr[k]=temparr[k];
        }
    }
    test=*count;
    sqrtn=sqrt(*result);
    if(sqrtn*sqrtn!=*result)
    {
        for(k=0;k<test;k++)
            arr[test+k]=*result/arr[test-k-1];
        *count=2*test;
    }
    else
    {
        arr[test]=sqrtn;
        for(k=1;k<=test;k++)
       arr[test+k]=*result/arr[test-k];
        *count=2*test+1;
    }
}
//自己用的测试函数
int main()
{
    unsigned long result,arr[200];
    int count,i;
    Search(80000,&result,&count,arr);
    printf(" %d...%d...\n",result,count);
    for(i=0;i<count;i++)
        printf("%d*  ",arr[i]);
    system("pause");
    return 0;

}
//算法中考虑了完全平方数。

4 楼

cjonathan [专家分：0] 发布于 2006-08-18 15:51:00

晕

5 楼

cjonathan [专家分：0] 发布于 2006-08-18 15:56:00

这个范围要好好选啊

6 楼

liyanguestc [专家分：90] 发布于 2006-08-18 16:43:00

上次接口写错了,不知道这次对了没??
为了防止写错我把时间函数也写了出来,直接在VC下运行就可以了!
#include <iostream>
#include <string.h>
#include <math.h>
#include <time.h>
using namespace std;
double start,end;//计算运行时间

unsigned long N;
void Search(unsigned long n, unsigned long *result,int *count,unsigned long arr[]);
int pnum(int cur);
int main()
{cout<<"请输入N:"<<endl;
cin>>N;
start=clock();
unsigned long result=0;
int count=0;
unsigned long *arr=0;

Search(N,&result,&count,arr);

cout<<"result="<<result<<endl<<
       "count="<<count<<endl;
end=clock();
cout<<"run for"<<(double)(end-start)/CLK_TCK<< "seconds"<<endl;
return 0;}
void Search(unsigned long n, unsigned long *result,int *count,unsigned long arr[])
{unsigned long max=0;
int maxp=0;
int nump=0;
int digitmax;
digitmax=3*5*7*9*11*16*13;

for(unsigned long i=n/2;i<=n;)
{
    if(i/2*2!=i){i++;continue;}
if(maxp>=32)
if(i/3*3!=i){i++;continue;}
if(i>100000)
{  if(i>100000000)
    {
    if(i/digitmax*digitmax!=i){i++;continue;}
    nump=pnum(i);
    if(nump>maxp)
    {maxp=nump;
    max=i;}
    i+=digitmax;
    }
   else
    {if(i>1000000)
   {if(i/digitmax*digitmax!=i){i++;continue;}
        nump=pnum(i);
       if(nump>maxp)
       {maxp=nump;
       max=i;}
       i+=digitmax;
        }
     else
     {if(i/3*3!=i||i/5*5!=i||i/7*7!=i||i/11*11!=i||i/4*4!=i||i/9*9!=i||i/8*8!=i)
        {i++;continue;}
        nump=pnum(i);
       if(nump>maxp)
       {maxp=nump;
       max=i;}
       i++;
     }
   }
}
else
{
    nump=pnum(i);
    if(nump>maxp)
    {maxp=nump;
    max=i;
    }
    i++;
}

}

*result=max;
*count=maxp;
arr=new unsigned long[maxp];
int tmp=0;
int kk=(int)sqrt(max);
for(i=1;i<=kk;i++)
  if(max/i*i==max)
        arr[tmp++]=i;
  //if((tmp*=2)==maxp)
    //  arr[tmp++]=(int)sqrt(max);
  for(i=0;i<tmp;i++)
      arr[maxp-i-1]=max/arr[i];
cout<<"输出结果:"<<endl;
cout<<"arr[]=";
for(int k=0;k<*count;k++)
cout<<arr[k]<<' ';
cout<<endl;
delete[] arr;
}

int pnum(int cur)//计算cur的约数个数
{int flag=1;
//int tt=sqrt(cur);
int a[10][2]={{2,0},{3,0},{5,0},{7,0},{11,0},{13,0},{17,0},{19,0},{23,0},{29,0}};
//    for(int j=1;j<tt;j++)
    //    if((cur/j)*j==cur)
    //        flag++;
    //    flag*=2;
    //    if(tt*tt==cur)
    //        flag++;
for(int j=0;j<10;j++)
if(cur/a[j][0]*a[j][0]==cur)
{a[j][1]++;
cur/=a[j][0];
j--;
if(cur==1)
break;
}
for(j=0;j<10;j++)
     flag*=(a[j][1]+1);
return flag;

}

7 楼

linxuanxu [专家分：9360] 发布于 2006-08-18 17:10:00

struct isNum{
    unsigned long num;
    isNum *next;
};
void Search(unsigned long n, unsigned long *result,int *count,unsigned long arr[]){
    unsigned long tempN=(long)n/2,i=0;
    unsigned long array[5000]={0.0};
    if(tempN%2!=0)tempN+=1;
    isNum *p_begin,*p_end;

    p_begin=p_end=(struct isNum*)malloc(sizeof(isNum));

    for(i=tempN;i<=n;i++){
        p_end->num =i;
        p_end=(p_end->next =(struct isNum*)malloc(sizeof(isNum)));
    }
    p_end->num =n;
    p_end->next =NULL;

    p_end=p_begin;

    *count=2;
    int count_temp=0;
    while(p_end->next !=NULL){
        count_temp=2;
        array[0]=1;array[1]=2;
        for (unsigned long x =3  ;x<=p_end->num  ;x++){

            if(p_end->num % x==0){
                count_temp++;
                array[count_temp-1]=x;
            }
        }
        if(count_temp>*count){
            *result=p_end->num ;
             *count=count_temp;
             for(int z=0;z<=count_temp;z++){
                arr[z]=array[z];
             }
        }
        p_end=p_end->next ;
    }
}

8 楼

novazhao [专家分：0] 发布于 2006-08-18 17:21:00

....d[em2]

9 楼

xyhx [专家分：0] 发布于 2006-08-18 17:23:00

#include<malloc.h>
#include<stdlib.h>
void Search(unsigned long n, unsigned long *result,
            int *count,unsigned long arr[])
{
    unsigned long i,j,*a;
    unsigned long MaxCount(unsigned long a[],unsigned long n);

    a=(unsigned long *)calloc(n+1,sizeof(unsigned long));
    if(a==NULL)
    {
        printf("Cann't allocate memory!\n");
        exit(1);
    }
    for(i=1;i<=n;i++)
        a[i]=2;
    for(i=2;i*i<=n;i++)
    {
        if(i*i>=n/2)
            a[i*i]++;
        for(j=i+1;j*i<=n;j++)
            if(i*j>=n/2)
                a[i*j]+=2;
    }
    *result=MaxCount(a,n);
    *arr++=1;
    *count=a[*result];
    for(i=2;i<=*result/2;i++)
        if(*result%i==0)
            *arr++=i;
    *arr=*result;
    free(a);
}
unsigned long MaxCount(unsigned long a[],unsigned long n)
{
    unsigned long i,k;
    unsigned long res=0;
    if(n<=3) return 2;
    for(i=n/2,k=1;i<=n;i++)
        if(a[i]>res)
        {
            res=a[i];
            k=i;
        }
    return k;
}

终于搞定了，好轻松^_^

10 楼

boxertony [专家分：23030] 发布于 2006-08-18 19:46:00

int cmp(const void*x, const void *y)
{
    return (*(int*)x - *(int*)y);
}

// 得到n范围内的所有素数
// nPrimes[] -- 存放所有的素数
// 返回n范围内素数个数
int GetPrimes(long n, long nPrimes[])
{
    int        nCount;
    long    *nums = new long[n];

    assert( nums != NULL);
    int        i;

    for(i=3; i<=n; i+=2)
    {
        nums[i>>1] = i;
    }

    long    nDivisor = 3;
    long    nInterval;
    long    nStart = 1;
    nCount = 2;
    nPrimes[0] = 2;
    nPrimes[1] = 3;
    while(1)
    {
        nInterval = nDivisor << 1;
        for(i=nDivisor+nInterval; i<=n; i+= nInterval)
        {
            nums[i>>1] = 0;
        }
        if(++nStart > (n>>1))
            break;
        for(i=nStart; i<=(n-1)/2; ++i)
        {
            if(nums[i] != 0)
            {
                nDivisor = nums[i];
                nPrimes[nCount++] = nDivisor;
                break;
            }
            else
                ++nStart;
        }
    }

    delete []nums;
    return nCount;
}

我来回复

您尚未登录，请登录后再回复。点此登录或注册

主题：第38次编程比赛第一题题目

回复列表（共47个回复）

我来回复

程序员工具箱 new

代码片段

本版新帖

主题：第38次编程比赛第一题题目

回复列表 （共47个回复）

我来回复

程序员工具箱 new

代码片段

本版新帖

回复列表（共47个回复）