[python]フルナビゲーションカーペット(手順2)

リンクテキスト

完全探索とは何ですか?

◆「無知に解く(brute-force)」とは、コンピューターの高速計算能力を利用して、可能な限り多くの数字を並べて、答えを探す方法だ.これはすべての可能な方法のアルゴリズムを創造することを意味する.
◆完全探求は、コンピューターを活用して速度を速く計算する方法だ.
◆(例)n個の要素からm個を選択した全ての組合せのコードを出力する
1.Brute Force:for文とif文を使用して最初から最後までナビゲート
2.ビットマスク
3.並べ替え:並べ替えの時間複雑度はO(N!)
4.バックトレース
5.BFS
以上の5つの方法を使って、すべての完全なナビゲーション方法を熟知することをお勧めします!!
すべての場合、ナビゲーション数は問題が発生した場合に最も簡単な方法ですが、ベースと見なすこともできます.
また,問題に制約条件と以上のいくつかのSKILLを加えることで,問題解決時間を大幅に向上させることができる.
リンクテキスト

問題の説明

Leoはじゅうたんを買いに行きました.格子じゅうたんの列が見えました.真ん中は黄色で、一列は茶色で、下図のように見えます.

Leoで見たカーペットでは,パラメータが茶色のメッシュの数はbrown,黄色のメッシュの数は黄色であった.
カーペットの縦横寸法を順番に並べて返します.

せいげんじょうけん

茶色の格子の水brownは8以上5000以下の自然水です.
黄色のメッシュの数黄色は、1つ以上の200000以下の自然数です.
カーペットの横方向の長さは、縦方向の長さ以上です.
->垂直<=横

I/O例

brownyellowreturn102[4, 3]81[3, 3]2424[8, 6]

練習する。

完全なナビゲーション->知識のないリスト、ルールの検索
1個の黄色(2^0)->brown 3+3+1+1個->[3,3]
2個の黄色(2^1)->brown 4+4+1+1個->[4,3]
黄色4個(2^2)->brown 4+2+2個->[4,4]
黄色6個(2^1*3^1)->brown 5+5+2+2個->[5,4]
全部で6[3,3]...黄色1個、brown 3+3+1+1
全部で7[4,3]...黄色2個、brown 4+4+1+1
全部で8[4,4]...黄色4個、brown 4+2+2+2=12
全部で9[5,4]...黄色6個、brown 5+5+2=2=14
全部で10[5,5]...黄色9個、brown 5+5+3+3=16
全部で11[6,5]...黄色12個、brown 6+6+3+3+3
[6, 6][7, 6]
[7, 7]
...[8, 6]...?
[8, 7][8, 8]
col 2+row 2+4が茶色の数である場合、col+2、row+2はカーペットの横方向と縦方向である
2a + 2b == brwon + 4
全部で10[5,5]...黄色9個、brown 5+5+3+3=16
25 + 25 = 20 = 16+4
取得->カーペットの横寸法と縦寸法を順番に並べて戻す

に答える

リンクテキスト

def solution(brown, yellow):
    answer = []
    total = brown + yellow                  # a * b = total
    for b in range(1,total+1):
        if (total / b) % 1 == 0:            # total / b = a
            a = total / b
            if a >= b:                      # a >= b
                if 2*a + 2*b == brown + 4:  # 2*a + 2*b = brown + 4 
                    return [a,b]
            
    return answer

def solution(brown, red):
    for i in range(1, int(red**(1/2))+1):
        if red % i == 0:
            if 2*(i + red//i) == brown-4:
                return [red//i+2, i+2]

def solution(brown, red):
    for row in range(1, int(red**0.5) + 1):
        if red%row == 0:
            col = red//row
            if 2 * row + 2 * col + 4 == brown:
                return [col + 2, row + 2]

最初はダブルfor文で数字を1つずつチェックし、row colがbrownとredの総数を返すことを実現します.しかしその後,この方法はタイムアウトし,反例があることが分かったので,ルールを見つけた.col 2+row*2+4が茶色の個数の場合,col+2,row+2がカーペットの横,縦になり,for文を赤の半分+1に変換して検査し実現した.

def solution(brown, yellow):    
    total = brown + yellow
    for i in range(3, int(total**0.5) + 1):
        if not total % i and (i-2) * ((total//i)-2) == yellow:
            return [total//i, i]

茶色のメッシュと黄色のメッシュの合計は、メッシュ全体のサイズになります.
また、メッシュ全体を矩形にするためには、横xで縦方向に表示できる必要がある.つまり、約束数を求めればいいのです.
問題の条件では黄色のメッシュが1より大きいため、メッシュ全体のサイズは少なくとも3 x 3より大きくなければならない.
したがって,for文の範囲は3から始まる.
いくつかの数の約数はいつも偶数である.ペアの2つの数が異なる場合は、1つは大きくて小さくなります.(もちろん)
薬水の偶数は平方根より大きくないはずだ.したがってrangeの終了範囲はtotal**0.5である.
iで割ると約数、2を掛けると黄色になります.答えが見つかったのでtotal//iとiを返します.
(iに比べてtotal//iがiよりも優先されるのは、iがより小さいか等しいためであり、問題条件下では横方向の長さが等しいかそれ以上である)