Title_View_Question

Mathematics


计算数学 >> 数据结构
Questions in category: 数据结构 (Data Structure).

1

一维装球问题(one-dimensional circle packing problem)

Posted by haifeng on 2018-05-15 17:09:29 last update 2018-05-15 18:21:52 | Answers (0) | 收藏

一维装球问题:

有 $N$ 个半径分别是 $r_1,r_2,\ldots,r_N$ 的圆盘(比如光盘). 将这些圆盘装到一个盒子中使得每个圆盘都与盒子的底边相切. 任何两个圆盘至多有一个公共点.

问这个盒子的底边长度最小是多少?

假设底边最短长是 $f(r_1,r_2,\ldots,r_N)$.

 

 

 

 

 

 

 

 

 

 

 

 

记 $h(x,y)=2\sqrt{xy}$.

Exer. 不妨假设 $r_1\leqslant r_2\leqslant r_3$.  记

\[
d=\max\{h(r_1,r_2)+h(r_1,r_3),\ h(r_2,r_3)\},
\]

证明

\[
f(r_1,r_2,r_3)=\max\{r_2+d, r_3\}+r_3.
\]

 

 

Q.  $f(r_1,r_2,r_3,r_4)=?$

 


 

如果圆盘的排放是按原有顺序的, 若记 $\varphi_n(r_1,r_2,\ldots,r_n)$ 为排放这 $n$ 个圆盘的盒子底边的最短长度, 对于依次输入的 $r_1,r_2,\ldots,r_k$, 请编程依次输出 $\varphi_k$ 值.

 

 

 


References:

Mark Allen Weiss, Data Structures and Algorithm Analysis in C++, Third Edition.

张怀勇 等译. Ex. 10.46, P.348

 


相关问题:

Circle packing in a circle

https://en.wikipedia.org/wiki/Circle_packing_in_a_circle




Search

New posted more ...