我正在尝试实现一个程序,该程序从用户读取一个正整数并输出2到userNum
之间的所有理想数字。它还输出2到userNum
之间的所有友好数字对。两个数字都必须在范围内。我为此很努力。
要求:
1)对AnalyzeDivisors
的调用必须一起保持theta(userNum)次。 2)函数void AnalyzeDivisors
必须采用以下参数int num, int& outCountDivs, int& outSumDivs
。 3)函数bool IsPerfect
必须采用以下参数int num
。
老实说,我不知道如何在该效率范围内执行此操作。目前,我可以通过将规则弯曲到IsPerfect函数的参数来确定范围内的所有理想数字,但是如何在不调用Analyze Dividors每次在主循环中for循环的无谓次数的情况下确定友好对?
任何帮助将不胜感激!代码如下:
主要
int main()
{
int userNum;
//Request number input from the user
cout << "Please input a positive integer num (>= 2): " << endl;
cin >> userNum;
for (int counter = 2; counter <= userNum; counter++)
{
//Set variables
int outCountDivs = 0, outSumDivs = 0, otherAmicablePair = 0;
bool perfectNum = false, isAmicablePair = false;
//Analyze dividors
AnalyzeDividors(counter, outCountDivs, outSumDivs);
//determine perfect num
perfectNum = IsPerfect(counter, outSumDivs);
if (perfectNum)
cout << endl << counter << IS_PERFECT_NUM;
}
return 0;
}
分析除数
void AnalyzeDividors(int num, int& outCountDivs, int& outSumDivs)
{
int divisorCounter;
for (divisorCounter = 1; divisorCounter <= sqrt(num); divisorCounter++)
{
if (num % divisorCounter == 0 && num / divisorCounter != divisorCounter && num / divisorCounter != num)
{
//both counter and num/divisorCounter
outSumDivs += divisorCounter + (num / divisorCounter);
outCountDivs += 2;
}
else if ((num % divisorCounter == 0 && num / divisorCounter == divisorCounter) || num/divisorCounter == num)
{
//Just divisorCounter
outSumDivs += divisorCounter;
outCountDivs += 1;
}
}
}
是完美的
bool IsPerfect(int userNum, int outSumDivs)
{
if (userNum == outSumDivs)
return true;
else
return false;
}
最佳答案
我想我找到了符合要求的解决方案。我通过在地图中存储每个数字和除数的总和来找到友好的数字。如果在地图中输入了除数的总和,并且除数的总和是当前数字,则它们是友好的。
因为每次都会保存结果,所以每个号码只呼叫AnalyzeDivisors
一次。
请原谅惰性变量命名。
#include <iostream>
#include <map>
#include <cmath>
void AnalyzeDivisors(int num, int& divc, int &divs)
{
divc = 1;
divs = 1;
for (int x = 2, y = std::sqrt(num); x <= y; ++x)
{
if (num % x == 0)
{
++divc;
divs += x;
if (num / x != x)
{
++divc;
divs += num / x;
}
}
}
}
bool IsPerfect(int num)
{
static std::map<int, int> amicable;
int divc = 0, divs = 0;
AnalyzeDivisors(num, divc, divs);
if (amicable.find(divs) != amicable.end() && amicable[divs] == num)
std::cout << num << " and " << divs << " are best bros for life.\n";
amicable[num] = divs;
return num == divs;
}
int main()
{
int num;
std::cout << "Pick a number: ";
std::cin >> num;
for (int x = 2; x < num; ++x)
{
if (IsPerfect(x))
std::cout << x << " is perfect in every way!\n";
}
}
关于c++ - 确定Theta(n)范围内的友好对,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/42429577/