Python
 Computer >> コンピューター >  >> プログラミング >> Python

Pythonの配列内の1つの要素を除くすべての除数である整数Xを見つけます

数値の配列があるとします。与えられた配列の1つの要素を除いて、すべての約数である数Bを見つける必要があります。すべての要素のGCDが1ではないことに注意する必要があります。

したがって、入力が{8、16、4、24}のような場合、これは4を除くすべての除数であるため、出力は8になります。

これを解決するには、次の手順に従います-

  • n：=配列のサイズ
  • nが1と同じ場合、
    • return（array [0] + 1）
  • プレフィックス：=サイズnの配列、0で埋める
  • 接尾辞：=サイズnの配列で、0で埋めます
  • prefix [0]：=array [0]
  • 1からnの範囲のiについては、
    • prefix [i]：=gcd of（array [i] and prefix [i-1]）
  • サフィックス[n-1]：=配列[n-1]
  • n-2から-1の範囲のiの場合、1ずつ減少します。
    • suffix [i]：=gcd of（suffix [i + 1] and array [i]）
  • 0からn+1の範囲のiの場合、do
    • cur：=0
    • iが0と同じ場合、
      • cur：=接尾辞[i + 1]
    • それ以外の場合、iがn-1と同じ場合、
      • cur：=prefix [i-1]
    • それ以外の場合、
      • cur：=gcd of（prefix[i-1]およびsuffix[i + 1]）
    • array [i] mod curが0と同じでない場合、
      • リターンカー
  • 0を返す
サンプルコード

理解を深めるために、次の実装を見てみましょう-

from math import gcd
def getDivisor(array):
   n = len(array)
   if (n == 1):
      return (array[0] + 1)
   prefix = [0] * n
   suffix = [0] * n
   prefix[0] = array[0]
   for i in range(1, n):
      prefix[i] = gcd(array[i], prefix[i - 1])
   suffix[n - 1] = array[n - 1]
   for i in range(n - 2, -1, -1):
      suffix[i] = gcd(suffix[i + 1], array[i])
   for i in range(0, n + 1):
      cur = 0
      if (i == 0):
         cur = suffix[i + 1]
      elif (i == n - 1):
         cur = prefix[i - 1]
      else:
         cur = gcd(prefix[i - 1], suffix[i + 1])
      if (array[i] % cur != 0):
         return cur
   return 0;
array = [8, 16, 4, 24]
print(getDivisor(array))

入力

[8, 16, 4, 24]

出力

8

  1. 配列内の最大の要素を見つけるPythonプログラム

    この記事では、以下に示す問題ステートメントの解決策について学習します。 問題の説明 −配列が与えられたので、配列の最大要素を計算する必要があります。 ここでは、ループ全体をトラバースして最大の要素を計算し、要素を取得するブルートフォースアプローチを使用します。 以下の実装を観察できます。 例 # largest function def largest(arr,n):    #maximum element    max = arr[0]    # traverse the whole loop    for

  2. 配列内の最大の要素を見つけるPythonプログラム

    この記事では、特定の問題ステートメントを解決するための解決策とアプローチについて学習します。 問題の説明 入力として配列を指定すると、配列内で最大の要素を見つける必要があります。 アプローチ maxを最初の要素として初期化します。 この後、指定された配列を2番目の要素から最後までトラバースします。 トラバースされたすべての要素について、現在のmaxの値と比較します maxより大きい場合、maxが更新されます。 それ以外の場合、ステートメントはを超えます 以下の実装を見てみましょう- 例 def largest(arr,n):    #maximal element