2015年12月25日金曜日

水着ゲットできました(^。^)

学生さんからの投稿です。水着ゲットおめでとうございます。

どうも、とある研究室のオーナーです。
少し前、水着がゲットできないというブログの記事があります。
  • 水着がGetできない(T_T)(リンク)
  • プログラミングで彼女を作る (リンク
私も、どういう問題か気になったので、やってみました。

問題
与えられるNの階乗N!を計算し、下位桁から続く0を取り除き、下位9桁を求めるプログラムを作成すれば、この彼女は羞恥心を解放し、真の姿を表すと言い伝えれられています。

計算例
Cで解きました。
水着をゲットした実行画面
やったぜ。
ちなみに、私はまだ他に何もやっていないので、知り合ったばかり好感度0の女の子に水着を着させてしまっています。はじめまして。
水着を着せた実行画面
プログラムはあえて載せません。頑張ってください。

この問題のポイント※ネタバレ注意
  • 計算の途中で、下位の数字を取り出さないと膨大な計算になり型に入りきらなくなるため、逐次取り出す。
  • 計算の途中11桁で取り出す理由は、0を除くことで桁が減る場合があるので余分に取る。
9桁切り出しの場合
49!=137921024
137921024×50=6896051200
0を取り除くと
68960512
となり、8桁になってしまう。

11桁切り出しの場合
49!=83137921024
83137921024×50=4156896051200
0を取り除いてから9桁取り出すと
568960512
と、正しい値を取り出すことができる。
ちなみに10桁は通らず、14桁からは型がオーバーフローする。

  • 階乗の計算を格納する変数は、11桁×9桁の計算が最大で入るので、long long int

いかがでしょうか。プログラミングをすることができれば知り合ったばかりの女の子ですら水着を着させることができます。やっぱりプログラミングは最高ですね。
これで卒業研究に戻ることができます。卒論仮提出まであと12日と7時間59分です。(このブログ作成時)

頑張ります。

補足:
  • 単純に計算すると、大変大きな数になりますが、下位の部分だけを保持して計算すればよいため、64bitあれば計算できます。64bitはlongです。long longと書いてもlongと書いても、現在の処理系は同じ64bitを指すことが多いようです。
  • 計算のときは、下位の0を取り除いた後の、下位9桁を用いれば良さそうです。つまり、モジュロ計算(10億を法とする計算)です。しかし、この場合は先頭ではないけれど特定の場所の9桁を計算に使うので、計算のたびに9桁にしてしまうと切り捨て誤差が出てしまいます。そのため、10桁程度で計算を済ませ、最後出力するときに、9桁にします。『「法とする計算」ではなく「有効数字を意識した計算」』であるところが、多くのプログラマを悩ませるポイントでしょう。

0 件のコメント:

コメントを投稿