■■C++で大きな数を作るスレ■■
■ このスレッドは過去ログ倉庫に格納されています
0001デフォルトの名無しさん
2009/03/24(火) 20:27:50以下のプロトタイプの関数の戻り値で出来るだけ大きな数を返すものを作りましょう。
int main();
●ルール
最大でも１スレに収まる範囲とし、
１スレで完結したプログラムとしてください。
文字数も書いてください
●言語仕様
言語は C++ 2003 準拠とします
int と float は十分な精度があるとします
メモリは十分にあるとします
実行時間は問わないこととします
機種依存、コンパイラ依存の値が返るプログラムは不可
プリプロセッサ、ライブラリの使用は不可
●文字数カウントルール
動作上不要なコメント、スペース、タブ、改行は文字数に含めない
言語上必要なスペース、タブ、改行はカウントする（改行は１文字とする）
0448デフォルトの名無しさん
2010/07/14(水) 01:09:30存在しても、それを探し当てるアルゴリズムがないと計算できないんじゃない？
0449デフォルトの名無しさん
2010/07/14(水) 08:27:13計算理論で言う「計算可能」の意味ではなくて、
実際に計算して結果を得ることが出来るかって意味なら、
int main(){return 9<<(9<<99);}
この時点で無理。
0450デフォルトの名無しさん
2010/07/14(水) 10:03:38計算可能の意味だよ。
0451デフォルトの名無しさん
2010/07/14(水) 18:01:17たとえばフェルマーの最終定理が成り立つかどうかのアルゴリズムは
bool f
{
return true;
}
でもOK？
0452デフォルトの名無しさん
2010/07/14(水) 19:18:06計算理論ではアルゴリズムが存在すれば「計算可能」なので、
現実世界のリソースを用いてそのアルゴリズムを記述出来るかどうかとは無関係。
>>451
YES
0453デフォルトの名無しさん
2010/07/14(水) 21:16:22現実世界のリソースじゃなくてもいいよ。
アルゴリズムの集合の中からアルゴリズムを選び出す方法が存在することと、計算可能であることに違いはある？
0454デフォルトの名無しさん
2010/07/14(水) 22:29:35アルゴリズムの集合からアルゴリズムを選び出す方法があるかどうかにかかわらず、
アルゴリズムの存在が示されれば計算可能と言える。
そもそも、選び出す方法に対して何の限定もしなければ、
アルゴリズムの集合からアルゴリズムを選び出すのが不可能な場面なんて無い気がする。
人間じゃとても理解できない高度なアルゴリズムだって
人間じゃなければ理解できるかもしれない。
人間の能力だって人や時代によっても変わるし、
神様ならすべてお見通しかもしれない。
そんな不確定な要素に左右されないのが計算可能性の理論。
0455デフォルトの名無しさん
2010/07/15(木) 23:43:10いったい>>453の話のどこに人間が出てくるんだ？
0456デフォルトの名無しさん
2010/07/15(木) 23:52:47人間が選ばなかったらどうやってアルゴリズムを選び出すつもり？
その選び出したアルゴリズムが正しいかどうかを人間が確認しなかったら誰が確認するの？
たとえば、
>>407 が最小の奇数の完全数を返すアルゴリズム（存在すればだが）というのを
人間が確認しなかったらだれが確認するの？
アルゴリズムで確認するというなら、
その確認用アルゴリズムが正しいかどうかは誰がどうやって確認するの？
0457デフォルトの名無しさん
2010/07/16(金) 00:00:38BB(BB(10000)) を計算するアルゴリズムは存在するし、
そのアルゴリズムを選び出すアルゴリズムも存在するし。
さらにそのアルゴリズムを選び出すアルゴリズムも存在する。
しかし、選び出す方のアルゴリズムの方が選び出されるアルゴリズムより複雑で、
それらのアルゴリズムが具体的にどんなものかはだれも分からないし、
0458デフォルトの名無しさん
2010/07/16(金) 02:16:50それ言い出したら人間が計算しなければ誰が計算するんだ。
0459デフォルトの名無しさん
2010/07/16(金) 08:00:39だから『それを言いだしてもしょうがないでしょ』という説明なんだけど。
計算可能性理論では、実際に計算を行う時間や方法を考えなくて良いだけじゃなく、
実際にだれが（または何が）どうやってアルゴリズムを選ぶかも、考えなくて良い。
ただアルゴリズムが存在するかしないか、というのが計算可能性の定義。
>>453 の「選び出す方法が存在する」ってのはまさか
『アルゴリズムの集合の中からある1個のアルゴリズムを選ぶアルゴリズム』が存在する
って意味なのか？
こんなことはあまりに自明でそんなことを論じてるとは思わなかったんで、
現実世界のリソースじゃなくても良い ====> じゃあ神か何か？
と思ったんだけど。
『アルゴリズムの集合の中からある1個のアルゴリズムを選ぶアルゴリズム』に限らず、
有限の文字で表せるある1個の物を吐き出すアルゴリズムは存在する。
0460デフォルトの名無しさん
2010/07/16(金) 08:19:46たぶん質問してるのは一人じゃなくていろんなレベルの人がいる。
こっちはどういう前提で何を聞かれているのかが分からないんで
回答も適切なものにならないかもしれない。
>>448 とか >>453 は結局何が聞きたいのかいまだ良くわからない。
0461デフォルトの名無しさん
2010/07/16(金) 23:07:45(計算可能な)計算を表した文字列を引数にとり、計算の結果を返す関数。
すなわち、
f("1レスで書けるプログラムの停止可能性を求める上で十分なステップ数") = BB(BB(20000))
f("BB(BB(20000))文字以下で書けるプログラムの停止可能性を求める上で十分なステップ数") = BB(BB(BB(20000)))
なる関数。
0462デフォルトの名無しさん
2010/07/16(金) 23:32:59その関数fが計算可能かどうか？という質問？
当然関数fは計算可能ではない。
Nがある自然数の定数だとして、
"N文字以下で書けるプログラムの停止可能性を求める上で十分なステップ数"
は計算可能である。
一方、
f は N の部分にどんな自然数定数を入れても、
f("N文字以下で書けるプログラムの停止可能性を求める上で十分なステップ数") の値を返さなくてはならない。
この値は >>426 の Cstep(N) である。
f が計算可能だと仮定すると、Cstep も計算可能となって >>426 と矛盾するので、
f は計算不可能。
0463デフォルトの名無しさん
2010/07/17(土) 01:53:57> 入力として n を受け取り Σ(n) を計算するような単一のアルゴリズム A は存在しないものの（Σは計算不能なので）、n までの全ての自然数について Σ(n) を「計算」するようなアルゴリズム An は存在する
これが分からん。nは限りなく大きくできるんじゃないのか。
具体的には
A∞=lim(n->∞) An
とか
A(n)=An
ってできるだろ。
0464デフォルトの名無しさん
2010/07/17(土) 07:27:23An の n は（有限の値なら）いくらでも大きくすることが出来るが
A∞ は存在しない。
An のアルゴリズムを記述するのに（仮に）n文字以上必要だとすると、
A∞ のアルゴリズムを記述するのに有限文字じゃ出来ないよね？
∞文字必要になってしまう。
∞文字必要な物はアルゴリズムって呼ばないんで、
A∞ を計算する単一のアルゴリズムは存在しない。
0465デフォルトの名無しさん
2010/07/17(土) 09:32:36そしたら、A(n)=Anを、nが有限の値をとるものとして定義したら？
0466デフォルトの名無しさん
2010/07/17(土) 22:09:11nは初めから有限だが。
0467デフォルトの名無しさん
2010/07/18(日) 00:08:47うん。そう。
すると、>>394のいう
> プログラムの文字数が限定されていれば、
> たとえばBB(BB(10000))のような非常に大きな数による
は、どうやって十分に大きな数を選ぶんだ？
計算可能な数として存在はするが、それを選ぶことはできないんじゃないの？
0468デフォルトの名無しさん
2010/07/18(日) 07:36:02>>454 に戻ってループ？
一般的な計算理論での「計算可能」の定義は、
それを計算するアルゴリズムが存在すること。
そのアルゴリズムを選べるかどうかは無関係。
BB(BB(10000))を返すアルゴリズムは存在するのでBB(BB(10000))は計算可能。
（定義に不満なら、あなたがその道の権威者になって定義を変えてください）
じゃあそのアルゴリズムを選ぶことが出来るか？
これは誰がどうやって選ぶことを想定しているかでまったく結果が異なる。
●この世界のリソースを用いて人間が選ぶ
効率良く書いてもBB(10000)文字くらい必要なので事実上不可能。
●神が選ぶ
有限の文字数でC++で記述出来るのだから、神なら選べるんじゃないの？
●アルゴリズムが選ぶ
BB(BB(10000))を返すアルゴリズムを選ぶアルゴリズムは存在する。
存在するがそのアルゴリズムを選べるかってのは誰がどうやって選ぶことを想定しているかでまったく結果が異なる。
これもアルゴリズムが選ぶ場合、
BB(BB(10000))を返すアルゴリズムを選ぶアルゴリズムを選ぶアルゴリズムは存在する。
BB(BB(10000))を返すアルゴリズムを選ぶアルゴリズムを選ぶアルゴリズムを選ぶアルゴリズムは存在する。
BB(BB(10000))を返すアルゴリズムを選ぶアルゴリズムを選ぶアルゴリズムを選ぶアルゴリズムを選ぶアルゴリズムは存在する。
.....
●拡張マシン
オラクル付きマシン、無限実行マシン、などチューリングマシンを超える能力のあるマシンを使えば
現実的な文字数で簡単にBB(BB(10000))を求めるプログラムが記述可能。
0469デフォルトの名無しさん
2010/07/18(日) 11:10:26つまり、計算可能なアルゴリズムの集合の中には
Nstep(1)回でプログラムが止まるかを判定するアルゴリズム
Nstep(2)回でプログラムが止まるかを判定するアルゴリズム
Nstep(3)回でプログラムが止まるかを判定するアルゴリズム
...
Nstep(BB(BB(20000)))回でプログラムが止まるかを判定するアルゴリズム
...
が含まれているから、アルゴリズムのうちの「どれか」は
1レスでのプログラムの停止判定ができる、
それがどれであるかについては、議論不要
(どうせ人には書けないし、神にとっては自明すぎるから)
、ということ？
じゃあ、任意の正の整数nを取る関数として
Nstep(n)
は、なぜ存在しない？
整数がどれだったとしても、計算可能なアルゴリズムの集合の中にはNstep(n)は含まれているのでは？
0470デフォルトの名無しさん
2010/07/19(月) 00:49:41前半は大筋ではYES
> じゃあ、任意の正の整数nを取る関数として
> Nstep(n)
> は、なぜ存在しない？
Cstep が計算不可能である簡単な証明が >>425 の【3】【4】【5】に書いてある。
> 整数がどれだったとしても、計算可能なアルゴリズムの集合の中にはNstep(n)は含まれているのでは？
これはYES
0471デフォルトの名無しさん
2010/07/19(月) 00:56:01>>425 の【3】【4】【5】は理解できるし、それが事実だというのは分かったが。
全てのnについて
λn. Nstep n
は計算可能なのに、
λn. Nstep
が計算不能というのが理解できない。
0472デフォルトの名無しさん
2010/07/19(月) 01:08:09>>1
浮動小数点数の実現方法って、処理系依存だっけ？
int main(){
float a=1.0;
while(a/2>0.0)a/=2;
return (int)(9e9/a);
}
0473デフォルトの名無しさん
2010/07/19(月) 02:17:05自然数nに対して、『Cstep(n) の値を出力するC++プログラムを書くのにn文字以上必要』だったら
『すべての自然数の入力値に対してCstepを出力する』C++関数は、有限文字じゃ書けないでしょ？
>>472
C++の規格的にはfloatやdoubleの精度や実装方法は処理系依存。
アンダーフロー時の動作も不定だったような。
ただし、このスレでは float は十分な精度があることになっており、
事実上無限の精度があると思ってもらって問題無い。
（>>34 で補足説明をしている）
この辺はintと同じ考え。
0474デフォルトの名無しさん
2010/07/20(火) 02:35:25unsigned i = 0;
while (++i);
は停止すんの？しないの？
0475デフォルトの名無しさん
2010/07/20(火) 02:58:27しないんだろ。
0476デフォルトの名無しさん
2010/07/20(火) 03:13:02enum {SET=0,MOV,ADD,CMP,JF,OP=0xf000000,R1=0xfff000,R2=0xfff};
int i,f,r[4096];
vm *p;
int e(int *c,int l) {
for (i=0; i<4096; ++i) r[i]=0;
f=i=0;p=0;
while (0 < i && i < l) {
vm *s=p,*c = new vm(*this);
int op=r[i]&OP,r1=r[i]&R1,r2=r[i]&R2;
switch(op){
case SET:r[r1]=r2;break;
case MOV:r[r1]=r[r2];break;
case ADD:r[r1]+=r[r2];break;
case CMP:f=r[r1]<r[r2];break;
case JF:i+=((r1&2)-1)*r2-1;break;
}
i++;
while(s){if(s->eq(this))return 0; s=s->p;}
p=c;
}
return r[0];
}
int eq(vm *o) {
for(int t=0;t<4096;++t) if (r[t] != o->r[t]) return 0;
return i == o->i && f == o->f;
}
};
int n(int *c,int l){int p=0;while(p<l){if(++c[p]&0xfffffff)return 1;p++;}return 0;}
int main(int ac, char *av[]){int m = 0;for (int i=0;i<999999999; ++i) {vm v;int t, *c = new int[i];for (t = 0; t < i; ++t) c[t] = 0;while(n(c, i)){t=v.e(c,i);m=(m<t)?t:m;}}return m;}
0477476
2010/07/20(火) 03:13:530478デフォルトの名無しさん
2010/07/20(火) 03:17:070479デフォルトの名無しさん
2010/07/20(火) 10:53:49無限ループと考えてもらった方が話は簡単。
そう考えてもらっても本質的差は無い。
厳密に書くと、
一応C++上はunsigned intは有限のビットで表わされ、
unsigned int の最大値に対して++をすると0になることになってるので、
言語仕様にのっとると、無限ループせずに停止することになる。
>>474 の場合はこのループがあるだけでは環境依存な値が返らないので一応問題は無い。
十分な精度とは、
たとえばBB(BB(10000))ビットなど非常に大きなサイズ以上であるということ。
（つまり事実上無限と思って問題無い程度に大きいサイズ）
この条件の元で int や unsigned int のサイズに依存しない処理を行った場合、
1レスプログラムでは決してビット数不足になることが無い。
lim n→∞ (unsigned int のbit数がnである時のmainの戻り値)
が考えられるすべての環境で存在し値が一致するプログラム
が環境依存の無いプログラムであるとしても良い。
0480デフォルトの名無しさん
2010/07/20(火) 11:07:34いくつかバグがあるみたいだが、設計の意図をくみ取って解釈してみる。
簡単な命令からなるインタープリタ言語の、
999999999未満の命令数のプログラムをすべて実行させて、
その戻り値の最大値を返すもの。
一応簡単な無限ループ検出機能があり、
過去の状態と、すべてのレジスタ、フラグ、インストラクションポインタがすべて一致したら無限ループと判断する。
インタープリタの仕様は、
レジスタが4096個 (int の中の負でない値を取りうる)
命令が以下の5個
○0〜4095の即値のレジスタへの代入
○レジスタからレジスタへの値のコピー
○レジスタにレジスタの値を加算
○レジスタ同士の大小比較を行いフラグにセット
○フラグがセットされていたら、インストラクションポインタに -4095から4095の固定値を加える
これだけあれば、本質的にC++と同じことが出来る。
0481デフォルトの名無しさん
2010/07/20(火) 11:21:27このプログラムの問題点は、正確に無限ループを判断できないこと。
たとえば以下のプログラム。
0: SET r[2], 1
1: MOV r[0], r[1]
2: ADD r[1], r[2]
3: CMP r[0], r[1]
4: JF 1
インタープリタ言語的にはr[1]が1個ずつ無限に増えていく無限ループとなっているが
これを検出出来ない。
最終的にintの上限を超えてしまって環境依存の値が返ることになる。
（intが無限精度と考えれば無限ループ）
0482デフォルトの名無しさん
2010/07/20(火) 11:25:41インタープリタのレジスタの範囲を制限して正確に無限ループを判断できるようにしたら、
今度はインタープリタのレジスタのマックス値しか作れない。
0483デフォルトの名無しさん
2010/07/21(水) 01:01:50バイトコード列の長さが有限のとき、実行する命令数に制限を作って
lp:
y = 最大x命令実行して停止するバイトコード列から得られる数の最大
if (y > x) { x = y; goto lp; }
return x;
ってした場合、停止するんかね？
0484デフォルトの名無しさん
2010/07/21(水) 02:01:03-----
lp:
y = x+1
if (y > x) { x = y; goto lp; }
return x;
-----
つまり
lim n→∞ (intのbit数がnである時のmainの戻り値)
が存在しない環境依存コード。
命令セット的には SET MOV ADD CMP JF の5個だけで十分ぽいよ。
（C++やチューリングマシンと同じ能力がある）
JFの動作が以下の間違いだと仮定しての話だけど。
× case JF:i+=((r1&2)-1)*r2-1;break;
○ case JF:if(f)i+=((r1&2)-1)*r2-1;break;
0485デフォルトの名無しさん
2010/07/21(水) 02:34:100486デフォルトの名無しさん
2010/07/21(水) 02:34:570487デフォルトの名無しさん
2010/07/21(水) 09:54:29またループになってしまって申し訳ないのだが、λn.Cstepは、
計算可能なアルゴリズム集合の中からちょうどλn.Cstep nを選び出すアルゴリズムに帰着する気がするんだが、
そういうことでいいのかな？
0488デフォルトの名無しさん
2010/07/21(水) 21:03:39n命令から成るプログラムで、
nステップ実行して 4095*pow(2,n-1) の値を返せる
MOV r[0], 4095
ADD r[0], r[0]
ADD r[0], r[0]
ADD r[0], r[0]
.....
0489デフォルトの名無しさん
2010/07/21(水) 21:43:24帰着って？
0490デフォルトの名無しさん
2010/07/22(木) 00:23:45命令数は増やさないんですよ。
0491デフォルトの名無しさん
2010/07/22(木) 01:26:58計算可能なアルゴリズム集合の中からちょうどλn.Cstep nを選び出すアルゴリズムがあれば、λn.Cstepは表現可能。
0492デフォルトの名無しさん
2010/07/22(木) 19:51:41ああ、有限じゃなくて、ある自然数以下ってことね。
ある自然数以下の長さのコードでのステップ数には当然限界があるので、
当然停止する。
で、肝心のどのくらいで停止するかをちょっと考えてみたけど、
全然大きさが見積もれない。
しばらく考えてみます。
0493デフォルトの名無しさん
2010/07/22(木) 23:39:05大きさが見積もれました。
●1回のループでのxの増加分
最大プログラム長をn命令とする。
1回のループで x が f(x, n) になるとする。
>>488 の通り、xステップでの戻り値は 4095*pow(2,x-1)以下なので、
f(x, n) ≦ 4095*pow(2,x-1) ≦ pow(4095, x)
●ループ回数
最大プログラム長をn命令とした時のループ回数を g(n) とする。
n命令以下のプログラムは
pow(0x10000000, 1) + pow(0x10000000, 2) + ... + pow(0x10000000, n)
通りである為、
g(n) ≦ pow(0x10000000, 1) + pow(0x10000000, 2) + ... + pow(0x10000000, n) ＜ pow(0x10000001, n)
●戻り値
xの初期値に対し、f(x, n) を g(n)回繰り返した値以下である。
上記より、大きく見積もっても、
4095↑↑(0x10000001↑[最大プログラム長(命令数)]) 程度であることが分かる。
※↑はべき乗、 ↑↑ はテトレーション
0494デフォルトの名無しさん
2010/07/23(金) 01:25:540495デフォルトの名無しさん
2010/07/23(金) 07:45:531命令でできる演算を2重ループしたくらいにしかならないから、
それほど大きくならない。
0496デフォルトの名無しさん
2010/07/23(金) 10:25:35pow(95, 1) + pow(95,2) + ... + pow(95,n)
通りであるため (95 = 127 - 32)、
ループ回数 g(n)≦ pow(95, 1) + pow(95, 2) + ... + pow(95, n) ＜ p(96, n)
ってそんなアホな。
0497デフォルトの名無しさん
2010/07/23(金) 20:00:29たぶんすごい勘違いをしてると思う。
0498デフォルトの名無しさん
2010/07/23(金) 21:27:321命令は6bit, レジスタは8個、命令はSUB reg, reg の1個のみです。
条件ジャンプは特定のレジスタに値を書くことで行います。
ip が負になったらプログラム終了で、-ipが返ります。
指定stepを超えたら0以下の値が返ります。
一応これだけでチューリング完全な言語になっています。
議論の手助けにでも使ってください。
int emu(int code, int step){
int reg[7] = {1}, ip = 0;
for ( ; step-- && ip >= 0 ; ip+=6){
reg[code >> ip & 7] -= reg[code >> ip+3 & 7];
if (reg[0] < 0){
ip += reg[1];
}
}
return -ip;
}
指定step数以下で停止するcode以下のプログラムの戻り値の最大値
int cmaxs(int code, int step){
int m = 0;
while (code){
int r = emu(code--, step);
if (r > m){
m = r;
}
}
return m;
}
0499デフォルトの名無しさん
2010/07/23(金) 22:10:51int cmax483(int n){
int x, y = 9;
do {
x = y;
y = cmaxs(1<<n*6, x);
} while (y > x);
return x;
}
インタープリタの命令の種類によってステップ数の増える速さが大きく変わってしまうので、
初めからstepの増加度合いを関数にしてみる。
int cmax483_(int n, int func(int)){
int x, y = 0, step = 9;
do {
x = y;
y = cmaxs(1<<n*6, step);
step = func(step);
} while (y > x);
return x;
}
>>493 と同じ方法で見積もると、
cmax483_(Ackermann(9e9999999,9), Ackermann)
とやっても、Ackermann(9,9,9)よりはるかに小さい値しか返らないというのは驚きである。
Ackermann(9e9999999,9)命令程度という、人間が組めるサイズを大きく超えたプログラム長をもってしても、
返すことの出来る値はAckermann(9,9,9)付近ではかなりスカスカであることになる。
0500デフォルトの名無しさん
2010/07/24(土) 02:45:470501デフォルトの名無しさん
2010/07/24(土) 08:59:45（とはいっても >>493 の見積もりは超えられないが）
//指定step数以下で停止するcode以下のプログラムの数を数える
int ccnts(int code, int step){
int c = 0;
while (code){
c += emu(code--, step) > 0;
}
return c;
}
//ccnts の値が増えなくなるまでstepを増やし続ける
int cmax501(int n, int func(int)){
int x, y = 0, step = 9;
do {
x = y;
y = ccnts(1<<n*6, step);
step = func(step);
} while (y > x);
return cmaxs(1<<n*6, step);
}
0502デフォルトの名無しさん
2010/07/24(土) 18:20:58どうせループ回数はcodeの取り得る値を超えられないので、
単にこれの方がマシか。
int cmax502(int n, int func(int)){
int step = 9;
for (int i = 0 ; i < 1<<n*6 ; i++){
step = func(step);
}
return cmaxs(1<<n*6, step);
}
結局cmaxsはstepより極端に大きな数は返らないので、
cmaxsを使って大きな数を作るのは厳しいか。
int main(){return emu(適当な大きな数, -1);}
とやる方が、
偶然とてつもなく大きな数が返る可能性があって、
しかも大きさを簡単に見積もれない為、夢がある分マシかも。
int a(int b,int c=9){return b*c?a(b-1,a(b,c-1)):c+9;}
int e(int c,int s){int r[7]={1},i=1;for(;s--&&i>0;i+=6)r[c>>i&7]-=r[c>>i+3&7],*r<0&&(i+=r[1]);return-i;}
int main(){return e(a(9e9999999)/a(9e999999), -1);}
0503デフォルトの名無しさん
2010/07/24(土) 18:28:16無限ループかもしれないし、とてつもなく大きな値が返るかもしれない。
現在では誰も分からない。
>>325 や >>407 と同じ分類になるのかな。
0504デフォルトの名無しさん
2010/11/02(火) 23:58:28int *max(){int *x=new int[a+1];for(int i=a;i--;)x[i]=a;x[a]=-1;return x;}
int next(int *x){while(!*x)*x++=a;if(*x==-1)return 0;(*x)--;return 1;}
void f(int *b,int *c,int *d,int *e)
{
a<<=a<<a;
if(!next(e)){e=max();
if(!next(d)){d=max();
if(!next(c)){c=max();
if(!next(b)){
return;
}
}
}
}
for(int i=a;i--;)
{
f(dup(b),dup(c),dup(d),dup(e));
}
}
int main()
{
int *b,*c,*d,*e;
b=max();c=max();d=max();e=max();
f(b,c,d);
return a;
}
0505デフォルトの名無しさん
2010/11/03(水) 00:11:34int a=9e99;
int *max(){int *x=new int[a+1];for(int i=a;i--;)x[i]=a;x[a]=-1;return x;}
int *dup(int *x){int i=0;while(x[i]==-1)i++;int **y=new int[i];i=0;while(x[i]==-1)y[i]=x[i];y[i]=-1;return y;}
int next(int *x){while(!*x)*x++=a;if(*x==-1)return 0;(*x)--;return 1;}
void f(int *b,int *c,int *d,int *e)
{
a<<=a<<a;
if(!next(e)){e=max();
if(!next(d)){d=max();
if(!next(c)){c=max();
if(!next(b)){
return;
}
}
}
}
for(int i=a;i--;)
{
f(dup(b),dup(c),dup(d),dup(e));
}
}
int main()
{
int *b,*c,*d,*e;
b=max();c=max();d=max();e=max();
f(b,c,d,e);
return a;
}
0506デフォルトの名無しさん
2010/11/03(水) 10:06:44記述ミスと思える所(dup)があるので適当に修正して大きさを見積もると、
大きさが分からないものと >>264 とを除けば
今まででダントツにデカイ。
コードも読みやすく、処理の流れも綺麗。
現段階だと文字数が多いけど、
可読性や処理の流れのきれいさを犠牲にすれば、
文字数はかなり減らせそう。
0507デフォルトの名無しさん
2010/11/10(水) 21:32:53int a=9e99;
template<class T>
void max(T *t){t=new T[a+1];for(int i=0;i<a;i++)max(t[i]);t[a]=NULL;}
void max(int *t){t=new int[a+1];for(int i=0;i<a;i++)t[i]=a;t[a]=-1;}
template<class T>
bool next(T *t){while(t&&!next(*t))max(*t++);return !t;}
bool next(int *t){while(!*t)*t++=a;if(*t==-1)return 0;*t--;return 1;}
template<class T>
T *dup(T *t){int i,j;for(i=0;t[i]!=NULL;i++);T *x=new T[i+1];for(j=0;j<i;j++)x[j]=dup(t[j]);x[i]=NULL;return x;}
int *dup(int *t){int i,j;for(i=0;t[i]!=-1;i++);int *x=new int[i+1];for(j=0;j<i;j++)x[j]=t[j];x[i]=-1;return x;}
template<class T>
void f(T *t)
{
a<<=a<<a;
if(next(t)){for(int i=a;i--;){f(dup(t));}}
}
int main()
{
int *****************************t;
f(max(t));
return a;
}
0508デフォルトの名無しさん
2010/11/10(水) 22:26:57main()
{
0509デフォルトの名無しさん
2010/11/10(水) 22:28:16{
int ******************************t;
max(t)
f(t);
return a;
}
が正しい。
0510デフォルトの名無しさん
2010/11/10(水) 23:40:11template<class T>
bool next(T *t){while(t&&!next(*t))max(*t++);return t!=NULL;}
0511デフォルトの名無しさん
2010/11/11(木) 21:00:52とてつもなく大きい予感が。
----
NULLは未定義なので0で
void max(T *t){
void max(int *t){
はぞれぞれ
void max(T *&t){
void max(int *&t){
こうですかね？
0512デフォルトの名無しさん
2010/11/11(木) 21:30:50すごく似てるのがなんかもったいない気がする。
配列の各要素を1ずつ増やして、
終端が0, 各要素の最低値を1にすると、
テンプレートの初期関数を簡単に出来そう。
以下でたぶん返る値は同じ。
void max(int &t){
t = a+1;
}
bool next(int &t){
return --t||(max(t),0);
}
int dup(int t){
return t;
}
0513デフォルトの名無しさん
2010/11/11(木) 21:48:00bool next(int *t){while(!*t)*t++=a;if(*t==-1)return 0;--*t;return 1;}
>max(t)
max(t);
0514デフォルトの名無しさん
2010/11/11(木) 22:21:55>>507 に解説願いたい。
0515５０７
2010/11/14(日) 19:02:290516デフォルトの名無しさん
2010/11/15(月) 00:59:03おそらく２重リストアッカーマンくらい。
0518デフォルトの名無しさん
2010/11/16(火) 21:29:00f( c, b, a ) ≒ Ak( [2, c], [1, b], [0, a] )
f( d, c, b, a ) ≒ Ak( [3, d], [2, c], [1, b], [0, a] )
f( e, d, c, b, a ) ≒ Ak( [4, e], [3, d], [2, c], [1, b], [0, a] )
f( [d, c], [b, a] )
≒ Ak( [1, 1, d], [1, 0, c], [0, 1, b], [0, 0, a] )
f( [i, h, g], [f, e, d], [c, b, a] )
≒ Ak( [2, 2, i], [2, 1, h], [2, 0, g], [1, 2, f], [1, 1, e], [1, 0, d], [0, 2, c], [0, 1, b], [0, 0, a] )
f( [[h, g], [f, e]], [[d, c], [b, a]] )
≒ Ak( [1, 1, 1, h], [1, 1, 0, g], [1, 0, 1, f], [1, 0, 0, e], [0, 1, 1, d], [0, 1, 0, c], [0, 0, 1, b], [0, 0, 0, a] )
f( [[[b, 0], [0, 0]], [[0, 0], [0, 0]]], [[[0, 0], [0, 0]], [[0, 0], [0, a]]] )
≒ Ak( [1, 1, 1, 1, b], [0, 0, 0, 0, a] )
....
0519デフォルトの名無しさん
2010/12/06(月) 05:29:400520デフォルトの名無しさん
2010/12/16(木) 22:08:46だれかやってみて！
0521デフォルトの名無しさん
2010/12/17(金) 02:06:030522デフォルトの名無しさん
2010/12/17(金) 02:26:240523デフォルトの名無しさん
2010/12/17(金) 20:30:42手始めにschemeで>>9
84バイト
■ このスレッドは過去ログ倉庫に格納されています