java - 输入一个整数，输出一个a边和b边相差最小的矩形

Question

有人可以对这个问题有想法或代码实现吗？多谢!这不是家庭作业。

给定一个整数，写一个函数foo(int area)，这个函数应该返回一个矩形，这个矩形在a和b的两条边上的差值最小，而且a*b必须大于area小于or等于(面积 + 2)。

Answer 1

好吧，如果你没有大面积(如果输入“int”那么是)，复杂度为 O(sqrt(n)) 的解决方案对你来说已经足够了。然后你可以使用愚蠢的解决方案。

#include "math.h"

void foo(int area)
{
    long a = (long)sqrt(area + 2);
    while ((area + 1)  % a != 0 && (area + 2) % a != 0) a--;
    long total_area = ((area + 1) % a == 0) ? (area + 1) : (area + 2);
    long b = total_area / a;
    printf("%ld = %ld X %ld", total_area, a, b);
}

此任务的复杂度为 O(N^(1/2))。即使对于 long 类型，这也足够了。如果您要长期寻找解决方案。然后你需要使用更复杂的算法:

1. 使用快速因式分解法得到所有质因数的数组。
2. 使用动态规划解决标准任务。 Concat 数组用于两部分，因此所有部分的总积应尽可能接近。