主题:第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。
回复列表 (共47个回复)
41 楼
Mejao [专家分:30] 发布于 2006-08-20 10:23:00
hehe jiu shi zhe
42 楼
luyantie [专家分:0] 发布于 2006-08-20 11:43:00
我编好了 如何提交啊
43 楼
intelinside [专家分:170] 发布于 2006-08-20 12:40:00
一时想不出来
44 楼
luyantie [专家分:0] 发布于 2006-08-20 13:07:00
#include<stdio.h>
#include<stdlib.h>
int yueshu(int);
main()
{
int num,e,h=0,sum,x;
printf("输入你要查询的范围\n");
scanf("%d",&num);
for(e=2;e<=num;e++){
sum=yueshu(e);//sum 是约数的个数
if(h<sum){
h=sum;
x=e;}//x是约数最多中最小的数
else {
if(h==sum)
if(e<x)
x=e;
}
}
printf("约数最多的是%d有%d个约数",x,h);
system("pause");
return 0;
}
int yueshu(int digia)
{
int m,n=0;
for(m=1;m<=digia;m++){
if(digia%m==0)
n=n+1;
}
return n;
}
45 楼
ITER [专家分:680] 发布于 2006-08-20 13:42:00
不好意思 大哥 我这两天出去了
昨天晚上才看到题目 今天早上10点起来开始编的- -
迟到了
#include <iostream>
#include <math.h>
using namespace std;
typedef struct sample
{
unsigned long value;
unsigned long Tmp[2000];
int Count;
sample *next;
}sample;
void Search(unsigned long n, unsigned long *result,int *count,unsigned long arr[])
{
int i=2;
sample *p3;
unsigned long low;
unsigned long high;
unsigned long half = n/2;
unsigned long Sqrt = sqrt(n);
unsigned long tmp=0;
int Decount=0;
int beishu=2;
int TCount=1;
int max = 0;
int flag = 1;
unsigned long maxV;
int maxresult;
sample *maxAddress = NULL;
sample *head=NULL,*p1=NULL,*p2=NULL;
if(1==n)
{
*result = 1;
*count = 1;
arr[0] = 1;
return ;
}
if(1<=n&&n<12)
{
switch(n)
{
case 1:*result=1;*count=1;arr[0]=1;break;
case 2:
case 3:*result=2;*count=2;arr[0]=1;arr[1]=2;break;
case 4:
case 5:*result=4;*count=3;arr[0]=1;arr[1]=2;arr[2]=4;break;
case 6:
case 7:
case 8:
case 9:
case 10:
case 11:*result=6;*count=4;arr[0]=1;arr[1]=2;arr[2]=3;arr[3]=6;break;
}
return;
}
head = new sample;
head->value = 1;
head->next = NULL;
for(;i<=Sqrt&&flag;i++)
{
high = n/i;
low = half/i;
for(;low<=high;low++)
{
if(i>low)
continue;
tmp=i*low;
p1 = head;
while(p1->value!=tmp&&p1->next!=NULL)
{
p1 = p1->next;
}
if(p1->value==tmp)
{
p1->Tmp[p1->Count++] = i;
if(p1->Count>max)
{
max = p1->Count;
maxV = p1->value;
maxAddress = p1;
}
}
else
{
p2 = new sample;
p2->value = tmp;
if(12==tmp)
p3=p2;
p2->Tmp[0] = i;
p2->Count = 1;
p1->next = p2;
p2->next = NULL;
}
}
}
*result = maxV;
maxresult=(max+1)*2;
*count = maxresult;
arr[0] = 1;
maxresult--;
for(i=1;i<=max;i++)
{
tmp = maxAddress->Tmp[i-1];
arr[i] = tmp;
arr[maxresult-i] = maxV/tmp;
}
arr[maxresult] = maxV;
}
main()
{
unsigned long haha;
int gaga;
int i,j;
unsigned long arr[100];
for(i=70;i<120;i++)
{
Search(i,&haha,&gaga,arr);
cout<<i<<" "<<gaga<<" "<<haha<<" ";
for(j=0;j<gaga;j++)
cout<<arr[j]<<" ";
cout<<endl;
}
}
46 楼
ITER [专家分:680] 发布于 2006-08-20 13:47:00
去吃饭喽 肚子都饿死了
我来回复