質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.50%
Ruby

Rubyはプログラミング言語のひとつで、オープンソース、オブジェクト指向のプログラミング開発に対応しています。

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

Q&A

解決済

2回答

2010閲覧

[Ruby]回文数の範囲中央値

tsutou

総合スコア11

Ruby

Rubyはプログラミング言語のひとつで、オープンソース、オブジェクト指向のプログラミング開発に対応しています。

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

0グッド

1クリップ

投稿2017/09/25 12:31

[Ruby]回分数の中央値を求める

プログラミング初心者です。以下の問題の実行速度を上げたいです。

問題:回文数の中央値

【概要】

数の範囲を指定します。
その範囲内にある回文数( seeWikipedia - 回文数) の、真ん中の値を計算してください。

例えば下表の通りです:
値の範囲 回文数 真ん中の値
99〜120 99, 101, 111 101
200〜232 202, 212, 222, 232 212, 222

【入出力】
入力は
99,120
のようになっています。
下限と上限がコンマ区切りで並んでいます。

下限以上で、上限以下の回文数の真ん中の値を求めてください。

出力も普通に10進数です。
範囲内にある回文数が奇数個の場合には、中央の値はひとつに決まるのでそれを。

偶数個の場合にはぴったり中央の値はありませんので、
中央付近の2つの値をコンマ区切りで昇順に出力してください。

ただし、範囲内に回文数がひとつもない場合は
'-'
を出力してください。

###発生している問題

入力の桁数が多くなって来ると(具体的には8桁以上)を超えて来ると、実行速度1秒を超えてエラーが出てしまいます。

###該当のソースコード

ruby:palindrome.rb

1 2def palindrome_middle(a,b) 3 4inputs = Array(a..b) 5 6palindrome = inputs.reject{ |num| num.to_s != num.to_s.reverse } 7 8 if palindrome.length % 2 == 0 && palindrome.length >= 1 9 idx1 = palindrome.length / 2 - 1 10 idx2 = idx1 + 1 11 print palindrome[idx1.floor],',',palindrome[idx2.floor] 12 elsif palindrome.length >= 1 13 idx = palindrome.length / 2 + 1 14 print palindrome[idx.floor - 1 ] 15 else 16 puts '-' 17 end 18 19end 20 21 22input = gets 23a,b = input.split(',').map(&:to_i) 24palindrome_middle(a,b) 25

###試したこと
処理の高速化を試みたのですが、配列を順番に処理したらこれが限界なのかなと思い、根本から書き直した方がいいのか、悩んでおります。

ぜひもっといいやり方がありましたら、ご教授願いたいです。

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答2

0

ある範囲の数字を全部列挙して、その中で回文数になっているものを探しているのでしょうか?
それは時間がかかります。
例えば、2桁の回文数は、1199の9つです。
3桁の回文数は101
191,202292,...,909999と、910で90個あります。
別の考え方をすれば、2桁の回文数9パターンの間に09の10パターンの数字を入れる作り方があります。
4桁の回文数は、両端に11
99を置いて、間に2桁の回文数+「00」が入るパターンがあるため、
9
(9+1)=90個あります。
5桁の回文数は、両端1199で、間は(3桁の回文数 or「0(09)0」)となり、9*(90+10)=900個あります。
こう考えれば、「範囲内に回文数がいくつあるか」は比較的簡単に求まるのではないでしょうか。
下限の数および上限の数の桁数の場合、その桁数の数が全部範囲内にあるわけではないので、
その桁だけ特殊処理をする必要はありますが。
後は、その中央の場所に該当する回文数を探せばいいことになります。

投稿2017/09/26 02:19

編集2017/09/26 02:42
swordone

総合スコア20649

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

0

ベストアンサー

時間なかったので、本当にあってるかは確かめて欲しいですが考え方を参考にしてください。
上半分の数字と下半分の数字を抽出し、上半分を反転させて下半分を引いた値を足すことで一気に回文の数値にたどり着けるので計算量を抑えることができます。
ex)
2000

上半分:20
下半分:00

02 - 00 = 2

2000 + 2 = 2002 -> 回文数

ex)
34001

上半分:34
下半分:01

43 - 01 = 42

34001 + 42 = 34043 -> 回文数

引いた値がマイナスの場合は上半分の最初の数字を1足して下半分数値を全て0に戻します。
ex)
2010

上半分:20
下半分:10

02 - 10 = -8

上半分に+1、下半分を00とすると2100にしてもう一度計算

上半分:21
下半分:00

12 - 00 = 12

2100 + 12 = 2112 -> 回文

上記を桁数が偶数と奇数で分けて計算しています。

ruby

1def palindrome_middle(a,b) 2 current = a 3 palindrome = [] 4 while (current <= b) do 5 current_str = current.to_s 6 palindrome.push current if current_str == current_str.reverse 7 current_str_length = current_str.length 8 if current_str_length % 2 == 0 9 above = current_str[0..(current_str_length / 2 - 1)] 10 below = current_str[(current_str_length / 2)..(current_str_length - 1)] 11 diff = above.reverse.to_i - below.to_i 12 if diff > 0 13 current += diff 14 else 15 current += 10 ** (current_str_length / 2) 16 current -= below.to_i 17 end 18 else 19 above = current_str[0..((current_str_length - 1) / 2)] 20 below = current_str[((current_str_length - 1) / 2 + 1)..(current_str_length - 1)] 21 diff = above.reverse.to_i - below.to_i 22 if diff > 0 23 current += diff 24 else 25 current += 10 ** ((current_str_length + 1) / 2) 26 current -= below.to_i 27 end 28 end 29 end 30 31 if palindrome.length % 2 == 0 && palindrome.length >= 1 32 idx1 = palindrome.length / 2 - 1 33 idx2 = idx1 + 1 34 print palindrome[idx1.floor],',',palindrome[idx2.floor] 35 elsif palindrome.length >= 1 36 idx = palindrome.length / 2 + 1 37 print palindrome[idx.floor - 1 ] 38 else 39 puts '-' 40 end 41end 42input = gets 43a,b = input.split(',').map(&:to_i) 44palindrome_middle(a,b)

投稿2017/09/25 13:48

akichim21

総合スコア93

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

tsutou

2017/09/25 17:08

ありがとうございます。すごくわかりやすく、勉強になります。 早速明日、試してみようと思います。
tsutou

2017/09/25 17:16

連投申し訳ありません、おかげさまで12桁までは算出できるようになったのですが、それ以上は1秒の制限を超えてしまいます。16桁まであるのですが、12桁以上なら半分に分割するなどの処理を加えた方がよろしいでしょうか..?
akichim21

2017/09/26 01:52

まだ最適な解き方ではないんでしょうね。。 半分に分割しても16桁までは行かなそうですね。。 真ん中の値を算出するだけなら(a + b) / 2あたりの回文数をだすだけで解けそうですが、回文数が偶数奇数をどう判別するかがキモになりそうですね。 解けたらまた書きますね。
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問