arr and recursive func

**megazord** · 12-11-2009

Hi all,

I have and ass, and I can't reach the reqeirment:
"you are not allowed to change array; you are not allowed to use more than 2 additional (helper) functions(recursive and no recursive) that can be reached from findword.."

This is the ass description:
"Notice: Length[Sub-String] >= Length[word] – we allow other characters to appear between the appearances of letters of the word.
Example: arr = “do no good”, word = “dog”. The Sub-String “do no g” contains the word “dog” since the letters of ‘dog’ appear in same order in it.
Example: arr = “good is done”, word = “dog”. The array does not contain the word, since although all the letters of the word appear in the array, they don’t appear in correct order.

We say a letter in the sub-string “Matches” a letter in word if it is the same. A match is the assignment of every letter of the word to a specific letter in the sub-string.

Example: Consider again = “do no good”, word = “dog”. The Sub-String “do no g” can be matched in 2 ways:
1. “do no g”
2. “do no g”

Function Prototype:
int findWord(char arr[], char word[])"

I will be glad to hear even just ideas how (the#%@%#@) I implement this..

**laserlight** · 12-11-2009

One way is to loop over the substring and the word at the same time. If the current character in the substring matches the current character of the word, you advance the index to both the substring and the word, otherwise you just advance the index of the substring. If you reach past the end of the word before or at the same time as you reach past the end of the substring, then there is a match, otherwise there is no match.

If you are constrained to use recursion only, then you should implement this loop as recursion.

**megazord** · 12-11-2009

oh that was fast, thnx.

yes I have a restrictions to not use any loops (for,while) and no libery func except of printf, scanf and gets.

and I don't know how to overpass this restriction regarding this func:\
recursive implementation is not my strong ability

**laserlight** · 12-11-2009

Well, start by using recursion to print a string character by character.

**megazord** · 12-11-2009

here is my code for what you ask, did I did it ok?

Code:

int findWord(char arr[], char word[]){
      checkArray(char arr[],int length);
      checkArray(char arr[],int length);
}
void checkArray(char arr[],int length){
	if (arr[length]==0) return;
	checkArray(char arr[],int length+1);
	printf("%c",arr[length]);
	return;
}

**laserlight** · 12-11-2009

You might want to compile your code before asking

I managed to implement findWord using a single return statement, but that's just me trying to be funny. The idea that I used is that you are really just dealing with pointers to elements of the arrays here. So, concentrate on arr[0] and word[0]. Consider what happens if they are null characters. If not, consider what happens if you recursively call findWord(arr + 1, word).

**megazord** · 12-11-2009

I can't use pointers (*p,null etc).

opps..
here I compiled my code..
insted of printf i need to put if somewhere, I don't know where :/

Code:

#include <stdio.h>
#define INPUT_LEN 256


int findWord(char arr[], char word[]); 
void checkArray(char arr[],int length);


void main(){
	char word1[INPUT_LEN]={0},word2[INPUT_LEN]={0};

	printf("Enter first string:\n");
	gets(word1);
	printf("Enter second string:\n");
	gets(word2);
	printf("Output:\n");
	printf("%d\n\n",findWord(word1,word2));
}

int findWord(char arr[], char word[]){
      checkArray(arr, 0);
	  printf("\n");
      checkArray(word,0);
}
void checkArray(char arr[],int length){
	if (arr[length]==0) return;
	printf("%c",arr[length]);
	checkArray(arr,length+1);
	return;
}

**quzah** · 12-11-2009

Originally Posted by megazord

I can't use pointers (*p,null etc).

Code:

int findWord(char arr[], char word[]){

/facepalm

Quzah.

**megazord** · 12-12-2009

if it's a joke, i did'nt understand that :\

**megazord** · 12-12-2009

I try'd somthing...
but i you can see that it's not working very well 'cuse I'm running in the same time on both substring...

Code:

#include <stdio.h>
#define INPUT_LEN 256

int findWord(char arr[], char word[]);
int compareArray(char arr1[],char arr2[],int length);
char checkArray(char arr[],int length);

void main(){
	char word1[INPUT_LEN]={0},word2[INPUT_LEN]={0};

	printf("Enter first string:\n");
	gets(word1);
	printf("Enter second string:\n");
	gets(word2);
	printf("Output:\n");
	printf("%d\n\n",findWord(word1,word2));
}

int findWord(char arr[], char word[]){
    return compareArray(arr,word,0);
}
int compareArray(char arr1[],char arr2[],int length){
	if (arr1[length]==0||arr2[length]==0) return 0;
	if	(checkArray(arr1,length)==checkArray(arr1,length))
		return (compareArray(arr1,arr2,length+1)+1);
	else
		return (compareArray(arr1,arr2,length+1)+0);
}
char checkArray(char arr[],int length){
	if (arr[length]==0) return -1;
	return (arr[length]);
}

**megazord** · 12-12-2009

oh yhea!
I think I got it!
maybe someone will make me SQA :P

Code:

#include <stdio.h>
#define INPUT_LEN 256

int findWord(char arr[], char word[]);
int compareArray(char arr1[],char arr2[],int pos1,int pos2);
int checkArray(char arr[],int pos);

void main(){
	char word1[INPUT_LEN]={0},word2[INPUT_LEN]={0};

	printf("Enter first string:\n");
	gets(word1);
	printf("Enter second string:\n");
	gets(word2);
	printf("Output:\n");
	printf("%d\n\n",findWord(word1,word2));
}

int findWord(char arr[], char word[]){
	if (compareArray(arr,word,0,0)<checkArray(arr,0))
		return compareArray(arr,word,0,0);
	else 
		return 0;
}
int compareArray(char arr1[],char arr2[],int pos1, int pos2){
	if (arr1[pos1]==0||arr2[pos2]==0) return 0;
	if (arr1[pos1]== arr2[pos2])
		return (compareArray(arr1,arr2,pos1+1,pos2+1)+1);
	else
		return (compareArray(arr1,arr2,pos1+1,pos2)+1);
}
int checkArray(char arr[],int pos){
	if (arr[pos]==0) return 0;
	return (checkArray(arr,pos+1)+1);
}

**megazord** · 12-12-2009

I don't have it! :\
my program don't stad the:

"• Given i,j,k are the indices of 3 following matched letters, k-j =< 2 * (j-i)
o In other words- if the distance between 2 matched letters (a,b) is X, then the distance between (b,c) can’t be more than 2*X (‘c’ is the next matched letter after ‘b’).

Example: Consider once more = “do no good”, word = “dog”. We look again at the 2 possible matches we can do with the sub-string “do no g”:
1. “do no g” – this is a match, but not a legal match: the distance between the matched d and matched o is 1, and the distance between the matched o and matched g is 5, which is more than twice of the previous.
2. “do no g” – this is a legal match: all letters appear in-order, and the distances between the matched letters fits out requirements."

**megazord** · 12-13-2009

Someone? Plz help :\
I stayed all night trying to make it work! :\
but no luck.

if I enter substring "7778"
and 2nd substring "78", I get 0 and I need to get 2 (according to theirs program).
(it's one of 50% input that not working for my code :\)

someone plz help me out..

**EVOEx** · 12-13-2009

Originally Posted by megazord

Someone? Plz help :\
I stayed all night trying to make it work! :\
but no luck.

if I enter substring "7778"
and 2nd substring "78", I get 0 and I need to get 2 (according to theirs program).
(it's one of 50% input that not working for my code :\)

someone plz help me out..

You should learn how to use a debugger. It's not that difficult to find the bug with that. But okay, let me give you a hint where the bug is:

Code:

	if (arr1[pos1]==0||arr2[pos2]==0) return 0;

**megazord** · 12-13-2009

I will ignore yours degrading "tone", and explain this line:
if some of the substring is ended I need to finish the recursion function, so this is my STOP SIGEN.

I'm not a good C progammer (putting it mildly).. I'm working on this for 3 days allready and this is the best i got :/

I tryed to build an algorithem before I go programming, and I burn all the first day on it.
next I tryed to write something, and you can see on this thread the evolution of what I can program :\

Thread: arr and recursive func

Thread Tools

Search Thread

Display

arr and recursive func