- ベストアンサー
巨大数生成アルゴリズム
次のようなアルゴリズムで巨大数を生成していくのは効率がいいと言えますか おそらく、いえると思いますが、これを論理的に示すにはどうしたらよいでしょうか？ 1. F(a,b,0)=a+b , F(a,0,c)=a+c F(a,b,c)=F(a,b-1,F(a,b,c-1)) 2. F(a,b,c,0)=F(a,b,c) F(a,b,0,d)=F(a,b,d) F(a,b,c,d)=F(a,b,c-1,F(a,b,c,d-1)) 3. F(a,b,c,d,0)=F(a,b,c,d) F(a,b,c,0,e)=F(a,b,c,e) F(a,b,c,d,e)=F(a,b,c,d-1,F(a,b,c,d,e-1)) ・・・ おそろらく添え字か5つか6つ位でグラハム数オーダーではないかと思ったりしますが。。 いかがなものでしょうか？
- SariGEnNu
- お礼率80% (461/574)
- 数学・算数
- 回答数5
- ありがとう数6
- みんなの回答 （5）
- 専門家の回答
質問者が選んだベストアンサー
そうそう, 忘れていたんだけど, 「だからどうしたの」という疑問はありますね. Ackermann関数なら「原始帰納的でない帰納的関数を実際に作った」という意味があるんだけど, この関数はどのように意味を見出せばいいんでしょうか?単に「大きくなる」だけではちょっと....
その他の回答 (4)
- Tacosan
- ベストアンサー率23% (3656/15482)
重ね重ねすみません. じっと見てみたら, Conway のチェーン記法と (境界条件が違うだけで再帰の式そのものは) 本質的に同じです. 「よく考えたら」と書いたにもかかわらず「ほとんど考えていない」ことが露見してますねぇ....
お礼
ありがとうございます。 こういうことを考えてみたのは単なる興味本位ですが 何か有用なことにつながるといいと思います。
- Tacosan
- ベストアンサー率23% (3656/15482)
すみません, よく考えてみたら 3引数の F(a, b, c) で Knuth の矢印記法と本質的に同じですね. あっちは F(a, b; k) = 1 if b = 0, a^b if k = 1, and F(a, F(a, b-1; k); k-1) で定義してますから. そこから Conway のチェーン記法にもちこむことはできるかも.
お礼
ありがとうございます。 初期条件や添え字の順番を無視したら F(a,b,c)=a→b→cですね。 ですが、a→→bやa→→→bなどのオーダーに行くには添え字が何個くらいになればいいのかよく分かっていません。
- stomachman
- ベストアンサー率57% (1014/1775)
「効率がいい」がどういう意味かはともかく、添字の数を増やさないと先に行けないんじゃ、明らかにAckermann関数に負けてます。
お礼
ありがとうございます。 >添字の数を増やさないと先に行けないんじゃ、 添え字の個数が任意の場合について定義しているだけなので 添え字の数を固定しても先に進めると思います。 >明らかにAckermann関数に負けてます。 Ackermann関数の定義 http://ja.wikipedia.org/wiki/%E3%82%A2%E3%83%83%E3%82%AB%E3%83%BC%E3%83%9E%E3%83%B3%E9%96%A2%E6%95%B0 を拝見した所、サリジェンヌ関数(質問の関数)が勝っていると思います。 ただ、本質的には同じようなものだと思います。
補足
すみません、アッカーマン関数の定義をよく確認してみると A(m,0)=A(m-1,1)(第二添え字が増えている！)の部分はサリジェンヌ関数より強烈だったことに気付き その点では、アッカーマンの方が勝っていると言えるように思いました。 ただ、それ以外の部分については、今でも余り差異がないと思います。
- Tacosan
- ベストアンサー率23% (3656/15482)
多分, 本質的に Ackermann 関数とか Knuth の矢印記法を拡張したものになってるんじゃないかな? ちなみに「巨大数を効率的に生成する」という表現の意味は不明.
お礼
ありがとうございます。 >「巨大数を効率的に生成する」という表現の意味は不明. 少ない式や文字で大きい数を定義していくという意味です。 あるいは、増加の激しい関数を定義するということもできるかもしれません。
関連するQ&A
- 乗積 Π のアルゴリズム
はじめまして。 質問内容が表題と多少ズレる事をご承知下さい。 アルゴリズムを教えて頂きたいと思っています。 ＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊ Π(2x-1) ,x=1～m 上式においてm=3とすると、総数は15となります。 今、A～Fまで6つのアルファベットがあります。 このうち2つをペアにしてグループを作ります。 上式により、グループ総数は15となります。 ペアの組み方は以下のようになります。 ＜例＞ (1) A-B、 C-D、 E-F (2) A-B、 C-E、 D-F (3) A-B、 C-F、 D-E ・ ・ ・ (14) A-F、 B-D、 C-E (15) A-F、 B-E、 C-D ＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊ このような取り方をプログラムしようと思うのですが どこから手をつけてよいかわかりません。 是非アドバイスをお願いします。
- ベストアンサー
- Visual Basic
- かけ算に関してのアルゴリズム
アルゴリズムに関して全くの初心者なので、お力を貸してくれると幸いです。 タイトルにもありますが、かけ算を使ってのアルゴリズムですが、足し算なり、引き算なりを使ったほうが効率がいいのですが、どのようにすればいいのか悩んでおります。 x=a*b-c*c+bd y=b*b-cc+a*d と全部で６つののかけ算があります。 新しい変数（例えば、temp=c*c のような）を作ってもかまいませんので、 かけ算の使用回数を３回までに押さえたいのです。 私が考えたのは、 x=b(a+d)-temp y=b(b+a)-temp+a(d-b) ほかに効率の良いアルゴリズムはありますでしょうか？ よろしくお願いします
- ベストアンサー
- C・C++・C#
- 表の値を組み合わせて新しい表を生成したい
表の値を組み合わせて新しい表を生成したい 元となる表は↓のようなものです。 0 0501 A 1 0502 B 2 0503 C 3 0504 D 4 0505 E 5 0506 F 6 0507 G 7 H 8 9 10 これをもとに繰り返し処理を行い、↓のような新しい表を生成したいのです。 A B C D E F G H 0 0501 0 0502 0 0503 0 0504 0 0505 0 0506 0 0507 1 0501 1 0502 1 0503 1 0504 1 0505 1 0506 1 0507 2 0501 2 0502 2 0503 2 0504 2 0505 2 0506 2 0507 3 0501 3 0502 3 0503 3 0504 3 0505 3 0506 3 0507 ・ ・ ・ VBAもOKwaveも初心者です。あつかましいのですが、どなたかVBAの例文を作っていただけないでしょうか・・・ ようするには、もとの表の値を使って、集計表を作りたいのです。
- ベストアンサー
- Visual Basic
- √3-√2の共役な数は?
√3-√2の共役な数は? -√2+√3と考えることもできますが…。 A.√3+√2のみ B.-√2-√3のみ C.AとBどちらも共役な数 D.AもBも他にもある E.定義できない。 もしAやBが正しいとしたら、他方が不適な理由は何ですか?(判定方法は?) xの共役な数を求める関数をf(x)としたら f(f(x))=xが成り立たないこともあるのですか?
- ベストアンサー
- 数学・算数
- 16進数イチゼロ以降の対応(?)
16進数で、 01→0f 0a→06 02→0e 0b→05 03→0d 0c→04 04→0c 0d→03 05→0b 0e→02 06→0a 0f→01 07→09 10→？ 08→08 11→？ 09→07 …→… とこのように対応(この様に言うの判りませが...)すると思うのですが、 10以降は何に対応するのか判りません。 何がしたいかと言うとC6 7A FA 等の適当な値があった場合、 上のように対応するのでしょうか。 関数電卓などで計算することは可能ですか？
- ベストアンサー
- 数学・算数
- エクセル データの抽出。延べ数を構成する個の数を求める。
エクセル初心者です。 エクセルでに下のように500人ほど人名(a b c d e f・・・)が無作為乱雑に列挙されています。 c d d c c b b a a d d d a a b b c c a a b b c c c c c c a c c c d e e e d d e e e・・・500人分 のべ500人のうち、一度でも出現していた人名を上手く抽出できますでしょうか？ 最終的に求めているのは、一度でも出現していた人名の「数」ではなく、「一度でも出現していた人名それ自体」を新しいシートなりで利用したいのです。 ご教示願います。
- ベストアンサー
- オフィス系ソフト
- 配列の要素を任意の数で割って、割り振る方法
$abc = array("A", "B", "C", "D", "E", "F", "G", "H", "I"); 上記のような配列があったとします。 これを任意の数で割って、割り振っていきたいのですが、例えば7で割ったとしたら、 1. A, B 2. C, D 3. E 4. F 5. G 6. H 7. I という風に、割り振りたいのですが、どのようにすれば、こういったことがPHPのプログラムで実現できるか教えてください。 もしくは、 1. A, H 2. B, I 3. C 4. D 5. E 6. F 7. G という割り振り方でも大丈夫です。
- ベストアンサー
- PHP
- スケジュールを立てるのに、数学が弱くて困っています。
スケジュールをうまく分配することについてアドバイスお願いします。 A…15,B…7,C…18,D…19,E…26,F…15 この6つを重ならないようにうまく分けたいのですが、数に差があってどうしてもうまく分けることができません。 例えばA…5,B…4,C…6,D…5,E…4,F…6だったら C→F→A→D→F→B→C→E→A→D→C→F→A→B→C→D→E→F→A→B→C→D→E→F→A→B→C→D→E→F という順にうまく分けられるのですが、A…15,B…7,C…18,D…19,E…26,F…15だと数にさがありすぎてうまく分けることができません。 そういうのをできるツール、フリーソフトウェアや解決方法など些細なことでもかまいませんのでアドバイスよろしくお願いします。
- 締切済み
- 数学・算数
- 化学の推定問題について質問です
次の問題が分からないので教えてください。 C12H16O2の同一分子式を有するA,Bがある。A,Bのエステル結合を酸加水分解すると、AからはC,Dが、BからはE,Fが得られ、CとE、DとFは同一分子式を有し、D,Fの水溶液は酸性を示した。CはDより、EはFより重かったが、水酸化ナトリウムで加水分解すると、C,Eとも、もう一方の生成物より軽くなっていた。また、CはFeCl3aqで呈色したが、同じ環状構造を有するEは示さなかった。 この時A,Bの推定される構造式の数はそれぞれいくつか。また、そのうち一つを示せ。
- ベストアンサー
- 化学
- リーグ戦日程表作成アルゴリズム求む
nチームのサッカーのリーグ戦を行います。 （１）各チームは1日1回試合します。相手チームとは1回づつ試合しますので、各チームともn-1回試合します。総試合数はn(n-1)/2です。 （２）グラウンドはn/2 面用意します。nが奇数の場合は(n-1)/2 面で試合のないチームが発生します。 （３）なので、必要日数はnが偶数の時はn-1日 奇数の場合はn日必要です。 例 n=5 チームa,b,c,d,e 日程：グラウンド1，グラウンド2,休み 1日目：a-b,c-d,e 2日目：a-c,b-e,d 3日目：a-d,c-e,b 4日目：a-e,b-d,c 5日目：b-c,d-e,a 問題はnを与えて上記組合せ日程表を作るアルゴリズムを作りたいと思っています。 解は複数ありますが、1つ出せばOKです。ただし、 解の条件：どのチームもそれぞれのグラウンドの使用回数はできるだけ等しくする。（直感的には等しくなる解があると思っています） 上記例ではチームaはグラウンド1でばかり試合をしていますが、ほしいのはどのチームもグラウンド1で2試合、グラウンド2で2試合となるような組合せ表です。 上記条件を除いて組合せを作った後、条件を満たすように入れ替えていく等の2段階のアルゴリズムでもかまいません。 一発(変な表現ですが）で出す方法ももちろん歓迎です。皆さんのお知恵をいただきたいのでよろしく。
- 締切済み
- その他（プログラミング・開発）
お礼
ありがとうございます。 >この関数はどのように意味を見出せばいいんでしょうか?単に「大きくなる」だけではちょっと.... この関数を考えた経緯は、大きくなる関数を考えることに興味があることでしたが、再帰的に定義できる関数(終着できる関数)とそうでない関数の境目を考えることに繋がらないでしょうか？