Algorithm with Math

1.GCD/LCM（最大公倍数、最小公倍数）

最大公約数:2つ以上の公約数の最大公約数
*ユークリッド弧除去法

を使用

最小公倍数(LCM.Least Common Multiple):2つ以上の公倍数のうち最小公倍数

1）最大公約数

幅24センチ、奥行き12センチの矩形の縁に照明を取り付けたいです.4つのコーナーに照明器具を設置し、残りの照明器具を一定の時間間隔で設置しようとすると、最低何個の照明器具が必要ですか?頂点を除いて、長方形のすべてのエッジに少なくとも1つの光源を取り付ける必要があります.(取り付けの照明ピッチは、整数で表すセンチメートル単位です.)

24と12の最大承諾数は12ですが、上記の問題では12を除く最大承諾数は6です.
*

のため、すべての長方形のエッジに少なくとも1つの照明を取り付ける必要があります.

幅:6個の照明間隔=>24/6 X 2

奥行き:6照明間隔=>12/6 X 2

(1)GCDの関数を求める

function GCD(a, b) { 
  // 단, a가 b보다 커야함
  let R
  // R이 0이 될 때까지
  while (a % b !== 0)  {
    R = a % b
    a = b
    b = R
  }
  return b
}

(2)再帰的にGCDを求める関数

function GCD (a, b) {
  if(a % b === 0) {
    return b 
  }
  
  return GCD(b, a % b) 
}

（3）一方通行コード

const GCD = (a, b) => a % b === 0 ? b : GCD(b, a % b);

2）最小公倍数

防疫マスクを製作・販売するMask States社は、珍しい伝染性インフルエンザを予防するため、既存価格を維持し、所定数の防疫マスクを提供している.この会社にはA、B、Cの3人しかいません.社長も含めて、マスクを作っています.それぞれの制作速度は以下の通りである.
Aは55分ごとに9個、Bは70分ごとに15個、Cは85分ごとに25個の防疫マスクを作る.同社の人は05:00からマスクを同時に作り、55分、70分、85分ずつ5分間休憩.この3人が初めて同時に休憩した時間が退勤時間だったら、当日作ったマスクは全部で何個ですか?△休憩時間と退社時間が重なると、休憩後に退社する.

60,75,90の最小公倍数は900

である.

A:900分で135個(900/60=15=>15 X 9)

B:900分以内180個(900/75=12=12 X 15)

C:900分で250個(900/90=10=>10 X 25)

(1)GCDによるLCM取得

let LCM = a*b/GCD

(2)LCMの関数を求める

function LCM (a, b) {
  return a * b / GCD(a, b)
}

（3）一方通行コード

// 한줄로 작성한 코드
const LCM = (a, b) => a * b / GCD(a, b)

2.配列/組合せ

1）シーケンス

一桁と書かれた紙片が散らばっている.ばらばらの紙切れを貼って、いくつかの小数点を作ることができることを見たいです.もし紙に記録されているすべての数字が順番に並んでいたら、この紙でできるのはいくつですか.

順序:n個のオプションから1つのオプションを選択し、順序でリストすると、異なる場合があります:

Permutationの略P、

を表す

普通食:nPr = n! / (n - r)!

2）組み合わせ

王妃を避けるため、7人の小人と平和に暮らしていた白雪姫は危機に直面した.一日の仕事を終えて帰ってきた「七」矮人は「九」名.9人の小人はみな「白雪姫と7人の小人」の主役だと主張している.白雪姫は7人の小人の身長の和が100だったことを覚えています.9人の小人がそれぞれ背があるとき、白雪姫と平和に生活していた7人の小人を探す方法は何ですか.

組み合わせ:

を順番に並べない

の組み合わせの略語Cで、

を表す.

普通食:nCr = n! / (r! * (n - r)!)

3.べき乗セット

べき乗セット:セットのすべての部分セット

は、すべての部分集合をどのようにリストするかを決定します.

は、最も前の要素(または任意の集合要素)が階層化されているかどうかを決定します.

の集合の要素がn個である場合、すべての部分集合の個数は2 n個の

である.

べき乗セットを求める方法は循環構造を持ち,循環構造は任意の要素を除いて集合を小さい単位に縮小する.
*

まで問題を縮小

集合{1,2,3}のべき乗セットを求めます