得到X个整数,这些整数相乘可以得到接近Y的数
本文关键字:整数 接近 的数 得到 | 更新日期: 2023-09-27 18:09:45
这很难在标题中解释,但基本上我已经创建了一个系统,输入一些数字N并输出两个数字(不包括1和N),可以乘在一起尽可能接近N(超过而不是低于)。
下面是一些例子:
- 25→5 &5.
- 40→5 &8.
- 53→6 &9.
- 13→2 &7 .
我有一个方法Factor
,它返回X除1和X外的所有因子的列表。这段代码也不需要处理大数,所以我通过检查它是否在素数列表中来测试素数。
完成它的代码在这里:
if (primes.Contains(N))
N++;
List<int> facts = Factor(N);
double root = Math.Sqrt(N);
int cl1;
int cl2;
if (root == (int)root)
{
cl1 = (int)root;
cl2 = (int)root;
}
else if (N == 2)
{
cl1 = 1;
cl2 = 2;
}
else
{
cl1 = facts.Aggregate((x, y) => Math.Abs(x - root) < Math.Abs(y - root) ? x : y);
facts.Remove(cl1);
cl2 = facts.Aggregate((x, y) => Math.Abs(x - root) < Math.Abs(y - root) ? x : y);
}
什么是一个好的方法来概括它,使它可以给出三个输出,或者四个,五个或九个?(显然我会用数组交换cl1
和cl2
,但我的意思是代码明智)
获取N的所有因子是一个相当昂贵的操作。实际上这样做会更快(伪代码):
For p = floor(sqrt(N)); p>1; --p:
q = ceil(N/p);
error = p*q-N; //always positive
record=make_tuple(p,q,error);
//... remember the records with the smallest error
维护记录列表的最佳方式取决于您需要多少记录。叫那个号码m
如果只有几个,那么你可以把它们放在一个列表中,当列表大小达到2M时,按错误排序并截断为m。
如果有很多,那么首先将它们放在错误最大的优先队列中,当大小>M时,删除错误最大的队列。最后,您可以将它们以相反的顺序拉出来并向后填充输出数组