トップページ⇒tech
523コメント255KB

■■C++で大きな数を作るスレ■■

■ このスレッドは過去ログ倉庫に格納されています
0001デフォルトの名無しさん2009/03/24(火) 20:27:50
C++ で大きな数を返すプログラムを作るスレです。
以下のプロトタイプの関数の戻り値で出来るだけ大きな数を返すものを作りましょう。

int main();

●ルール
最大でも１スレに収まる範囲とし、
１スレで完結したプログラムとしてください。
文字数も書いてください

●言語仕様
言語は C++ 2003 準拠とします
int と float は十分な精度があるとします
メモリは十分にあるとします
実行時間は問わないこととします

機種依存、コンパイラ依存の値が返るプログラムは不可
プリプロセッサ、ライブラリの使用は不可

●文字数カウントルール
動作上不要なコメント、スペース、タブ、改行は文字数に含めない
言語上必要なスペース、タブ、改行はカウントする（改行は１文字とする）
0289デフォルトの名無しさん2009/09/27(日) 18:38:14
int h(int f,int a){return f?a?h(f-1,h(f,a-1)):h(f-1,9):a+9;}
int main(){return h(9,9);}

//87文字
//結局アッカーマン

// >>288 取り消し
0290デフォルトの名無しさん2009/09/27(日) 23:49:12
>>285 >>286
main関数だけで再帰呼び出すを行うというスゴイ技を
>>91 さんが見せてくれました。
それを微妙に修正したのが >>96 の 43文字の作品。
>>286 とまったく同じ値となります。

>>289
アッカーマン（相当の）関数は >>9 さんが始めに書いていて、
>>83 で 77文字まで縮まっています。

現状の記録は >>227-230 にあります。
詳しそうなので、ぜひ記録更新に挑戦してみてください。
1レス内文字数無制限での記録もお待ちしております。
0291デフォルトの名無しさん2009/09/28(月) 00:08:24
やはり基本はアッカーマンなんだね。もう少し考えてみる。
0292デフォルトの名無しさん2009/09/28(月) 01:09:31
int main()[int r;for(unsigned i=1;i;i++)r=r<(int)i?i:r;return r;]

未定義動作はないぞ。(unsignedな型の計算はオーバーフローにはならないと書いてある)
0293デフォルトの名無しさん2009/09/28(月) 01:10:39
bracketはbraceの間違い…ｽﾏｿ
0294デフォルトの名無しさん2009/09/28(月) 16:01:09
プログラムを書くプログラムで大きな数できない？
0295デフォルトの名無しさん2009/09/28(月) 16:19:42
ライブラリ関数を使えないから事実上無理だね。
0296デフォルトの名無しさん2009/09/28(月) 21:23:04
>>292
r が初回不定
i を int にキャストした時点でオーバーフローする
環境依存な値が返る

上２個が解決したとしても
環境依存な値が返るのはこの方法では不可避

ところで、
このスレのルールを守って
（int が十分な精度という条件を除いて）
確実にintの最大値を返すものはいままで上がって無かったと思うけど、
出来るのかな？

>>294 >>295
簡単なインタープリタなら１レスで作れるかも。
でも大きな数を返すプログラムをプログラムで作れるかどうか。
0297デフォルトの名無しさん2009/09/29(火) 01:03:47
おっと。indeterminentの解釈がおかしかった。int r;はmain()の外でないとだめですね。
unsignedからintへのキャストで元の値がintで表現できない場合の変換後の値はimplementation definedですがそれはオーバーフローではないのでは?

環境依存なのはその通り。
0298デフォルトの名無しさん2009/09/29(火) 01:09:38
ビット数の決まってる unsigned の 0 から 1 引いて ffff... にするのは環境依存じゃなくね？
0299デフォルトの名無しさん2009/09/29(火) 01:12:00
整数の内部表現は環境依存
0300デフォルトの名無しさん2009/09/29(火) 01:20:38
-1U が unsigned の最大値なのはその通りだけどね。(ffff....とは限らないが)
0301デフォルトの名無しさん2009/09/29(火) 01:23:26
int main(){return (~(unsigned int)0)>>1;}

もダメってこと？
論理演算は全部禁止？
0302デフォルトの名無しさん2009/09/29(火) 01:25:09
最上位ビットが符号っていつ決まったの？
0303デフォルトの名無しさん2009/09/29(火) 01:29:51
じゃあ論理演算それ自体は使っていいのね？
シフト使ってる例は沢山あるし。
0304デフォルトの名無しさん2009/09/29(火) 01:34:31
ttp://xy.yu.to/
寂しい人向け
混む時間帯は人気ありすぎて定員オーバーで入れん

24時間荒れ放題の超カオスな絵チャット
本当の本当に完全無法地帯の絵チャット
（２ちゃんとは比較にならない）

荒しとプログラマーと防衛プログラマーの攻防戦
防衛側が強し、求む強力荒しプログラマー
しかも外国サーバー（イギリス）で管理人は荒し容認
殺人予告すらOKっぽい。ログなんて当然取ってないし
0305デフォルトの名無しさん2009/09/29(火) 01:44:12
左右シフトも補数も論理演算も全部使用禁止だろ。
内部での二進表現に依存してるから。
0306デフォルトの名無しさん2009/09/29(火) 02:41:33
過去ログを読むってこともできんのか？この無能ども
0307デフォルトの名無しさん2009/09/29(火) 13:41:51
オーバーフローがない限りa<<bがa*(2のb乗)に等しいってことは規格で決まってるよ
0308デフォルトの名無しさん2009/09/29(火) 22:28:14
>>307
bが負なら動作不定
bが非負でaが負なら結果は環境依存
a, b とも非負なら >>307 の通り
0309デフォルトの名無しさん2009/09/29(火) 23:36:22
>>297
ごめんなさい。その通りでした。

----
外部参照無しに、（インクルード、ライブラリ、外部入力など）
確実にintの最大値を返すC++のプログラムは存在しない
という証明が私の中では出来たつもり。

●証明
２つの環境ＡとＢがあって、
int の内部表現や動作は下記「異なる点」を除いて全く同じであるとする。
この時、環境ＡとＢではintの最大値は異なるが、
環境ＡとＢで動作の異なるプログラムを作ることは出来ない。
よって、ＡとＢ両方の環境でintの最大値を返すプログラムは存在しない。

----異なる点----
環境Ａのintの最大値はaであり、
環境Ｂのintの最大値はa-1である。
環境Ｂでは環境Ａのaと同じ内部表現でNaNを表すが、
NaNの場合の動作は環境Ａのaの時と全く同じである。
（つまり、動作は全く同じで意味付けのみ異なる）

..................................................................................................■
0310デフォルトの名無しさん2009/09/29(火) 23:41:48
全く証明になっていない件について
0311デフォルトの名無しさん2009/09/29(火) 23:50:29
>>309
「動作」とか「意味付け」とか俺用語が多すぎて意味不明
0312デフォルトの名無しさん2009/09/30(水) 05:09:29
>309
implementation-defined valueはunspecified valueのうち処理系がドキュメントすべきもので、
unspecified valueはtrap representationにならないとC++03が参照するC99に書いてあるのですが。
0313デフォルトの名無しさん2009/09/30(水) 12:59:53
template<int N>
struct T {
enum { A = N + 1U };

static int f() { regturn g(+A); }

static int g(int x) { return T<A>::f(); }
static int g(unsigned x) { return N; }
static int g(long x) { return N; }
static int g(unsigned long x) { return N; }
};

int main() { return T<0>::f(); }

オーバーロードの解決のとこまだ読めてないから長いけど、implementation-definedなものに依存しないんのができた。
0314デフォルトの名無しさん2009/09/30(水) 22:44:19
>>312
たしかにそう書いてありますね。
（範囲外の値から型変換してトラップ表現にならないのならトラップ表現の意味が無い気がする）

int r;
unsigned i;
int main(){ while(--i)r=r<(int)i?i:r;return r; }

これで int の最大値が返るかな？

まあいずれにしろ環境依存な値が返るので
ルール違反ですが。
0315デフォルトの名無しさん2009/09/30(水) 23:33:13
再帰で何度もかけあわせるか、ルールの穴を突くしかないわけで。
結局は >>9 で終わってるスレ。
0316デフォルトの名無しさん2009/09/30(水) 23:47:35
>>314 これはひどいｗｗｗｗｗ
0317デフォルトの名無しさん2009/10/01(木) 00:41:54
>>315
>>316
過去ログ嫁。
0318デフォルトの名無しさん2009/10/01(木) 00:44:48
>>317
？
>>314の酷さに過去ログ関係ないだろ
0319デフォルトの名無しさん2009/10/01(木) 01:02:18
>>318
何がどう酷いのかさっぱり。
やっぱり過去ログを読んだ方が良い気がする。
0320デフォルトの名無しさん2009/10/02(金) 04:21:43
intの最大値は一時は求まらないことが証明されたりもしたけど>313-314で出来ることになったが、最小値は何も思いつかんな…
0321デフォルトの名無しさん2009/10/02(金) 22:40:05
>>320
(3 & -1) == 1 なら 符号+絶対値表現
(3 & -1) == 2 なら 1の補数表現
(3 & -1) == 3 なら 2 の補数表現

負の数が、
1の補数表現の場合と、符号+絶対値表現の場合は、
int の最小値は -[int の最大値]

2の補数表現の場合は
int の最小値は -[int の最大値] または -[int の最大値]-1

2の補数表現の場合に、
このどちらになるかが調べられれば
int の最小値が得られる。
0322デフォルトの名無しさん2009/10/02(金) 23:11:59
嘘つくな。バカ。
0323デフォルトの名無しさん2009/10/02(金) 23:49:56
詰め物ビットを除いた、値ビットと符号ビットの部分

符号+絶対値表現 1000...000 はトラップ表現
符号+絶対値表現 1000...000 はマイナスゼロ
1の補数表現 1111...111 はトラップ表現
1の補数表現 1111...111 はマイナスゼロ
2の補数表現 1000...000 はトラップ表現
2の補数表現 1000...000 は1000...001より1小さい数

規格書によるとこの６種類しか許されていないとある。
0324デフォルトの名無しさん2009/10/02(金) 23:53:51
>2の補数表現 1000...000 はトラップ表現

？？？？
0325デフォルトの名無しさん2009/10/07(水) 00:33:35
int main(){
  for (int n = 2 ; ; n++)
    for ( int a = n ; a = a%2 ? 3*a+1 : a/2, a != 1 ; )
      if (a == n)
        return n;
}
0326デフォルトの名無しさん2009/10/07(水) 22:57:33
>>325
あえて断言しよう。
それは無限ループであると。
0327デフォルトの名無しさん2009/11/05(木) 06:02:25
int main(){int n=9,i=0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF;while(i--){n<<=n;}return n;}
94文字
0328デフォルトの名無しさん2009/11/05(木) 22:41:53
>>327
2↑↑22300745198530623141535718272648361505980418
よりちょっと小さいくらい。
（↑↑ はパワータワー（テトレーション）の記号）

int a=9e99;int main(){return a--?9<<main():9;} // 46文字
こっちのが大きくて、
2↑↑9000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000003
よりちょっと小さいくらい。
0329デフォルトの名無しさん2009/11/06(金) 02:51:29
int main(){int n=9,i=9e99;while(i--){n=pow(n,n);}return n;}
59文字
0330デフォルトの名無しさん2009/11/06(金) 03:08:25
int main(){int n=9,i=9e99;for(;i--;n=pow(n,n));return n;}
57文字にしとく
0331デフォルトの名無しさん2009/11/06(金) 21:21:41
2↑↑9000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000003
よりちょっと大きくて
2↑↑9000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000004
よりは小さい。

ちなみに、標準ライブラリなどの外部ライブラリや
外部ファイルのインクルードは禁止ですので、
powを使う場合はその定義も文字数に含めてください。

int pow(int a,int b){return b?a*pow(a,b-1):1;}
03322332009/12/19(土) 11:29:44
1のレスをよんですっかり理解した気になってたけど、いまふっと見返したらやっぱりちょっと理解が足りないっぽいので
１のレスを参考に233を書き直してみた。これだとどれぐらいの大きさ？
struct Object {
Object *next;
virtual void f() {}
virtual Object *dup() { return this; }
Object **last_next(){if(next)return next->last_next();return &next;}
Object(){ next=(Object *)0;}
};
Object *o;
int a;
void IntegerGrow() { a<<=a<<a;}
struct ObjectGrow : Object { void f(){ Object *t=o->dup(); *(o->last_next())=t;} };
struct Loop : Object
{
void f(){ int *e,*p,*q,*x;
x=new int[a+1];e=x+a;
for(p=x;p<e;p++)*p=a;*p=-1;
for(;;){for(p=x;!*p;p++){
if(*p==-1)return;
for(q=x;q<p;q++){IntegerGrow();*q=a;}
(*p)--;next->f();}}}
Object *dup() { Loop *l=new Loop(); if(next)l->next=next->dup(); return l;}
};

int main()
{
Object *loop;o=new Loop();a=99;
for(int i=a;i--;){loop=o->dup();*(loop->last_next())=new ObjectGrow();loop->f();}
}

03332332009/12/19(土) 16:54:39
すんません。mainでreturnすんのわすれてた。後、IntegerGrowをObjectGrowに統合した。大きさはω＋ωくらいなんだろか？
struct Object {
Object *next;
virtual void f() {}
virtual Object *dup() { return this; }
Object **last_next(){if(next)return next->last_next();return &next;}
Object(){ next=(Object *)0;}
};
Object *o;
int a;
struct ObjectAndIntegerGrow : Object { void f(){ Object *t=o->dup(); *(o->last_next())=t; a=a<<a;} };
struct Loop : Object
{
void f(){ int *e,*p,*q,*x;
x=new int[a+1];e=x+a;
for(p=x;p<e;p++)*p=a;*p=-1;
for(;;){for(p=x;!*p;p++){
if(*p==-1)return;
for(q=x;q<p;q++)*q=a;
(*p)--;next->f();}}}
Object *dup() { Loop *l=new Loop(); if(next)l->next=next->dup(); return l;}
};

int main()
{
Object *loop;o=new Loop();a=99;
for(int i=a;i--;){loop=o->dup();*(loop->last_next())=new ObjectAndIntegerGrow();loop->f();}
return a;
}
0334デフォルトの名無しさん2009/12/19(土) 22:02:58
>>333
Loop :: f() の二重ループの中身って合ってます？
!*p の部分が１回も false にならずに
右端の -1 までたどりついて return しちゃうような気がするのですが。
0335デフォルトの名無しさん2009/12/19(土) 22:26:34
あ、すみません。

!*p の部分が１回も true にならないで無限ループ

の間違いでした。

>>233 のようにしたければ、

for(;;){
  for(p=x;!*p;p++);
  if(*p==-1)return;
  for(q=x;q<p;q++)*q=a;
  (*p)--;
  next->f();
}

こうじゃないかと。
03363332009/12/19(土) 22:41:45
あ、ほんとだ。
おっしゃるとおり、>>335が正しいです。
ありがとうございます。
0337デフォルトの名無しさん2009/12/19(土) 23:12:05
複雑なチェーン構造がいまいち生かされてないような...
o のチェーンの長さより a の方が大きく、
o のチェーンの長さ分 f を再帰コールしてるだけなので、
以下で良い気がする。

----------------
int a;

void f(int o){int *e,*p,*q,*x;
x=new int[a+1];e=x+a;
for(p=x;p<e;p++)*p=a;*p=-1;
for(;;){for(p=x;!*p;p++);
if(*p==-1)return;
for(q=x;q<p;q++)*q=a;
(*p)--;a<<=a;if(o)f(o-1);}}

int main()
{
a=99;
for(int i=a;i--;)f(a);
return a;
}
03383332009/12/19(土) 23:37:33
個人的に再帰でかかれるとメモリの大きさとかが見えにくいので
メモリの大きさが実感しやすい形にしました。
03393332009/12/19(土) 23:41:15
だいたい、再帰変数１つがチェーン一本に相当するってことですかね。

0340デフォルトの名無しさん2009/12/19(土) 23:59:34
>>339
>>337 のメモリの大きさが見えにくく、
>>333 のメモリの大きさが見えにくく無い
というのが良く分からない。

どちらもとてつもなくたくさんのメモリを使うし、
使うメモリの量を調べることは、
ほとんど main() の戻り値を調べることに等しい。

というか、
チェーンが１個伸びることで、
f の再帰を意図的に１回増やすように作った訳では無いの？
loop->f() のコール前後で loop のチェーンの長さは不変なので、
f() の再帰数は loop のチェーンの長さになることは簡単にわかるのだけど。
03413332009/12/20(日) 00:08:54
あくまで個人的な感覚なんですが、スタックに積まれたメモリというのは普段あまり意識しないので、
なんだか無い物のように感じてしまいます。
リストの形にすると実体が実感しやすいという、その程度のことです。
この場合、どちらも本質的に同じものであることは一応理解できます。

0342デフォルトの名無しさん2009/12/20(日) 08:40:36
肝心の大きさですが、
>>333 に >>335 の修正を加えると、
>>233 よりはずいぶんと大きくなって、

>>233 の、n重ループ相当の巨大化操作をn回繰り返して出来た関数を
さらにループさせた感じでしょうか。
03433332009/12/21(月) 22:05:46
ん？もしかして私の返事をまっている？
03443332009/12/22(火) 21:32:37
とりあえず、>>1さんはこちらの間違いを指摘するほど>>333のコードを理解していらっしゃるので、
>>335の修正を入れたプログラムがアッカーマン換算でどれくらいの大きさか教えてくらさい。

0345デフォルトの名無しさん2009/12/22(火) 23:10:26
>>230 の100文字のよりはずっと大きい。
この中に出てくる３変数アッカーマンもどきを
ループで回したくらいで,
下のより微妙に小さい位ではないかと。
int a(int b,int c=9,int d=9){return b+c&&d?a(b-!c,c?c-1:d,a(b,c,d-1)):d+9;}int b=99;int main(){return a(b--?main():9);} // 119

たぶんこの２つの数の間だと思う。
int a(int b,int c=9,int d=9){return b+c&&d?a(b-!c,c?c-1:d,a(b,c,d-1)):d+9;}int b=97;int main(){return a(b--?main():9);} // 119
int a(int b,int c=9,int d=9){return b+c&&d?a(b-!c,c?c-1:d,a(b,c,d-1)):d+9;}int b=98;int main(){return a(b--?main():9);} // 119

>>333 + >>335 で、o のLoopのチェーンが１個伸びるのと、
上の３変数アッカーマンもどきの一番左の引数b が１個増えるのが大体同じ位の効果。
03463332009/12/23(水) 09:05:08
うーん。なんだかいまいち納得できない。
簡単なところから確認していっていいですか。
テーマはループと再帰、定数と自己複製ってところで。


0347デフォルトの名無しさん2009/12/23(水) 09:09:21
まずループと再帰ですが、次の記述が等価ですよね。

void f(int a) { if(a) { g() ; f(a-1) ; }}
void f(int a) { while(a--) g() ; }
0348デフォルトの名無しさん2009/12/23(水) 09:15:48
+1を使って足し算を書いてみるとこんなかんじ。

int add(a,b) { if(a) { return 1+add(a-1,b);} return b;}
int add(a,b) { while(a--) b++ ; return b; }
0349デフォルトの名無しさん2009/12/23(水) 09:41:04
あーそうか。すんません。
勢いで書き始めちゃったけど、ちょっとまとめなおします。
しばしおまちを。
03503332009/12/23(水) 22:43:02
えーと、すいません。まとまりませんでした。
ざっくりと疑問のポイントだけ書くと

（１）Loop :: f()の中の配列の長さがNならLoop :: f()の大きさは２変数アッカーマンA(N,x)と同じくらいの大きさになるんじゃないか？

（２）もしそうなら>>233の配列の大きさはN重ループと４重ループを使って、繰り返し大きくしているので
　　　>>233自体の大きさは3変数アッカーマンのA(4,a,b)くらいになるんじゃないか？

の２点です。

どうでもいいけど、>>346で自己複製とか書いたけどただのコピーと自己複製の区別がついてませんでした。
すんませんw。
0351デフォルトの名無しさん2009/12/23(水) 23:37:35
>>350
(1) は YES.
(2) は NO.

fを関数,b,cをある定数とし、
f(x) ≒ a(b,c,x) である場合、
f をループさせた関数 f' は f'(x) ≒ a(b,c+1,x)
f を3重ループさせた関数 f''' は f'''(x) ≒ a(b,c+3,x)

>>233 の関数D は大まかには
D(x) ≒ a(x ,x) ≒ a(1,0,x) となり、
D(x) を3重ループさせて出来た関数は大まかに a(1,3,x) 位、
これをループさせで出来る a(1,4,x) よりは小さい。
03523332009/12/24(木) 20:26:36
うー。
普通の数式ならごりごりっと展開していけば何とかなることが多いんですが、
３変数アッカーマンを展開しようとするとえらいことにｗ
なかなか手強いっす。
0353デフォルトの名無しさん2009/12/24(木) 21:20:00
>>352
int a(int b,int c=9,int d=9){return b+c&&d?a(b-!c,c?c-1:d,a(b,c,d-1)):d+9;}

a(b,c,0) = 9
a(0,0,D) = d+9
a(B,0,D) = a(b-1,d,a(b,0,d-1))
a(b,C,D) = a(b,c-1,a(b,c,d-1))

大文字の引数は1以上、小文字の引数は0以上の値とすると、
引数は上の４パターンのどれかになる。

４つめがアッカーマンの心臓部となる式である。
cを1以上の数の場合、f(x) = a(b,c-1,x) とおく。
a(b,c,0) = 9
a(b,c,1) = a(b,c-1,a(b,c,0)) = a(b,c-1,9) = f(9)
a(b,c,2) = a(b,c-1,a(b,c,1)) = a(b,c-1,f(9)) = f(f(9))
a(b,c,3) = f(f(f(9)))
a(b,c,4) = f(f(f(f(9))))
となる。
つまり、a(b,c,x) は a(b,c-1,x) をループさせて出来る関数になる。
0354デフォルトの名無しさん2009/12/24(木) 21:42:34
a(b,c,x) は c が大きくなると、非常に増大度の大きな関数になる。

では次に1個目の引数bについて考えてみる。（とりあえずbを固定して考える）
３つ目の式の出番である。

a(3,c,x) を考える。
a(3,c,x) はcが大きくなればどんどん増大度が増えていく。
ところが、いくらcが大きくても、a(3,x,x) にはいずれ抜かれることになる。
（実際、xがc を超えれば、a(3,c,x) < a(3,x,x) となることがわかる）

a(3,x,x) でなくて、たとえば a(3,x,1) でも大した差はなく、
a(3,c,x) をいずれ抜くことになる。

つまり、a(3,x,1) は a(3,0,x) を固定回ループさせて作ったどんな関数よりも増大度が大きい。

a(4,0,x) を考えてみる。
式3によると、xが1以上の時、
a(4,0,x) = a(3,x,a(4,0,x-1)) ≧ a(3,x,9)
となるので、a(3,0,x) を固定回ループさせて作った関数よりも増大度が大きい。
0355デフォルトの名無しさん2009/12/24(木) 21:44:56
３つ目の式は
a(B,0,D) = a(b-1,d,1)
や
a(B,0,D) = a(b-1,d,d)
で十分なのだが、
４つ目の式となるべく共通化した方が文字数が減らせるので
a(B,0,D) = a(b-1,d,a(b,0,d-1))
となっている。
03563332009/12/25(金) 22:28:18
ふーむ。だんだんわかってきたような。
4変数はこれで良いですか？
A(0,0,0,d)=d+9
A(a,b,c,0)=A(a,b,c-1,1)
A(a,b,0,d)=A(a,b-1,d,d)
A(a,0,0,d)=A(a-1,d,d,d)
A(a,b,c,d)=A(a,b,c-1,A(a,b,c,d-1))
0357デフォルトの名無しさん2009/12/26(土) 08:57:32
>>356
良いと思います。
03583332009/12/27(日) 00:20:39
なるほど。
ありがとうです。
>>353の展開の仕方がわかりやすかったです。
きれいな構造ですね。

a(b,x,y)=f(x,y)とおいてf(N,1)を展開すると
f(N,1)=f(N-1,f(N-2,f(N-3,f(N-4,...f(0,1)))...)
となるようでこれもまたきれいな構造です。

この構造をどう解釈すればいいのかはよくわからないですが…
03593332010/01/14(木) 20:08:38
int a=9e99;
int *dup(int *x){
      int *p,*q;
      p=x;while(*p++!=-1);
      q=new int[p-x];p=q;while(*x!=-1)*p++=*x++;*p=*x;
      return q;
}
void f(int *x){
      int *y;
      a<<=a<<a;
      if(*x==0){
            y=x;while(!*y)*y++=a;if(*y==-1)return;
            (*y)--;f(x);
      }
      else{
            for(int i=a;i--;){
                  *y=dup(x);y[0]--;f(y);
            }
      }
}
int main()
{
      int *x;
      for(int i=a;i--;)
      {
            x=new int[a+1];
            for(int j=0;j<a;j++)x[i]=a;x[a]=-1;
            f(x);
      }
      return a;
}
0360デフォルトの名無しさん2010/01/14(木) 21:35:17
>>359
おっと、一気に大きくなりましたね。

>>259 の 138文字のよりも大きくて、
138文字のを 9e99 回ループさせたくらいでしょうか。

--------
ちなみに、138文字のはもうちょっと縮んで131文字になりました。
int a=9;struct b{int c,d;b*e;void operator*(){b f={c-!d,d?d-1:++a,e},g=f;g.e=&f;if(e)**e;if(c+d)*g;}}c={a};int main(){*c;return a;} // 131文字
0361デフォルトの名無しさん2010/01/17(日) 02:09:19
発想が新しく、効率も良さそうなので、
がんばって >>359 を極限まで縮めてみました。
>>360 とほとんど同じ値になるのですが、
3文字届きませんでした。
( >>360 も限界と思ったところから 7文字縮めたので、さらに縮められるかもしれません)

>>192 もそうですが、
だいたい同じ値をまったく異なる発想で作って、
だいたい同じ文字数になっているのがおもしろいです。

// 134
int a;
struct b{
    int c[9],*d;
    void operator*(){
        b e=*this;
        d=e.c+9;
        for(;--*--d<0?*d=++a,d!=e.c:(*e,*e,0););
    }
}c={9};
int main(){
    *c;
    return a;
}
0362デフォルトの名無しさん2010/01/17(日) 02:18:30
あ、
int c[9],*d;
じゃなくて
int*d,c[9];
にしたら1文字縮まりました。

あと2文字。
0363デフォルトの名無しさん2010/01/17(日) 02:25:55
>>362 は間違いでした。
取り消します。

>>362 だと
}c={9};
のところを
}c={0,9};
にする必要があるので、逆に長くなっちゃいますね。
0364デフォルトの名無しさん2010/01/18(月) 00:38:04
>>316
8文字縮めました。
これで >>360 を抜いてこのクラス最短に。

// 126文字
int a;
struct b{
    int c[9],*d;
    void operator*(){
        b e=*this;
        for(d=e.c+9;d>e.c;--*--d>0?*e,0:*d=++a);
    }
}c={9};
int main(){
    *c;
    return a;
}
0365デフォルトの名無しさん2010/01/18(月) 21:16:57
>>364 を2文字縮めて124文字に
int a;struct b{int c[9],*d;void e(){b f=*this;for(d=f.c+9;d>f.c;--*--d>0?f.e(),0:*d=++a);}}c={9};int main(){c.e();return a;} // 124

>>192 を2文字縮めて76文字
>>83 の77文字を抜いてこのクラス最短に
int a,b[9]={9},*c=b;int main(){for(;c>=b;--*c>0?c=b+8,0:*c--=++a);return a;} // 76
0366デフォルトの名無しさん2010/02/25(木) 07:34:47
>>365 の124文字のが縮まって96文字に
>>83 の77文字のが縮まって64文字に
なりました。
0367デフォルトの名無しさん2010/06/05(土) 11:34:17
>>296
短い順にすべての文字列の組み合わせを順番に全部インタプリタで食わせてみて
同じ文字数で最も大きい値を返すプログラムになってるものを採用すればいいんじゃね?
と思ったが停止判定ができないから不可能なのか。
0368デフォルトの名無しさん2010/06/08(火) 19:34:56
そうだね。
ステップ数====>戻り値
はそれほど大きな関数には成り得ないから
ステップ数で制限しちゃうと全然大きくならないし。
0369デフォルトの名無しさん2010/06/24(木) 00:37:28
intの最大値を返すスレ？
こういうのじゃだめなのか43文字

int main()
{return (((unsigned int)0)-1)/2;}
0370デフォルトの名無しさん2010/06/24(木) 23:47:23
>>369
>>1-368
0371デフォルトの名無しさん2010/06/25(金) 20:31:32
>>369
もろに >>2 のダメな例に書いてあるし。
しかも >>2 よりも長い。
0372デフォルトの名無しさん2010/06/26(土) 13:08:14
> （int のサイズに依存したプログラムで無ければ、1レスで作れる最大の数が定義出来るはず）
これ本当かなあ。「1レスで作れる最大の数」が定義できたと仮定すると、
リシャールのパラドックス的なことをして矛盾を導ける可能性はないの?
ビジービーバー関数みたいに定義はできるけど計算不可能だから
プログラムには書けない、ということで矛盾しないのかな?
0373デフォルトの名無しさん2010/06/26(土) 16:04:23
int a(int m,int n){return (m)?(n)?a(m-1,a(m,n-1)):a(m-1,1):n+1;}
int main(){return pow(a(9,9),a(9,9));}

と

int a(int m,int n){return (m)?(n)?a(m-1,a(m,n-1)):a(m-1,1):n+1;}
int main(){return a(9999999,9999999);}

はどっちが大きいんだ（文字数は同じ）
0374デフォルトの名無しさん2010/06/26(土) 16:19:08
powは定義も含めないと違反(>>331)
0375デフォルトの名無しさん2010/06/26(土) 16:21:29
なんと
0376デフォルトの名無しさん2010/06/26(土) 16:51:23
int a(int m,int n){return (m)?(n)?a(m-1,a(m,n-1)):a(m-1,1):n+1;}
int main(){return a(a(9,9),a(9,9));}
のほうが圧倒的に大きくて文字数も少ない
大雑把に言ってpow(x,x)はa(4,x)にも勝てない
0377デフォルトの名無しさん2010/06/26(土) 19:44:19
アッカーマン圧巻だな
0378デフォルトの名無しさん2010/06/26(土) 20:54:16
>>372
別に矛盾しないだろ。
1レスの文字数上限が決まっているので、
1レスで作れるプログラムも有限個しかない。
その中の >>1 の条件に当てはまるものの戻り値の最大値
が「1レスで作れる最大の数」になる。
>>1 のように適切に言語を制限すればベリーのパラドックスは発生しない。
（ISO/IEC 14882:2003 という言語に曖昧な部分が無いという仮定 は必要）

その最大値がどのくらいの大きさの数かを知るすべは無いとは思うが。
0379デフォルトの名無しさん2010/06/26(土) 20:58:56
>>378
たとえば
int main(){int i=0;for(;;)++i;return i;}
みたいなプログラムは停止しないから(明記されてないけどたぶん)ルール違反でしょ?
ということは1レスで作れる最大の数を定義するには
1レスで書けるプログラム全てに対して停止判定ができなきゃいけないと思うんだけど。
停止判定ができないのはプログラムサイズに上限を付けなかった場合で
任意の有限サイズ以下のプログラムに対する停止判定だったら原理的には
可能なんだっけ?
0380デフォルトの名無しさん2010/06/26(土) 21:19:43
停止判定ができないことの証明は、停止判定を行う関数h(x,y)が書けたと仮定して
その関数を使ったプログラムを書いて矛盾を導くから、
h(x,y)が1レスでは決して書けないことを証明できれば
1レスで書けるプログラム全てに対してh(x,y)で停止判定ができても矛盾しない。
0381デフォルトの名無しさん2010/06/26(土) 21:37:01
>>380
少なくともh(x,y)が書けたら停止判定できないことは証明されてるけど、
h(x,y)さえなければ停止判定できることって証明されてたっけ？
0382デフォルトの名無しさん2010/06/26(土) 21:37:39
>>376
もっともっといじると、>>197 の80文字にまで縮まる。
>>376 よりは微妙に大きい。

>>377
いままで私が把握してる中では、
64文字〜135文字、140文字〜148文字はすべてアッカーマン関数やその拡張を使った記録が続いている。
（136文字〜139文字は >>259の考えを使ったもの）
アッカーマン圧巻！

単に私の知識や発想が狭いからそうなっちゃってるという可能性も否定はできないが....
0383デフォルトの名無しさん2010/06/26(土) 21:49:01
>>379
停止判定出来ようが出来まいが、
無矛盾に値を定義することはできる。
値を返すプログラムがどのようなものかを調べるアルゴリズムが存在するかどうか
という命題とは関係無しに。

で、そのアルゴリズムが存在することも簡単にわかる。
単に十分大きな値で停止判定すれば良い。

でその十分大きな値というのがどの程度大きな値であるか
を調べるアルゴリズムが存在するかどうかはわからない。
値を調べるアルゴリズムが存在するかどうかはわからないが、
停止判定を行うのに十分な大きな値が存在するということはわかる。
0384デフォルトの名無しさん2010/06/26(土) 21:49:58
>>381
すべてのプログラムは停止するかしないかのいずれかだから、
1レスで書けるプログラムすべてを表に登録して、表引きで停止するかしないか
返すプログラムを書けば判定できる。
その表をどうやって作るんだと言われても知らないけど表の長さが有限であることさえ
示せばプログラムが存在することは確か(判定したいプログラムの長さに上限がなければ
表も有限にならないのでダメ)。
0385デフォルトの名無しさん2010/06/26(土) 22:08:54
>>383
停止判定ができるなら>>367みたいなプログラムが実際に存在するということだから
int a(){/*1レスで書ける最大値を計算するプログラム*/}
int main(){return a()+1;}
が1レスに収まるなら矛盾する。だから無矛盾に定義するには
停止判定ができないか、>>367みたいなプログラムは十分短く書けないことを
証明する必要がある。
0386デフォルトの名無しさん2010/06/26(土) 22:16:25
>>380
後半２行、
ある証明で用いたテクニックが使えない ===> 無矛盾
というのは無理がありすぎる。

----
具体的に1レスで収まるプログラムの停止判定アルゴリズムを示すと、

1レスで記述できるプログラムをすべて列挙する。
この中で、N※ ステップ以内に停止しないものを除く。
さらに、プログラム終了までの間に環境依存な動作を行ったプログラムを除く。
残ったプログラムの戻り値のうちの最大のものが求める数。

※ Nは十分大きな整数。
（1レスで記述出来るプログラムの最大ステップ数以上であればなんでも良い）
0387デフォルトの名無しさん2010/06/26(土) 22:29:51
>>386
『Nは十分大きな整数』で気に入らないなら、
N = BB(BB(10000)) とかに決めても良いよ。
0388デフォルトの名無しさん2010/06/26(土) 22:33:53
ところで、
『値が定義出来る』と
『値を求めるアルゴリズムが存在する』と
はまったく別ものなんだよね。

>>372 の疑問からなぜ『値を求めるアルゴリズムが存在するか』にすり変わったのかがわからない。
■ このスレッドは過去ログ倉庫に格納されています