階乗のなぞ
の編集
https://www2.hamajima.co.jp:443/~mathenet/wiki/index.php?%B3%AC%BE%E8%A4%CE%A4%CA%A4%BE
[
トップ
] [
編集
|
差分
|
バックアップ
|
添付
|
リロード
] [
新規
|
一覧
|
単語検索
|
最終更新
|
ヘルプ
]
-- 雛形とするページ --
2008(Fractal)2学期
2008(Fractal)3学期
?????©?¢Â???ªÓ
??ªÑ???´???£?¢Â???ª±?¢ð?ªÂ??ª???¢ë????
??ªÑ??ªª??ª???©°??ªª?¡ß??¢î???ª???±???´?¢Â?
??©¬?????¡ß
?ª©??À??©??¢ð?ªÓ?¢ð??±?¢ð??´?ª´??¤?¢ð??¢Â?ª´¡ò?¡ò?ª£?¢Â?ª?
?ªÂ?¢í?ª¤?ªÂ?ª±?¢±?¡Þ
?ª´?¢Ä?ªÀ?ªÀ?¢Ä?©°??ª¡?¢ð?ªÂ?ªÀ??£?ª¤??´(2)
BracketName
DivisionByZero
FrontPage/練習
HyperCard
InterWikiName
InterWikiSandBox
KaleidoCycle
L-system
MenuBar
NETANETAAKASHI
POV-Ray
PukiWiki
RecentDeleted
Rubyで整数の計算
seito
ShortestAdditionChain
TaneAkashi
WikiName
WikiWikiWeb
Xaos
ソーラーボート製作
ノーベルメダルチョコ
;
2007高1生冬課題
4サイクルエンジンの模型
91の不思議
きれいな模様だけど(2)
けいはんなDEサイエンス
だまし缶
なんとかの部屋
イスラエル(星形)
エンジンの構造
ガウス生誕150周年
クアラルンプールの高校の壁画
ケーキの問題
ケプラー関連
サイクロイドの滑り台
シャッフルの記録
シンプルな作図問題
スライスモデル
ビリヤードのパズル
フィボナッチ数列の図形パズル
フラーレン
フラクタル3学期(クライマックス)
ヘルプ
マンデルブロ集合とπ4
ルーロー三角形食器?
Σのパズル
伊号-401
一般公開・科学教室
河崎テスト
階乗のなぞ
角の3等分線
角錐で多面体
関西テクノアイデアコンテスト(高校の部)の模様
京都府高等学校数学研究会
鏡で合わせ絵
行事(仮置き)
作図問題!
初期の落書き
新砂箱
進学環境に科学を伝える取組(紹介本一覧)
数学オリンピック解説会
正多面体さいころ
素数
多面体の硬さ
第2回勉強会
談話室バックナンバー01
中学生の問題(1)
等比数列の続き
統計学習用
二次関数バスケット
日経サイエンス
入れ子トリック
年齢当てマジック
平行・回転・対称移動シート
平成15年度 教員養成大学・学部等教官研究集会
平成16年度京都教育大学公開講座募集
平面図形(4)
平面図形(6)in国立科学博物館
平面図形の問題(1)
平面図形の問題(3)
勉強会(例会と銘打って良いのか?)
方べき
有機化学カードゲーム
有理数の樹
羊歯
立体の問題(1)
立体標識
立方体のパズル
立方体の展開図
...
COLOR(#006789){パスカルの三角形を塗りわけてフラクタル図形を作ろうとしてるのですが,思わぬところで難問にぶつかってしまいました。} 正の整数 N について CENTER: N! = p * 2^k と表す。ここで p は奇数,k は整数 である。k を求めるにはどうしたらよいか。 たとえば N = 5 であれば, CENTER: 4! = 120 = 15 * 2^3, → k = 3 というふうに。これを任意の N について簡単に求めたい。 COLOR(#006789){で,考え始めたけど分からんのです。もうひとつ砕いて考えると,} 任意の正の整数 i について,i を素因数分解したら 2 は何個現れるか COLOR(#006789){という問題に帰着します。ノートに書き並べていくと,規則性があるけれども,単純じゃないんですね。どうもこれは一筋縄ではいかないような。うーむ} COLOR(#fe891c){そうですね。関数というわけにはいかないのでしょう。元々の階乗の中に2が因数として幾つ含まれるかという問題は、Nが偶数の場合だけを考えれば良いわけですよね。プログラムは書けても、定式化は無理ですね。きっと。} COLOR(#fe891c){因みに規則性って、} 1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,5, 1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,6, 1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,5, 1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,7, 1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,5, 1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,6, 1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,5, 1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,8, 1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,5, 1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,6, 1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,5, 1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,7, 1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,5, 1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,6, 1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,5, 1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,9,... COLOR(#fe891c){ですよね。これぞフラクタル!?ですかな。} COLOR(#006789){''そそ,そうなんですよ!''} COLOR(#006789){プログラミングでは「関数」はいろいろな手続きを含めてるんだけど,それはともかくとして,毎回描画のたびに関数呼び出ししていたら遅くなりそう。最初に計算して一気にテーブルを作成しておくのがよさそうですねえ。} COLOR(#006789){しかし,それにしても,しらみつぶしじゃないうまいアルゴリズムないかなあ。} COLOR(#fe891c){やはり、家の環境では書き込めませんねえ。タイムラグがありますが、フラクタルな構造はこんな具合ですね。rubyだと簡単に実装できますよ。} 0 最初に0を1つ準備 1 全部に1を足す 0 1 0 間に0を埋める 1 2 1 全部に1を足す 0 1 0 2 0 1 0 間に0を埋める 1 2 1 3 1 2 1 全部に1を足す 0 1 0 2 0 1 0 3 0 1 0 2 0 1 0 間に1を埋める、、、 COLOR(#fe891c){さて、このアルゴリズムで(虱潰しですが)作れます。ドラゴンカーブ?なんかと同じですね。、、、ってなんだか断言しただけで「検証」というか「論証」というか「何故かの説明」はありません。どなたか簡単に説明を付けてください。} COLOR(#fe891c){ってそうかあ、2進数にして、一の位?から連続する0の数を数えれば因数としての2の数が分かるわけですよね。ふむふむ。} 5!(10進)=101×100×11×10×1(2進) だから、3 ^^ ^ COLOR(#fe891c){ってそうかあ、そもそもパスカルの三角形を色で塗り分けて「フラクタル図形」なんだから、構造的に仕方ないのですよね。} COLOR(#006789){2進法表記からもっていくのは高速にできる可能性があると思ったですが,結局2で何回割れるかを数えるわけでちょっと面白くない。で,効率のよいアルゴリズムを考えることにしました。} + hoge(n) + n が奇数なら n <- n-1 とする + n は偶数だから(上の結果として), n <- n/2 とする + n + hoge(n) を計算してくれ + n = 1,2 のときにはそれぞれ 0, 1 を返す COLOR(#006789){という流れです。つまり 6! に含まれる 2 のべき数を数えるには,6!! について考えればよい。すると 6!! = 2^3 × 3! と砕くことができるので,再帰的に呼び出す方法が使えるというわけです。Ruby で実装してみたら簡単でした。このアルゴリズムだと消費されるスタックも浅いので,n = 2000 くらいは余裕で実行してくれます。} ---- #! /usr/local/bin/ruby def powerof2inFactorial(n) if n == 1 return 0 elsif n == 2 return 1 end if n % 2 == 1 n -= 1 end n /= 2 return n + powerof2inFactorial(n) end ######################################### # n = 2000 まで計算させてみる。 for i in 1 .. 1000 printf("%3d -- %3d\n",i*2,powerof2inFactorial(i*2)) end ---- COLOR(#006789){それにしても,こういうところにもフラクタルな構造が出現するものですね。おもしろい!} COLOR(#fe891c){そうですね。それだけ「フラクタル」が自然な概念なんだってことでしょうね。ところで、このアルゴリズムって} 6!=6×5×4×3×2×1 6 4 2 3×2×1 2 1 COLOR(#fe891c){ってことですよね。階乗に含まれる因数2の個数?ってことだから、まず問題になるのは偶数の個数。偶数だけ取り出して数えたら(n<-n/2)、その分差っぴいて2で割る。すると、半分の長さの階乗が現れる。で、また同じことを考えるという再帰なんですね。うまくできていますね。先に私が書いたものの逆なんですね。} ---- COLOR(#fe891c){それにしても、此処を何人の人が見ているか知らないけど、二乗階乗ってどれぐらいの人が知っているのでしょう?と言いつつ、自身もあまり話したことはなかったりするのですが。} 二重階乗:これは、自然数 n に対し、 n が奇数なら 1 から n までの奇数の総乗、 n が偶数なら 2 から n までの偶数の総乗である。 これを n!! と書く。
タイムスタンプを変更しない
COLOR(#006789){パスカルの三角形を塗りわけてフラクタル図形を作ろうとしてるのですが,思わぬところで難問にぶつかってしまいました。} 正の整数 N について CENTER: N! = p * 2^k と表す。ここで p は奇数,k は整数 である。k を求めるにはどうしたらよいか。 たとえば N = 5 であれば, CENTER: 4! = 120 = 15 * 2^3, → k = 3 というふうに。これを任意の N について簡単に求めたい。 COLOR(#006789){で,考え始めたけど分からんのです。もうひとつ砕いて考えると,} 任意の正の整数 i について,i を素因数分解したら 2 は何個現れるか COLOR(#006789){という問題に帰着します。ノートに書き並べていくと,規則性があるけれども,単純じゃないんですね。どうもこれは一筋縄ではいかないような。うーむ} COLOR(#fe891c){そうですね。関数というわけにはいかないのでしょう。元々の階乗の中に2が因数として幾つ含まれるかという問題は、Nが偶数の場合だけを考えれば良いわけですよね。プログラムは書けても、定式化は無理ですね。きっと。} COLOR(#fe891c){因みに規則性って、} 1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,5, 1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,6, 1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,5, 1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,7, 1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,5, 1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,6, 1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,5, 1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,8, 1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,5, 1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,6, 1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,5, 1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,7, 1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,5, 1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,6, 1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,5, 1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,9,... COLOR(#fe891c){ですよね。これぞフラクタル!?ですかな。} COLOR(#006789){''そそ,そうなんですよ!''} COLOR(#006789){プログラミングでは「関数」はいろいろな手続きを含めてるんだけど,それはともかくとして,毎回描画のたびに関数呼び出ししていたら遅くなりそう。最初に計算して一気にテーブルを作成しておくのがよさそうですねえ。} COLOR(#006789){しかし,それにしても,しらみつぶしじゃないうまいアルゴリズムないかなあ。} COLOR(#fe891c){やはり、家の環境では書き込めませんねえ。タイムラグがありますが、フラクタルな構造はこんな具合ですね。rubyだと簡単に実装できますよ。} 0 最初に0を1つ準備 1 全部に1を足す 0 1 0 間に0を埋める 1 2 1 全部に1を足す 0 1 0 2 0 1 0 間に0を埋める 1 2 1 3 1 2 1 全部に1を足す 0 1 0 2 0 1 0 3 0 1 0 2 0 1 0 間に1を埋める、、、 COLOR(#fe891c){さて、このアルゴリズムで(虱潰しですが)作れます。ドラゴンカーブ?なんかと同じですね。、、、ってなんだか断言しただけで「検証」というか「論証」というか「何故かの説明」はありません。どなたか簡単に説明を付けてください。} COLOR(#fe891c){ってそうかあ、2進数にして、一の位?から連続する0の数を数えれば因数としての2の数が分かるわけですよね。ふむふむ。} 5!(10進)=101×100×11×10×1(2進) だから、3 ^^ ^ COLOR(#fe891c){ってそうかあ、そもそもパスカルの三角形を色で塗り分けて「フラクタル図形」なんだから、構造的に仕方ないのですよね。} COLOR(#006789){2進法表記からもっていくのは高速にできる可能性があると思ったですが,結局2で何回割れるかを数えるわけでちょっと面白くない。で,効率のよいアルゴリズムを考えることにしました。} + hoge(n) + n が奇数なら n <- n-1 とする + n は偶数だから(上の結果として), n <- n/2 とする + n + hoge(n) を計算してくれ + n = 1,2 のときにはそれぞれ 0, 1 を返す COLOR(#006789){という流れです。つまり 6! に含まれる 2 のべき数を数えるには,6!! について考えればよい。すると 6!! = 2^3 × 3! と砕くことができるので,再帰的に呼び出す方法が使えるというわけです。Ruby で実装してみたら簡単でした。このアルゴリズムだと消費されるスタックも浅いので,n = 2000 くらいは余裕で実行してくれます。} ---- #! /usr/local/bin/ruby def powerof2inFactorial(n) if n == 1 return 0 elsif n == 2 return 1 end if n % 2 == 1 n -= 1 end n /= 2 return n + powerof2inFactorial(n) end ######################################### # n = 2000 まで計算させてみる。 for i in 1 .. 1000 printf("%3d -- %3d\n",i*2,powerof2inFactorial(i*2)) end ---- COLOR(#006789){それにしても,こういうところにもフラクタルな構造が出現するものですね。おもしろい!} COLOR(#fe891c){そうですね。それだけ「フラクタル」が自然な概念なんだってことでしょうね。ところで、このアルゴリズムって} 6!=6×5×4×3×2×1 6 4 2 3×2×1 2 1 COLOR(#fe891c){ってことですよね。階乗に含まれる因数2の個数?ってことだから、まず問題になるのは偶数の個数。偶数だけ取り出して数えたら(n<-n/2)、その分差っぴいて2で割る。すると、半分の長さの階乗が現れる。で、また同じことを考えるという再帰なんですね。うまくできていますね。先に私が書いたものの逆なんですね。} ---- COLOR(#fe891c){それにしても、此処を何人の人が見ているか知らないけど、二乗階乗ってどれぐらいの人が知っているのでしょう?と言いつつ、自身もあまり話したことはなかったりするのですが。} 二重階乗:これは、自然数 n に対し、 n が奇数なら 1 から n までの奇数の総乗、 n が偶数なら 2 から n までの偶数の総乗である。 これを n!! と書く。
テキスト整形のルールを表示する