Có bao nhiêu ô vuông có kích thước a × a có thể được đóng gói thành một vòng tròn bán kính R?Có bao nhiêu ô vuông có thể được đóng gói thành một vòng tròn?
Tôi không cần giải pháp. Tôi chỉ cần một số loại ý tưởng bắt đầu.
Tôi xin lỗi vì đã viết câu trả lời dài như vậy. Cách tiếp cận của tôi là bắt đầu với mức tối đa lý thuyết và mức tối thiểu được đảm bảo. Khi bạn tiếp cận vấn đề, bạn có thể sử dụng các giá trị này để xác định xem bạn sử dụng bất kỳ thuật toán nào tốt. Nếu bạn có thể nghĩ đến mức tối thiểu tốt hơn thì bạn có thể sử dụng nó để thay thế.
Chúng ta có thể xác định một giới hạn trên đối với vấn đề bằng cách đơn giản bằng cách sử dụng diện tích của vòng tròn
Upper Limit = floor((PI * (r pow 2))/(L * L))
đâu L là chiều rộng hoặc chiều cao của các hình vuông bạn đang đóng gói và r là bán kính của vòng tròn bạn đang đóng các ô vuông vào. Chúng tôi chắc chắn đây là giới hạn trên vì a) chúng tôi phải có số hộp rời rạc và b) chúng tôi không thể chiếm nhiều không gian hơn diện tích của vòng tròn. (Một bằng chứng chính thức sẽ làm việc ở đâu đó dọc theo các dòng giả định chúng tôi có thêm một hộp nữa, sau đó tổng diện tích của các hộp sẽ lớn hơn diện tích của hình tròn).
Vì vậy, với giới hạn trên trong tay, giờ đây chúng tôi có thể lấy bất kỳ giải pháp nào tồn tại cho tất cả các vòng kết nối và gọi đó là giải pháp tối thiểu.
Vì vậy, chúng ta hãy xem xét một giải pháp tồn tại cho tất cả các vòng kết nối bằng cách nhìn vào hình vuông lớn nhất mà chúng tôi có thể vừa với hình tròn.
Quảng trường lớn nhất bạn có thể phù hợp với bên trong vòng tròn có 4 điểm trên perimiter, và có chiều rộng và chiều dài của sqrt(2) * radius (bằng cách sử dụng định lý Pythagoras' và sử dụng bán kính cho độ dài của các cạnh ngắn hơn)
Vì vậy, điều đầu tiên chúng tôi lưu ý là nếu sqrt(2) * radius nhỏ hơn kích thước của hình vuông của bạn, thì bạn không thể phù hợp với bất kỳ hình vuông nào trong vòng tròn, bởi vì sau đó, đây là hình vuông lớn nhất bạn có thể vừa vặn.
Bây giờ chúng ta có thể thực hiện tính toán đơn giản để chia ô vuông lớn này thành lưới vuông bình thường bằng cách sử dụng L mà bạn đã chỉ định, sẽ cung cấp cho chúng tôi ít nhất một giải pháp cho vấn đề. Vì vậy, bạn có một mạng lưới sqaures bên trong hình vuông tối đa này. Số lượng các ô vuông bạn có thể phù hợp với một dãy này lưới này là
floor((sqrt(2) * radius)/ L)
Và như vậy giải pháp tối thiểu này khẳng định rằng bạn có thể có ít nhất
Lower Limit = floor((sqrt(2) * radius)/ L) pow 2
số ô vuông bên trong vòng tròn. Vì vậy, trong trường hợp bạn bị lạc, tất cả những gì tôi làm là lấy hình vuông lớn nhất tôi có thể vừa vặn trong vòng tròn và sau đó đóng bao nhiêu ô vuông vào một lưới bình thường bên trong, để cho tôi ít nhất một giải pháp.
Nếu bạn nhận được câu trả lời ở mức 0 cho giai đoạn này thì bạn không thể phù hợp với bất kỳ hình vuông nào trong vòng tròn.
Bây giờ được trang bị tối đa quan trọng và tối thiểu tuyệt đối, bạn có thể bắt đầu thử bất kỳ loại thuật toán heuristic nào bạn muốn cho hình vuông đóng gói. Một thuật toán đơn giản sẽ chỉ là chia vòng tròn thành các hàng và phù hợp với nhiều sqaures khi bạn có thể vào mỗi hàng. Sau đó, bạn có thể lấy mức tối thiểu này làm hướng dẫn để đảm bảo rằng bạn đã đưa ra giải pháp tốt hơn. Nếu bạn muốn chi tiêu nhiều sức mạnh xử lý tìm kiếm một giải pháp tốt hơn, bạn sử dụng lý thuyết như là một hướng dẫn cho cách gần bạn là tốt nhất lý thuyết.
Và nếu bạn quan tâm đến điều này, bạn có thể tính toán phần trăm tối đa và tối thiểu lý thuyết bao gồm thuật toán tối thiểu mà tôi đã cung cấp cho bạn. Hình vuông lớn nhất luôn luôn bao gồm một tỷ lệ cố định (pi/4 hoặc khoảng 78,5% diện tích bên trong của vòng tròn tôi nghĩ). Vì vậy, tối thiểu lý thuyết tối đa là 78,5% bao gồm. Và tối thiểu không nhỏ (nghĩa là không không) tối thiểu lý thuyết là khi bạn chỉ có thể vừa với 1 hình vuông bên trong hình vuông lớn nhất, xảy ra khi các ô vuông bạn đóng gói là 1 lớn hơn một nửa chiều rộng và chiều cao của ô vuông lớn nhất bạn có thể phù hợp trong vòng tròn. Về cơ bản, bạn chiếm hơn 25% hình vuông bên trong với 1 hình vuông được đóng gói, có nghĩa là bạn có được một khoảng gần đúng khoảng 20%
Cảm ơn bạn ..được chấp nhận là câu trả lời: D – Transcendental
Bạn có thể đóng bao nhiêu ô vuông tùy thích vào vòng tròn. Nếu bạn nghi ngờ câu lệnh này, vẽ một vòng tròn lớn trên một mảnh giấy, sau đó vẽ một hình vuông có chiều dài cạnh 10^(- 18) m bên trong nó, lặp lại. Khi bạn đến gần ranh giới của vòng tròn, bắt đầu vẽ hình vuông với chiều dài cạnh là 10^(- 21) m.
Vì vậy, bước đầu tiên của bạn phải là tinh chỉnh câu hỏi và nêu rõ vấn đề của bạn chính xác hơn.
Tôi nghĩ rằng "theo một chiều nào đó", có nghĩa là, với một chiều D, có bao nhiêu ô vuông D có thể đan thành một vòng tròn bán kính R. – yshavit
Tôi nghĩ High Performance Mark hoàn toàn nhận thức được điều đó và chỉ muốn troll một chút – hirschhornsalz
@drhirsch Hm, sẽ là một con troll khá ngớ ngẩn để nhận được câu hỏi khá rõ ràng và giả vờ là không. – yshavit
Chỉ cần một shot trong bóng tối sau một vài phút suy nghĩ ...
gì nếu bạn làm việc với một nửa vòng tròn và gấp đôi nó ở cuối. Tôi sẽ bắt đầu với một mạng lưới hình vuông có chiều dài đường kính và chiều rộng của bán kính, về cơ bản làm trống bán vòng tròn. Sau đó kiểm tra tất cả 4 góc của mỗi ô vuông và đảm bảo tọa độ của chúng nằm trong bán kính của hình tròn. Điều này tất nhiên sẽ yêu cầu bạn vẽ vòng tròn và hình vuông trên một số loại hệ tọa độ hoặc lưới.
Tôi hy vọng điều này có ý nghĩa ... Đó là trong đầu của tôi và nó có vẻ hơi khó để nói lên :)
EDIT: Sau khi vẽ nó ra, tôi nghĩ rằng phương pháp này sẽ làm việc với một chút tinh chỉnh. Tôi sẽ xếp hàng các ô vuông dọc theo đường kính, nhưng trượt cái đầu tiên xuống cho đến khi nó vừa khít. Đặt một cái tại chỗ và bắt đầu xếp các ô vuông bên cạnh nó cho đến khi chúng không còn phù hợp nữa. Di chuyển ra rìa của dòng này của hình vuông và lặp lại các bước tương tự cho đến khi hàng của bạn của hình vuông đạt bán kính.
Điều gì sẽ xảy ra nếu câu trả lời yêu cầu các ô vuông tồn tại trên đường kính (như trong bisect của hình vuông có đường kính) thay vì dọc theo nó? Giải pháp này không tính đến điều đó. – kylex
Rasterise vòng tròn bằng cách sử dụng một cái gì đó như midpoint circle algorithm. Số lượng pixel được lấp đầy là số ô vuông bạn có thể vừa với hình tròn. Tất nhiên, vì bạn không thực sự lấp đầy các pixel, chỉ cần đếm chúng, điều này sẽ mất thời gian tỷ lệ thuận với chu vi của vòng tròn, không phải khu vực của nó.
Bạn sẽ phải chọn bán kính để rasterisation cẩn thận, để bạn chỉ đếm các pixel nằm trong vòng tròn.
Chỉnh sửa: Điều này có thể không chính xác, vì có thể áp dụng bù trừ pixel phụ vào lưới có thể thay đổi kết quả. Tôi sẽ để lại câu trả lời ở đây vì nó có thể cung cấp một điểm khởi đầu hữu ích cho một giải pháp chính xác.
Tôi nghĩ có thể là do tính đối xứng của vấn đề, trường hợp subpixel thú vị duy nhất là "thậm chí" và "lẻ" dọc theo mỗi trục (tâm vòng tròn ở giữa hình vuông, hoặc ở cạnh hình vuông), vì vậy bạn chỉ có thể thử cả bốn. –
Hình vuông luôn có kích thước hai (2). Bạn không nên sử dụng thứ nguyên từ trong ngữ cảnh toán học nếu bạn có nghĩa là kích thước hoặc độ dài. – hirschhornsalz
Có thể xoay hình vuông không? Điều đó sẽ làm phức tạp thuật toán một cách đáng kể. – Tony
"Ngôn ngữ lập trình không quan trọng vì đây là vấn đề toán học nhiều hơn" → bỏ phiếu để đóng làm chủ đề. Thử hỏi trên [Exchange Stack Exchange] (http://math.stackexchange.com/). –