C++相談室 part149
レス数が1000を超えています。これ以上書き込みはできません。
>>895
そしてテスト、保守性といったものには誰も興味を持たないのである。おしまい。 >>898から、>>860は末尾再帰であると言える
g(n)x=nx,h(n)x=xと考える >>901 あんたきのうの>881だよね?
たぶん「末尾再帰」の定義が他の人(たとえば Wikipedia の「自身の再帰呼び出しが、
その計算における最後のステップになっているような再帰」)と違いそうだから、まず定義を示してもらいたい。 いや違うよ
級数積が関数という認識があるかないかが彼とは違う 違うのか、悪かった。
で、あんたの「末尾再帰」の定義はどうなってんの? その昔、こんな再帰もやったがw
JSREE EQU *
* DO PREPARE
BSR *+2
* DO SOMETHING
RTS 「自身の再帰呼び出しが、その計算における最後のステップになっているような再帰」
に異論ない。言葉通りだ
ただしそう定義したものは、>>898の性質を持つ >>906
そうなると >860 の "return n * factorial(n-1) ;" における「最後のステップ」は
再帰呼び出しではなく乗算なので、その末尾再帰の定義には合致しないのでは? >>901を適用して
f(n+1)x=f(n)g(n)x
g(n)x=x'
として、
f(n+1)x=f(n)x'
と書けば納得いただけるだろうか >>908 いやサッパリ。
その g やら x やらが >860 の関数とどう関係してるか、示されてないように思うし、
関係が示されたところで "return n * factorial(n-1) ;" の最終ステップが何であるかに
影響するとは思えない。 こう書いた方がよかったかな
f(n+1)x=f(n)g(n)x
f(n)g(n)=h(n)として
h(n+1)x=h(n)x
具体的には
(n+1)f(n+1)x=nf(n)x
例外は最上位の呼び出し元だけがf(n)xになっていることで、
実質h(n)=n * factorial(n-1)という関数の末尾再帰になっている f(n)xはf(n)の結果にxを掛けるんだからf(n)が最終ステップじゃないだろ まずfactorialを末尾再帰に書き換えられるって話なら、そんなの当たり前だし誰も否定してない
それに加えてお前の書き換え方はおかしい
二重に話が噛み合ってなくて訳がわからない
宇宙人か? おそらくわからないという人は、
末尾再帰⇔ループ
の書き換えがどうなっているのかわかっていない
末尾再帰な関数は、関数の戻り値以外のローカル変数はすべて再利用可能であるのでスタックする必要がない
そしてreturnが返しているのは戻り値である
n*はリターン値に含まれている
よってn * factorial(n-1)は一つの関数単位として扱われ得る
実際にそう扱っているかどうかは実装によるだろうが末尾再帰な関数の定義からは漏れていない >>915
仮に「n * factorial(n-1)は一つの関数単位として扱われ得る」を認めたところで
最終ステップはその「関数単位」とやらであって「自身の再帰呼び出し」ではないので、
末尾再帰とは言えないよね。
・・・ >860 を末尾再帰と言えないと死ぬ病気か何かなの? >>916
factorialの呼び元は大本の読み出し元以外はすべてnがかかっていること
実際にループに書き換えられること
よって>>860を否定する必要はないというだけのこと
否定する必要があるならそれでもいいが意味はあるか? >n*はリターン値に含まれている
>よってn * factorial(n-1)は一つの関数単位として扱われ得る
リターン値に含まれていようが関数の呼び出しに含まれていなんだから「一つの関数単位」にはならんわな。 そもそもこの人の数学とやらが意味不明
> (n+1)f(n+1)x=nf(n)x
乗算なのか関数の適用なのかどっちだこれ?
左辺の(n+1)はどっからでてきたんだよ >>917
ループに書き換えられれば末尾再帰と言えるんならやっぱり Wikipedia の定義と違うんじゃん。
「>>860は末尾再帰であると言える」を否定しないと「末尾再帰」の定義(共通認識)が変わってしまうし、
共通認識を壊す行いを認めることになる。それは害悪。やめてほしい。 末尾再帰とかschemeじゃないと意味無い話
末尾再帰だとループに最適化されることが言語で保証されてるって前提なのだから
そこで言う末尾再帰ではn*f(n-1)みたいなのは違う
だから変形して末尾再帰にしろって話になるのだから >>920
それは
return n * factorial(n-1);
と書いてはいけないと強制するということだろうか
だとしたらそれは間違っている
末尾再帰の定義を満たしているにもかかわらず認めないということはそういうことだ 末尾再帰は関数の最後で自身を呼び出してそれをそのままreturnするものだけ
末尾再帰に変形できる関数は末尾再帰に変形できる関数であって、末尾再帰関数ではない >>922
強制とか間違ってるとか認めないとか
お前は誰と戦ってんの?
誰もそんな話してないんだが
読んでで怖いわ >>923
それでいいと思う
だがだとすれば君らは何がわからなかったのかそれがわからない >>915
>n*はリターン値に含まれている
>よってn * factorial(n-1)は一つの関数単位として扱われ得る
return 式
の式に全部書いてしまえるからといっても、その式の中に存在する演算が複数あれば、それぞれの演算に順序があるわけですから
一つに扱うことはできないでしょう、この場合、リターン値を得た後で * n しているのだから、これは一つじゃなく二つ
したがって >>902 の末尾再帰の定義
>「自身の再帰呼び出しが、その計算における最後のステップになっているような再帰」
には合致せず(なぜならば、この場合の最終ステップは * n をすることだから)、>>860 で引用されたプログラムは末尾再帰ではありませんね >>922
>それは
>return n * factorial(n-1);
>と書いてはいけないと強制するということだろうか
いいえ、単に return * factorial(n-1) と書くのならば、末尾再帰ではなくなるというだけのことです。
>末尾再帰の定義を満たしているにもかかわらず認めないということはそういうことだ
もう一度ききましょう、あなたの「末尾再帰」の定義は何ですか? >>927
あなたのいう、「関数」の定義は何ですか
わたしはn * factorial(n-1)は関数だと思います やっぱりこいつ、末尾再帰と末尾呼び出しの区別がついていないとしか思えない >わたしはn * factorial(n-1)は関数だと思います
これがfractional自身とは異なる以上、末尾再帰にはならんわけ。 >>931
では何がわからなくてここまでの長い議論をしていたのですか?
末尾再帰が理解したいというのなら、定義そのままを暗記するだけで済んだはず
一連の私の書き込みは単に理解の方法を提示したに過ぎず、
それを否定するということは定義が理解できていたということでしょう? 中置で書くから分かりづらくなる
ポーランドか逆ポーランドで書けば自明なのに >>928
>あなたのいう、「関数」の定義は何ですか
>わたしはn * factorial(n-1)は関数だと思います
仮に関数の定義をあきらかにしたからといっても、それは末尾再帰の定義とは関係ないでしょうね
繰り返しますが、末尾再帰の定義は >>902
>>「自身の再帰呼び出しが、その計算における最後のステップになっているような再帰」
であり、>>860 で引用されたプログラムの「自身の再帰呼び出し」すなわち「return n * factorial(n-1);」
は、計算における最後のステップになっていない(なぜならば、最後のステップはこの場合 n * であるから)ので、
>>860 で引用されたプログラムは末尾再帰ではありませんね >>932
>>860は末尾再帰にならないということをアンタだけが理解できていないというだけ。 >>934
それを最初から言っていれば、ここまでの無意味な議論はしなくて済んだでしょうね
よって示された 逆になぜ末尾再帰にするかを考えれば、>>934の制限は強すぎる ID:QlEyGkfmは何でもかんでもここのみんなに教えてもらおうとせず
まず落ち着いて自分のペースでしっかり考えてみたらどうかな
みんな呆れてるよ >>938
昔私が末尾再帰を間違えていたとき、当時からこのコテで煽り気味にやっていたにもかかわらず、最上級の親切を示して
「末尾再帰はジャンプ最適化だ!」
と教えてくださった方がおられました、当時のその方ほどの忍耐力を今回発揮できず、申し訳ございません… 皆さんこそ落ち着いてください
nはスタック変数ではなく、ループのインクリメント変数なんですよ 「末尾再帰」という情報処理用語を定義しているJIS規格票もしくは
"tail recursion" という情報処理用語を定義しているISO規格票の
条項を出せるやついるの?
これだけ上から目線でマウント取っといて
あげくオレ用語だったら恥ずかしいぞ 江添が間違えたのが全部悪い
奴が間違えてなければ同じ勘違いをした気違いを呼び寄せることもなかった 江添氏は勘違いと言うより
末尾再帰というもんを単に知らなかったのではと思ってる
末尾再帰の最適化が保証されてる言語使ってる人じゃないだろうから 消費税の計算を例題にあげたけど、計算方法間違ってたみたいなもの
c++的には関係ない分野の知識 蒸し返して悪いんだけど
>>898 の数式解読できる人いる?
この人何を勘違いしてんのか興味でてきたんだが 「添字を持つ添字」みたいなもんを上手に管理する方法ってある?
例えば、
0 <= i < n である全ての i について a[i] を 0 から m の範囲で動かす
みたいなループの構造を想定してる。
当然大きな多重ループになるから小さい n と m についてしか使えないと思うけど、デバッグなどのときにこういうのを簡潔にミスらず書けたらと思っての質問です >>947
> a[i] を 0 から m の範囲で動かす
これの意味がわからない
具体例書いて >>948
for(a=0; a<m; a++)
for(b=0; b<m; b++)
for(c=0; c<m; c++)
...
という形の多重ループのループ変数 a, b, c,... を a[0], a[1], a[2],... にしたいという意味です。
TeX の文法で数式を書けば
\prod_{i=0}^{n} \sum_{a[i]=0}^{m}
という意味です。
・数式との対応が分かりやすい形で書きたい
・簡潔でミスしにくい形で書きたい
といった理由で質問させていただいてます。 >>948-949
すみません。必ずしも和をとりたいだけではないので、式はあくまで例です。
あとレンジが1つずれてるのもすみません。 >という形の多重ループのループ変数 a, b, c,... を a[0], a[1], a[2],... にしたいという意味です。
やればいいだけの話じゃなくて?質問は何だろう。 >>951
n が実行時に決まるような場合どうしたら良いかという意味です >>949
ループのネストが可変なんだよね
templateが許されるなら再帰template
ダメならきれいには書けないと思う >>953-954
ありがとうございます。
再帰templateで調べてみます。
あと書いてて気付いたのですが、n桁のm進数にループ変数 a[0], a[1],... をエンコードするっていうのも一つの方法かなと思いました。 確かにtemplateでなくても再帰で可能か
ただlambdaで渡せないからstd::functionで包む必要あるね >>949
やりたいことは、係数をm^2の2次元配列xとm^3の3次元配列yに入れておいて、2番目のループではx[a][b], 3番目のループではy[a][b][c]を使用するということか?
サイズ可変でも動的に確保すればいいだけ。 >>957-958
m^n 通りの添字 (a[i] for all i) の組み合わせを列挙し、その中でなんらかの処理をしたいという意味です。
説明の仕方が悪くて失礼しました。 全てのa[i]が始点0,終点mならa[i]でなくてもjとかでよくね? std::sortに並列化+ベクトル化指定つけて実行したら、コア数以上に高速化したんだけど、なんで? >>959
あー全部使うのか
function(a[0],a[1],a[2],a[3],....) >>955
こういう解釈でいいのかな
ループがふたつになるかな
a=new int[n];
for(i=0;i<m^n;i++){
for(j=0;j<n;j++){
a[j]=i%m;
i/=m;
}
function(a,n);
}
delete[] a; >>964
はい。
再帰が難しかったらそれにします。 多重継承のときのCRTPについて説明してるサイトないですか そんなモンがあるなんて初めて知った
やはりC++は奥が深いな >>949
>TeX の文法で数式を書けば
>\prod_{i=0}^{n} \sum_{a[i]=0}^{m}
>という意味です。
絶対ではないが、標準的な数学の記法だと、その意味では、
\sum_{a[0]=0}^{m}・・・\sum_{a[n]=0}^{m}
と書くのがが普通だと思う。
ところでそれは量子力学の経路積分か何かですか?
経路積分の場合は、本によって上記の部分に割と独特の変な記号を使う場合があって、
あなたの書いたように書いてある本もあるかもしれません。
ただ、普通の数学記法だと余り使いませんよね、その書き方は。 >>969
補足すれば、普通の数学記法だと
\sum_{a[0]=0}^{m}・・・\sum_{a[n]=0}^{m} f(a[0],・・・,a[n]) //(1)
ですね。
\prod_{i=0}^{n} \sum_{a[i]=0}^{m} //(2)
の記号の場合は、
X= \prod_{i=0}^{n} \sum_{a[i]=0}^{m} g_i(a[i]) //(3)
の場合は、
b[i] = \sum_{a[i]=0}^{m} g_i(a[i]) //(4)
(i=0, ・・・, n)
を先に計算しておいて、
X = \prod_{i=0}^{n} b[i] //(5)
= b[0]・・・b[i] //(6)
の意味に解釈するのが標準的な数学の記号の使い方だと個人的には思います。
(1)と(3)ではかなり意味が違いますが、(2)の記号を、(1)の先頭に使えるかと言えば、
絶対使えないわけでは有りませんが、使う前に何らかの補足説明が必要になりそうです。 >>970
誤: = b[0]・・・b[i] //(6)
正: = b[0]・・・b[n] //(6) >>967
派生が継承してる複数の基底を受け取りたいとか? int *pInts = new int[10]();
とした場合の最後の()の意味は何でしょうか?
付けない場合との差を教えてください。 >>973
イニシャライザ。
普通のクラスではそれがないときはデフォルトコンストラクタで初期化される (空の括弧があっても無くても同じ挙動) けど、
int 等では初期化を明示しない限り初期化されない。
逆に言えばこの場合は初期化を明示しているので初期化される。 (0 が入る) >>974
有難うございます。では、
int *pInts = new int[3](1,2,3); //(1)
int *pInts = new int[3]{1,2,3}; //(2)
の違いは何でしょうか? >>975
(2) の場合には集成体初期化になる。
https://ja.cppreference.com/w/cpp/language/new#.E6.A7.8B.E7.AF.89
(1) も C++20 からは集成体初期化になる。
だけど gcc と clang の最新版で試しても出来ないっぽいし、
あえて丸括弧で書きたい理由はないなぁ。 >>976
ちょっとまってください。
>>973 の場合の >>976
ちょっとまってください。
>>973 の場合の >>976
ちょっと待ってください。
>>973 の場合の () は、「集成体初期化」のうちの「中身が全く入ってない括弧」と解釈してよろしいのでしょうか? >>979
いいえ。
> initializer が空の括弧の場合、それぞれの要素は値初期化されます。
に該当する。 >>980
最初は集成体初期化を使って、
int *pInts = new int[100](1,2,3); //(1)
int *pInts = new int[100](1,2); //(2)
int *pInts = new int[100](1); //(3)
int *pInts = new int[100](); //(4)
とどんどん()の中の項目を減らして行き、最後に0個にした場合、
推論的な延長線上にあると思えるか、それとも全く違った結果になるかどちらですか? >>981
C++20 的に言えば集成体初期化の文法に統合されたということにはなるんだと思うけど、経緯はよくしらない。 もし、
{1,2,3,0,0,0,0,0}
{1,2,0,0,0,0,0,0}
{1,0,0,0,0,0,0,0}
{0,0,0,0,0,0,0,0}
のようになるんであれば、()は(xxx)のxxxを書かない場合と捉えるのは数学的推論として
正しい見方になりますね。
実際に上のようになるのか、未初期化の部分が残るのかは知りませんが。 >>983
足りない分はゼロ初期化されるよ。
C の時代からの配列の初期化の文法と一貫させてるつもりなんだと思う。 >>983
空の丸括弧でゼロ初期化されるのは C++03 にはすでに有って、
波括弧で初期化する文法は C++11 から入って、
(そこから色々と条件の緩和やら変更やらがありつつ)
空ではない丸括弧で集成体初期化になるのは C++20 からという段階的な変化がある。
追加された文法が既存の文法となるべく一貫性を持つように統合しようとはしているけど、
互換性を壊さないようにというのも C++ の強い要件なので、
正確なルールはごちゃごちゃした条件の塊になりがち。
まあまあ整理されている部分もあるけど、
勝手な予想ではなくちゃんと資料にはあたった方がいいよ。 結局、波括弧と丸括弧はどっちが良いの?
C++11の時点では、波括弧が使えるところでは波括弧使っとけってのがMayers神の教えだったけども 好きなようにやったところで法(規格なりデファクトスタンダード)にはならんだろw よし、じゃあ今から俺が法な。
ここの住人は全員システムハンガリアン強制 >>987
シンタクス的にどちらでも良いときには波括弧を優先した方がよいと思う。
波括弧は縮小変換を許さないので意図しない情報の欠落は防止できる可能性が高い。
縮小変換が必要な場面に限って丸括弧を使えばそこが要注意ポイントってのがわかりやすい。
----
ところで縮小変換より狭化変換という用語の方が好きなんだけど、
みんなどっち使ってる? やっぱ縮小変換の方が標準的かな? >>969-971
> 絶対ではない
> 思う
> 個人的には
話にならん へぇこんな配列の初期化の仕方あるんだねぇ
お前らC++に詳しいじゃん C言語の時点で int a[100] = {0}; でゼロクリア
もはや裏ワザの部類
https://cpplover.blogspot.com/2010/09/blog-post_20.html
int a[2][2] = { 1, 2, 3, 4 } ;
多次元配列の初期化での謎機能
これも裏ワザにしか見えない
裏ワザ・例外・隠し機能が相まって配列の初期化だけで一冊の同人誌が出来上がる >>993
数学の記号法と言うのは本によって違ってるから。
特に物理学は必要に迫られて新しい記法を発明してしまう。 >>998-999
いや、だからなんだよ
なんの主張にもなってないお気持ち表明するだけの雑魚多いな レス数が1000を超えています。これ以上書き込みはできません。