gpt4 book ai didi

arrays - 给定一个数 N 和一个已排序的数组 A,检查 A 中是否有两个数的乘积为 N

转载 作者:行者123 更新时间:2023-12-04 13:26:36 26 4
gpt4 key购买 nike

给定一个数字 N和一个排序数组 A , 设计算法 - 使用 分而治之方法 - 检查是否存在索引 i 和索引 j 使得 A[i]*A[j] == N (如果存在则返回 1,否则返回 0)。
我很难以所需的(递归)方式进行。我想我只找到了一个可能解决方案的一部分,但即使在那里我也不能 100% 确定它是否正确:我认为如果数组的第一个元素和中心元素之间的乘积大于 N,那么我正在寻找的数字(如果存在)肯定在数组的前半部分,所以我可以递归调用该部分的函数,就像这样(我使用的是 C):

int productN(int A[], int i, int j, int N){

// missing base case

int m = (i+j)/2;

if(A[i]*A[m] > N){
return productN(A, i, m, N);
} else{
// do something else
}
}
int main(){

int A[]={1, 2, 3, 4, 5};
printf("%d\n", productN(A, 0, 4, 15)); // initial value for i and j are the first and last index of the array

return 0;

}
除此之外,我被卡住了,我什至想不出一个基本案例,所以任何帮助将不胜感激,谢谢。
编辑:
根据您非常有用的答案,使用二进制搜索,我想我明白了:
int productN(int A[], int i, int j, int N){

int m = (i+j)/2; // central element of the current array

int x;
for(x=i; x<=m; x++){
if(N%A[x]==0 && binarySearch(A, m, j, N/A[x]))
return 1;
}

if(i!=j){
if(productN(A, i, m, N) || productN(A, m+1, j, N))
return 1;
}

return 0;

}
好吗?可以更好吗?
编辑:我问这个问题已经有一段时间了,但我写了另一个解决方案,更容易阅读。如果有人感兴趣,我会把它留在这里。
int productN(int A[], int i, int j, int N, int size){

if(i==j){ // base case
if(N%A[i]==0)
return binarySearch(A, 0, size-1, N/A[i]);
else
return 0;
}

int m = (i+j)/2;

if((N%A[m])==0){
if(binarySearch(A, 0, size-1, N/A[i]))
return 1;
}

return productN(A, i, m, N, size) || productN(A, m+1, j, N, size);

}

最佳答案

使用分而治之,您可以使用类似于归并排序算法的方法。正如评论所暗示的那样,有更简单的方法。但如果分而治之是必须的,这应该就足够了。
(我不精通C,所以我只会写算法)

def productN(arr):
x = len(arr)
left_half = arr[0:x/2]
right_half = arr[x/2:]
if productN(left_half) or productN(right_half):
return True
for i in left_half:
if N%i==0 and binary_search(right_half, N/i):
return True
return False

关于arrays - 给定一个数 N 和一个已排序的数组 A,检查 A 中是否有两个数的乘积为 N,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/68091499/

26 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com