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

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

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

int main();

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

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

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

●文字数カウントルール
動作上不要なコメント、スペース、タブ、改行は文字数に含めない
言語上必要なスペース、タブ、改行はカウントする（改行は１文字とする）
0002デフォルトの名無しさん2009/03/24(火) 20:29:33
ダメな例
int main(){ return sizeof(int); } 　　　　　　　　　　// 環境依存
int main(){ return (unsigned int)-1/2; }　　　　// 環境依存
int main(){ return 'z'; }　　　　　　　　　　　　　　　// 環境依存
int main(){ return 1.0/0.0; }　　　　　　　　　　　　// 環境依存
int main(){ int a = 9; return a <<= a <<= a; }　　// 未定義動作
int main(){ int a = 9; return ++a * ++a; }　　　　　// 未定義動作
int main(){ quit(9) }　　　　　　　　　　　　　　　　// main の戻り値じゃない、ライブラリ使用不可
int main(){ while(1) printf("9"); }　　　　　　　　// main の戻り値じゃない、ライブラリ使用不可
int main(){ return 1.0/【>>1の知能指数】; }　　// ネタとしてもいまいち
int main(){ return 【このスレでの最大値】+1 ; }　　　 // ネタとしてもいまいち

小さいものの例
int main(){return 9;} // 21文字
int main(){return 99;} // 22文字
int main(){return 999;} // 23文字
int main(){return 9999;} // 24文字
int main(){return 9<<99;} // 25文字

ちょっと大きい数の例 (50文字)
int main()
{
　　int n=99,m=n;
　　while(m--)
　　　　n<<=n;
　　return n;
}
0003デフォルトの名無しさん2009/03/24(火) 21:01:23
>>言語は C++ 2003 準拠とします
その自信は何処から？
何で、言語は C++ 2003 準拠とします ？
環境依存不可としながら、糞スレ立てるな
0004デフォルトの名無しさん2009/03/24(火) 21:15:03
>>3
もしかして Visual C++ 2003 のことだと思ったのかな？
ISO/IEC 14882:2003 のことだよ。
0005デフォルトの名無しさん2009/03/24(火) 21:23:32
>>1スレで完結したプログラム！？
0006デフォルトの名無しさん2009/03/24(火) 21:26:46
まちがった。

最大でも１レスに収まる範囲とし、
１レスで完結したプログラムとしてください。
0007デフォルトの名無しさん2009/03/24(火) 22:55:48
1レスで完結したスレ
0008デフォルトの名無しさん2009/03/24(火) 23:05:08
はいはい　かちこい　かちこい
0009デフォルトの名無しさん2009/03/24(火) 23:33:37
とりあえず、ベタなところから行っとくか。（９４文字)

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(9,9);}
0010デフォルトの名無しさん2009/03/25(水) 01:33:48
int main(){int a,b;for(a=b;a<++b;a=b);return a;}

４８文字。常にint型で表現可能な最大値を返す。
0011デフォルトの名無しさん2009/03/25(水) 02:05:07
int main(){int a,b;for(;(a=b)<++b;);return a;}
>10 をショートコーディング 46文字
0012デフォルトの名無しさん2009/03/25(水) 02:13:11
int main(){int i=0;for(;++i>0;);return i-1;}
普通にやったら、11より短くなった。
44文字　ついでにsageわすれる
0013デフォルトの名無しさん2009/03/25(水) 02:21:11
int main(){int a;for(;a<a+1;a++);return a;}

４３文字。アイディアは>>10と同じ。
0014デフォルトの名無しさん2009/03/25(水) 02:34:23
int main(int x){return(x<x+1)?main(x+1):x;}

４３文字。無理やり再起を使ってみた。
0015デフォルトの名無しさん2009/03/25(水) 02:42:58
int main(){int a;for(;a+1>--a;);return a;}
>13
をヒントにしたが、既に原型をとどめていない。
しかも、コンパイラ依存かな。
42文字
main()再帰もやりたかったけどプロトタイプ宣言されてたからなぁ。
0016デフォルトの名無しさん2009/03/25(水) 03:06:07
int main(){int i=0;for(;--i<0;);return i;}
>15作った後に>12を見直したら
これでいいことがわかった。
42文字
0017デフォルトの名無しさん2009/03/25(水) 03:35:07
int main(){return(1<<sizeof(int)*8-1)-1;}
1Byteが、8bitじゃないですよね。４１文字。
「char型は、1である」だっけ、これ名言だもんな。
0018デフォルトの名無しさん2009/03/25(水) 04:50:07
BigNumberをム板住民で実装するスレかと思ったら違うのか
0019デフォルトの名無しさん2009/03/25(水) 08:08:44
>>9
いきなりそんなとてつもなく大きな数が出てくるとは....

>>10-13 >>15-17
C++規格上はオーバーフロー、アンダーフロー時の値は不定で、
特殊なマシンだとintの値の１個が無効値を表すものがあるので上手く動かない場合がある
多くのコンパイラの場合に動作すれば良いなら、>>2 のダメな例の２個目の方が短くて同じ値を返す

>>14
プロトタイプが
int main();
だからmainの引数は使っちゃダメだよ
0020デフォルトの名無しさん2009/03/25(水) 08:10:28
>>1 の仕様だとintに上限が無いから >>10 は無理じゃないか?
0021デフォルトの名無しさん2009/03/25(水) 14:33:42
int main(){int i=8;float f=9e+9;for(;f>0;f-=1e-9)i*=i;return i;}
intに上限が無いと聞きまして、６４文字。
いくらになるかは知らない。シフトしたらぐはっ。
0022デフォルトの名無しさん2009/03/25(水) 18:24:08
int main(){return 1e+9;} // 24文字
int main(){return 1e+99;} // 25文字
0023デフォルトの名無しさん2009/03/25(水) 18:33:36
>>22
eまたはE表現は、double型なので、int型にキャストしてやる必要があるのではないかしらん。
C言語なら暗黙でやってくれると思うけど、C++ですから。static_cast<int>()
0024デフォルトの名無しさん2009/03/25(水) 19:15:34
C++にもその暗黙の型変換あるぜ
0025デフォルトの名無しさん2009/03/25(水) 20:12:20
>>21
i=8 より i=9 の方が大きくないか？
0026デフォルトの名無しさん2009/03/25(水) 20:37:40
運営移転ミスってるな　まぁ、乙と言っておくか

>48
もちろん9の方が、大きくなると思うけど、
あそこまでいくと些細なことなので、最適化されるように2の乗数にしておいただけ。

i*=i -> i<<=i
乗算を左シフト演算にするとA[1] = 8, A[n+1] = An*2^A[n]ほえ〜
0027デフォルトの名無しさん2009/03/25(水) 20:49:59
意味が分からんのだが、sizeof(int)が不明な場合ってことなのか？
0028デフォルトの名無しさん2009/03/25(水) 20:56:11
>>21
int main(){int i=8;float f=9e+9;for(;f>0;f-=1e-9)i<<=i;return i;}
int main(){int i=8;float f=9e+18;for(;f>0;f-=1)i<<=i;return i;}
int main(){int i=8,f=9e+18;while(f--)i<<=i;return i;}
int main(){int i=9e+99,f=i;while(f--)i<<=i;return i;} // 53文字
最適化したら >>2 とそっくりだよ〜
0029デフォルトの名無しさん2009/03/25(水) 20:58:33
>>28
よくわからんが、sizeof(int)が一定のある値だったとして、i <<= i が未定義でないとしても
1ﾋﾞｯﾄづつうごかさなければ最大値は取れんよね。
いまいちﾙｰﾙが分からん。
0030デフォルトの名無しさん2009/03/25(水) 21:21:59
>>27 >>29
int で表せる範囲は十分大きいということしか決まっていない。
決まってないにも関わらずmain関数が同じ値を返すようなプログラムに
しなくてはいけないというのがルール。

十分大きいとはどういうことかというと、
>>1 のルールでいくら大きな数を作っていったとしても、
1レスではオーバーフローさせることが出来ないほど大きいということ。

ISO/IEC 14882:2003 では int の最小範囲は決まってるが、
最大範囲は決まっていないので、
int の範囲がいくら広くても
ISO/IEC 14882:2003 に反しない。

charがintと同じサイズでsizeof(int)は1という可能性もあるし、
sizeof(int)はとてつもなく大きな値である可能性もある。
0031デフォルトの名無しさん2009/03/25(水) 21:30:58
>>13 はなぜダメかというと、
int の大きさに依存した値が返るから。
（厳密に言うとISO/IEC 14882:2003のルールでは無限ループの可能性もある）

int や float の大きさに依存しないプログラムであれば、
1レスで作れる最大の数があるはずで、
それよりも int は大きな数を保持できますよ
ということ。
0032デフォルトの名無しさん2009/03/25(水) 21:38:10
>>31
さっぱり分からんのだが、
int main() { return 1e99999999999999999999;}
じゃだめなのか？
0033デフォルトの名無しさん2009/03/25(水) 21:41:31
それじゃ小さすぎる。
0034デフォルトの名無しさん2009/03/25(水) 21:41:56
floatに関して十分な精度というのは、
たとえば内部的には整数÷整数の有理数の形で保持されていて
誤差がまったく無いようなものを想定している。

有限文字の浮動小数点定数と四則演算では
有理数しか作れないので。
0035デフォルトの名無しさん2009/03/25(水) 21:46:38
>>32
42文字使えばもっとずっと大きな数が作れる。
たとえば、

int main(){return 9<<(9<<(9<<(9<<9999)));} // 42文字
0036デフォルトの名無しさん2009/03/25(水) 22:13:25
多くのプログラマは自力で>>9を超えるプログラムは組めまい。
というか>>9のプログラムが何であるか知らずに>>9を超えるプログラムを自力で組んだらほとんど天才だが。
0037デフォルトの名無しさん2009/03/25(水) 22:24:39
>>36
ﾙｰﾙ違反だし(m)の括弧とか不要だし、ﾌﾟﾛｸﾞﾗﾏとしては三流だな。
0038デフォルトの名無しさん2009/03/25(水) 22:28:26
>>37
どの辺がルール違反？
括弧はおれもすごく気になってた。
0039デフォルトの名無しさん2009/03/25(水) 22:34:41
main関数の中にすべて入れる必要はないですよ。

int factorial(int n){ return n ? n*factorial(n-1) : 1; }
int main(){ return factorial(99); }

こんなのもＯＫ。
0040デフォルトの名無しさん2009/03/25(水) 22:37:13
できたぞ。まさか無限とは言わんだろうな。
int main(){char a=1,b=0;for(;a==b+1;a++,b++);return a;}
0041デフォルトの名無しさん2009/03/25(水) 22:38:09
もちろんcharじゃなくてintな。
0042デフォルトの名無しさん2009/03/25(水) 22:41:56
>>39
それ許すならmain()の引数許した方がよっぽどスマート。
0043デフォルトの名無しさん2009/03/25(水) 22:45:58
>>42
最初に呼ばれるmainの引数は何になるの？
不定？
0044デフォルトの名無しさん2009/03/25(水) 22:47:19
>>43
int argc, char argv[]に決まってる。
別に不定でもなんでもいいだろ。
0045デフォルトの名無しさん2009/03/25(水) 22:53:59
>>44
不定の引数なんて意味が無いと思って
int main();
に限定したんだけど、
その引数で大きな数が作れるなら是非作ってみて！
ただし、引数に依存しない数を返してね。
00469=362009/03/25(水) 22:55:50
mainの引数許してどうするんだよ。
結果がmainの引数に依存したら評価しにくいだろ。

括弧は三項演算子書くときの癖だ。
つい、いつものように書いちまった。

0047デフォルトの名無しさん2009/03/25(水) 22:58:19
>>9 を整形してみた。

// 86文字
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(9,9);}

たぶん下の方が大きいよね。

// 80文字
int a(int m,int n){return m?n?a(m-1,a(m,n-1)):m:n*9;}
int main(){return a(99,9);}
0048デフォルトの名無しさん2009/03/25(水) 23:02:40
>>40で終了だろうが。
0049デフォルトの名無しさん2009/03/25(水) 23:08:19
>>40
・charのサイズに依存した値が返る

・オーバーフローした場合の値は ISO/IEC 14882:2003 では未定義であり
　環境によっては無効値を表す値をとる場合がある
　無効値での == の結果も ISO/IEC 14882:2003 では未定義
0050デフォルトの名無しさん2009/03/25(水) 23:16:32
>>40
それ以前に、ほとんどの環境で無限ループだった。
インクリメントでオーバーフローしたときの値と
+1 でオーバーフローした時の値は
普通は同じだよ。
0051デフォルトの名無しさん2009/03/25(水) 23:23:09
オーバーフローねたは>>1の思い描くスレの趣旨とは違うので、そろそろ勘弁してやれ。
0052デフォルトの名無しさん2009/03/25(水) 23:23:30
これまでの記録

int main(){return 9;} // 21文字
int main(){return 99;} // 22文字
int main(){return 999;} // 23文字
int main(){return 1e+9;} // 24文字
int main(){return 1e+99;} // 25文字
int main(){return 9<<(9<<(9<<(9<<9999)));} // 42文字
int main(){int n=99,m=n;while(m--)n<<=n;return n;} // 50文字
int main(){int i=9e+99,f=i;while(f--)i<<=i;return i;} // 53文字

// 80文字
int a(int m,int n){return m?n?a(m-1,a(m,n-1)):m:n*9;}
int main(){return a(99,9);}
0053デフォルトの名無しさん2009/03/25(水) 23:30:32
>>50
無限ループじゃねーよ。+1と++の違いには依存してねーよ。
0054デフォルトの名無しさん2009/03/25(水) 23:33:54
>>52
1e+9なら9e99の方がでかい。
0055デフォルトの名無しさん2009/03/25(水) 23:54:18
>>53
b+1 の型は int になるんだったね。
うっかりしてた。

>>40 は
char の範囲よりも int の範囲が広い場合には、
char の最大値をインクリメントした値が返る。
（多くの場合 -128）

char の範囲と int の範囲が同じ場合には、
無限ループ。
0056デフォルトの名無しさん2009/03/26(木) 00:00:36
>>54
たしかに。

int main(){return 9e99;} // 24文字
int main(){int i=9e99,f=i;while(f--)i<<=i;return i;} // 52文字
0057デフォルトの名無しさん2009/03/26(木) 00:02:22
これもだ

int main(){return 9e9;} // 23文字
0058デフォルトの名無しさん2009/03/26(木) 02:00:38
>>30の
>ISO/IEC 14882:2003 では int の最小範囲は決まってるが、
が結論で、その最小範囲内における最大値が唯一の答えだと思うんだが。
それ以上は環境によってオーバーフローする可能性がある。



0059デフォルトの名無しさん2009/03/26(木) 11:52:16
表向きは数学の演習問題だが、>>1の本心は
C++の規約(ISO/IEC 14882:2003)を理解しているかどうか試したいんだろ。
0060デフォルトの名無しさん2009/03/26(木) 21:01:53
>>58
標準規格で定義してない部分を追加で定義してるんで。
int のサイズが制限されてたら大きな数を作れないでしょ。

自力で巨大な整数を保持出来るクラスを作るにも、
組み込み整数型のサイズ制限があったら、
メモリ確保時のサイズが制限を超えちゃうんで作れないし。

>>59
当方、標準規格に詳しいわけでもないし、
C++のテクニックをたくさん知っているわけでもない。
むしろ教えてもらいたい方ですよ。

単純に、C++という言語を使って限られた文字数で
どのくらい大きな数が定義できるのか知りたいのよ。

たとえば私の能力では50文字で >>2 が精一杯だけど、
C++に詳しい人やいろんな人の頭脳を使えば
もっと大きく出来たり文字数を減らせたりするんじゃないかと。

>>21 のような、浮動小数点定数を用いる発想は私には無かったわけだし。
0061デフォルトの名無しさん2009/03/26(木) 23:14:42
おりゃ！

int a(int z){ return z?z<<a(z-1):9 }
int b(int z){ return z?a(b(z-1)):9 }
int c(int z){ return z?b(c(z-1)):9 }
int d(int z){ return z?c(d(z-1)):9 }
int e(int z){ return z?d(e(z-1)):9 }
int f(int z){ return z?e(f(z-1)):9 }
int g(int z){ return z?f(g(z-1)):9 }
int h(int z){ return z?g(h(z-1)):9 }
int i(int z){ return z?h(i(z-1)):9 }
int j(int z){ return z?i(j(z-1)):9 }
int k(int z){ return z?j(k(z-1)):9 }
int l(int z){ return z?k(l(z-1)):9 }
int m(int z){ return z?l(m(z-1)):9 }
int n(int z){ return z?m(n(z-1)):9 }
int o(int z){ return z?n(o(z-1)):9 }
int p(int z){ return z?o(p(z-1)):9 }
int q(int z){ return z?p(q(z-1)):9 }
int r(int z){ return z?q(r(z-1)):9 }
int s(int z){ return z?r(s(z-1)):9 }
int t(int z){ return z?s(t(z-1)):9 }
int u(int z){ return z?t(u(z-1)):9 }
int v(int z){ return z?u(v(z-1)):9 }
int w(int z){ return z?v(w(z-1)):9 }
int x(int z){ return z?w(x(z-1)):9 }
int y(int z){ return z?x(y(z-1)):9 }
int main(){ return y(9e9999999999); }
0062デフォルトの名無しさん2009/03/26(木) 23:30:34
>>36
あっさり抜かれてるじゃん。
0063デフォルトの名無しさん2009/03/26(木) 23:41:48
>>61
それa〜yを一つの関数にできるな
第一引数が0ならa, 1ならbとして振舞うって具合に
で、そのように書き換えると>>9とほぼ同じコードになる
■ このスレッドは過去ログ倉庫に格納されています