39°

【蓝桥杯训练】第一天1250

1250

[蓝桥杯2015初赛]方程整数解

方程: a^2 + b^2 + c^2 = 1000
这个方程有正整数解吗?有:a,b,c=6,8,30 就是一组解。
求出 a^2 + b^2 + c^2 = n(1<=n<=10000)的所有解,解要保证c>=b>=a>=1。
输入
存在多组测试数据,每组测试数据一行包含一个正整数n(1<=n<=10000)
输出
如果无解则输出"No Solution"。
如果存在多解,每组解输出1行,输出格式:a b c,以一个空格分隔
按照a从小到大的顺序输出,如果a相同则按照b从小到大的顺序输出,如果a,b都相同则按照c从小到大的顺序输出。
样例输入 Copy
4
1000
样例输出 Copy
No Solution
6 8 30
10 18 24
提示
题目已改编。

注意

  1. C++中常规读入:
    while(cin>>a)
  2. c语言
  3. python:
    while True:

算法

  1. 明显最大数不超过 up = sqrt(n)
  2. 因为有c>=b>=a>=1,扫描时直接从上一个循环变量开始
  3. 用一个SF作为标志量

C++ v1.0 、python v1.0:直接用的以上算法,时间复杂度O(n^3)

python v2.0:

  1. 减少一个循环枚举,采用减法,时间复杂度O(n^2)

可以看出,速度有显著提升。

题解

C++ v1.0:

#include <iostream>
#include <cmath>
using namespace std;

void f(int n){ int SF = 0; int up = sqrt(n); for (int i = 1; i <= up; i++){ for (int j = i; j <= up; j++){ for (int k = j; k <= up; k++){ if (ii+jj+k*k == n){ SF = 1; cout<<i<<" "<<j<<" "<<k<<endl; } } }

}
if(SF == 0)
    cout&lt;&lt;"No Solution"&lt;&lt;endl;

}

int main() { int n; while(cin>>n){ f(n); } return 0; } /************************************************************** Problem: 1250 User: yanshanbei Language: C++ Result: 正确 Time:21 ms Memory:2084 kb ****************************************************************/

python v1.0:

from math import sqrt
def f(n):
    SF = 0
    up = int(sqrt(n))
    for i in range(1,up + 1):
        for j in range(i, up + 1):
            for k in range(j, up + 1):
                if i*i+j*j+k*k == n:
                    SF = 1
                    print(i,j,k)
    if SF == 0:
        print("No Solution")
while True:
    n = eval(input())
    f(n)

python v2.0:

from math import sqrt
def f(n):
    SF = 0
    up = int(sqrt(n))
    for i in range(1,up + 1):
        for j in range(i, up + 1):
            s = i*i + j*j
            if s >= n:
                break
            k = int(sqrt(n-s))
            if s+k*k == n and k>=j>=i>=1:
                    SF = 1
                    print(i,j,k)
    if SF == 0:
        print("No Solution")
while True:
    n = eval(input())
    f(n)

本文转载自博客园,原文链接:https://www.cnblogs.com/yanshanbei/p/12207672.html

全部评论: 0

    我有话说: