CommonLisp Scheme Part13

1 名前：デフォルトの名無しさん [2005/05/12(木) 21:44:01 ] 過去スレ Part1: piza2.2ch.net/tech/kako/987/987169286.html Part2: pc.2ch.net/tech/kako/1002/10025/1002584344.html Part3: pc.2ch.net/tech/kako/1008/10082/1008220265.html Part4: pc.2ch.net/tech/kako/1016/10162/1016211619.html Part5: pc3.2ch.net/tech/kako/1023/10230/1023091882.html Part6: pc3.2ch.net/tech/kako/1031/10315/1031560687.html Part7: pc5.2ch.net/tech/kako/1042/10421/1042167213.html Part8: pc5.2ch.net/tech/kako/1058/10582/1058263391.html Part9: pc2.2ch.net/test/read.cgi/tech/1069594582/ Part10: pc5.2ch.net/test/read.cgi/tech/1075630259/ Part11: pc5.2ch.net/test/read.cgi/tech/1091456033/ Part12: pc8.2ch.net/test/read.cgi/tech/1100229366/ 関連リンクは>>2-10あたり 552 名前：デフォルトの名無しさん mailto:sage [2005/07/08(金) 23:58:27 ] >>551 Common Lisp 勉強汁 553 名前：デフォルトの名無しさん mailto:sage [2005/07/08(金) 23:59:42 ] >>551 mapcanはmapcarと同じ動作をした後に各館数の返り血をappendで連結した物を返す関数。 #`はそのシンボルを関数として扱うという意味。 554 名前：デフォルトの名無しさん mailto:sage [2005/07/09(土) 00:04:19 ] >>552-553 よくわかりました。 本当にありがとうございました。 555 名前：デフォルトの名無しさん mailto:sage [2005/07/09(土) 00:06:49 ] >>553 重箱の隅ですまんが append ではなく nconc、#` ではなく #' だね。 556 名前：デフォルトの名無しさん mailto:sage [2005/07/09(土) 02:43:36 ] 素人質問への解答乙。 つか、明らかに荒らしだよなこいつの質問は。 557 名前：デフォルトの名無しさん mailto:sage [2005/07/09(土) 02:44:24 ] 基本的な関数のみで書いた、初心者向け版。 (defun p (x) (if (null x) '() (if (consp (car x)) (append (p (car x)) (p (cdr x))) (cons (car x) (p (cdr x)))))) 558 名前：デフォルトの名無しさん mailto:sage [2005/07/09(土) 03:01:55 ] Scheme には mapcan が無いとお嘆きの貴兄に、Scheme 版。 (define (p x) (if (list? x) (apply append (map p x)) (list x))) 559 名前：デフォルトの名無しさん mailto:sage [2005/07/09(土) 03:49:56 ] nconc や append! を使う自信が無くて、つい append を使ってしまう自分。 560 名前：デフォルトの名無しさん [2005/07/09(土) 09:51:51 ] (defun p (x) (cond ((null x) '()) ((consp x) (nconc (p (car x)) (p (cdr x)))) (t (cons x '())))) (p '((x . y) (x))) 561 名前：デフォルトの名無しさん mailto:sage [2005/07/09(土) 16:49:29 ] >>559 静的関数型言語方面じゃ型推論と同じなノリで、 破壊しても問題ないと推論される場合には破壊的にやっちゃうようなコードを吐かせよう、 みたいなことやってるみたいね。 ttp://sky.zero.ad.jp/~zaa54437/programming/clean/LanguageReport21/Chap9.html 562 名前：デフォルトの名無しさん mailto:sage [2005/07/09(土) 19:21:50 ] >>548 うまいこと宿題やってもらえて良かったね。 563 名前：デフォルトの名無しさん mailto:sage [2005/07/09(土) 21:46:39 ] 最近に処理系では破壊的な方が速いとは限らない みたいなことがANSI Common Lisp(P. Graham)に書いてあったんだけど、そんなもんなのかね。 どうしたらそうなるのか見当もつかないんだが。 564 名前：デフォルトの名無しさん mailto:sage [2005/07/09(土) 22:03:44 ] gcがめちゃくちゃ速いから？ 565 名前：デフォルトの名無しさん mailto:sage [2005/07/09(土) 22:15:14 ] Write Barrier のコストとか。 566 名前：デフォルトの名無しさん mailto:sage [2005/07/10(日) 00:09:20 ] copy on write とか? 567 名前：デフォルトの名無しさん [2005/07/10(日) 00:14:17 ] ttp://www.ai.mit.edu/projects/cl-http/dist/からcl-http-70-190a.tar.gz落として cmuclで動かそうとしたんだけどパッチすらあたらなかった。 うまく動作してる人いない？ 568 名前：デフォルトの名無しさん mailto:sage [2005/07/10(日) 02:21:43 ] >>561 ああっ、それいいなあ。 LISP と関数型言語の差って、何でも自分でいじれるオフロード車と、外装内 装に便利なものが作り込まれたタウンカーの差みたいなものかな。 569 名前：デフォルトの名無しさん [2005/07/11(月) 22:48:53 ] 総称関数モデルがメッセージ駆動モデルよりも強力だといえるのは何故？ メリットとかデメリットとか教えて欲しい。 570 名前：デフォルトの名無しさん mailto:sage [2005/07/11(月) 23:08:22 ] >>569 メッセージ駆動モデルって何? 571 名前：デフォルトの名無しさん mailto:sage [2005/07/12(火) 00:21:25 ] >>570 メソッドはオブジェクトに属していて、オブジェクトにメッセージを送ることでメソッドが活性化される。 メソッドはデータと一緒に継承される。 SmalltalkとかJavaとかはメッセージ駆動モデルなんだって。 572 名前：デフォルトの名無しさん mailto:sage [2005/07/12(火) 00:29:57 ] それって総称関数のサブセットじゃないか 573 名前：デフォルトの名無しさん mailto:sage [2005/07/12(火) 02:54:29 ] Lisp 関係の古典がオンラインで読めるようになったので一応アドレス貼っておきますね。 John McCarthy, Paul W. Abrahams, Daniel J. Edwards, Timothy P. Hart and Michael I. Levin. LISP 1.5 Programmer’s Manual. The M.I.T. Press, 1962, second edition. community.computerhistory.org/scc/projects/LISP/book/LISP%201.5%20Programmers%20Manual.pdf Berkeley and Bobrow, editors. The Programming Language LISP: Its Operation and Applications. Information International, Inc., March 1964 and The MIT Press, April 1966. community.computerhistory.org/scc/projects/LISP/book/III_LispBook_Apr66.pdf 574 名前：デフォルトの名無しさん mailto:sage [2005/07/12(火) 03:50:45 ] >>571 そういう話は無益だから止めれ Java にメッセージ式は無い Smalltalk のメソッドはクラスに属している（クラスもオブジェクトだけど） 575 名前：デフォルトの名無しさん mailto:sage [2005/07/12(火) 09:17:12 ] Ｒｕｂｙｙｙｙｙｙｙｙｙｙｙｙｙｙｙｙｙｙｙｙｙｙｙｙ 576 名前：デフォルトの名無しさん mailto:sage [2005/07/12(火) 17:19:47 ] とりあえず総称関数だとマルチメソッドが考えやすい。レシーバーだけでなく、複数の引数のクラスで処理を分けたいときに便利。 その分、メソッドが特定のクラス(やオブジェクト)に属さないのでオブジェクト指向モデリングとやや相性が悪い。 総称関数の方ができることが多い(いや、究極的にはできることは同じだけどやり易さとして)けど、オブジェクト指向とはちょっと考え方が違う感じ。メッセージモデルの方がオブジェクト指向らしい。 もっと計算理論的な話は別の人に任す。 577 名前：デフォルトの名無しさん mailto:sage [2005/07/12(火) 21:51:56 ] 複数引数の型を見て処理を割り振る話(メソッド・ディスパッチだっけ？)について。 多くのOO言語では、静的な解決しかできない。 総称関数ベースなら、呼び出された時の型を見て動的に処理を割り振ることができる。 これがメリット？ 578 名前：デフォルトの名無しさん mailto:sage [2005/07/12(火) 22:15:42 ] >>577 マルチディスパッチと動的ディスパッチは一応別の問題だよね。 Smalltalkなんかはシングルの動的ディスパッチじゃないかな。 静的なマルチディスパッチの例としてはC++の関数や演算子ね。 579 名前：デフォルトの名無しさん mailto:sage [2005/07/12(火) 22:20:22 ] えぇ〜とLispのは、具体的なメソッド選択を明示的に書く仕組みだったと思います。(実使用体験０、80年代のbit記事受け売り) ってな話だと、>>578とは違うんじゃないかなぁ〜。 580 名前：デフォルトの名無しさん mailto:sage [2005/07/12(火) 22:39:20 ] >>577 >多くのOO言語では、静的な解決しかできない。 んな事は無い 581 名前：577 mailto:sage [2005/07/12(火) 22:42:26 ] >>580 そのとおり。 でも、引数を親クラスにキャストしてメソッド呼出したら、、、 582 名前：デフォルトの名無しさん mailto:sage [2005/07/12(火) 22:53:23 ] 何でキャストの話が出て来るんだよ OO のモデルなんか趣味の世界だから、自分で使って勝手に判断すれば良い 583 名前：577 mailto:sage [2005/07/13(水) 00:00:29 ] なんだぁ？ヴァカか。 584 名前：デフォルトの名無しさん mailto:sage [2005/07/13(水) 01:03:28 ] では、そろそろ LISP の話に戻りましょうか 585 名前：デフォルトの名無しさん mailto:sage [2005/07/13(水) 02:14:15 ] まとめると 総称関数だといくつかのクラスにまたがった複数引数をとるメソッドがかける ってことか 586 名前：デフォルトの名無しさん mailto:sage [2005/07/14(木) 15:03:45 ] SICPの5.4 The Explicit-Control Evaluatorで、 > Our Scheme evaluator register machine includes a stack and > seven registers: exp, env, val, continue, proc, argl, and unev. とあるのですが、unevという名前の意味や由来は何なのでしょうか? 他のものは一目瞭然なのですが、unevだけ全く見当がつきません。 587 名前：デフォルトの名無しさん mailto:sage [2005/07/14(木) 15:09:51 ] >>586 unevaluated (未評価)かな？ 588 名前：586 mailto:sage [2005/07/14(木) 19:58:40 ] >>587 なるほど! 確かに「後で評価する式を格納しておく」という使い方をされてますから、 それで正解だと思います。ありがとうございました。 ああすっきりした! 今日は気持ちよく眠れる! 589 名前：デフォルトの名無しさん [2005/07/22(金) 14:37:51 ] xn(n ∈ N)は，次のように再帰的に定義することができる． xn = xm×xm (n = 2m,m >= 1) = x×xm×xm (n = 2m+1,m >= 0) = 1 (n = 0) これを利用して，xnを計算する2引数関数pow2を定義せよ．なお，再帰呼び出しの回数をできるだけ減らすようにすること． これ教えてもらえませんでしょうか… 解答例をお願いします。。。 590 名前：589 [2005/07/22(金) 14:41:15 ] あぁ、書き忘れ。schemeです。 591 名前：デフォルトの名無しさん mailto:sage [2005/07/22(金) 15:03:50 ] 夏休みの宿題くらい自分でやれ 592 名前：デフォルトの名無しさん mailto:sage [2005/07/22(金) 15:27:50 ] 「できるだけ」ってのがひっかかるな。 593 名前：デフォルトの名無しさん mailto:sage [2005/07/22(金) 15:39:49 ] どうしてもループに直せないおバカ救済用じゃね? 594 名前：デフォルトの名無しさん mailto:sage [2005/07/22(金) 15:55:59 ] Lispもschemeもうぜえええええええええ 595 名前：589 [2005/07/22(金) 16:02:10 ] 出来ないからこうして書いてるんです(　´,_ゝ`) 596 名前：デフォルトの名無しさん mailto:sage [2005/07/22(金) 16:14:52 ] 出来ないなら教官に質問しにいくとかすれば? 出来ないことを色々考えて出来るようになるのが学生の仕事だろ? ロクに考えもせずに答教えろとか言う奴は単位なぞ落としてしまえ。 597 名前：デフォルトの名無しさん mailto:sage [2005/07/22(金) 16:36:44 ] 最近の小学校はScheme教えてるのか。すごいな。 598 名前：デフォルトの名無しさん mailto:sage [2005/07/22(金) 18:16:05 ] ※しょうがくせいのみんなへ ・なつやすみのしゅくだいは、じぶんでやりましょう。 599 名前：?デフォルトの名無しさん mailto:sage [2005/07/22(金) 22:03:21 ] Schemeの問題で >再帰呼び出しの回数をできるだけ減らすようにすること ってのはどんなんだろうね？ 再帰をなるべく末尾再帰にしろってんならいいんだけど。 600 名前：デフォルトの名無しさん mailto:sage [2005/07/22(金) 23:29:41 ] x は関数または演算子なんだよね？x×(xm×xm)って、演算子と整数の 積なの？意味がわからない。 601 名前：デフォルトの名無しさん mailto:sage [2005/07/22(金) 23:43:50 ] 頭悪いのを披露するためだけにわざわざ横から出てきてごくろうさん。 602 名前：600 mailto:sage [2005/07/22(金) 23:45:57 ] あ、問題を読み間違えていた。 603 名前：ビッケ ◆Jyl0Z1ahKc mailto:sage [2005/07/22(金) 23:52:54 ] xnなどと書かれているのはベキ乗 x^n のことでしょう。 「再帰呼び出しの回数」については、設問中のベキ乗の定義を見ると 再帰呼び出しのネスティングの深さのことを言ってるのかも知れませんね。 その授業（？）でそういうことを扱った直後の演習問題とか。 「できるだけ」なんていわれても困るけど、設問中の定義に従って ネスティングの深さがO(log n)となる定義を書けばOKということなのかも。 604 名前：デフォルトの名無しさん mailto:sage [2005/07/23(土) 00:02:33 ] ちゃんと自分の頭で噛み砕いて質問すれば親切な香具師は答えてくれる かもしれんが、ここまで露骨に「宿題やって」だと誰も答えてくれんわな。 605 名前：デフォルトの名無しさん mailto:sage [2005/07/23(土) 00:12:28 ] これ、ループに直せるの？定義が再帰的だから、どうしてもループには出来ないや。 末尾再帰も無理っぽい。 結局、let (let*) で途中経過をまとめるぐらいしかできないよ。こまった。 606 名前：デフォルトの名無しさん mailto:sage [2005/07/23(土) 00:19:22 ] これ定義どおり実装するなら幼稚園児向けの問題で面白くもなんともないじゃん。 おまいら小学生ならもっと頭を使おうぜ。ｗ 607 名前：デフォルトの名無しさん mailto:sage [2005/07/23(土) 00:19:34 ] (define (pow2 x n) (let loop ((x x) (n n) (r 1)) (if (= n 0) r (loop (* x x) (quotient n 2) (if (even? n) r (* r x)))))) 608 名前：デフォルトの名無しさん mailto:sage [2005/07/23(土) 00:33:24 ] >>607 きれいだけど、定義から離れすぎてない？ 漏れの頭では、>>589 の定義からは、これを自明には導き出せない…。 609 名前：デフォルトの名無しさん mailto:sage [2005/07/23(土) 00:47:05 ] >>607 が >>589 の定義と同値かどうかは興味深い問題だね。 "1" が "×" の単位元でない場合とか "×" が可換でない 場合とかを考えるとちゃんとした証明が必要かも。 610 名前：デフォルトの名無しさん mailto:sage [2005/07/23(土) 01:58:59 ] (define (pow2 x n) (apply * (vector->list (make-vector n x)))) 611 名前：デフォルトの名無しさん mailto:sage [2005/07/23(土) 02:10:26 ] >>608 >>589 をそのまま実装すると (define (pow2 x n) (if (= n 0) 1 (let ((x1 (pow2 x (quotient n 2)))) (* x1 x1 (if (even? n) 1 x))))) x^n * x^n = (x * x)^n だから (define (pow2 x n) (if (= n 0) 1 (* (pow2 (* x x) (quotient n 2)) (if (even? n) 1 x)))) 末尾再帰に変換して >>607 612 名前：デフォルトの名無しさん mailto:sage [2005/07/23(土) 02:30:33 ] >>611 ありがとう。おかげで疑問点がはっきりしてきました。 x^n * x^n = (x * x)^n って、使っていいの？ 我々は pow2 が累乗を返す関数だと知っているから、この変形は自然に見えるけど、 この問題で使っていいのは、あくまで pow2(x, 2n) = pow2(x, n) * pow2(x, n) pow2(x, 2n + 1) = x * pow2(x, n) * pow2(x, n) pow2(x, 0) = 1 の3式だけではないんだろうか？ 613 名前：デフォルトの名無しさん mailto:sage [2005/07/23(土) 02:53:57 ] なるほど、確かに pow2(x * x, n) = pow2(x, n) * pow2(x, n) は自明ではないな。 614 名前：デフォルトの名無しさん mailto:sage [2005/07/23(土) 03:24:59 ] (define pow2 expt) 615 名前：デフォルトの名無しさん mailto:sage [2005/07/23(土) 03:43:39 ] >>612-613 pow2(x, 0) * pow2(x, 0) = pow2(x * x, 0) = 1 pow2(x, n) * pow2(x, n) = pow2(x * x, n) とすると 定義より pow2(x, n + 1) = x * pow2(x, n) (これも証明する?) なので pow2(x, n + 1) * pow2(x, n + 1) = x * pow2(x, n) * x * pow2(x, n) = (x * x) * (pow2(x, n) * pow2(x, n)) = (x * x) * pow2(x * x, n) = pow2(x * x, n + 1) 以上から数学的帰納法により pow2(x, n) * pow2(x, n) = pow2(x * x, n) 616 名前：デフォルトの名無しさん mailto:sage [2005/07/23(土) 05:11:48 ] >>615 数学的帰納法を使ったら pow2 の一般項 =x^n だって証明できてしまうと思われ。 そもそも関数の再帰的定義とは数学的帰納法を機械にやらせることなのに、 それを人間がやってしまったら本末転倒ではないかと。 617 名前：デフォルトの名無しさん mailto:sage [2005/07/23(土) 06:39:58 ] ん? 元々 x^n を求める pow2(x, n) を定義せよって話でしょ。 x^2n = x^n * x^n x^(2n+1) = x * x^n * x^n x^0 = 1 となる性質を使えって条件があるだけで。 618 名前：デフォルトの名無しさん mailto:sage [2005/07/23(土) 10:34:49 ] 求める関数を pow2(x,n), s(x,n)=log_x pow2(x,n) とおくと、pow2 漸化式は次のようになる。 s(0,x)=0 s(2n,x)=2*s(n,x) s(2n+1,x)=2*s(n,x)+1 ここまで見ると何となく s(n,x)=n になりそうな事が見えて来るが、 帰納法を使わず直観的に考えてみる。 s(n,x)の",x"を以後省略することとし、 nの2進表記を b_n...b_1b_0 とすると s(b_n...b_1b_0) =2*s(b_n...b_1)+b_0 =4*s(b_n...b_2)+2*b_1+b_0 ... =2^n*b_n+...+2*b_1+b_0 すなわち s(n)=n となる。 よって pow2(x,n)=x^n である。 故に>>614 619 名前：デフォルトの名無しさん mailto:sage [2005/07/24(日) 19:52:58 ] でもってexptを高速化する手法の一つが今回の問題だったんでないかい？ 620 名前：デフォルトの名無しさん mailto:sage [2005/07/24(日) 20:17:31 ] ヒント：exptは浮動小数でも(略) 621 名前：デフォルトの名無しさん mailto:sage [2005/07/24(日) 21:58:13 ] R5RS には (expt EXACT INTEGER) => EXACT とは書いてないから (define (expt x n) (exp (* (log x) n))) な実装もアリ。 だから処理系に依存せずに EXACT ^ INTEGER => EXACT が欲しければ 自前で書くしかない。 Common Lisp だと (expt RATIONAL INTEGER) => RATIONAL が保証 されてるのに…… 622 名前：デフォルトの名無しさん mailto:sage [2005/07/25(月) 08:43:33 ] >>621 ふが〜　おれ (expt 2 128) とかがEXACT INTEGERで正確に得られることを期待してコード書いてたけど、これ処理系依存になっちまうのか....いたいぜ。 623 名前：デフォルトの名無しさん mailto:sage [2005/07/25(月) 08:53:40 ] >>620 意味不明。（略）が（おれは無知です）の意味ならどうでもいいけど。 624 名前：デフォルトの名無しさん mailto:sage [2005/07/25(月) 09:04:10 ] expt は "Finally, the procedures listed below will always return an exact integer result provided all their arguments are exact integers and the mathematically expected result is representable as an exact integer within the implementation:" の中にある。 625 名前：デフォルトの名無しさん mailto:sage [2005/07/25(月) 10:30:53 ] >>624 THX! 626 名前：デフォルトの名無しさん mailto:sage [2005/07/25(月) 17:31:11 ] エキスパートシステムで、たとえば「stop」と入力した場合、 強制終了させるにはどうしたらいいんですか? 627 名前：デフォルトの名無しさん mailto:sage [2005/07/25(月) 17:32:57 ] 「stop」と入力されたときに強制終了すれば良いと思う。 628 名前：デフォルトの名無しさん mailto:sage [2005/07/25(月) 17:37:21 ] >>627 強制終了の仕方を教えてください 629 名前：デフォルトの名無しさん mailto:sage [2005/07/25(月) 18:03:19 ] >>628 期待した答えが返って来ないときは、質問のしかたが 間違ってる可能性が高いよ。 開発者なら、どういう言語のどういう処理系を使っていて、 どういう風に大域脱出したいのかを説明しないと。 けど、その前に近くにいる人に聞きなさい。それができない なら電源をいきなり切ってボスに辞表を叩きつければ、仕事を 強制終了できるよ。 630 名前：デフォルトの名無しさん mailto:sage [2005/07/25(月) 20:12:54 ] 人生を強s(ry 631 名前：デフォルトの名無しさん mailto:sage [2005/07/25(月) 20:15:08 ] 人生を強すぎる精神力で乗り切る。 632 名前：デフォルトの名無しさん [2005/07/26(火) 23:14:30 ] >>623 exptは浮動小数でも動くから、pow2がexptを高速化するという命題は 常に成り立たないということだよカス。 633 名前：デフォルトの名無しさん mailto:sage [2005/07/27(水) 01:54:37 ] ところでpow2って掛け算の回数最小になるんだろうか? 証明できるor反例ある? 634 名前：デフォルトの名無しさん mailto:sage [2005/07/27(水) 02:15:48 ] 3つ以上の項を一度に乗算する命令でも想定しない限りは自明だろう。 それくらい瞬間的にわからないというのはちょっとヤバイのでは。 pow2(x, n)=x^nについて考える。末端リーフがn個の二分木を考えてみろ。 二分木で高さが最小になるのはなるべく均等な木のときであることはわかるだろう。 その二分木の高さイコール乗算の回数だ。 635 名前：デフォルトの名無しさん mailto:sage [2005/07/27(水) 02:42:10 ] ごめん、大嘘でした。 >>634はnが奇数のときは2を掛けるから偶数のときで乗算の数が違う ということを見落としてた。 (^ x 9) = (* x (let ((y (^ x 4))) (* y y))) => 6回 (^ x 4) = (let ((y (^ x 2))) (* y y))) => 4回 (^ x 2) = (let ((y (^ x 1))) (* y y))) => 3回 (^ x 1) = (* x (let ((y (^ x 0))) (* y y))) = x ;; ちょっと省略 => 2回 (^ x 7) = (* x (let ((y (^ x 3))) (* y y))) => 6回 (^ x 3) = (* x (let ((y (^ x 1))) (* y y))) => 4回 (^ x 1) = x => 2回 636 名前：デフォルトの名無しさん mailto:sage [2005/07/27(水) 04:38:27 ] >>633 乗算回数最小はこれでどうだろう? 最速かどうかは知らない。 (define (pow2 x n)   (define (pow2-sub l m r)     (if (= m 0) r         (let loop ((l l))           (if (> (caar l) m) (loop (cdr l))               (pow2-sub (cdr l) (- m (caar l)) (* (cdar l) r))))))   (if (= n 0) 1     (let loop ((m 1) (two^prevm 1) (two^m 2) (r x) (l (list (cons 1 x))))       (if (<= two^m n)           (let ((rr (* r r)))             (loop (+ m 1) two^m (+ two^m two^m) rr (cons (cons two^m rr) l)))           (pow2-sub l (- n two^prevm) r))))) 637 名前：デフォルトの名無しさん mailto:sage [2005/07/27(水) 04:45:26 ] 回数はこんな感じ。左から指数n、r=3^n、(expt 3 n)と比較しての検証、乗算の回数。 n=0 r=1 [OK] *-count=0 n=1 r=3 [OK] *-count=0 n=2 r=9 [OK] *-count=1 n=3 r=27 [OK] *-count=2 n=4 r=81 [OK] *-count=2 n=5 r=243 [OK] *-count=3 n=6 r=729 [OK] *-count=3 n=7 r=2187 [OK] *-count=4 n=8 r=6561 [OK] *-count=3 n=9 r=19683 [OK] *-count=4 n=10 r=59049 [OK] *-count=4 n=11 r=177147 [OK] *-count=5 n=12 r=531441 [OK] *-count=4 n=13 r=1594323 [OK] *-count=5 n=14 r=4782969 [OK] *-count=5 n=15 r=14348907 [OK] *-count=6 n=16 r=43046721 [OK] *-count=4 n=17 r=129140163 [OK] *-count=5 n=18 r=387420489 [OK] *-count=5 n=19 r=1162261467 [OK] *-count=6 n=20 r=3486784401 [OK] *-count=5 638 名前：デフォルトの名無しさん [2005/07/27(水) 13:21:00 ] いきなり横レスですみません、超初心者です。こことSICPのスレは とても勉強になるので感謝してます。上のアイデアというか原理は たとえば　3^20 = (3^4)^5 = ((3^2)^2)^(2*2+1)　で５回って意味でしょうか？ ……うぅぅ凄すぎて式が追えないorz 639 名前：デフォルトの名無しさん mailto:sage [2005/07/27(水) 20:58:21 ] 順番が前後するが 3^20=3^16*3^4 ... 1回 3^16=3^(2^4)=(((3^2)^2)^2)^2 ... 4回 3^4は3^16を求める途中で得られているので0回 合計5回 640 名前：デフォルトの名無しさん mailto:sage [2005/07/27(水) 23:36:31 ] s/順番が前後するが/話が前後するが/ 641 名前：デフォルトの名無しさん mailto:sage [2005/07/28(木) 00:25:58 ] あほ 642 名前：デフォルトの名無しさん mailto:sage [2005/07/28(木) 22:57:26 ] >>632 最初からそう書けよ。 相手する価値もないヤシだってすぐわかるからさ。 643 名前：638 [2005/07/29(金) 04:53:54 ] >>639　レスありがとうございます。やっと SICP の1.2.4節に辿り着きました mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#%_sec_1.2.4 後半の改善策が　>>589　と同じ例題で、 ;nが偶数なら　b^n = (b^(n/2))^2 ;nが奇数なら　b^n = b*b^(n-1) 解答も　>>607　と似てました。これを使った乗算回数は、たとえば 3^20 = (3^10)^2 = ((3^5)^2)^2 = ((3*3^4)^2)^2 = ((3*((3^2)^2))^2)^2 で理屈上は>>636と同じ５回(でも実は末尾で余計に1掛けたりとかで、少し多そう)。 オーダーとしてはどちらも log2(n) で、>>634の話が実は正しいような気がしました Orders of Growth を理解するための頭の体操とはいえ、疲れた… まだ木構造リストの演算をきちんと勉強してないので、勘違いしてたらすみません 644 名前：デフォルトの名無しさん [2005/07/29(金) 23:03:59 ] age 645 名前：デフォルトの名無しさん [2005/08/08(月) 17:23:07 ] a b 　c 　　d 　　　　　　dd 　　e 　f 　g 　　h 　　　i 　j k というインデント付きのテキストから (a b (c (d (dd) e) f g (h (i)) j) k) というリストを得たいのですが、 どうやったらうまく書けるかいまいちよくわかりません。 再帰を使えばよさそうというのはわかるんですが。 スタックみたいなバッファが必要でしょうか？ ちなみにテキストデータの仕様は 半角2文字インデントで1階層を表現して、 ddみたいな数階層上のインデントがあっても直前の階層の1つ上とみなす。 a, b, c ・・・はシンボルです。 646 名前：デフォルトの名無しさん [2005/08/08(月) 17:35:29 ] 入力の話を簡単にするために、 ((a 0) (b 0) (c 2) (d 4) (dd 12) (e 4) (f 2) (g 2) (h 4) (i 6) (j 2) (k 0)) という(シンボル インデント文字数)という組のリストから (a b (c (d (dd) e) f g (h (i)) j) k) という形に直すにはどうしたらいい？ ということでお願いします。 逆の変換は簡単にできそうなんですが・・・。 647 名前：デフォルトの名無しさん mailto:sage [2005/08/08(月) 18:28:54 ] どっかの宿題？ 648 名前：デフォルトの名無しさん mailto:sage [2005/08/08(月) 18:34:19 ] いいえ、思いつきです。。 ちなみに２５過ぎのおっさんですよ。。 649 名前：デフォルトの名無しさん mailto:sage [2005/08/08(月) 18:46:54 ] つーか久しぶりにSchemeやってんだけど 頭固くなってるというか、頭悪くなってる。 仮にeまでだとして、 スタックで持ちまわって ((a)) ↓ ((b a)) ;; 同一インデントはそのままスタック先頭にcons ↓ ((c) (b a)) ↓ ((d) (c) (b a)) ↓ ((dd) (d) (c) (b a)) ↓ ((d (dd) e) (c) (b a)) ((c (d (dd) e)) (b a)) ((a b (c (d (dd) e)))) => (a b (c (d (dd) e))) みたいな感じで並べ替えればいいのはなんとなくわかるんだけどね。 肝心のコード思いつかない。 650 名前：デフォルトの名無しさん mailto:sage [2005/08/08(月) 20:39:31 ] 汚く、token がchar の、indent(space)-num conscious な gauche 版ならできた。 (define (port->sp/char/nls iport) (reverse (fold (lambda (x y) (cond ((eq? x #\newline) (cons '() y)) ((null? y) `((,x))) (else (cons `(,@(car y) ,x) (cdr y))))) '() (port->list read-char iport)))) (define (proc arg) (let lp ((rest arg) (temp '()) (result '())) (if (null? rest) (reverse (if (null? temp) result `(,(proc temp) ,@result))) (let ((node (car rest))) (case (length node) ((0) (if (null? temp) (lp (cdr rest) '() result) (lp (cdr rest) '() `(,(proc (reverse temp)) ,@result)))) ((1) (if (null? temp) (lp (cdr rest) '() `(,(car node) ,@result)) (lp (cdr rest) '() `(,(car node) ,(proc (reverse (cons (cdr node) temp))) ,@result)))) (else (lp (cdr rest) `(,(cdr node) ,@temp) result))))))) 651 名前：デフォルトの名無しさん mailto:sage [2005/08/08(月) 20:40:04 ] (proc (port->sp/char/nls (open-input-string "a b c d dd e f g h i j k"))) => (#\a #\b (#\c (#\d (((((#\d))))) #\e) #\f #\g (#\h (#\i)) #\j) #\k) 652 名前：デフォルトの名無しさん mailto:sage [2005/08/08(月) 21:04:45 ] むっ! Pythonのトランスレータを書こうとしているな。

---

---

[ 続きを読む ] / [ 携帯版 ]

read.cgi ver5.27 [feat.BBS2 +1.6] / e.0.2 (02/09/03) / eucaly.net products.
担当:undef