« 2016年4月 | トップページ | 2016年6月 »

2016年5月25日 (水)

「レッド・アンド・ホワイト問題」の高度じゃないコード

非常に遅ればせながらの「高度じゃないコード」シリーズその12、「レッド・アンド・ホワイト問題」です。

数学の問題をプログラミングで解こう!「レッド・アンド・ホワイト」問題解説

最初には1箇所だった赤マスがルールに従って1秒毎に変化していきます。その時、n秒後(1 ≦ n ≦ 108)の赤マスの数を答えろという問題です。
イメージがわきにくいので、まずは1秒~32秒のパターンを調べてみました。0が白マスで1が赤マスです。

01秒101
02秒10001
03秒1010101
04秒100000001
05秒10100000101
06秒1000100010001
07秒101010101010101
08秒10000000000000001
09秒1010000000000000101
10秒100010000000000010001
11秒10101010000000001010101
12秒1000000010000000100000001
13秒101000001010000010100000101
14秒10001000100010001000100010001
15秒1010101010101010101010101010101
16秒100000000000000000000000000000001
17秒10100000000000000000000000000000101
18秒1000100000000000000000000000000010001
19秒101010100000000000000000000000001010101
20秒10000000100000000000000000000000100000001
21秒1010000010100000000000000000000010100000101
22秒100010001000100000000000000000001000100010001
23秒10101010101010100000000000000000101010101010101
24秒1000000000000000100000000000000010000000000000001
25秒101000000000000010100000000000001010000000000000101
26秒10001000000000001000100000000000100010000000000010001
27秒1010101000000000101010100000000010101010000000001010101
28秒100000001000000010000000100000001000000010000000100000001
29秒10100000101000001010000010100000101000001010000010100000101
30秒1000100010001000100010001000100010001000100010001000100010001
31秒101010101010101010101010101010101010101010101010101010101010101
32秒10000000000000000000000000000000000000000000000000000000000000001

すると面白いことがわかります。この中で1(赤マス)の数が2つしかないのは1秒・2秒・4秒・8秒・16秒・32秒、つまり2のべき乗秒です。そして、それより1秒前は1(赤マス)と0(白マス)が交互に並びます。そうして調べていくと、秒数を2進数にした時の1の数を m とすると、2m が1(赤マス)の数があることがわかります。

続きを読む "「レッド・アンド・ホワイト問題」の高度じゃないコード"

| | コメント (0) | トラックバック (0)

2016年5月13日 (金)

「コード・トライアスロン2」の高度じゃないコード

またまた一ヶ月以上間が開いてしまいましたが、「高度じゃないコード」シリーズその11、「コード・トライアスロン2」です。

数学の問題をプログラミングで解こう!「コード・トライアスロン2」問題解説

この問題は、三角関数の誤差で悩みました。第一段階で求めた答えが少しずれると、最後の答えが全く違った値になるからです。でも、実際は、誤差のせいではなく、私がπの値として「PI」を使わずに「3.1416」を使っていたからなのでした。そして、そのような状態でも、6問のうち5問まではクリアできてしまっていたので、そこが悪いことになかなか気付かなかったのでした。

思い起こしてみると、Cとかでも今までπや三角関数を使ってプログラムを書いたことが一度もありませんでした。円(楕円)を描くプログラムを作ったことはありますが、描くだけならせいぜい二乗とルートしか使いませんので。

さて、今回の問題は、3つの問題を合わせたものですが、第一問の角度を求める問題で早くも躓いてしまいました。色々と補助線を引いたりしましたが、なかなか解決方法がわからず、仕方がないのでネットで検索して求め方を拾ってきました。

次に第二問ですが、n を d で割った余りが 1 になるということは、d は n-1 の約数ということです。ということで、約数の合計を求めますが、約数のうち 1 だけは取り除く必要があるので 1 を引きます。

最後の第三問は、2つのステップに分けて計算することにしました。m の桁数未満の回文数の合計と、m の桁数と同じ桁数の回文数の合計です。まぁ、別に分けなくても充分時間には余裕があるようでしたが・・・。テストプログラムを作って走らせてみると、桁数未満の回文数合計は次のような結果となりました。

リミット値回文数合計桁増え増分
100 540
100050040+49500
10000545040+495000
10000050045040+49500000
1000000545045040+495000000
1000000050045045040+49500000000


この表からわかるように、1桁増えると増分は10倍と100倍を交互に繰り返しています。ということで、これを使えば、m の桁数未満の回文数合計は桁数回のループで計算できます。その後は、m の上半分の桁の数を増やしながら、それをリバースした数を後ろにくっつけます。ただし、m の桁数が奇数の場合はくっつける数の最初の桁を取り除きます。

続きを読む "「コード・トライアスロン2」の高度じゃないコード"

| | コメント (0) | トラックバック (0)

« 2016年4月 | トップページ | 2016年6月 »