3

私はコーディングの問題に取り組んでいましたが、そのサブパートとして次の問題が発生しました。

数xが与えられ、それを2乗して、数がx^2になるようにします。これで、1からx ^2までの数値が得られます。例：if number = 4; 次に4^2 = 16

         1             ----->1
      2     3          ----->2
   4     5     6       ----->3
7     8     9    10    ----->4
  11    12    13       ----->5
     14    15          ----->6
        16             ----->7

今、私はkと言う番号を与えられており、それがどのグループに属しているかを伝える必要があります。ここで8は4番目のグループに属しています。

私が思ったのは、1から始めて、カウントを1に初期化し、1<8かどうかを確認することです。はいの場合、2を1（前の合計）に追加し、カウントを2に増やして、3 <8かどうかを確認しますか？はいの場合は3から3（前の合計）を追加し、カウントを3に増やして6 <8かどうかを確認します。はいの場合は4から6を追加し、カウントを4に増やして10 <9かどうかを確認しますか？いいえの場合は終了します。したがって、グループ番号。カウントすなわち4です。

しかし、私のアプローチよりも速い方法はありますか？

編集1： 私のアルゴリズムで、カウントが前の例では4である指定された数に達したときに、5ではなく3を追加する必要があることを言及するのを忘れました。例：

検索する番号が14の場合、

1<14 yes then add 2

3<14 yes then add 3

6<14 yes then add 4

10<14 yes then add **3**  ---->here I need to add 3 instead of 5

13<14 yes then add **2**  ---->here I need to add 2 instead of 6

15<14 No so output count.

if条件を使用して5の代わりに3を追加することは可能ですが、追加する値がxの値に応じて自動的に増加してから減少する方法はありますか（xが何を指すかについては上記の例を参照してください）

4

5 に答える 5

5

長方形の上半分は三角形です。

         1             ----->1
      2     3          ----->2
   4     5     6       ----->3
7     8     9    10    ----->4

右側の数字（1、3、6、10）は三角数と呼ばれます。そこでの逆式（「三角根と三角数のテスト」というサブタイトルの下）を問題に使用できます。

def group(x, number):
    if number <= x^2 / 2 :
        return ceiling( (sqrt(8*number+1) - 1) / 2 )
    else:
        return 2*x - group(x, x^2+1-number)
于 2013-02-05T10:07:18.277 に答える
4

前半では、グループiは番号で終わりますi*(i+1)/2。nしたがって、で番号が与えられていると仮定しましょう。で最小のものをn <= x^2/2見つける必要があります。ii*(i+1)/2 <= n

i*i+i-2n = 0歩留まりを解くi：((sqrt(1+8n)-1/2) 例n = 8：i = ceil((sqrt(65)-1)/2) = 4

もちろん、ケースn > x^2/2はもう少し複雑です。

于 2013-02-05T10:02:43.257 に答える
3

まず、簡単にするために、 x <= n ^ 2/2であり、xがグループtに属していると仮定します。それで：

t*(t-1)/2 < x <= t*(t+1)/2

ここから、2つの2次不等式が得られます。

t^2 - t - 2x < 0
t^2 + t - 2x >= 0

ここでD=1+8x、そしてt> 0であるため、それらの一般的な解は次のようになります。

t ∈ [ (-1-sqrt(D))/2; (1+sqrt(D))/2 )

ここで、tは整数である（そして定義上一意である）ことを思い出してください。そのため、解の式が得られます。

t = floor( 1+sqrt(D))/2 )

これは、ケースx <= n ^2/2の解決策でした。それ以外の場合は、次のようにして解決できます。

  1. x：= n ^ 2-x + 1
  2. 上記のようにtを見つける
  3. t：= n-t + 1

お役に立てれば。

于 2013-02-05T10:07:54.127 に答える
2

右上の対角線上の数字は、いわゆる「三角数」であり、式がありn(n+1)/2ます。

右下の対角線上の数字は、16から三角数を引いたものに等しく、式がありx^2 - (2*x-n-1)(2*x-n)/2ます。

したがって、とが与えられkた場合、式が、以上であるようなx最小のものを探し、 thの三角数（この場合は10）より大きいか小さいかに応じてどの式を選択します。両方の関数は単調（常に増加）であるため、浮動小数点で（2次式を使用して）2次方程式を解き、次の整数（いわゆる「天井」）に切り上げることでこれを行うことができます。nkkxx(x+1)/2n

多くの複雑さを導入せずに浮動小数点の不正確さを説明するには、整数演算を使用して結果を確認する必要があります。浮動小数点計算が正しい結果をわずかにオーバーシュートまたはアンダーシュートし、間違った整数値に丸められる可能性があります。小さな数値の場合、最悪の場合1を超えて外れることはないので、それを検出して修正するコードは単純です。結果を数式にk入れて得られる値と、どちらかの側の値を比較するだけです。nn

于 2013-02-05T10:11:29.940 に答える
1

xthまず、行が正確に真ん中の行であり、x個の要素が含まれていることを確認する必要があります。したがって、この特定の行の要素は何ですか？それらはからのもの[x(x+1)/2-x, x(x+1)/2]です。したがって、アルゴリズムは次のようになります。

  1. 検索する番号が中央の行にあるか、それより少ないか多いかを確認します。
  2. 真ん中の行にある場合はxを印刷します。
  3. 中央の行よりも小さい場合は、すべての行が三角数で終わることを確認する必要があります。数式を使用してceil((sqrt(8x+1)-1)/2)、正確な行を取得できます。

  4. それ以外の場合、数値が中央の行よりも大きい場合、uができることは、下の三角形を次のように考えることです。

    6 5 4

    3 2

    1

つまり、すべての数値はに等しくなりx^2+1-that numberます。x^2+1-number to be searchedしたがって、上記の式自体を使用して下の三角形を検索します。これにより、行番号が反転した形になります。その番号がであることがわかりますk。その場合、正しい形式の値はですx-1+k+1。最後に値に追加xして、答えを下の三角形にシフトします。したがって、答えはになり2x+kます。

これは、問題に対するO（1）ソリューションです。

于 2013-02-05T10:25:24.113 に答える