Longest Index

This is a discussion on Longest Index within the C Programming forums, part of the General Programming Boards category; I have a second Q. this time I wroth somthing, and it's working! but again I can't reach the reqeirment: ...

  1. #1
    Registered User
    Join Date
    Nov 2009
    Posts
    27

    Longest Index

    I have a second Q.
    this time I wroth somthing, and it's working!
    but again I can't reach the reqeirment:
    "you are not allowed to change array; you are not allowed to use more than 1 additional (helper) functions(recursive and no recursive) that can be reached from longestIndex."

    This is the ass description:
    "Example: Consider arr={0,5,1,1,2}. Indices 0,2 and 3 are well-placed:
    • Index 0 is well-placed since P0=0.
    • Index 1 is not well-placed, since P1=5>1. Since all elements are positive, it’s impossible to find a sequence starting at index 1 that can be summed to 1.
    • Index 2 is well-placed since P2+P3= 2.
    • Index 3 is well-placed, since P3 + P4 = 3.
    • Index 4 is not well-placed: We can’t find a sequence starting at index that can be summed to 4 – that’s because P4 is the last element in the array, and it’s only 2.

    We define ‘well-placed length’ of a well-placed index to be j-i+1 – The length of the sequence that when summed shows that the index is well placed. It is possible an index is well-placed with more than a single sequence of elements. The ‘well-placed length’ in that case is the maximal length of the various sequences defining the index as ‘well-placed’.

    "Example: Looking at previous example:
    • Index 0 well-placed length is 1 (i=0, j=0, j-i+1 = 1).
    • Index 2 well-placed length is 2 (i=2, j=3, j-i+1 = 2).
    • Index 3 well-placed length is 2 (i=3, j=4, j-i+1 = 2).
    • For indices 1 and 4, well-placed length is not defined, since the indices are not well-placed.
    • Consider arr= {0,5,1,1,2,0} – index 3 well-placed length is now 3 (i=3, j=5, j-i+1=3). Another sequence that defines index 3 as well-placed is (i=3, j=4, j-i+1=2) as before, but we’ve defined well-placed length to be the maximal value for the index.


    Function Prototype:
    int longestIndex(int arr[], int length)[])"

    my code is:
    Code:
    #include <stdio.h>
    #define INPUT_LEN 256
    
    int longestIndex(int arr[], int length);
    void scan2(int arr[] ,int length, int beginLength);
    int count(int arr[],int length,int beginLength, int sum ,int i,int biggestSum ,int chekIndex);
    int chekZero(int arr[] , int length ,int place , int zeroCount);
    
    
    void main(){
    
    	int	 length;
    	int  arr[INPUT_LEN];
    
    	printf("Enter the length:\n");
    	scanf("%d",&length);
    	printf("Enter the array:\n");
    	scan2(arr,length,0);
    	printf("Output:\n");
    	printf("%d\n\n",longestIndex(arr,length));
    }
    //Help Input recurcive func.
    void scan2(int arr[] ,int length , int beginLength){
    	if (beginLength > length-1) return;
    	scanf("%d",&arr[beginLength]);
    	scan2(arr,length,beginLength+1);
    	return;
    }
    
    int longestIndex(int arr[], int length){
    	return(count(arr,length,0,0,0,0,0));
    }
    
    int count(int arr[],int length,int beginLength, int sum ,int i,int biggestSum,int chekIndex){ 
    	if (beginLength > length) return(biggestSum); 
    	i++;
    	sum += arr[beginLength];
    	if (sum == chekIndex){
    		if (biggestSum < i) 
    			biggestSum = i;
    			biggestSum += chekZero(arr,length,beginLength+1,0);
    			beginLength = chekIndex; 
    		return(count(arr,length,beginLength+1,0,0,biggestSum,chekIndex+1));
    	}
    	if (sum > chekIndex){
    		beginLength = chekIndex;
    		return(count(arr,length,beginLength+1,0,0,biggestSum,chekIndex+1));
    	}
    	if (sum < chekIndex){			
    	return(count(arr,length,beginLength+1,sum,i,biggestSum,chekIndex));
    	}
     return 0;		
    }
    
    int chekZero(int arr[] , int length ,int place , int zeroCount){
    	if (place > length) return (zeroCount);
    	if (arr[place] != 0) return (zeroCount);
    	else{
    		zeroCount++;
    		return(chekZero(arr,length,place+1,zeroCount));
    	}
    }
    I need some how to merge between count to chekZero, to stand the reqeirment.

  2. #2
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by megazord View Post
    I need some how to merge between count to chekZero, to stand the reqeirment.
    Shouldn't be too hard, you only call it once. Basically, you want to put the return value:
    Code:
    biggestSum +=
    inside the an if/else block starting with:
    Code:
    if (place > length)
    Of course, you will need to use iteration instead of recursion. Something like:
    Code:
    for (i=beginLength+1; i<=length; i++) {
         if (arr[place] != 0) break;
         biggestSum+=1;
    }
    Pretty stupid of your prof to encourage people to do that, since it is a far better practice to write shorter specific functions, for a bunch of reasons:

    1) avoids duplication of code
    2) simplifies debugging and optimizing
    3) is more versatile

    However, there is the possibly unnecessary expense of constructing a new stack, especially if you are just passing arguments straight thru like this (length, beginLength, array). That is a serious factor with recursion, and that's why iteration is almost always more efficient. Everytime that function calls itself a new stack must be built!

    So maybe I'll concur with your prof's mental engineering after all. Recursion seems "clever" but don't fall in love with it for that: it is usually NOT a good method.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  3. #3
    Registered User
    Join Date
    Nov 2009
    Posts
    27
    This ass, is for practice recursion method.
    so it's forbidden to use loops (for,while etc)

  4. #4
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    You should be able to combine longestIndex() and count() then I think, which gets rid of one function.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. how to combine these working parts??
    By transgalactic2 in forum C Programming
    Replies: 0
    Last Post: 02-01-2009, 07:19 AM
  2. 20q game problems
    By Nexus-ZERO in forum C Programming
    Replies: 24
    Last Post: 12-17-2008, 04:48 PM
  3. Reiventing the wheel (again)
    By Elysia in forum C++ Programming
    Replies: 5
    Last Post: 12-02-2007, 02:26 AM
  4. Function to check memory left from malloc and free?
    By Lechx in forum C Programming
    Replies: 4
    Last Post: 04-24-2006, 05:45 AM
  5. file index update error
    By daluu in forum C Programming
    Replies: 1
    Last Post: 04-28-2003, 02:47 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21