[白俊アルゴリズム]193号「点数を探す」

3416 ワード
白駿 テキストリンク

[白俊アルゴリズム]193号「点数を探す」


質問する


白俊1193号です。
無限大の配列には以下の点数が書かれています.

このように列挙した点数は,1/1→1/2→2/1→3/1→2/2→…の等号順に1番,2番,3番,4番,5番,…の点数となる.
Xが与えられた場合、Xの2番目の点数を求めるプログラムを作成してください.입력第1行は、X(1≦X≦1000000)を与える.출력1行目にスコアを出力します.예제 입력11예제 출력11/1

問題を解く



この問題は군수열題です.
{1/1}, {1/2, 2/1}, {3/1, 2/2, 1/3}, {1/4, 2/3, 3/2, 4/1}, ...
ビーム中の分数の個数は1,2,3,4,1の順に増大した.
上の情報で問題を解くと.

  • 入力されたXが何番目のビームに属しているかを見つけます.

  • 見つかったN番目の束の最初の数字は何ですか.

  • 次に、クラスタの数番目の後にXを見つけます.

  • Nが偶数の場合は、配列から対角線方向に沿って上に下がります.(分母減少、分子増加)
    nが奇数の場合、配列の下から対角線方向に上向きになります.(分母増加、分子減少)

  • スコアを計算して出力します.
    • x = int(input())
num = 0
variable_add = 1
n = 0
while num < x:
    num += variable_add
    n += 1
    variable_add += 1

first_index = num-(variable_add-1)+1
N_th = x - first_index
if n % 2 == 0:
    a = 1 + N_th
    b = n - N_th
else:
    a = n - N_th
    b = 1 + N_th

print('%d/%d'%(a,b))
    マルチスレッドでの二重チェックロックについて
    なぜ鍵を使うのですか?