Write code for a modified version of the Grade School addition algorithm that adds the integer one to an m-digit integer. Thus, this modified algorithm does not even need a second number being added. Design the algorithm to be fast, so that it avoids doing excessive work on carries of zero.
I encountered this question looking over last year's final for my algorithms course. I'm not really sure how to answer it, although it seems like it isn't a very challenging question.
Asked By : Chaz
Answered By : Rick Decker
To slightly expand on @greybeard's answer, here are a few hints:
- Start adding from the right, as usual.
- When can you stop? Obviously, when you don't have a carry. When will that happen?
- When do you have to look at the next digit? Obviously, when you have a carry. When will that happen?
Challenge: show that the average number of steps this algorithm will take on an $m$-digit number represented in base $b$ is less than $b/(b-1)$.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/35492
0 comments:
Post a Comment
Let us know your responses and feedback