回 帖 发 新 帖 刷新版面

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

在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。

回复列表 (共47个回复)

31 楼

main()
{int a=2,b=5;
printf("a=%%d,b=%%d\n".a.b);}这个两个%%是什么意思〉能告诉我吗?谢谢

32 楼

嘿嘿,我也来一次!
#include <stdio.h>
#include <stdlib.h>
int arr[100],count,result,n;
void Search(unsigned long n)
{int i,j,t,k;
 for(i=1;i<=n;i++)
    {t=0;
     for(j=1;j<i;j++)
        {if(i%j==0)
          t++;
        }
      if(t>count) 
        {count=t;t=0;result=i;
          for(j=1;j<=i;j++)
            {if(i%j==0)
              arr[t++]=j;
            }
            
        }
    } 
    for(k=0;k<t;k++)
    printf("%d,",arr[k]);
}
int main()
{
    printf("Please Enter n:");
    scanf("%d",&n);
    Search(n);
    printf("\nn=%d,result=%d\n",n,result);
    system("PAUSE");
}

33 楼

不错,不错,非常的不错!

34 楼

第一次路过这里,看上去这个题目比较有意思
就做了一个试试看
不是很动这里的规矩
不知道我得代码是否符合标准


// t9.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "stdio.h"

unsigned int primearr[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};
const int primenum = 12;
unsigned __int64 maxN = 0xFFFFFFFF;

struct  node
{
    unsigned int number;
    int          count;
    char         prime;
    char         two;
    struct node* next;
};

struct node *head = 0;

struct node resultarray[4000];
int  totalnum = 0;

void adjust(node *p)
{
    node *q = p->next;

    while (q && (q->count <= p->count))
    {
        p->next = q->next;
        delete q;
        q = p->next;
    }
}

void enqueue(node *p)
{
    node *q = head;
    node *last = q;

    if (head == 0)
    {
        head = p;
        p->next = 0;
        return;
    }

    if ((p->number < head->number) || 
        ((p->number == head->number) && (p->count > head->count)))
    {
        p->next = head;
        head = p;
        adjust(head);
        return;
    }

    while (q && (p->number > q->number))
    {
        if (p->count <= q->count)
        {
            delete p;
            return;
        }
        last = q;
        q = q->next;
    }

    if (q && (p->number == q->number) && (p->count <= q->count))
    {
        delete p;
        return;
    }

    last->next = p;
    p->next = q;
    adjust(p);
}

void buildresult()
{
    node *p;
    node *n1;
    node *n2;

    head = new node;
    head->next = 0;
    head->number = 2;
    head->count = 2;
    head->prime = 0;
    head->two = 1;

    while (head)
    {
        unsigned __int64 num1, num2, res;

        resultarray[totalnum] = *head;
        totalnum++;

        p = head;
        head = p->next;

        n1 = new node;
        n1->two = p->two;
        n1->prime = p->prime + 1;
        num1 = p->number;
        num2 = primearr[n1->prime];
        res = num1 * num2;
        if (res <= maxN)
        {
            n1->number = (unsigned int)res;
            n1->count = p->count * 2;
            enqueue(n1);
        }

        n2 = new node;
        n2->two = p->two + 1;
        n2->prime = p->prime;
        num1 = p->number;
        res = num1 * 2;
        if (res <= maxN)
        {
            n2->number = (unsigned int)res;
            n2->count  = (n2->two + 1) * p->count / (p->two + 1);
            enqueue(n2);
        }

        delete p;
    }
}


int c = 0;

void getnextvalue(int index, int primenum, int value, unsigned long arr[])
{
    if (primenum > resultarray[index].prime)
    {
        arr[c] = value;
        c++;
        return;
    }

    getnextvalue(index, primenum+1, value, arr);
    getnextvalue(index, primenum+1, value * primearr[primenum], arr);
}

void generatearray(int index, unsigned long arr[])
{
    unsigned int x = 1;
    c = 0;
    for (int i=0; i<= resultarray[index].two; i++)
    {
        getnextvalue(index, 1, x, arr);
        x = x * 2;
    }
}


void sortarr(int count, unsigned long arr[])
{
    unsigned long tmp;
    int index;
    for (int i=0; i<count-1; i++)
    {
        index = i;
        for (int j=i+1; j<count; j++)
            if (arr[j] < arr[index])
                index = j;
        if (index != i)
        {
            tmp = arr[i];
            arr[i] = arr[index];
            arr[index] = tmp;
        }
    }
}

35 楼

代码太长了
一贴不让发
所以只好发了两铁


void Search(unsigned long n, unsigned long *result,int *count,unsigned long arr[])
{
    int i=0;

    if (totalnum == 0)
        buildresult();

    while ((i < totalnum) && (n > resultarray[i].number)) i++;

    if (i == totalnum)
        i--;

    if (n < resultarray[i].number)
        i--;

    *result = resultarray[i].number;
    *count  = resultarray[i].count;

    generatearray(i, arr);
    sortarr(*count, arr);
}


int main(int argc, char* argv[])
{
    unsigned long n, result;
        int count;
    unsigned long arr[4000];

    n = 0xffffffff;
    Search(n, &result, &count, arr);

    printf("result=%u \tcount=%d\n", result, count);
    for (int i=0; i<count; i++)
        printf("%u\t", arr[i]);

    return 0;
}

36 楼

#include<math.h>
#include<stdio.h>
void Search(unsigned long n, unsigned long *result,int *count,unsigned long arr[])
{


    unsigned long x=0;
    int m,a,max=0;
   unsigned long i,j,k=0;

if(n>=60)
{  a=60;
}
else if(n>=6) {
    a=6;
}
else
{a=1;
}
    m=n%a;
for(i=n-m;i>n/2;)
{    

    int count1=0;
    for(j=1;j<=(unsigned long)sqrt(i);j++)
    {
        
        if(i%j==0)
        count1++;
        
    }
    if(i==(unsigned long)sqrt(i)*(unsigned long)sqrt(i))
    count1=2*count1-1;
    else count1=2*count1;
    if(count1>=max)
    {
      max=count1;//最大
      x=i;//result
    }
     i=i-a;
     
}

for(j=1;j<=(unsigned long)sqrt(x);j++)
    {
        
        if(x%j==0)
        {    arr[k]=j;k++;
        }
        
    }
if(max%2==0)
{
for(i=k,j=k-1;i<max;i++,j--)
{
    arr[i]=x/arr[j];
    
}
}
else{
    for(i=k,j=k-2;i<max;i++,j--)
{
    arr[i]=x/arr[j];
}

}


 
*result=x;
*count=max;

}
void main()
{
   unsigned long n,result;
int count,i;
unsigned long arr[1000];
scanf("%d",&n);
    Search(n,&result,&count,arr);
    printf("result:%d   count:%d\narr[%d]:",result,count,count);

 for(i=0;i<count;i++)
 printf("%d  ",arr[i]);

}
呵呵~我的算法数太大的时候很慢,想不出什么办法了

37 楼


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

#define assert(con) if(!(con)){printf("Argument NULL\n");return;}
#define MAX 100

void Search
(
    unsigned long n,        /*输入*/
    unsigned long *result,  /*最大约数的整数*/
    int *count,             /*最大约数个数*/
    unsigned long arr[]     /*存放约数*/
);

void Search
(
    unsigned long n,        /*输入*/
    unsigned long *result,  /*最大约数的整数*/
    int *count,             /*最大约数个数*/
    unsigned long arr[]     /*存放约数*/
)
{
    unsigned long temp = n;
    int iMaxCount = 0;
    unsigned long iResult = 0;
    unsigned long i,j;
    unsigned long alTemp[100] = {0};
    int k;

    assert((result != NULL) && 
           (count != NULL) &&
      (arr != NULL));

    *count = 0;
    *result = 0;

    for(i=1;i<n;i++)
    {
        if(iMaxCount > *count)
        {
            *count = iMaxCount; /*保存最大约数个数*/
            *result = iResult;  /*保存最大约数*/
            memcpy(arr, 
                   alTemp, 
         iMaxCount * sizeof(long));/*保存约数*/
    }
    iMaxCount = 0;
    k = 0;
    memset(alTemp, 0, MAX);

    //printf("[%d]:",i);

    /*求i的约数个数*/
    for(j=1;j<=i;j++)
    {
        if(i%j)
             {
            continue;   /*不是约数*/
        }
        else
        {
        iMaxCount++; /*约数加一*/
        alTemp[k++] = j;/*保存约数*/
        iResult = i; /*保存约数个数最大的值*/
        //printf(" %d ",j);
        }
    }
    //printf("\n");
    }

    printf("[%d]:",*result);
    for(k=0;k<*count;k++)
    {
    printf(" %d ",arr[k]);
    }
    printf("\n");
}

int main ()
{
    /*printf("Call afun():%d\n",afun(80));*/
    unsigned long arr[100] = {0};
    unsigned long n = 100;
    unsigned long result;
    int count;

    Search(n,&result, &count, arr);/*测试*/
}

38 楼

#pragma warning(disable: 4786)

#include <cstdio>
#include <cmath>
#include <cassert>
#include <vector>
#include <algorithm>
#include <map>

using namespace std;

class PrimeList
{
public:
    typedef vector<unsigned long>::size_type size_t;
    unsigned long get(size_t index)
    {
        if (index >= d.size())
            generate(index);
        return d[index];
    }
    void generate(size_t index)
    {
        if (d.size() == 0)
        {
            unsigned long buf[] = {2, 3, 5, 7, };
            d.insert(d.begin(), buf, buf + sizeof(buf)/sizeof(buf[0]));
        }
        for (unsigned long p = d.back() + 2; d.size() <= index; p += 2)
        {
            if (isPrime(p))
                d.push_back(p);
        }
    }
    bool isPrime(unsigned long n)
    {
        size_t i;
        unsigned long dd;
        for (i = 0; dd = get(i), dd * dd <= n; i++)
        {
            if (n % dd == 0)
                return false;
        }
        return true;
    }
    vector<unsigned long> d;
} gPrimeList;

struct node
{
    node():value(0),count(0){}
    unsigned long value;
    unsigned long count;
    map<unsigned long, unsigned> p;
    struct cmp
    {
        bool operator () (const node *a, const node *b)
        {
            if (a->count == b->count)
                return a->value > b->value;
            return a->count < b->count;
        }
    };
};
// greedy
void Search(unsigned long n, unsigned long *result,int *count,unsigned long arr[])
{
    node max_n;
    max_n.value = 1;
    max_n.count = 1;
    for(;;)
    {
        node max_n2, t;
        for (PrimeList::size_t i = 0;; i++)
        {
            __int64 p = gPrimeList.get(i);
            if (p > 0x10000Lu || p * p > __int64(n))
                break;
            __int64 value = __int64(max_n.value) * p;
            if (value > __int64(n))
                break;
            t.value = unsigned long(value);
            t.p = max_n.p;
            unsigned count = ++t.p[i];
            t.count = max_n.count / count * (count + 1);
            if (node::cmp()(&max_n2, &t))
            {
                max_n2 = t;
            }
        }
        if (node::cmp()(&max_n, &max_n2))
        {
            max_n = max_n2;
        }
        else
            break;
    }
    //printf("%d %d %d %d\n", max_n.value, max_n.count, gPrimeList.d.size(), gPrimeList.get(gPrimeList.d.size() - 1));
    *result = max_n.value;
    *count = max_n.count;
    n = max_n.value;
    int i, j = 0;
    for (i = 1; i * i <= n; i++)
    {
        if (n % i == 0)
        {
            arr[j++] = i;
            arr[*count - j] = n / i;
        }
    }
}

39 楼

////Vc++6.0
#include "string.h"
#include "math.h"
int Count(int num[],int len)//求带权值的序列的组合数(权值表示此位置可以取多少个不同的值)
{
    int i,sum=1;

    for(i=0;i<len;i++)
    {
        sum*=num[i]+1;
    }
    return sum;
}

unsigned long fac[32];
int num[32];
int factor(unsigned long n)//求n的所求素数因子放入fac[!max][]中,并将此因子出现次数放入num[]中,返回因子个数
{
    unsigned long f;
    int i,c=0;

    for(f=2;f<=n;f++)
    {
        if(n%f==0)
        {
            for(i=0;i<c;i++)
            {
                if(f==fac[i])
                {
                    num[i]++;
                    break;
                }
            }
            if(i>=c)
            {
                fac[c]=f;
                num[c]=1;
                c++;
            }
            n=n/f;
            f=1;
        }
    }
    return c;
}
int parr=0;
void getarr(unsigned long arr[],unsigned long fac[],int num[],int len,int cur,unsigned long val)
{
    unsigned long v;
    if(len==cur+1)
    {
        for(int i=0;i<=num[cur];i++)
        {
            arr[parr++]=val*(unsigned long)pow(fac[cur],i);
        }
    }
    else
    {
        for(int i=0;i<=num[cur];i++)
        {
            v=val* (unsigned long)pow((double)fac[cur],(double)i);
            getarr(arr,fac,num,len,cur+1,v);    
        }
    }
}
void Search(unsigned long n, unsigned long *result,int *count,unsigned long arr[])
{
    unsigned long i,j,e,cur,t;
    int max=0,ml,c,l;
    unsigned long mfac[32];
    int mnum[32];

    if(n<=0)
    {
        *result=0;
        *count=0;
        return;
    }else if(n==1)
    {
        *result=1;
        *count=1;
        arr[0]=1;
        return;
    }
    e=n/2;
    for(i=n;i>e;i--)
    {
        l=factor(i);
        c=Count(num,l);
        if(c>max)
        {
            memcpy(mfac,fac,l*sizeof(unsigned long));
            memcpy(mnum,num,l*sizeof(unsigned long));
            max=c;
            cur=i;
            ml=l;
        }
        else if(c==max&&i<cur)
        {
            memcpy(mfac,fac,l*sizeof(unsigned long));
            memcpy(mnum,num,l*sizeof(unsigned long));
            max=c;
            cur=i;
            ml=l;
        }
    }
//    printf("%ld,%d\n",cur,max);
//    for(i=0;i<ml;i++)
//        printf("[%d:%ld]",mnum[i],mfac[i]);
//    printf("\n");
    parr=0;
    getarr(arr,mfac,mnum,ml,0,1);
    for(i=0;i<max-1;i++)
        for(j=i+1;j<max;j++)
            if(arr[i]>arr[j])
            {
                t=arr[i];
                arr[i]=arr[j];
                arr[j]=t;
            }
//    for(i=0;i<max;i++)
//    {
//        printf("{%ld}",arr[i]);
//    }
    *result=cur;
    *count=max;
}
 

40 楼

//在18楼已经提交过一个程序,但是计算速度太慢。
//以下把18楼的程序改进了一下,基本思想没变。
//Visual C++ 6.0下编译通过。

/***********************************************
   在N以内(小于等于N)找出一个数,要求:
   1.这个数的约数的个数达到最大,
   2.如果有好几个数满足条件1,仅取最小的那个数
***********************************************/
#include <stdio.h>
#include <math.h>

void Search(unsigned long n, unsigned long *result,int *count,unsigned long arr[]);
void main()
{
    unsigned long n;
    unsigned long *result;
    int *count;
    unsigned long arr[65535]={0};
    result = new unsigned long;
    count = new int;

    printf("输入范围(1~N):N=");
    scanf("%ld",&n);
    Search(n,result,count,arr);

    printf("约数最多数是:%ld,它的约数的个数是:%d\n",*result,*count);
    printf("它的约数分别为:");
    for(int i=0;i<*count;i++)
    {
        if(i%8==0)
            printf("\n");
        printf("%9d",arr[i]);
    }
    printf("\n");
}

void Search(unsigned long n, unsigned long *result,int *count,unsigned long arr[])
{
    unsigned long *prime;
    int pnum=(int)sqrt(n);
    unsigned long rtl=1;    
    int cnt=1;
    unsigned long i;
    int k;
    int a,b,c;
    prime=new unsigned long[pnum];

    /*** 得到1~sqrt(n)的质数数组,存到prime[]中***/
    prime[0]=2;
    a=1;
    for(b=3;b<=pnum;b++)
    {
        for(c=0;c<a;c++)
        {            
            if(prime[c]>sqrt(b))
            {
                prime[a++]=b;
                break;
            }
            if(b%prime[c]==0)
                break;
        }
    }
    prime[a]=0;
    pnum=a;
    /*****************************************/

    for(i=1;i<=n;i++)
    {
        /******以下得到i的约数的个数,存到tmpcnt中**************/
        unsigned long num=i;
        unsigned long primediv[31]={0};    //质因数数组
        int divnum[31]={0};
        int tmpcnt=1;
        int j,l,m;        
        //以下获得质因数数组,比如n=360,则primediv={2,2,2,3,3,5}
        for(l=0;;l++)
        {
            for(j=0;j<pnum;j++)
            {
                if(num%prime[j]==0)
                {
                    num=num/prime[j];
                    break;
                }
            }
            if(j==pnum)
            {
                primediv[l]=num;
                num=1;
            }
            else
                primediv[l]=prime[j];
            if(num==1)    break;
        }
        //以下获得另外一个数组,保存各质因数的个数,比如
        //primediv={2,2,2,3,3,5},则divnum={3,2,1}
        l=0;
        divnum[0]=1;
        for(m=1;m<=31;m++)
        {
            if(primediv[m]==primediv[m-1])
                divnum[l]++;
            else if(primediv[m]!=0)
                divnum[++l]=1;
            else break;
        }
        //得到因数的个数,如divnum={3,2,1},则tmpcnt=(3+1)(2+1)(1+1)
        //因为如果rtl=(p1^n1)(p2^n2)(p3^n3)...
        //其中p1,p2,p3...是质数,n1,n2,n3...是自然数
        //则因数个数为(n1+1)(n2+1)(n3+1)...
        for(l=0;l<=31;l++)
        {
            if(divnum[l]==0)    break;
            tmpcnt*=(divnum[l]+1);
        }
        /**********************************************/
        if(cnt<tmpcnt)
        {
            cnt=tmpcnt;
            rtl=i;
        }
    }
    *result=rtl;
    *count=cnt;

    k=0;
    arr[k]=1;
    arr[cnt-1]=rtl;
    for(i=2;i<=sqrt(rtl);i++)
    {
        if(rtl%i==0)
        {
            arr[++k]=i;
            arr[cnt-k-1]=rtl/arr[k];
        }
    }
}

我来回复

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