z*********8
发帖数: 332 | 1 问个题目： 从1-n 中找出k, 使得 k=a^2 +b^2 (a b 为整数）
有好的算法吗？ |
p*****2
发帖数: 21240 | 2
a,b是啥东西呀？任意整数？a，b可以重复吗？
【在 z*********8 的大作中提到】
: 问个题目： 从1-n 中找出k, 使得 k=a^2 +b^2 (a b 为整数）
: 有好的算法吗？
|
z*********8
发帖数: 332 | |
c*******7
发帖数: 438 | 4 筛法，a，b从1到sqrt(n)算出所有可能的结果 |
z*********8
发帖数: 332 | |
z*********8
发帖数: 332 | 6 public class Find_A_K
{
public static void findK(int n) {
List result = new ArrayList();
for (int k = 1; k <= n; k++)
{
for (int i = 1; i <= Math.sqrt(k); i++)
for (int j = 1; j <= Math.sqrt(k); j++) {
if ((i * i + j * j) == k)
{
if(!result.contains(k))
result.add(k);
}
}
}
for(int i = 0; i
{
System.out.println(result.get(i));
}
}
这样子对吗？ 时间复杂度 是 n^3 ? |
p*****2
发帖数: 21240 | 7
(defn find-k [n]
(let [s (int (Math/sqrt n))]
(distinct
(for [a (range 1 (inc s))
b (range a (inc s))
:let [c (+ (* a a) (* b b))]
:when (<= c n)]
c))))
【在 z*********8 的大作中提到】
: public class Find_A_K
: {
: public static void findK(int n) {
: List result = new ArrayList();
: for (int k = 1; k <= n; k++)
: {
: for (int i = 1; i <= Math.sqrt(k); i++)
: for (int j = 1; j <= Math.sqrt(k); j++) {
: if ((i * i + j * j) == k)
: {
|
e*******o
发帖数: 4654 | 8 没去重吧。
【在 p*****2 的大作中提到】
:
: (defn find-k [n]
: (let [s (int (Math/sqrt n))]
: (distinct
: (for [a (range 1 (inc s))
: b (range a (inc s))
: :let [c (+ (* a a) (* b b))]
: :when (<= c n)]
: c))))
|
l*****a
发帖数: 14598 | 9 if ((i * i + j * j) == k)
<=n就可以了
少一重循环
【在 z*********8 的大作中提到】
: public class Find_A_K
: {
: public static void findK(int n) {
: List result = new ArrayList();
: for (int k = 1; k <= n; k++)
: {
: for (int i = 1; i <= Math.sqrt(k); i++)
: for (int j = 1; j <= Math.sqrt(k); j++) {
: if ((i * i + j * j) == k)
: {
|
l*****a
发帖数: 14598 | 10 注意他的循环初始条件
【在 e*******o 的大作中提到】
: 没去重吧。
|
|
|
z*********8
发帖数: 332 | 11 update:
public class Find_A_K
{
public static void findK(int n)
{
List result = new ArrayList();
for (int i = 1; i <= Math.sqrt(n); i++)
{ for (int j = 1; j <= Math.sqrt(n); j++)
{
int mul = i*i + j*j;
if (mul <= n)
{
if(!result.contains(mul))
result.add(mul);
}
}
}
for(int k = 0; k
{
System.out.println(result.get(k));
}
} |
s**x
发帖数: 7506 | 12 something I am missing.
k = a^2 + b^2, what else do you need to do? there will be only one K.
if k is given, find a and b, which may make more sense. |
e*******o
发帖数: 4654 | 13 假设 b >= a , 参考二爷的程序。
最后去重，你一个一个的检验多费功夫。
去重不可少的
5,5,50
1,7,50
【在 z*********8 的大作中提到】
: update:
: public class Find_A_K
: {
: public static void findK(int n)
: {
: List result = new ArrayList();
: for (int i = 1; i <= Math.sqrt(n); i++)
:
: { for (int j = 1; j <= Math.sqrt(n); j++)
: {
|
a***s
发帖数: 206 | 14 你们以上的搜索都是brute force没有注意到数字的特殊性。
当 a + b = c 时而且a,b,c都是正整数，
a^2 + b^2 <= c^2 是永远成立的。
所以搜索的范围可以减小。只需要从两个数的和大于等于sqrt(k),并且两个数都比sqrt
(k)小，里面找就行了。在利用对称性又可以进一步减少搜索的范围。
edit:
另外如果k是偶数，两个数必须同时是奇数或偶数
如果k是奇数，两个数必须一个是奇数一个偶数 |
p*****2
发帖数: 21240 | 15
确实有问题。fix了。
【在 e*******o 的大作中提到】
: 假设 b >= a , 参考二爷的程序。
: 最后去重，你一个一个的检验多费功夫。
: 去重不可少的
: 5,5,50
: 1,7,50
|
T******e
发帖数: 157 | 16 用一个min heap，每次把a，b的组合压进去，取出的时候每次都能保证顶部的值都是最
小，对于取出的组合，如果a和b相等就把(a，b+1)压入heap，否则压入(a+1,b)和(a,b+
1)（因为a和b是对称的，所以我们每次都要保证一个数不能比另一个数小，否则会有重
复） |
m********e
发帖数: 170 | 17 public static void findSquareSum(int n)
{
for(int a = 1, lenA = (int) Math.ceil(Math.sqrt(n)); a < lenA ; a++)
for (int b = 1, lenB = (int) Math.sqrt(n - a * a); b <= lenB && b <= a;
b ++)
System.out.println("a : " + a + ", b : " + b + " -> " + (a*a + b*b));
} |
b****f
发帖数: 138 | |
p*****3
发帖数: 488 | 19
可以把找a^2 + b^2 = k的双重循环改成单循环吗
比如找 k = 41
1, 2, 3, 4, 5, 6
1^2 + 6^2 = 37 < 41, left++
2^2 + 6^2 = 40 < 41, left++
3^2 + 6^2 = 45 > 41, right--
3^2 + 5^2 = 34 < 41, left++
4^2 + 5^2 = 41 return
【在 p*****2 的大作中提到】
:
: 确实有问题。fix了。
|
b*****o
发帖数: 72 | 20 应该是给定k求a，b吧？？
★ 发自iPhone App: ChineseWeb 8.6
【在 z*********8 的大作中提到】
: 问个题目： 从1-n 中找出k, 使得 k=a^2 +b^2 (a b 为整数）
: 有好的算法吗？
|
