令和5年春期試験 午後問3(プログラミング)についての投稿を受け付けるスレッドです。

最後の式って3^log2 N であってますか？

それに2をかけるのかと思ってました。

この投稿は投稿者により削除されました。(2023.04.16 16:29)

問3かなり難しかったですね！！
私の解答は以下のようになったのですが、皆さんどうでしたか？(特に設問5が不安)

設問1
・ア  3*7
・イ  4*12
設問2
・①48
・②260
・③48
・④84
設問3
・ウ  pow(3, i-1)
・エ  3 * i - 1
・オ  pe.val1
・カ  pe.val2
設問4
・キ  mod(mul, 10)
・ク  elements[cidx + 2]
・ケ  elements[cidx]
設問5
・2N (桁数が最大となるのは層1のresults、N桁どうしの乗算の場合多くても2N桁)

エを(i-1)*pow(3,dp-1)にした以外は
五反田さんと同じですが、自信ないです

この投稿は投稿者により削除されました。(2023.04.19 23:25)

設問1
・ア  3×7
・イ  4×12
設問2
・①48
・②260
・③48
・④84
設問3
・ウ  pow(3, i - 1)
・エ  3×(i - 1)
・オ  pe.val1
・カ  pe.val2
設問4
・キ  mod(mul, 10)
・ク  elements[cidx + 2]
・ケ  elements[cidx] 
設問5
・N+1 (勘)

設問5わからないです

パウか....

最後Nにしちゃったよ

イがなぜ4*12になるのかが分からないです、、
教えていただきたいです。

>わーさん
(C+D)で桁ごとの加算を行う場合、10の位が5+7=12になるためです（図2の上の文参照です）

最後が1/2（3^（log2n ＋1）-1）になりました

最後の問題は、冷静に応用情報レベルで、そんなややこしい答えになるかなという疑問もあり2Nにしました。

ノードの個数と勘違いしました

どうだろう

設問1(ア)3×7 (イ)4×12
設問2①48 ②260 ③48 ④84
設問3(ウ)pow(3, i - 1) (エ)3 × i (オ)pe.val1 (カ)pe.val2
設問4(キ)mod(mul, 10) (ク)elements[cidx + 2] (ケ)elements[cidx]
設問5Σ[i=1..ceil(log2N)]pow(3, i - 1) （ceil(x)をx以上の最小の整数とする）

この投稿は投稿者により削除されました。(2023.04.17 02:17)

設問1(ア)3×7 (イ)4×12
設問2①48 ②260 ③48 ④84
設問3(ウ)pow(3, i - 1) (エ)3 * (i-1) (オ)pe.val1 (カ)pe.val2
設問4(キ)mod(mul, 10)  (ク)elements[cidx + 2]  (ケ)elements[cidx] 
設問5  2N

最後の問題、自分もノード数と勘違いしてて「まさ」さんのようなΣ使ったような回答になったのだけど、ちょっとΣとかlog2とかが回答に出てくるのはおかしい気がして、問題文読み返したら、問われているのはelementsではなくvalues。配列valuesは「桁ごとの値を管理する一次元配列」。だから、ノード数の最大ではなく、多倍長整数の桁数の最大を問われている。問題を勘違いしてたことに気づきました。
この問題で多倍長整数の桁数が最大となるのは、明らかに乗算結果を格納するためのanswerだろうから、answerの桁数を考えればいい。
それはたとえばN=1桁の場合、考えうる最大の掛け算は9×9=81で結果は２桁。
N=2桁の場合、99×99は、100×100=10000よりはやや少ない何らかの数字になるはずだから４桁。
N=4桁の場合9999×9999も同様に考えれば10000×10000=100000000よりはやや少ない何かで８桁。
そう考えてくると2N桁あればいいと考えました。どこだったか忘れましたけど、過去問でこのパターンで2Nを回答する問題があった気がします。その記憶も微かにあったので…2Nにしました。

アは3×7、簡単やな…さてイは…桁数が違うな。
そういや問題文に「桁数が異なる整数同士の乗算を扱う場合は0で埋める」って書いてあるな…46×134は0046×0134ってことか。
A:00、B:46、C:01、D:34だからイ:00×01か。あれ怪しいぞ？というかその右の6×14って何や？46×34ちゃうんか？
…………切るか！ってなりました

設問1(イ)の「4×12」は、図１の「桁ごとの加算」で説明されている各桁の加算結果のままで、「繰り上がり」処理はされていない状態で考える必要があると思います。
問題文でp.17の第２段落の最後に「”繰り上がり”の処理はツリーを用いて行う演算の最後でまとめて行う」とあるので、ツリーを細かい桁へ展開していく過程のこの段階では、繰り上がり処理はまだされていないということだと思います。
図２のすぐ上の段落にある「③の(C+D)は...」のくだりを読んでみると、図２の中では「１３４」表記なのですけどその内実は、１０の位が「１２」で、１の位が「１４」だから、「１２」×１０＋「１４」×１＝１３４なんだという説明がされています。
だから、ここの１３４をＣとＤに分解するときに、Ｃ＝１２、Ｄ＝１４という分解になる、ということなのだと思います。

あああああ！！！pe.val1のとこpe.val1.valuesにしちゃった…
しかも設問5も2N-1とかにしちゃったし考え方合ってんのに勿体ない…
配点次第なとこあるなぁ

>>SilverPengさん
解説ありがとうございます！理解できました！

ただ、問題文からは読み取れなかった…皆すごいなぁ

4のケ、めちゃめちゃに慌てていて elements[cidx+1] にしちゃった…ソースみれば[cidx]名の余裕でわかるのに…

ちなみにwikipediaによると、カラツバ法の計算量は、O(n^(log底2 真数3))だそうです。

設問4のキ、
関数一覧にあるの見落として「mul % 10」
ってしちゃったんですけど、これ加点対象になるんでしょうかね・・・

各層の左端のインデックスを配列に持って算出しなくても、親のインデックス×3とその±1が子のインデックスだしすっきりしないか？とか考えながら読んでたら混乱して全然ダメだった・・・

>123
私なんか冷静に考えれば皆さんと同じ答えなの分かるのに
mul-(int)(mul/10)*10
とかいうよく思いつくな！？みたいな解答にしちゃったし…
intがどこにも出てこないから私の解答は駄目でしょうけど、123さんの解答は既存の関数無視しただけでその記述でも十分動くからいいんじゃないかなあと個人的に思います…