[CS] Algorithm with Math Day-47

問題を解決する3つの概念

GCD/LCM(最大公倍数、最小公倍数)
(greatest common divisor/least common multiple)

シーケンス/組合せ

べき乗セット

Math(シーケンス/組合せ)付きアルゴリズム

整列

シーケンス:順番にリストされます
ex)5枚のカードから3枚抜き出してリストした場合、5 p 3

5章と3章で選択したすべてのシーケンスの数.
5p3 = (5 x 4 x 3 x 2 x 1)/(2 x 1) = 60

普通式5 p 3=5!/(5 - 3)!

0! && 1! === 1

コンポジット

グループ:順序を考慮せずにグループ

たとえば...[a,b,c],[a,c,b]同じ友达として他の[b,c,a]も同じグループです!

重複する部分を取り除く.

5章から3章までランダムに選択した組合せの数.
5c3 = 5!/(3! 2! 1!) = 10

質問:小数点を検索

小数点は1と自分だけの数に分けます.

1は小数ではありませんので、2から実行します.1は含まれません.

数字2は自分以外の2の倍数を除く.

3を除いて、3の倍数を取り除きます.

4は2によって削除されました.

5を除き、5の倍数を削除します.

let solution = (n) => {
    let arr = [];
    for(let i = 1; i <= n; i++){
    	arr.push(i);
    }
    for(let i = 1; i * i < n; i++){
    	if(arr[i]){
            let num = arr[i];
            for(let j = num * num; j <= n; j += num){
            	arr[j-1] = 0;
            }
         }
     }
     let result = arr.filter((number) => number);
     result.shift();
     return result.length;
 };

質問:7人の小人

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

function solution(arr) {
    let result = arr; // result에다가 얕은 복사
    let sum = arr.reduce((a, b) => a + b, 0);
    for(let i = 0; i < 8; i++){
    	for(let j = i+1; j < 9; j++){
        	if((sum - (arr[i]+arr[j])) === 100){
                  arr.splice(j, 1); // 뒤에서부터 하나씩 지우기
                  arr.splice(i, 1);
            }
        }
    }
    return result;
}

Algorithm with Math (GCD/LCM)

薬水:ある数を分ける

倍数:ある数の1,2,3...n倍数

公約数:2つ以上の公約数

公倍数:2つ以上の公倍数

最大公約数:GCD:2つ以上の公約数のうち最大公約数

最小公倍数:複数の公倍数のうち最小公倍数

質問:最小公倍数-LCM(Mask)

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

最小公倍数を考慮すれば、問題を簡単に迅速に解決することができる.

勤務時間、休憩時間に5分を加え、A、B、Cは60分、75分、90分ごとにマスクを生産する.したがって、休憩後に同じ時点を初めて探す場合は、公倍数と最小公倍数の概念を理解し、問題に近づく必要があります.
従って、LCM(60、75、90)は900である.
従って、Aは900/60=15回、15回*9個、135個のマスクを製造した.
Bは180個のマスクを作り、Cは250個のマスクを作るため、1日に作られるマスクは135個+180個+250個=565個である.
ex)最小公倍数と最小公倍数を求める問題

function solution (n, m) {
	let result = [];
    let greatest = (a, b) => {
    	if(b === 0) {
        	return a;
        }
        return greatest (b, a%b);
    }
    let least = (a, b) => (a * b) / greatest(a, b);
    return [greatest(n, m), least(n, m)]
}

質問:照明の取り付け(最大公約数)

光源を矩形(幅24センチ、深さ12センチ)の縁に取り付け、コードベースのラウンジに置きたいです.4つのコーナーに照明器具を設置し、残りの照明器具を一定の時間間隔で設置しようとすると、最低何個の照明器具が必要ですか?頂点を除いて、長方形のすべてのエッジに少なくとも1つの光源を取り付ける必要があります.(取り付けの照明ピッチは、整数で表すセンチメートル単位です.)
最大の承諾数を考慮すると、問題を迅速に解決できます.
GCD(12,24)は12である.したがって(12/12+24/12)x 2=3 x 2=6となる.
問題では、頂点以外のすべての矩形エッジに少なくとも1つの照明を取り付ける必要があるため、12以外の最大公約数で問題を解決しなければならない.
(12/6+24/6)x2=6x2=12.

Math-べき乗セットを持つAlgorithm

集合{1,2,3}のすべての部分集合は{},{1},{2},{3},...{1,2,3}とすることができ、サブセットの総数は8である.
これらのサブセットはすべてべき乗セットと総称されます.
ある集合が存在する場合、その集合のすべての部分集合をべき乗セットと呼ぶ.