スポンサーサイト
0

    一定期間更新がないため広告を表示しています

    カテゴリ:- | | - | - |
    Project Euler013, 014
    0
      JUGEMテーマ:数学

      ProjectEuler013,014解答。

      013:50桁の数100個の和の最初の10桁を求めよ。
      014:100万以下の数から始まるCollatz列(?)の長さで最長のものを与える初項を求めよ。

      013で学んだこと。
      Rubyでファイルを読み込むと1行を一つの要素として扱ってくれるようだ。
      これのおかげで013は大変簡単でした。

      f=open("aaa.txt")
      f.each do |n|
        行(n)に対する処理
      end

      ちなみに型変換も
      int→Stringは
      xxx.to_s
      String→intは
      sss.to_i
      かんたーん。

      014で新たに知ったことは特になし。
      でもCollatz問題のことは知らなかったのでよしとする。
      コーディングはすぐにできたんだけど、少し時間がかかってるんだよね。
      いまは単純に計算してるだけ。
      改善できるとしてはこんな感じか?
      ・ある数を与えた場合に生成されるCollatz列の長さを配列とかに格納しておく。
      ・そうすると別の初期値を与えた場合に途中の値で上記の値が出てきた場合は、もう計算せずにそれまでの列の長さとの和を求めればよい。 
      初期値と列の長さのペアをある程度の数持っていないとあんまり意味がなさそうだし、どの程度持っていればよいかも見当つかないなぁ。

      うーん。。。
      カテゴリ:Project Euler | 20:32 | comments(0) | trackbacks(0) |
      ProjectEuler012
      0
        JUGEMテーマ:数学

        ProjectEuler012の問題がやっと解決。
        約数を500個以上持つ最小の三角数を求めよ、という問題。

        頭の中ではちゃんと解けるのに、コードに落として実行すると答えが違うということが
        ずっと続いていたが、今朝ちょろっとやったらしょうもない間違いを発見した。

        やっぱ朝が良いということか。

        ちなみに高校でも習ったと思うが数Nの約数はNの素因数分解を
        N=(a1^p1)*(a2^p2)*....*(an^pn)
        とすると
        (p1+1)*(p2+1)*...*(pn+1)
        で表すことができる。

        素因数を適当にいくつかとってきて約数を表す方法のパターンを数え上げています。
        各項で1足しているのは0乗があるためです。

        僕も誰かの真似をしてRubyコードを貼ろうかな。

        そういえば、風のうわさではRubyの1行はCの100行に相当する。
        というくらいRubyは実行速度が遅いらしい!(Cが速い?)
        ショック!


        #500個以上の約数をもつ最初の三角数

        def count_division(target)
          total = 1
          div = 2
          count = [1]
          while div <= target
          #約数をカウント(1があるので初期値を1とする)
          count_tmp = 1
            while target%div==0
              target = target/div
              count_tmp +=1
              next
            end
            if div%2 != 0
              div += 2
            else
              div += 1
            end
            count << count_tmp
          end
          count.each do |n|
            total *= n
          end
          return total
        end

        triangle = 0
        i = 1
        while true
          triangle += i
          i += 1
          count = count_division(triangle)
          if count >= 500
           p triangle
            break
          end
        end
         

        カテゴリ:Project Euler | 08:25 | comments(0) | trackbacks(0) |
        素数判定
        0
          JUGEMテーマ:数学

          ProjectEulerのProblem007の改良と、Problem010を解いた。

          試し割りと呼ばれる、素数かどうかを調べたい数をそれより小さい数でどんどん割っていき、
          すべての数で割り切れなければ素数と判定する
          という方法で実装していた。

          しかし、Problem007でも割と時間がかかるし、Problem010ではなかなか終わらないので、
          待ってられねー、問感じであった。
          (ちなみに問題の内容は、問7は10001番目の素数を求めよ、問10は200万以下の素数の和を求めよ、である。)

          改善しないとなー、と思いながらお風呂で物思いにふけっていたら
          割ってみる数は素数だけでよいということに気が付いた。

          具体的には、N(>0)が素数かどうかを調べるためにはN>p*pを満たすような素数pに
          対してのみNを割り切るかどうか調べればよいということだ。

          ということで、これを実装してみたところ、問10でも20秒弱で答えが出た。
          やったぜ。


          itProのRubyをめぐる冒険というコラムが私のような初学者には大変ためになる。
          あと、ProjectEulerをもう少し楽しむために
          「はじめての数論」9784894714922
          という本を注文しました。
          もう群とか環とかなんだっけ?正規部分群?シローの定理?
          等長変換群とかあったなぁ。という感じなので暇つぶしになればいいなぁ。

           
          カテゴリ:Project Euler | 22:54 | comments(0) | trackbacks(0) |
          ProjectEuler_Problem010
          0
             なんだかんだでProject Eulerまだやってます。

            やっとProblem009まで解けました。

            考え方はいいのにコーディングしてみたら、時間がかかりすぎて詰まってしまうということが多いです。

            ちゃんとRubyの文法のお勉強をしないと作業がはかどらないなぁ

            参考書を買おうかしら。


            Rubyで不便だなぁと感じていること。
            For文を大きいほうから小さいほうにループを回せないこと。
            (できるのかな?)

            for(i=Max;i<Min;i--){
            処理
            }
            みたいな書き方できないのかなぁ。

            カテゴリ:Project Euler | 00:26 | comments(2) | trackbacks(0) |
            Problem007
            0
              JUGEMテーマ:数学



              今日はProject EulerのProblem007に手を出した。

              10001番目の素数を求めよ。という問題。

              単純に1から素数かどうかをチェックしていくプログラムを書いたけど遅い。

              多少の工夫はしているけど、ほぼ素直に組んだ。

              改善の余地がありそうなのは、

              Nが素数かどうか判定するために、1から順に数字をカウントアップしていき

              すべての数で割り切れなければ素数と判定しているのだけど
              (実際は、奇数のみチェックし、カウントアップもN/2でやめている)

              やはり無駄が多い気がする。

              どこまでの数をチェックするのが妥当なのだろうか。

              というよりは、小さいほうから割っていくのだから、たとえば

              3と5で割り切れない場合は15で割ってみる必要はないのだけど

              それをやってしまっている。

              動的にカウントアップの上限値を変えるようにすればよいのだろうか?


              エラトステネスのふるいに倣って実装してみたら早いのかな。。。

              まぁでもできたので良し。

              一応、以下ソース。

              #############################################################################
              #
              #  Project Euler Problem6
              #  10001 番目の素数を求めよ.
              #
              ############################################################################

              #素数チェックするメソッド
              #num:素数かどうか反転したい数
              def CheckPrime(num)
                #2は偶数で唯一の素数
                if num == 2 then
                  return true
                end
                #2以降の偶数はすべてfalse
                if num%2==0 then
                  return false
                end
                i = 3
                #チェックしたい数の半分までで十分
                while i <= num /2#上限の値を動的にするともう少し早くなるかな
                   if num%i == 0 then
                     return false
                   else
                     #偶数はとばすので2カウントアップ
                     i = i+2
                   end
                end 
                #ここまで来たら素数確定
                return true
              end

              #素数の数の初期化
              count = 0
              #1はとばして2から素数かどうかをチェックする
              factor = 2
              while true
                if CheckPrime(factor) then
                  count = count + 1
                  #print("The ",count, "th Prime Number is ",factor ,"¥n" )
                end
                if count == 10001 then
                  break
                end
                  factor = factor + 1#ここも改良できる
              end

              print("The ",count, "th Prime Number is ",factor ,"¥n" )




               

              カテゴリ:Project Euler | 23:47 | comments(2) | trackbacks(0) |
              | 1/1PAGES |