我必须编写一个递归函数来检查两个相同大小的给定数组是否具有相同的元素,但它们可能顺序不同。
我认为最优雅的解决方案是对两个数组进行排序,然后比较每个元素,但我不知道如何在一个递归函数中对两个阵列进行排序。
所以我有另一个想法,使用线性搜索,获取数组1的最后一个元素并在数组2中搜索它,如果它在那里,使用移位函数,移动该元素前面的所有元素(在数组2中)并返回true,如果没有找到它,则返回false。这将经历所有级别的递归。
但它不起作用,我在调试器中看到数组在满足递归的停止条件很久之后很久突然成为1个元素。
据我所知,不将数组作为指针传递是不明智的,但是这能解决这个问题吗?到底是怎么做到的?
这是有据可查的代码:
注意:我不能使用库函数。
#include <iostream>
using namespace std;
bool sameelem(int A1[], int A2[], int len);
void shiftback(int a[], int len, int i);
bool lsearchandshift(int a[], int len, int key);
void main()
{
int arr[7] = { 1, -2, 3, 4, -1, 6, -7 };
int arr2[7] = { 1, -2, 3, 3, -1, 6, -7 };
cout << sameelem(arr, arr2, 7);
}
bool sameelem(int A1[], int A2[], int len){
///pick an element from arr1, if it appears in arr2 cut both out using shiftback
///if it doesn't appear rerturn false, false should go thorugh all levels till the end
//end: if true check last two elements, if false return false
if (size==0)return true;
else{
sameelem(Arr1, Arr2, len - 1);
return (lsearchandshift(Arr2, size, Arr1[size - 1]));//if the last element from Arr1 is in Arr2 this will be true
}
}
//linear search function, will return 0 if key isn't found, otherwise will 'kill' that element using shiftback function and return 1
bool lsearchandshift(int a[], int len, int key){
int i;
bool found = false;
for (i = 0; i < len && found==false; i++)//if found will turn true and stop searching
{
if (a[i] == key){
found = true;
shiftback(a, len, i);
}
}
return found;
}
//array shifting backward function
//len has to be logical size, array's physical size has to be larger than entered logical size
void shiftback(int a[], int len, int i){
//i is the index which will be moved one place forward to i+1 along with all the other elements
int j;
for (j = i; j < len; j++)
{
a[j] = a[j+1];
}
//return a[len-1];
}
拿这个给你参考:-
bool isSame(int *p, int *q, int n)
{
if( n == -1 )
return true;
if ( *p != *q )
return false;
else
isSame(++p, ++q, --n);
}
int main()
{
int arr1[] = {1,2,3,2,4,5};
int arr2[] = {2,1,5,2,3,4};
//check if two arrays have different number of elements...
//If yes then just jump past 4-5 lines...
std::sort(arr1, arr1 + sizeof(arr1)/sizeof(arr1[0])); <<< You can build your own
std::sort(arr2, arr2 + sizeof(arr2)/sizeof(arr2[0])); <<< sort.
if( isSame(arr1, arr2, 6) )
cout << "Arrays are same" << endl;
else
cout << "Arrays are different" << endl;
}
在这些算法中,首先对数组进行排序几乎总是比处理未排序的数组更好。另一个好处是,当您看到不匹配时,您就会停止进一步移动。
唯一调用自己的函数是haveSameElems
:
bool haveSameElems(int Arr1[], int Arr2[], int size)
{
///pick an element from arr1, if it appears in arr2 cut both out using shiftback
///if it doesn't appear rerturn false, false should go thorugh all levels till the end
//end: if true check last two elements, if false return false
if (size==0)return true;
else{
haveSameElems(Arr1, Arr2, size - 1);
return (lsearchandshift(Arr2, size, Arr1[size - 1]));//if the last element from Arr1 is \
in Arr2 this will be true
}
}
请注意,is不使用递归调用的返回值。因此递归调用可能返回<code>false</code>并且调用函数永远不会知道它。
您可以轻松解决此问题:
if(!haveSameElems(Arr1, Arr2, size - 1))
return(false);
这段代码和你编写它的方法还有很大的改进空间,但是这已经足够让你前进了。
我一直在努力学习SML NJ(standard ML New Jersey),我遇到了一个我理解为递归的函数,但我不太明白为什么这个函数会返回它的值。 功能: 我知道如果sum的值为0,那么将返回0。然而,我不明白第二部分是如何工作的。 测试函数: 我相信它应该计算如:sum n=(n(sum(n-1))),所以给定n=2,(2(sum(2-1))= 但是,给定n=4,(4(和(4-1))= 如果
问题内容: 我有一个我要为类创建的程序,该程序使用递归返回数组中所有整数的总和。到目前为止,这是我的程序: 但是,我相信我得到了三个都相关的错误,但是我不知道为什么它会找到一种null类型: 问题答案: 该解决方案比看起来简单,请尝试以下操作(假设数组的长度为非零): 这样称呼它:
正如标题所解释的,我有一个非常基本的编程问题,但我还没有找到。过滤掉所有(非常聪明的)“为了理解递归,你必须首先理解递归。”各种在线线程的回复我仍然不太明白。 当我们面对不知道自己不知道的事情时,我们可能会提出错误的问题或错误地提出正确的问题。我将分享我的“想法”。我的问题是希望有类似观点的人能够分享一些知识,帮助我打开递归灯泡! 以下是函数(语法用Swift编写): 我们将使用2和5作为参数:
本文向大家介绍深入理解python函数递归和生成器,包括了深入理解python函数递归和生成器的使用技巧和注意事项,需要的朋友参考一下 一、什么是递归 如果函数包含了对其自身的调用,该函数就是递归的。递归做为一种算法在程序设计语言中广泛应用,它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解,递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算,大大地减少了程序的代
问题 你想在一个函数中调用相同的函数。 解决方案 使用一个命名函数: ping = -> console.log "Pinged" setTimeout ping, 1000 若为未命名函数,则使用 @arguments.callee@: delay = 1000 setTimeout((-> console.log "Pinged" setTimeout arg
在函数内部,可以调用其他函数。如果一个函数在内部调用自身本身,这个函数就是递归函数。 举个例子,我们来计算阶乘n! = 1 x 2 x 3 x ... x n,用函数fact(n)表示,可以看出: fact(n) = n! = 1 x 2 x 3 x ... x (n-1) x n = (n-1)! x n = fact(n-1) x n 所以,fact(n)可以表示为n x fact(n-1),