81015


5000px x 5000pxで固定されている真っ白なキャンバスの上に  
(width = 300px) x (height = 500px) の画像を合計で変数x(エックス)枚並べるとします。

width,heightは縦横比固定ですが、縮小は可能で、縮小率sは初期値1.0で、widthとheightを2%ずつ縮ませる場合、縮小率はs=0.98%とします。

例えば、x=999枚の画像をこのキャンバスの中に並べるとしたら、横に何枚(変数n)、縦に何行(変数m)ずつ並べて縮小率sを何%とすると、最も効率良く、なるべく画像のサイズを大きく保ったまま並べられるのかというのをプログラミングで求めたいです。

関数に与える引数は、widht,heightとxで、求めたい戻り値はsとnとmです。  
どうやったら良い感じに求められるでしょうか...?

[![画像の説明をここに入力](https://i.stack.imgur.com/9k4iQ.png)](https://i.stack.imgur.com/9k4iQ.png)

[code]

    def return_s_and_nm(width,height,x):
       width_all = 5000
       height_all = 5000
       s = 1.0
       n = 1
       m = 1
       
       return s,n,m
    
    width = 300
    height = 500
    x = 999
    s,n,m = return_s_and_nm(width ,height,x)
    
[/code]


CC BY-SA 4.0
2021-08-24T07:47:58.810
81010
2021-08-24T13:18:27.293
2021-08-24T13:18:27.293
34471
34471
question
python アルゴリズム
画像を左詰めて並べていくアルゴリズムを作るにはどうしたら良いか


実用的な観点でいえば、今の制約ならnやmの値を総当たりで試すとか縮小後のサイズを総当たりで試しても何の問題もないと思います。

もっと大きなサイズが現れるような場合でも計算可能な方法であれば、次のように考えられます。

縮小率sさえ決めてしまえば、nとmは計算できます。なのでsを求めることだけ考えればいいです。  
縮小率の性質として、最大縮小率sと比べてそれより小さい縮小率ではx枚置くことができ、より大きい縮小率ではx枚置くことはできません。

このような単調性のある問題については二分探索が使えます。

[code]

    min = 0.0
    max = 1.0
    for _ in range(60):
        mid = (min + max) / 2
        n, m を縮小率midで計算
        if n * m >= x: #縮小率midでx枚置くことができる
            min = mid
        else:
            max = mid
    
[/code]

つまり、このようなコードで十分な精度でsが特定できます。

少し解説を加えると  
ループの中で、`min <= mid <= max`を満たしています。  
minが縮小率midでx枚置くことができる場合にmidで更新されるので、置けると確認された数の中で最大のものになっています。  
同様にmaxはx枚置くことができない数の中で最小のもの(もしくは1.0)になっています。

また浮動小数点の誤差を考えなければ、`(max - min) / 2 == mid - min == max - mid`
なので、ループが終わった段階で`max - min == 2^-60`になっています。  
minはx枚置くことができる縮小率で、maxはx枚置くことができない縮小率(もしくは1.0)なので、minは最大縮小率との誤差がせいぜい2^-60ということになります。

通常の用途であればこれで十分なはずですが誤差が気になるのであれば、ベストな縮小率では縦か横には隙間がないことを利用して縦や横に並べる枚数について二分探索することで理論上も誤差のない縮小率が求められます。


CC BY-SA 4.0
2021-08-24T10:22:18.793
81015
2021-08-24T10:22:18.793
33033
81010
answer