数学に基づいたアルゴリズム

Question

私はこれに新しいですが、私はいくつかの助けを得ることができたと思っていました。

次のようにだから私は、与えられた問題は、次のとおりです。明確な正の整数のリストを考えると

、2つの正の整数a、bが表すのリストを返す関数を書きます。 a/bの比率は最後の整数の半径の2倍にする必要があります。

与えられた[4,30,50]とは、4から30までの距離が26で、30から50までの距離が20であることを示しています。最初の半径は最後の半径の2倍です。これに対する解決策は、最初の半径は12であり、2番目の半径は14であり、最後は6です。最後のものは最初の半径の半分です。 12 + 14 = 26、14 + 6 = 20と同様に。だから、すべての歯車は互いに動くだろう。解[-1、-1]が返されないとすれば、[4,17,50]のようなものは解を持たないでしょう。

私はチェックのために使用しようとしているコードですが、間違いなく実行しません。

public static int[] answer(int[] pegs) 
{ 
    int[] noSolution = [-1,-1]; 
    int[] results = new int[2]; 
    int secondGear = pegs[1]; 
    int firstGear = pegs[0]; 
    int maxRadius = secondGear - firstGear; 

    int checkRadius = 0; 
    while(checkRadius < maxRadius) 
    { 
     int distance = maxRadius; 
     int changingRadius = distance - checkRadius; //Using this to get varying radii to see which one works 
     for(int i =1; i<pegs.length-1;i++) 
     { 
      distance = pegs[i+1] - pegs[i]; 
      if(changingRadius >= distance) 
      { 
       break; 
      } 
      else 
      { 
      changingRadius = distance - changingRadius // Given that our radius is less than the distance 
                 // let's continue to check if it is the same for the other distances 
      } 
     } 
     if((changingRadius*2) == checkRadius) 
     { 
      break; // Should be the case we found the right radius 
     } 
     checkRadius++; // Didnt find the right one, increment and test a new radius 

これはかなり困惑しているので、助けが必要です。

Answer 1

これを線形方程式のシステムとして設定することができます。

 --   ---- 
/ \ /  \ 
(  ) (  ) () 
(----><----)(-----><-----)(-><-) 
( 4 )x1( 30 )x2(50) 
    \ / \  /
    --   ---- 

x1とx2は、それぞれ第2の歯車と最後の二つの歯車のメッシュポイントとします。中間ギアはメッシュポイントの中間にあるので、式は

x1 + x2 
------- = 30, 
    2 

です。最後の2倍の大きさである第1のギアのための方程式は

一般に

x1 - 4 = 2*(50 - x2). 

は、我々は標準的な方法により線形時間で解くことができる

[1/2 1/2 0 0 ... 0 0 ] [ x1 ] [ c1 ] 
[ 0 1/2 1/2 0 ... 0 0 ] [ x2 ] [ c2 ] 
........................... .... = .... 
[ 0 0 0 0 ... 1/2 1/2] [xn-2] [cn-1] 
[ 1 0 0 0 ... 0 2 ] [xn-1] [c1 + 2*cn-1], 

のような線形システムを取得することです。このようにして得られた一意の候補が正の半径を意味することを確認する。