沒有矩形形成的矩形

Question

我正在解決這個問題，可以從N個單位長度的正方形形成多少個矩形。我遇到這個公式⌊3n/2⌋-1（n> 1），這是錯誤的公式。 任何人都可以解釋這個公式和給定的代碼。

#include<stdio.h> 
#include<math.h> 

int main() 
{ 
int i,j,n,cnt=0; 
scanf("%d",&n); 
int k= sqrt(n); 
for(i=1;i<=k;i++) 
    for(j=i+1;i*j<=n;j++) 
     cnt++; 
cnt+=k; 
printf("%d",cnt); 
return 0; 
} 

Answer 1

總的想法是要找到矩形的每一個可能的整數長度，和每一個可能的寬度對於每個高度，使得正方形的矩形中的總數目由N（*）

界

編號k = sqrt(N)是爲了擺脫冗餘檢查：如果寬度> k，則最大高度爲< k，反之亦然，這意味着通過對稱性，只需檢查寬度< = k，因爲這相當於檢查高度< = k代替。注意整數投下來。

如上所述，外部循環只計算每個可能的寬度。 內部循環計算每個可能的高度，使得寬度*高度< = N。索引i + 1用於避免每次計算1x1平方（假設它不被視爲矩形）。

當這些循環結合在一起時，將計算滿足條件（*）的每個可能的矩形。

看到這個職位爲什麼你的公式不起作用：https://math.stackexchange.com/questions/881386/number-of-possible-rectangles-from-at-most-n-identical-squares