Recursion Revisited again, and again!

This is a discussion on Recursion Revisited again, and again! within the C++ Programming forums, part of the General Programming Boards category; I'll crack it when I get home, don't you worry. I'll do it whether or not you need it So ...

  1. #76
    C++まいる!Cをこわせ! Elysia's Avatar
    Join Date
    Oct 2007
    Posts
    22,179
    I'll crack it when I get home, don't you worry. I'll do it whether or not you need it
    So check back later when I've cracked it open.
    Meh, unless someone else does it before me.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.
    For information on how to enable C++11 on your compiler, look here.
    よく聞くがいい!私は天才だからね! ^_^

  2. #77
    Registered User
    Join Date
    Sep 2007
    Location
    Arizona
    Posts
    164
    Ok Thanks!
    I think I have to sleep a little my eyes are slamming shut and I have downed a gallon of coffee! I must be tired!

  3. #78
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    I haven't tested it, but I suspect you may need to make this:
    Code:
    	if(first >= last)
    		return -1;
    into
    Code:
    	if(first > last)
    		return -1;
    Otherwise, it will not ever search the first & last positions.

    I'm only guessing tho'.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  4. #79
    Registered User
    Join Date
    Sep 2007
    Location
    Arizona
    Posts
    164
    I think I may have found it!!!
    I removed the '=' from the code:
    Code:
    //Function written for Test 5 Question 22
    template<class elemType> 
    int orderedArrayListType<elemType>::binarySearchImpl(const elemType& item, int first, int last)
    {
    	
    	if(first > last)           //REMOVED '=' from this statement and I think that fixed it.
    		return -1;
    	int mid = (first + last) / 2;
    	if(list[mid] == item)
    		   return mid;
    	if (list[mid] > item)
    		return binarySearchImpl(item, first, mid - 1);
        else
    		return binarySearchImpl(item, mid + 1, last);
    }//end binarySearch
    
    template<class elemType>
    int orderedArrayListType<elemType>::seqSearch(const elemType& item)
    {	
    	for (int loc = 0; loc < length; loc++)
    		if (list[loc] == item)
    			return loc;
    	return -1;
    }//end seqSearch on ordered list
    I haven't checked it completely, but the first few seem to work!
    We'll see tomorrow. I have to sleep now.
    Cindy

  5. #80
    C++まいる!Cをこわせ! Elysia's Avatar
    Join Date
    Oct 2007
    Posts
    22,179
    From a guessing standpoint, I'm guessing it's a bug, but not THE bug since the elements looked for shouldn't in the last or first index.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.
    For information on how to enable C++11 on your compiler, look here.
    よく聞くがいい!私は天才だからね! ^_^

  6. #81
    Registered User
    Join Date
    Sep 2007
    Location
    Arizona
    Posts
    164
    Mats you are back! Hey!

    That is the second time this evening I have posted something at the same time you all were responding. (no I am not from the south)

    I messed around and remembered something similar to that is another program I had to do. And that fixed the problem with that code. I don't know if it fixes everything with this program, but it seems to have helped.
    THANKS!!!

  7. #82
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by Elysia View Post
    From a guessing standpoint, I'm guessing it's a bug, but not THE bug since the elements looked for shouldn't in the last or first index.
    But it also applies for middle elements where you end up with a "miss by one" on the next to final search - e.g. mid = 3, but we want element 4, and our previous search had a mid of -> last = 4. Next search will do "first = 4, last = 4" and exit with "not found", rather than check element 4.

    Again, it's my sloppy pseudo-code.

    [But it's all good debugging experience, even if that's not really what you may feel that you need this very moment, clegs!]

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  8. #83
    C++まいる!Cをこわせ! Elysia's Avatar
    Join Date
    Oct 2007
    Posts
    22,179
    I see.
    Well, that's what debuggers are for.

    UPDATE:
    It seems matsp's suggestion was spot on. Your application works now just fine.
    Last edited by Elysia; 12-05-2007 at 10:01 AM.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.
    For information on how to enable C++11 on your compiler, look here.
    よく聞くがいい!私は天才だからね! ^_^

  9. #84
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,266
    Oh well, it's a shame I hadn't stayed up later. I've just been playing catch up and I noticed the >= instead of > bug, a couple of pages before now.

    What it would mean is that half of your items would not be able to be found. If you think of the array as a binary tree, you were only able to find the internal nodes (those that have children), but not the leafs. Once you got to a leaf, you stopped before doing the last compare.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  10. #85
    Registered User
    Join Date
    Sep 2007
    Location
    Arizona
    Posts
    164
    Thanks Elysia, Mats and iMalc for helping figure out my errors and sticking with it. I really appreciate all your help. And Mats, don't worry about it. I have gotten farther with your help regardless of you thinking it is sloppy ... or not. I appreciate all your help. And, the bottom line - it is my code and my errors that brought me here in the first place. So, it took longer and I got more experience in debugging subtle errors. It would have taken me a heck of a lot longer without your help. That is what it is all about - thinking, writing and debugging - the effort of code. I appreciate your time and help. More heads, especially more experienced heads, are better than my one. Thank you!

    I too have tested the code and removing the equal sign as noted above is THE fix. I am soooo excited. Three more chapters and 5 more programs along with the final and I can put this class to rest. Next language - Java Script!

    Cindy

    iMalc, I added your homepage to my C++ resources. It is a shame you didn't stay up later...I finally slept for 1 and 1/2 hours at 4:30am.
    Who NEEDS sleep anyway?!
    Last edited by clegs; 12-05-2007 at 07:18 PM.

  11. #86
    Deathray Engineer MacGyver's Avatar
    Join Date
    Mar 2007
    Posts
    3,211
    JavaScript.... ugh.

  12. #87
    Registered User
    Join Date
    Sep 2007
    Location
    Arizona
    Posts
    164
    So MacGyver you know Java Script?
    This may be a C++ Board, but...
    Are you saying that because it is hard, or just bad?
    I had Java last semester and it was about to kill me.

  13. #88
    C++まいる!Cをこわせ! Elysia's Avatar
    Join Date
    Oct 2007
    Posts
    22,179
    JavaScript, huh? I know that too. The one biggest thing I'm possibly most annoyed is the lack of a Sleep function. OH well.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.
    For information on how to enable C++11 on your compiler, look here.
    よく聞くがいい!私は天才だからね! ^_^

  14. #89
    Deathray Engineer MacGyver's Avatar
    Join Date
    Mar 2007
    Posts
    3,211
    I never took the time to actually formally learn it. I did some really simple stuff with it years ago, but I'm not a fan of many web-based nor most dynamically-typed languages. Sorry.

  15. #90
    Registered User
    Join Date
    Sep 2007
    Location
    Arizona
    Posts
    164
    Yea, lately I can relate to a lack of a sleep function. Actually, my sleep function exists, I just don't seem to be able to access it at appropriate times, I think I need a debug routine.

    My poor stab at programming humor, or is that an oxymoron?!

    Elysia, I may just call on you to ask a few questions if the need arises, if you are game. Not here of course! When I was struggling with Java I couldn't find a forum like this one - active, helpful, and always available. I really appreciate the level of sincere helpfulness this forum provides over the others.

    MacGyver, I am sorry to hear you aren't versed in JavaScript as well, I appreciate the way you have explained some things.

    Ah well, all good things must come to an end.

    I really appreciate all the help everyone has afforded me, it has been great.
    I am writing like this is the end, but I still have five more programs so I am not gone yet!!!
    Last edited by clegs; 12-06-2007 at 07:00 PM.

Page 6 of 7 FirstFirst 1234567 LastLast
Popular pages Recent additions subscribe to a feed

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