24小时热门版块排行榜    

CyRhmU.jpeg
查看: 3387  |  回复: 23
本帖产生 7 个 程序强帖 ,点击这里进行查看
当前只显示满足指定条件的回帖,点击这里查看本话题的所有回帖

libralibra

至尊木虫 (著名写手)

骠骑将军

★ ★ ★
ben_ladeng(金币+3, 程序强帖+1): 欢迎继续 2011-05-17 06:43:27
对此题我相当无语,难度在20题以内,我也不知道具体程序跑了多久,反正我吃了个泡面回来,打印出结果了,应该超过10分钟了

c的,matlab对此表示鸭梨很大
CODE:
#include
#include

int main(int args, char* argv[])
{
        long result=1,trinum=0,curnum=1;
        int n=0,i=0,big=0;
        int stop = 500;                //停止要求的除数个数,改成5可以测试28
        while(n         {
                n = 0;
                trinum = 0;
                // 计算当前三角数
                for(i=1;i<=curnum;i++)
                        trinum += i;

                // 从1开始除,计算除数个数
                for(i=1;i<=trinum;i++)
                {
                        if(trinum%i==0) // 如果整除,n+1
                                n += 1;
                }
               
                if(n>=stop) //如果超过stop个,保存结果跳出循环,这里是500个
                {
                        result = trinum;
                        break;
                }

                //如果没超过stop个,记录当前最大的个数并输出
                //这个if可以不要,因为我运行以为电脑死机了
                //所以加了这个判断,找到更接近stop的除数个数时输出,让我有点盼头
                if(n>big)  
                {
                        big = n;
                        printf("Current number: %i [%d]\n",trinum,big);
                }

                //自加自然数增加1,trinum = sum(1:curnum)
                curnum++;
        }
       
        // 打印结果
        printf("%i\n",result);
       
        system("PAUSE");
        return 0;
        }

结果
CODE:
% ans =
%       76576500

[ Last edited by libralibra on 2011-5-17 at 18:14 ]
matlab/VB/python/c++/Java写程序请发QQ邮件:790404545@qq.com
2楼2011-05-17 05:38:26
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

智能机器人

Robot (super robot)

我们都爱小木虫

sudo

木虫 (正式写手)

★ ★ ★ ★
小木虫(金币+0.5):给个红包,谢谢回帖
余泽成(金币+3, 程序强帖+1): 谢谢参与交流! 2011-05-17 22:10:21
抛砖引玉一个思路:
CODE:
1. 建立素数表prime[N],N取一个比较大的值
2. 对x=(1+i)*i/2进行质因数分解:
    x=k_1^m_1 * k_2^m_2 ... * k_n^m_n
    其中^表示指数,k_1 ... k_n表示素数
3. 计算x因子总数:
    divisors = (m_1 + 1) * (m_2 + 1) * ... * (m_n + 1)
4. 判断divisors是否超过500,如果没有,跳到第2步,尝试下一个x;如果已经超过500,则输出x

有素数表之后,这个算法应该比较快,因为质因数分解的时候,只要从小到大判断对素数的整除性,然后顺便统计质因数的指数,同时如果能整除,试除用的x可以缩小为
CODE:
x/=prime[i]

再继续作测试,这样,算法很快就收敛了

问题在于事先对prime[N]中的N的估计怎样才合理,恩...

[ Last edited by sudo on 2011-5-17 at 12:56 ]
4楼2011-05-17 12:54:30
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

huycwork

金虫 (著名写手)

★ ★ ★ ★
小木虫(金币+0.5):给个红包,谢谢回帖
余泽成(金币+3, 程序强帖+1): 好详细的分析! 2011-05-17 22:24:53
想到一个依赖组合计数的算法:
首先分析特殊情况,对于一个a1*a2*a3*a4*...*an=A酱紫的数,假定a1 如,2*3*5*7=210的因数数有:
2, 3, 5, 7
6, 10, 14,15, 21,35
30, 70,105,42
210
麻烦的问题是不完全是素数的情况,对于任意C=A*B,令A和B为素数积,当且仅当AB没有交集的时候C才是素数积,否则就带来可可怕的乘方,乘方会产生很多相同的因数。为了解决这个问题,需要分析素数的乘方能产生多少个相同解:
首先分析下素数乘方可能产生的相同解个数,假定某数可以分解出n个相同的素数因子:a1,a2,...an,这些因子的恼人之处就在于,不同的乘数可能产生相同的乘积,原本这些乘积是独立计数的,最终却需要剔除。一个简单的解决办法是,将n个数叠起来,使它们像这样:a1, a1^2, a1^3...a1^n,对这样的数列再次应用素数组合,但分析的时候要独立分析:这些数中只取一个的时候,产生独立解,其余的情况,都不能再计数,理由是,数列中的任意数的组合要么相同,要么不可能产生。因此,对于n个素数相同的情形,只能将其算一个素数的组合位置,但是要记入n种状况。最终的组合要借助计算机来完成,举例如下:
8*6 = 2*2*2*2*3,分离素数乘方表和素数表,得
乘方表:2,4,8,16,素数表2,3
在2的位置需要替换4种情况,当C21时,2本来只计数1,现在需要计数4,C22时2*3本来只有一个解,现在有4个解。对于2和3而言,原本的解像这样:
2, 3, 2*3
现在的解要将4个值替换到2的位置:
2,4,8,16,3,2*3,4*3,8*3,16*3
在更多情况下和这个类似,如果是24*6 = 2*2*2*3*2*3,分离出来的素数表仅有2,3,乘方表则有两个:2,4,8,16和3,9
原来的解是2,3,2*3,分两遍替换进去就成了这样:
替换2变成:2,4,8,16,3,2*3,4*3,8*3,16*3
再替换掉3变成:2,4,8,16,3,9,2*3,2*9,4*3,4*9,8*3,8*9,16*3,16*9
可以看到,由于无法知道哪个数是需要替换的,所以也无法直接构建公式,光组合算法还不成,得在组合算法之上再递归计数。
生成因数表和递归计数都不是啥问题,问题是组合算法,排列组合的算法的复杂度很高啊…
漩涡的中心有一块空地,空空的。
5楼2011-05-17 13:41:19
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

wangww2011

木虫 (著名写手)

★ ★ ★
小木虫(金币+0.5):给个红包,谢谢回帖
余泽成(金币+2, 程序强帖+1): 谢谢参与交流! 2011-05-17 22:30:26
楼上的分析的很多阿
还是直接写代码吧
最简单就是遍历了,其实也不是很慢,2秒多一点
优化一下也没有快多少,0.1s
先看运行结果
CODE:
triangle_num=76576500
slow version, elapsed time=2.060000 seconds.
triangle_num=76576500
normal version, elapsed time=0.090000 seconds.

代码:
CODE:
#include
#include
#include

#define TIMERSTART clock_t start_time,stop_time;double elapsed_time;start_time = clock();
#define TIMERSTOP stop_time = clock();elapsed_time=(double)(stop_time-start_time)/CLOCKS_PER_SEC;printf("elapsed time=%f seconds.\n",elapsed_time);

int euler12(int a, long n){
  static int last_a=0;
  static int count=1;
  int tmp_count=0;
  int i=0;
  
  for(i=a;i     if(n%i==0){
      if(i>last_a){
         last_a=i;
         tmp_count=count;
         count=2;
         return tmp_count*euler12(i,n/i);
       }
      
       count++;      
       return euler12(i,n/i);
    }
  }


  tmp_count=count;
  count=1;
  last_a=0;

  if (i*i-n==0){
    return 3*tmp_count;
  } else {
    return 2*tmp_count;
  }
}



int slow(int n){
  int i=0;
  int count=0;
  for(i=2;i<=sqrt(n);i++){
    if(n%i==0){
      count++;
     }
  }

  if (i*i-n==0) {
    return 2*count+1;
  }

  return 2*(count+1);
}


int main(void){
  long triangle_num=1;
  int i=2;
  int divisor_num=500;
  

  TIMERSTART;

  do {
    triangle_num+=i;
    i+=1;
  }while(slow(triangle_num)
  printf("triangle_num=%ld\n slow version, ",triangle_num);
  TIMERSTOP;



  start_time = clock();  
  triangle_num=1;
  i=2;

  do {
    triangle_num+=i;
    i+=1;
  }while(euler12(2,triangle_num)
  printf("triangle_num=%ld\n normal version, ",triangle_num);
  TIMERSTOP;

  return 0;
}

11楼2011-05-17 16:04:54
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

holmescn

金虫 (正式写手)

★ ★ ★ ★
小木虫(金币+0.5):给个红包,谢谢回帖
余泽成(金币+3, 程序强帖+1): 鼓励参与交流! 2011-05-19 19:16:20
CODE:
# -*- coding: utf-8 -*-

# 初始化一个质数表
i = 0
primes = range(2, 100)
while i < len(primes):
    primes = [x for x in primes if x == primes[i] or x % primes[i] != 0]
    i = i + 1

def numbersOfFactors(n):
    """计算n的因子数
    使用了sudo说的计算方法
    加上一个质数分解
    """
    factorNumbers = 1
    factorTimes = 0
    i = 0
    while i < len(primes):
        if n % primes[i] == 0:
            factorTimes += 1
            n /= primes[i]
            continue
        else:
            if factorTimes != 0:
                factorNumbers *= factorTimes + 1
                factorTimes = 0
            i = i + 1
            if n == 1:
                break
    return factorNumbers

# 从第三个三角数开始算,只算第奇数个三角数
n = 3
while numbersOfFactors(n*(n+1)/2) < 500:
    n += 2

# 为防止对偶数个三角数的遗漏,有最后这个计算
if numbersOfFactors(n*(n-1)/2) > 500:
    print n*(n-1)/2
else:
    print n*(n+1)/2

写了个质数分解版的。速度是很快啊!

[ Last edited by holmescn on 2011-5-19 at 16:34 ]
16楼2011-05-18 17:52:06
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

匿名

用户注销 (小有名气)

★ ★ ★ ★
小木虫(金币+0.5):给个红包,谢谢回帖
余泽成(金币+3, 程序强帖+1): 鼓励交流!欢迎常来程序语言版! 2011-05-24 12:36:56
本帖仅楼主可见
19楼2011-05-24 09:00:01
已阅   回复此楼   编辑   查看我的主页

asaka

银虫 (初入文坛)

★ ★ ★ ★
小木虫(金币+0.5):给个红包,谢谢回帖
余泽成(金币+3, 程序强帖+1): 鼓励交流! 2011-09-09 23:16:14
Python简洁版:
CODE:
def facp(n) :
  for i in xrange(2,n) :
    while n%i == 0 :
      n /= i
      yield i
    if i**2 > n : break
  if n!=1 : yield n

for n in xrange(3,99999) :
  p = list(facp(n/2))+list(facp(n+1)) if n%2==0 else list(facp(n))+list(facp((n+1)/2))
  c = reduce( lambda x,y: x*y, [p.count(i)+1 for i in set(p)] )
  if c > 500 : break
print n*(n+1)/2

21楼2011-09-09 00:51:35
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖
相关版块跳转 我要订阅楼主 libralibra 的主题更新
普通表情 高级回复(可上传附件)
信息提示
请填处理意见