1.1.1.?完全平方數(shù)（PerfectSquare）
判斷正整數(shù)y是否是完全平方數(shù)。如果能找到正整數(shù)x，使得x*x==y，則y是平方數(shù)。
1.?思路
|
條件 |
處理 |
|
x*x>y |
丟棄右半部分 |
|
x*x==y |
y是完全平方數(shù) |
|
x*x<y |
丟棄左半部分 |
x的取值范圍是[1,y]，我們用左閉右開空間，就是[1,y+1)。
注意：計(jì)算過程要注意溢出。
擴(kuò)展：如果y是自然數(shù)呢？y可以為0。
?文章來源地址http://www.zghlxwxcb.cn/news/detail-546275.html
代碼
?
#include <iostream>
#include <vector>
bool IsPerfectSquare(int y )
{
int left = 1, right = y + 1;
while (right - left > 1)
{
int x = left + (right - left) / 2;
if (x * x == y)
{
return true;
}
else if (x * x > y)
{
right = x;
}
else
{
left = x;
}
}
return left * left == y;
}
int main()
{
std::vector<int> v;
for (int i = 1; i < 1000; i++)
{
if (IsPerfectSquare(i))
{
v.emplace_back(i);
}
}
for (const auto& n : v)
{
std::cout << n << " ";
}
}
1.1.1.?排列箱子
有n個箱子，求可以排列多少行（包括不完整行）。第一行1個箱子，第二行2個箱子...第i行i個箱子。注意：最后一行可能沒滿，除最后一行外其他行全滿。
1.?解題思路
m行排滿，共有maxN= m*(1+m)/2個箱子。
m行只排一個，共有minN = maxN-m+1個箱子。
如果n小于minN，則拋棄右邊；
如果n大于maxN，則拋棄左邊。
邊界[1,n]，左閉右開空間是[1,n+1)
?
代碼
?
#include <iostream>
#include <assert.h>
?
int BoxLeve(int n)
{
int left = 1, right = n + 1;
while (right - left > 1)
{
int mid = left + (right - left) / 2;
int maxN = (1 + mid)* mid / 2;
int minN = maxN - mid + 1;
if (n < minN)
{
right = mid;
}
else if (n > maxN)
{
left = mid;
}
else
{
return mid;
}
}
return left;
}
int main()
{
assert(1 == BoxLeve(1));
assert(3 == BoxLeve(4));
assert(3 == BoxLeve(5));
assert(3 == BoxLeve(6));
assert(4 == BoxLeve(7));
assert(4 == BoxLeve(10));
//assert(51 == BoxLeve(11));
}
?
?
文章來源：http://www.zghlxwxcb.cn/news/detail-546275.html
?
到了這里，關(guān)于判斷是否是完全平方數(shù)[容易]和排列箱子[容易]的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
