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

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

ただいまの
回答率

90.61%

  • Ruby

    7381questions

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

  • アルゴリズム

    398questions

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

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

解決済

回答 2

投稿

  • 評価
  • クリップ 1
  • VIEW 479

tsutou

score 3

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

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

 問題:回文数の中央値

 【概要】

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

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

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

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

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

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

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

発生している問題

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

該当のソースコード

def palindrome_middle(a,b)

inputs = Array(a..b)

palindrome = inputs.reject{ |num| num.to_s != num.to_s.reverse }

  if palindrome.length % 2 == 0 && palindrome.length >= 1
    idx1 = palindrome.length / 2 - 1
    idx2 = idx1 + 1
    print palindrome[idx1.floor],',',palindrome[idx2.floor]
  elsif palindrome.length >= 1
    idx  = palindrome.length / 2 + 1
    print palindrome[idx.floor - 1 ]
  else
    puts '-'
  end

end


input = gets
a,b = input.split(',').map(&:to_i)
palindrome_middle(a,b)

試したこと

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

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

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

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

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

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 2

+1

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

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

checkベストアンサー

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 -> 回文

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

def palindrome_middle(a,b)
  current = a
  palindrome = []
  while (current <= b) do
    current_str = current.to_s
    palindrome.push current if current_str == current_str.reverse
    current_str_length = current_str.length
    if current_str_length % 2 == 0
      above = current_str[0..(current_str_length / 2 - 1)]
      below = current_str[(current_str_length / 2)..(current_str_length - 1)]
      diff = above.reverse.to_i - below.to_i
      if diff > 0
        current += diff
      else
        current += 10 ** (current_str_length / 2)
        current -= below.to_i
      end
    else
      above = current_str[0..((current_str_length - 1) / 2)]
      below = current_str[((current_str_length - 1) / 2 + 1)..(current_str_length - 1)]
      diff = above.reverse.to_i - below.to_i
      if diff > 0
        current += diff
      else
        current += 10 ** ((current_str_length + 1) / 2)
        current -= below.to_i
      end
    end
  end

  if palindrome.length % 2 == 0 && palindrome.length >= 1
    idx1 = palindrome.length / 2 - 1
    idx2 = idx1 + 1
    print palindrome[idx1.floor],',',palindrome[idx2.floor]
  elsif palindrome.length >= 1
    idx  = palindrome.length / 2 + 1
    print palindrome[idx.floor - 1 ]
  else
    puts '-'
  end
end
input = gets
a,b = input.split(',').map(&:to_i)
palindrome_middle(a,b)

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2017/09/26 02:08

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

    キャンセル

  • 2017/09/26 02:16

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

    キャンセル

  • 2017/09/26 10:52

    まだ最適な解き方ではないんでしょうね。。
    半分に分割しても16桁までは行かなそうですね。。

    真ん中の値を算出するだけなら(a + b) / 2あたりの回文数をだすだけで解けそうですが、回文数が偶数奇数をどう判別するかがキモになりそうですね。
    解けたらまた書きますね。

    キャンセル

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

  • ただいまの回答率 90.61%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

  • 解決済

    ハッシュにして出力したい

    下記humans.csvをrbファイルで読み取って、記載した実行結果を出したいです。その際、途中まで書いて下記記載しているrbファイルのコードを使って出したいのですがどのように続き

  • 解決済

    情報の初期化?

    お世話になります。 rubyでゲームを作っているのですが、ゲームを始めて、終わった後、タイトルに戻って、もう一度ゲームを始めるということをしたいのですが、タイトルに戻るまではでき

  • 解決済

    RubyでのFor文

    RubyのFor文で範囲オブジェクトを-1から始めようとするとsyntax error, unexpected tUMINUS_NUMとエラーが出ます 全文がこんな感じなので

  • 解決済

    rubyでgetsを使ったwhileから抜ける方法

    n = 0 num = 1 ary = [] while true ary[n] = gets.chomp print "num:#{num}" print "text:

  • 解決済

    Rubyのコードについて。

    ご協力お願いします。以下のrubyのコードで、エラーではないのですが、gets.chompした後に欲しい値が取れず、そのまま終わってしまいます。なぜなのかご説明お願いします!!

  • 解決済

    書いたコードのどこが間違っているのか分かりません

    num = gets.chomp.split("").map(&:to_i) while 1 flag = true (0..num.size-2).each do |i

  • 解決済

    二つの配列を組み合わせてつなげるには?

    ary0 = ["とんかつ定食", "ラーメン", ”チャーハン”, ”サラダ”] ary1 = [1, 3, 0, 2] (配列ary0とary1は同じ大きさ) ”とん

  • 受付中

    実装方法、検索アルゴリズムの改善

    課題 下記の課題を出題されました。 機能としては実装できましたが、よりよいアルゴリズム、実装方法があるのでは?と考えております。 アドバイスを頂きたく投稿致しました。 下記

同じタグがついた質問を見る

  • Ruby

    7381questions

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

  • アルゴリズム

    398questions

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