查看完整版本: 2008-04-08 Ruby 测试题(00010)

2008-04-08 Ruby 测试题(00010)

2的15次方是32768，每个数字之和是：3 + 2 + 7 + 6 + 8 = 26
那么，2的1000次方每个数字之和是多少呢？
（先做这个，随后上附加题）

1366
别告诉我还有更简单的方法来计算 ：）

**** Hidden Message *****

[[i] 本帖最后由 bbschat 于 2008-4-8 09:44 编辑 [/i]]

你的已经够简单了，:lol 。

我要变成代码偷窃者咯。。。

我的方法肯定不是最简单的，还是看看高手最简单的吧

哪个，顺便问一下 jmouse
Project Euler 做了几题了？这两天我把进度推进到了64 题，可是现在看不到 Top1000了，不知道还差多少能进榜。

1366，不知道算不算简单。
**** Hidden Message *****

回复 6# 的帖子

Your current rating is 40% genius, having solved 75 out of 188 problems.
我是按难度来做的。
目前为止跳过了两道。
一个是76，一个是54。
76我用回溯，但是应付100好像时间太长了，我没信心继续运行下去，准备换方法。
54我嫌太复杂，恩，准备把54简化一下过几天出在这里，哈哈。

之前有一道题，没用RUBY写，是那个猜密码的，用纸+笔，1分钟就出结果了。

[[i] 本帖最后由 jmouse 于 2008-4-8 15:18 编辑 [/i]]

我做题看兴趣，基本上按难度排吧，难度小于第 99 题的都　Over了。
但也跳着做，比如 102，108，122 我就过了。

刚刚下午又推进了2题，Now is 35% genius, having solved 66 out of 188 problems

54 过了，梭哈~我喜欢，花了2个半小时去解。以后可以做个游戏了。
76还没看，密码那题我暴力列出前20位所有的可能性，然后查找符合“The ”的字符，果然有还只有1个，呵呵~

[[i] 本帖最后由 bbschat 于 2008-4-8 17:15 编辑 [/i]]

**** Hidden Message *****

[[i] 本帖最后由 xavier 于 2008-4-8 17:49 编辑 [/i]]

回复 10# 的帖子

我以前也是用 split 分割，后来我发现 scan 也能分割，而且后面可以直接跟 代码块，不用加上 .each ，就换成 scan 了，至于哪个方法效率高倒是没比较过，至少代码是省一点是一点。 :lol

用Benchmark跑了一下,发现还是split快一些
              user            system       total               real
scan    1.469000   0.000000   1.469000 (  1.468000)
split      0.968000   0.000000   0.968000 (  0.969000)

Benchmark 还是蛮有用的，就是用起来有点麻烦。
不怎么舒服，楼上各位有没有好的模版参考下？

傍晚时分又推进了 2 题，081 为了调整坐标把我折腾得够呛。
069 硬算了前 5 个最大数字立马找到规律，20分钟解决~

Your current rating is 36% genius, having solved 68 out of 188 problems.

来踩拉～[code]def initialize
    @a = g((2**1000).to_s)
  end
  
  def g(x)
    s = 0
        for i in 0...x.size
          s += x.at(i).to_i
        end
        return s
  end[/code]

做了81就可以想82了。
69貌似我没花多少时间。[code]def Euler69(x)
  $arr=[]
  $arr<<2
  $arr<<3
  ret = 6
  while ret < x
    NextPrime()
    ret *= $arr.last
  end
  puts ret/$arr.last
end
def isPrime?(number)
  n = 0
  while $arr[n]**2<=number
    return false if number % $arr[n] == 0
    n += 1
  end
  return true
end
def NextPrime()
  n = $arr.last + 2
  while true
    if isPrime?n then
      $arr<<n
      break
    end
    n += 2
  end
end
#test
Euler69(1000000)[/code]另外，我说手工做的不是那个圣经的密码，圣经这个我是暴力猜三位用ASCII码范围来看的。
我手工做的是79题。

附加题来了。
把题目里的1000改成100000。

说是附加，其实是因为我做这道题目的时候还不知道Ruby的整型精度有那么高，白写了那么堆代码，好不甘心啊。
可以顺便讨论下在Ruby内部是怎么处理形如100！以及2的1000次方这类大数的，为什么精确度那么高的情况下又算得那么快。不知道谁能找到些资料来学习学习。

100000不够，Ruby 还是可以直接算，还得再加 1 个0，
By The Way 直接在Scite 显示 2 ** 100000 让我死机了 。。。。。。:L

如图，刚上去就看见了。
102本来想用矢量乘做的，后来偷懒了，直接一排的IF ELSE搞定。

今天战果：
Your current rating is 39% genius, having solved 73 out of 188 problems.

比较有意思的是第 71 题，一行代码解决~
然后看到73题，以为同样简单，结果被71的老套路给套死了，换成死办法才出结果。汗自己一个~

[[i] 本帖最后由 bbschat 于 2008-4-9 22:41 编辑 [/i]]

Your current rating is 42% genius, having solved 79 out of 188 problems.

82搞定看了眼 83 ，晕了，竟然还没完没了了 ~~~ 收工，今天不做题了

单行....

(2<<999).to_s.split('').inject(0){|k,v| k+=v.to_i}

=> 1366

product = 2**1000
sum = 0
while product != 0
  sum += product % 10
  product /= 10
end

puts sum

学习ing

回复 16# 的帖子

以前做高精度的时候，是用数组存储数，模拟笔算实现的！以下阶乘的c代码实现：

#include "stdio.h"  

int n;  
int a[2000],b[2000];  

void mult(int i,int m)  
{
        int j;  
        for(j=1;j<=i;j++)  
                a[j]=a[j]*m;  
        for (j=1;j<i+4;j++)  
        {
                a[j+1]+=a[j]/10; a[j]=a[j]%10;  
        }  
}  

void prnt(void)  
{
        int i,j;  
        for (j=2000;a[j]==0;j--);  
        for (i=1;i<=j;i++)  
        {
                printf("%1d",a[j-i+1]);  
                if(i%50 ==0)
                        printf("\n");  
        }  
        printf("\n");  
}  

main()  
{
        int i,j;  
        printf("input n:\n");  
        scanf("%d",&n);
        for(i=2;i<2000;i++)                 
                a[i]=0;         
        a[1]=1;  
        j=1;  
        for(i=2;i<=n;i++)                 
        {
                mult(j,i);         
                for (j=2000;a[j]==0;j--);  
        }  
        prnt();  
}

[[i] 本帖最后由 idoit 于 2008-4-20 11:15 编辑 [/i]]

我来看看

dddddddddddddddddddddddddd

回复 2# 的帖子

看看是什么算法。呵呵

跟我的想法一样，这个题目比较好。

**** Hidden Message *****

[[i] 本帖最后由 neohsiao 于 2008-7-13 13:51 编辑 [/i]]

学习一下