| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 1949 人关注过本帖
标题:考一下大家的算法...
只看楼主 加入收藏
蓝紫色
Rank: 1
等 级:新手上路
帖 子:17
专家分:0
注 册:2006-5-28
收藏
 问题点数:0 回复次数:18 
考一下大家的算法...

这是第38次编程比赛第一题:

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

说明:
1) 1<N<=2^32-1,每个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。


写出你们的算法就可以了(当然有程序的也可拿出来),考虑空间以及时间方面的问题,比如说省掉一些不必要的计算

搜索更多相关主题的帖子: 算法 内存 约数 result count 
2006-09-29 14:00
wfpb
Rank: 6Rank: 6
等 级:贵宾
威 望:29
帖 子:2188
专家分:0
注 册:2006-4-2
收藏
得分:0 

似乎有点问题,我再看看

[此贴子已经被作者于2006-9-29 18:33:18编辑过]


[glow=255,red,2]wfpb的部落格[/glow] 学习成为生活的重要组成部分!
2006-09-29 18:29
kai
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:52
帖 子:3450
专家分:59
注 册:2004-4-25
收藏
得分:0 
结合例子说一下我的解法: 这个解应该是落在 n/2 与 n 之间, 包括n 本身。

我假定你有了一个方法可以测的某一个数的可约数, 该函数的申明可以是这样的:
void getItsAllDivisor(int n, vector<int> & divisors);

具体以100 这个数为例, 首先我定义一个 类型为 unsigned 变量 number 用来记录这个数 将它初始化为100, 再定义一个 向量容器用来记录该数的所有可约数 vector<unsigned> divisors;

调用函数getItsAllDivisor(number, divisors); 现在你得到了 100 这个数的所有可约的数。

现在用一个for 循环, 从99 一直到 51 在for 循环内部定义一个局部变量 vector<unsigned> temp, 调用函数getItsAllDivisor(i, temp); 然后比较divisors 和temp 的size, 如果temp 的 size 大于等于 divisiors 的 size, 那么使用copy 函数 用temp 覆盖掉 divisors 的内容, 并且将 i 的值付给变量 number, 从而实现对变量 number 的更新。 当这个for 循环结束之后, 我们就得到答案了。 你的函数定义为 void Search(unsigned long n, unsigned long *result,int *count,unsigned long arr[]); 所以只要将 变量number 的值付给 result, 将divisors 的 size 付给count, 将divisors 的内容 copy 到数组 arr 就可以了。

自由,民主,平等,博爱,进步.
中华民国,我的祖国,中华民国万岁!中华民国加油!
本人自愿加入中国国民党,为人的自由性,独立性和平等性而奋斗!
2006-09-29 19:47
ww84020209
Rank: 1
等 级:新手上路
帖 子:190
专家分:0
注 册:2006-8-21
收藏
得分:0 
以下是引用kai在2006-9-29 19:47:42的发言:
结合例子说一下我的解法: 这个解应该是落在 n/2 与 n 之间, 包括n 本身。

我假定你有了一个方法可以测的某一个数的可约数, 该函数的申明可以是这样的:
void getItsAllDivisor(int n, vector<int> & divisors);

具体以100 这个数为例, 首先我定义一个 类型为 unsigned 变量 number 用来记录这个数 将它初始化为100, 再定义一个 向量容器用来记录该数的所有可约数 vector<unsigned> divisors;

调用函数getItsAllDivisor(number, divisors); 现在你得到了 100 这个数的所有可约的数。

现在用一个for 循环, 从99 一直到 51 在for 循环内部定义一个局部变量 vector<unsigned> temp, 调用函数getItsAllDivisor(i, temp); 然后比较divisors 和temp 的size, 如果temp 的 size 大于等于 divisiors 的 size, 那么使用copy 函数 用temp 覆盖掉 divisors 的内容, 并且将 i 的值付给变量 number, 从而实现对变量 number 的更新。 当这个for 循环结束之后, 我们就得到答案了。 你的函数定义为 void Search(unsigned long n, unsigned long *result,int *count,unsigned long arr[]); 所以只要将 变量number 的值付给 result, 将divisors 的 size 付给count, 将divisors 的内容 copy 到数组 arr 就可以了。

题目要求:1<N<=2^32-1,每个N的时限是1000ms。内存限制256M,注意使用适当数据类型,以免溢出.
2^32-1是40多亿大的数,你的算法能保证1秒得出答案吗?


2006-09-29 19:55
wfpb
Rank: 6Rank: 6
等 级:贵宾
威 望:29
帖 子:2188
专家分:0
注 册:2006-4-2
收藏
得分:0 

我也说说我的想法:
2
if大于n;结束 2
判断3%2==0;(如果等于,就把前面的删除,否则不删除)
2*3
if大于n;结束 3
判断4%2==0;(如果等于,就把前面的删除,否则不删除)
3*4;
if大于n;结束 4
判断5%3==0;(如果等于,就把前面的删除,否则不删除)
3*4*5;
if大于n;结束 5
判断6%3==0;(如果等于,就把前面的删除,否则不删除)
4*5*6;
if大于n;结束 6
结束


一直到>=n时,就会知道最基本的有哪些因子。
比如这个题100。
就是到6结束。
所以因子就是1,2,3,4,5,6的各种乘积的集合。


如果是10,那么就是4结束。

[此贴子已经被作者于2006-9-29 20:14:41编辑过]


[glow=255,red,2]wfpb的部落格[/glow] 学习成为生活的重要组成部分!
2006-09-29 20:09
kai
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:52
帖 子:3450
专家分:59
注 册:2004-4-25
收藏
得分:0 
方法倒是有一个, 有点搞笑了, 那就是实现做好一个答案表, 将它存在一个文件里面, 你给出一个数 n , 我就到表里面查一下, 然后给出答案, 这样的话, 1s 完全可以保证。

自由,民主,平等,博爱,进步.
中华民国,我的祖国,中华民国万岁!中华民国加油!
本人自愿加入中国国民党,为人的自由性,独立性和平等性而奋斗!
2006-09-29 20:11
ww84020209
Rank: 1
等 级:新手上路
帖 子:190
专家分:0
注 册:2006-8-21
收藏
得分:0 
以下是引用wfpb在2006-9-29 20:09:50的发言:

我也说说我的想法:
2
if大于n;结束 2
判断3%2==0;(如果等于,就把前面的删除,否则不删除)
2*3
if大于n;结束 3
判断4%2==0;(如果等于,就把前面的删除,否则不删除)
3*4;
if大于n;结束 4
判断5%3==0;(如果等于,就把前面的删除,否则不删除)
3*4*5;
if大于n;结束 5
判断6%3==0;(如果等于,就把前面的删除,否则不删除)
4*5*6;
if大于n;结束 6
结束


一直到>=n时,就会知道最基本的有哪些因子。
比如这个题100。
就是到6结束。
所以因子就是1,2,3,4,5,6的各种乘积的集合。


如果是10,那么就是4结束。




什么意思啊,有点看不懂,是不是求1,2,3,...,k的最小公倍数,找到最大的k,使最小公倍数小于n啊?


2006-09-29 20:29
wfpb
Rank: 6Rank: 6
等 级:贵宾
威 望:29
帖 子:2188
专家分:0
注 册:2006-4-2
收藏
得分:0 
是啊

[glow=255,red,2]wfpb的部落格[/glow] 学习成为生活的重要组成部分!
2006-09-29 20:42
ww84020209
Rank: 1
等 级:新手上路
帖 子:190
专家分:0
注 册:2006-8-21
收藏
得分:0 
以下是引用wfpb在2006-9-29 20:42:06的发言:
是啊

你那个算法是错误的.

前50个总表
序号 合数 分解质因数 约数个数
1 4 2×2 3
2 6 2×3 4
3 12 2×2×3 6
4 24 2×2×2×3 8
5 36 2×2×3×3 9
6 48 2×2×2×2×3 10
7 60 2×2×3×5 12
8 120 2×2×2×3×5 16
9 180 2×2×3×3×5 18
10 240 2×2×2×2×3×5 20
11 360 2×2×2×3×3×5 24
12 720 2×2×2×2×3×3×5 30
13 840 2×2×2×3×5×7 32
14 1260 2×2×3×3×5×7 36
15 1680 2×2×2×2×3×5×7 40
16 2520 2×2×2×3×3×5×7 48
17 5040 2×2×2×2×3×3×5×7 60
18 7560 2×2×2×3×3×3×5×7 64
19 10080 2×2×2×2×2×3×3×5×7 72
20 15120 2×2×2×2×3×3×3×5×7 80
21 20160 2×2×2×2×2×2×3×3×5×7 84
22 25200 2×2×2×2×3×3×5×5×7 90
23 27720 2×2×2×3×3×5×7×11 96
24 45360 2×2×2×2×3×3×3×3×5×7 100
25 50400 2×2×2×2×2×3×3×5×5×7 108
26 55440 2×2×2×2×3×3×5×7×11 120
27 83160 2×2×2×3×3×3×5×7×11 128
28 110880 2×2×2×2×2×3×3×5×7×11 144
29 166320 2×2×2×2×3×3×3×5×7×11 160
30 221760 2×2×2×2×2×2×3×3×5×7×11 168
31 277200 2×2×2×2×3×3×5×5×7×11 180
32 332640 2×2×2×2×2×2×3×3×3×5×7×11 192
33 498960 2×2×2×2×3×3×3×3×5×7×11 200
34 554400 2×2×2×2×2×3×3×5×5×7×11 216
35 665280 2×2×2×2×2×2×3×3×3×5×7×11 224
36 720720 2×2×2×2×3×3×5×7×11×13 240
37 1081080 2×2×2×3×3×3×5×7×11×13 256
38 1441440 2×2×2×2×2×3×3×5×7×11×13 288
39 2162160 2×2×2×2×3×3×3×5×7×11×13 320
40 2882880 2×2×2×2×2×2×3×3×5×7×11×13 336
41 3603600 2×2×2×2×3×3×5×5×7×11×13 360
42 4324320 2×2×2×2×2×3×3×3×5×7×11×13 384
43 6486480 2×2×2×2×3×3×3×3×5×7×11×13 400
44 7207200 2×2×2×2×2×3×3×5×5×7×11×13 432
45 8648640 2×2×2×2×2×2×3×3×3×5×7×11×13 448
46 10810800 2×2×2×2×3×3×3×5×5×7×11×13 480
47 14414400 2×2×2×2×2×2×3×3×5×5×7×11×13 504
48 17297280 2×2×2×2×2×2×2×3×3×3×5×7×11×13 512
49 21621600 2×2×2×2×2×3×3×3×5×5×7×11×13 576
50 32432400 2×2×2×2×3×3×3×3×5×5×7×11×13 600


2006-09-29 20:53
wfpb
Rank: 6Rank: 6
等 级:贵宾
威 望:29
帖 子:2188
专家分:0
注 册:2006-4-2
收藏
得分:0 
我看错了,对于是否我的想法错了,我不知道。

我不是想求最小公倍数,是答案。

我是说,那些k以下的数字可以构成得到的满足条件的数字的因子。

但答案还不是那个。

[glow=255,red,2]wfpb的部落格[/glow] 学习成为生活的重要组成部分!
2006-09-29 21:17
快速回复:考一下大家的算法...
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.052879 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved