☰

少数だけ？

tag-icon • tag-icon bash math algorithms
少数だけ？

完了しようとしていますプロジェクトオイラー＃5。私のコードは論理的に動作しなければならず、ShellCheckを通過しますが、何らかの理由で出力は提供されません。コードは以下のように表示されます。ありがとうございます。別のスタック交換サイトにいる必要がある場合は申し訳ありません。

#!/bin/bash
 i=1
 while [[ $((i % 2)) -eq 0 && $((i % 3)) -eq 0 && $((i % 5)) -eq 0 && $((i % 7)) -eq 0 && $((i % 11)) -eq 0 && $((i % 13)) -eq 0 && $((i % 17)) -eq 0 && $((i  % 19)) -eq 0 ]]
 do
     i=$((i+1))
 done
 echo $i

答え1

はい、検査を受ける必要があります[[ $((i % 2)) -eq 0 && $((i % 3)) -eq 0 … … ]]。数字が$iリスト内のすべての数字に分割されるかどうかをテストします。 同時に。しかし、数値がテストと一致する場合はどうすればよいですか？番号が見つかりましたので印刷してみますか？

いいえ、増やしています。つまり、この操作をキャンセルする必要があります。

$iテストが失敗すると増加します。

次のいずれかを実行します。

while ! [[ … . … ]]; do

または：

until [[ … . … ]]; do

これにより、9699690（コードで探している数字で正解でもない）を見つけるのに時間がかかります。

それを見つける正しい方法を読んでください。

少数だけ？

しかし、4、6、9などを含めるとどうなりますか？

少数ではないから？たとえば、このアイデアを説明します。
数値 9699690 は、テスト中のすべての素数 (2 3 5 7 9 11 13 17 19) に分割できますが、4 に分割することはできません。

作成したコードが失敗しました。無差別代入で答えを見つけるには長い時間がかかります（特に最も遅い言語の1つであるシェルで正しいものが見つかるまですべての整数を試してください）。

LCDモジュール

しかし、問題を次のように説明すると簡単になります。

リスト{1..20}のLCMを見つけます。

それはエル東氏アーモン中サイズ複数の数の倍数。最小公倍数は次のとおりです（ LCM(a,b) = (a×b) / gcd(a,b)数学式）。

GCD

gcdはどこにありますか？G再試験氏アーモンDアイバイザー。

ユークリッド（約2300年前）が最初を説明しました。  ユークリッドアルゴリズム2つの数字の最大公約数（GCD）を計算する効率的な方法です。

最新のシェルで関数として実装することは非常に簡単です。

gcd() {   # Calculate $1 % $2 until $2 becomes zero.
          until [ "$2" -eq 0 ]; do set -- "$2" "$(($1%$2))"; done
          echo "$1"
      }

これにより、lcmコードも非常に簡単です。

lcm() {   echo "$(( $1 / $(gcd "$1" "$2") * $2 ))";   }

必要なのは、1つだけ残るまで与えられたすべての引数を繰り返すことです。

while  [ $# -gt 1 ]
do
       t="$(lcm "$1" "$2")"
       shift 2
       set -- "$t" "$@"
done
echo "$1"

使用した番号でプログラム全体を呼び出すと、上記で使用した番号が提供されます。

$ ./script 2 3 5 7 11 13 17 19
9699690

次のスクリプトを呼び出すことができます。

$ ./script {2..20}

そうしてこそ、最終的な答えを得ることができます。

答え2

bash問題を解決するには、タグ付けを使用する必要がありますか？

それでは活用してみましょう。ここで文字列器具：

$ bc <<< '9*8*7*5'
2520
$ bc <<< '19*18*17*13*11*8*7*5'
232792560

ポイントは、前の数字に分割されていない最大の数字を掛けることです。たとえば、最初のケースでは... 9*8*7*(そして6はありません. *5，２は８，９，８に分けられる。

しばらく考えた後、私はすべての長さのシーケンスに対するより一般的なアプローチは、すべての素数を一緒に掛け、少数でない場合は残りを掛けることであることに気づきました。

2*3*2*5*1*7*2*3*1*11*1*13*1*1*2*17*1*19

2番目の2がすでにあるので、数字4の代わりに2を使用します。数字8と16の場合も同様のトリックが使用されます。数字6は2 * 3で覆われているため、数字10、12、14、15、18にも同様に1を使用します。最後に9を3に置き換えます。明らかに、これらすべては19*18*17*13*11*8*7*5前述の方法で単純化することができます。

関連情報