大佬救命

英俊男孩建坤

Python课老师出的题 实在是不会

There is a mathematical puzzle of the form 厂x + 厂y = 厂n. where x, y and n are all
positive integers. For example, if n = 8, x = 2 and y = 2 and if n = 666, x = 74 and y = 296. Given
n, the puzzle is to find the pair x and y, under the assumption that x<= y. It is possible to solve this
mathematically, just like solving for f(x) = 3x3-11x2+9x-2=0. However, we are here to use the
computer to systematically look for the answer for us, just like our way of solving for an equation
by searching for the root within an interval a and b. There is no answer for many values of n, e.g.
n = 17.
(a) Given an input of value of n, write the pseudo-code that will return a pair of values of x and y (x <= y) satisfying the puzzle 厂x + 厂y = 厂n.
Explain briefly your approach.

(b) Your pseudo-code may run fast to solve for n = 2009, with a possible pair x = 41 and y = 1476
(maybe x = 164, y = 1025 or x = 369 and y = 656). However, it is already running very slowly for
n = 2020923, and even much slower for n = 100151002. Redesign your pseudo-code without
solving the puzzle mathematically to make it run faster. In other words, try to search more
efficiently. You can assume the existence of a function iszero(v) that will return True if the
value v is technically zero (very close to zero) and False otherwise. Explain briefly how you
achieve the improvement in efficiency, i.e. running faster.



来个大佬解答一下吧 我快枯了。

昨非

帮你一把：


有一个数学难题，形式是厂x+厂y=厂n，其中x、y和n都是

正整数。例如，如果n=8，x=2和y=2，如果n=666，x=74和y=296。鉴于

n、 难题是在x<=y的假设下找到x和y对，这是可能的

数学上，就像求解f（x）=3x3-11x2+9x-2=0。但是，我们在这里使用

计算机系统地为我们寻找答案，就像我们求解方程的方法一样

通过在区间a和b内搜索根，许多n值都没有答案，例如。

n=17。

（a） 给定一个输入值n，编写一个伪代码，它将返回一对x和y（x<=y），满足谜题厂x+厂y=厂n。

简要说明你的方法。



（b） 您的伪代码可能运行得很快，可以求解n=2009，可能有一对x=41和y=1476

（可能x=164，y=1025或x=369和y=656）。然而，它已经运行得非常缓慢了

n=2020923，对于n=100151002则更慢。重新设计你的伪代码

用数学方法解决这个难题，使它运行得更快。换句话说，尝试搜索更多

效率高。可以假设存在一个函数为零（v），如果

值v在技术上是零（非常接近于零），否则为假。简要说明你

提高效率，即跑得更快。

英俊男孩建坤

昨非 发表于 2020-10-16 00:32
帮你一把：

亲爱的大佬 我题目还是看的懂主要是没有思路  不知道怎么进行下去

疾风怪盗

1. n=2009
   
2. result=[]
   
3. for y in range(n):
   
4.     for x in range(y):
   
5.         if pow(x,0.5)+pow(y,0.5)==pow(n,0.5):
   
6.             result.append((x,y))
   
7. print(result)

复制代码

最后那段重新设计代码，就不知道怎么弄了。。。。。。。。。。

wp231957

疾风怪盗 发表于 2020-10-16 01:28
最后那段重新设计代码，就不知道怎么弄了。。。。。。。。。。

不外乎  数值太大以后  需要更换算法

英俊男孩建坤

wp231957 发表于 2020-10-16 08:37
不外乎  数值太大以后  需要更换算法

大佬能教教怎么操作吗？

疾风怪盗

wp231957 发表于 2020-10-16 08:37
不外乎  数值太大以后  需要更换算法

我知道意思，所以就是没想到更好的算法了。。。。。。。。。

英俊男孩建坤

疾风怪盗 发表于 2020-10-16 01:28
最后那段重新设计代码，就不知道怎么弄了。。。。。。。。。。

大佬请问一下你这个怎么保证输出的时候x<=y? 并且x，y都是正整数

疾风怪盗

英俊男孩建坤 发表于 2020-10-16 10:47
大佬请问一下你这个怎么保证输出的时候x

1. for y in range(n):
   
2.     for x in range(y):

复制代码

这两句循环不都保证了么？range的起始是0开始，出来的都是整数，x的结束是y,那肯定小于y啊

zhaosiyu29

关于第二问，程序运行慢与循环次数多有直接关系。所以从两个角度去减少程序循环次数。
1. 由于x<=y，所以潜在y的最小值是跟x一样大时，这时y=n/4。所以对于y的循环从n//4开始到n-1结束。
2. 因为对于每个y，一般的想法是从1开始迭代一个x进去比较是不是能够等式成立。这里不如直接反过来想是不是能够直接计算这个x的值，然后判断x是否为整数。这样只用一句if判断就可以免去大量的循环迭代。
据此，代码如下：

1. import math as m
   
2. n=int(input('Input an n:'))
   
3. for y in range(n//4,n):
   
4.     x=n+y-2*m.sqrt(n*y)
   
5.     if x==int(x):
   
6.         print('x=%d, y=%d' % (x, y))

复制代码

Stubborn

首先，我们会关注一个区间 J-->K    他们满足这样的关系： J<  x,y < K  。
其次我们关注，如何从这个区间快速的搜索出 ，x,y满足题意的值。

由于这个区间是有序的，可以考虑二分，或者双指针！！

我就不做你那个题了，给个样例代码给你参考：

给定一个已按照升序排列的有序数组numbers和一个目标数target，找到两个数使得它们相加之和等于目标数。并返回该目标的索引。
这里有序数组对应上面的J到K区间，target对应n

二分法：：

1.     length = len(numbers)
   
2.     for index, value in enumerate(numbers):
   
3.         _ = index
   
4.         while _ < length:
   
5.             mid = (_ + length) >> 1
   
6.             number = numbers[mid]
   
7. 
   
8.             if number > target - value:
   
9.                 length = mid
   
10.             elif number < target - value:
    
11.                 _ = mid + 1
    
12.             else:
    
13.                 return [index + 1, mid + 1]

复制代码

双指针：

1. def double_pointer(numbers, target):
   
2.     # TODO {
   
3.     #      如果numbers[left] + numbers[right] > target，由于是已经排序好的。所以 right - 1。直到指针重叠
   
4.     #        反之 numbers[left] + numbers[right] < target,  left + 1 。
   
5.     #  }
   
6.     left, right = 0, len(numbers) - 1
   
7. 
   
8.     while numbers[left] + numbers[right] != target:
   
9.         if numbers[left] + numbers[right] > target:
   
10.             right -= 1
    
11.         else:
    
12.             left += 1
    
13. 
    
14.     return [left + 1, right + 1]

复制代码

不过更推荐你用数学的方式去解决问题~~

对N进行拆解 --> a * √z

a的集合 {m, n}--> m+n = a

x,y的集合={z*m^2 , z*n^2}

剔除掉不题意的x<=y

Stubborn

zhaosiyu29 发表于 2020-10-16 17:02
关于第二问，程序运行慢与循环次数多有直接关系。所以从两个角度去减少程序循环次数。
1. 由于x

n=2009，可能有一对x=41和y=1476   
这个案例，过不了

zhaosiyu29

Stubborn 发表于 2020-10-16 21:35
n=2009，可能有一对x=41和y=1476   
这个案例，过不了

运行了一下41和1476应该能循环到。因为对y是从小到大的排序，直到n为止。1476是y求得的最大结果。所以能被循环到。
不过你提到的数学拆解的方法应该效率不错的。一会儿试试。

Stubborn

zhaosiyu29 发表于 2020-10-16 22:51
运行了一下41和1476应该能循环到。因为对y是从小到大的排序，直到n为止。1476是y求得的最大结果。所以能 ...

没注意看，你循环的是y

塔利班

这个题感觉可以先把n分解下因数，比如x,y,n都包含t**2那就都约掉好了