DouKaku?beta

解答・コメントを送る方法

コメントを送るには2つの方法があります。
  • 匿名でコメントを書く
    ログインせずにコメントを書くことができます。 名前は「匿名」となります。
  • アカウントを作成してコメントを書く
    アカウントを作成すると、記名での投稿ができます。 また、プロフィールページが作成され、 簡単なプロフィールや 統計情報が表示されるようになります。
どちらの場合も投稿後の修正・削除はできないので、 投稿前によくご確認下さい。

投稿ボタンを押す前に以下の文章を確認してください

  • 当サイトへの投稿は クリエイティブ・コモンズ・ライセンス BY(表示)および、その解釈に同意するものとみなされます。各ページには下のようにライセンス表示が行われます。
    Creative Commons License このサイトの内容は、 クリエイティブ・コモンズ・ライセンスの下でライセンスされています。 [詳細]
  • あなたの投稿したコード・コメント・トピックが再利用・添削されることを望まない場合は、投稿をお控えください。
  • 自分が書いていない、ウェブサイトや書籍などからの無断コピーは著作権の侵害です。著作権者の了解を得るか、自分で0から書いてください。
  • 著作権の侵害、名誉毀損、など投稿内容に問題がある場合、削除することがあります。
  • これらのことにあなたはあらかじめ同意したものとみなされます。

Post comment

Post a comment to the following challenge: 最大公約数（除算禁止） (Nested Flatten)

As a reply to the following comment: shiro: 引き算のみで。 Z80マシン語で遊...(#4783) [show]

[hide]
引き算のみで。

Z80マシン語で遊んでいたころ、除算を使わないでもこれでgcdが計算できることに気づいて大発見をしたような気分になりました。後でよく考えたらユークリッドの互除法を非効率にやっているだけでした。

隣り合うフィボナッチ数の場合は実は減算法でもあまり効率が悪くなりません。常に差がひとつ前のフィボナッチ数になるわけですから。

 gosh> (time (gcd-nodiv (fib 2000) (fib 1999)))
 ;(time (gcd-nodiv (fib 2000) (fib 1999)))
 ; real   0.002
 ; user   0.000
 ; sys    0.000
 1

ループ回数は互除法でやった場合と同じになります。

 gosh> (gcd-nodiv/cnt (fib 2000) (fib 1999) 1)
 1
 1998

実はこの引数の場合は、組み込みのgcd (互除法使用) の方が遅かったりします。bignumの除算が重いんじゃないかな。

 gosh> (time (gcd (fib 2000) (fib 1999)))
 ;(time (gcd (fib 2000) (fib 1999)))
 ; real   0.014
 ; user   0.010
 ; sys    0.000
 1 


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
(define (gcd-nodiv m n)
  (cond [(= n m) n]
        [(or (= m 1) (= n 1)) 1]
        [(> m n) (gcd-nodiv n (- m n))]
        [else    (gcd-nodiv m (- n m))]))

;;
;; 以下は測定用
;;
;;ループ回数のカウント
(define (gcd-nodiv/cnt m n cnt)
  (cond [(= n m) (values n cnt)]
        [(or (= m 1) (= n 1)) (values 1 cnt)]
        [(> m n) (gcd-nodiv/cnt n (- m n) (+ cnt 1))]
        [else    (gcd-nodiv/cnt m (- n m) (+ cnt 1))]))

;;メモワイズ版fib
(define fib
  (let1 memo (make-hash-table 'eqv?)
    (lambda (n)
      (cond [(<= n 2) 1]
            [(hash-table-get memo n #f)]
            [else (let1 val (+ (fib (- n 1)) (fib (- n 2)))
                    (hash-table-put! memo n val)
                    val)]))))
コメント本文
 形式 [?]
コード
 言語
タグ
半角スペースで区切って複数のタグを入力できます。
参考ページタイトル

参考ページURL
利用規約を読んで同意する必要があります。
by guest

Index

Feed

Other

Link

Pathtraq

loading...
Creative Commons License このサイトの内容は、 クリエイティブ・コモンズ・ライセンスの下でライセンスされています。 [詳細]