Learntofish's Blog

A blog about math, physics and computer science

Basic Algorithm 3: cut the number

Posted by Ed on November 12, 2011

Last time we talked about calculating the sum of the integers from 1 to N. Today we deal with the following problem:

Given an integer, e.g. 31415926, produce the following output:
31415926
3141592
314159
31415
3141
314
31
3
So, you have to cut the number from right to left.

a) Write a function with a while loop that produces this output.
b) Write a function without a while loop producing the output (Hint: recursion).
Part b) is a little difficult if you don’t have experience with recursion.

Test your function with the following integers:
31415926, 1000, 5 and 0

Before I post my solution let me give you a hint:
Take an integer and divide it by 10 (integer division). What happens with the integer?

Here is my solution in C++:

#include <iostream>
using namespace std;

// function prototype
void cutNumber(int x);
void cutNumberRecAux(int x);
void cutNumberRec(int x);

// main function -----------------------------------------------------
int main(){
    int myNumber=31415926;
    int thousand=1000;
    int five=5;
    int zero=0;

    cout << "Non-recursive:" << endl;
    cutNumber(myNumber);
    cutNumber(thousand);
    cutNumber(five);
    cutNumber(zero);

    cout << "Recursive:" << endl;
    cutNumberRec(myNumber);
    cutNumberRec(thousand);
    cutNumberRec(five);
    cutNumberRec(zero);

    cout << "End of program";

    return 0;
}
// -------------------------------------------------------------------

void cutNumber(int x){
    cout << "cutting " << x << " from right to left..." << endl;
    if(x==0){
        cout << x << endl;
    }
    while(x>0){
        cout << x << endl;
        x=x/10;
    }
    cout << endl;
}

// -------------------------------------------------------------------

// Recursive function
// The actual recursive function is "cutNumberRecAux()",
// where Aux stands for auxiliary.
void cutNumberRecAux(int x){
    if(x>0){
        cout << x << endl;
        cutNumberRecAux(x/10);
    }
}

// This function uses the auxiliary function.
// I needed it to handle the case x==0.
void cutNumberRec(int x){
    cout << "cutting the number " << x << " from right to left" << endl;
    if(x==0){
        cout << x << endl;
    }
    else{
        cutNumberRecAux(x);
    }
    cout << "\n" << endl;
}

Some things to note: The while loop checks whether x is 0. If it is not then x is printed and afterwards divided by 10 (integer division).
Example: myNumber= 1234
output:
6789
678
67
6

If you then divide 6 by 10 the result is 0, hence the while loop stops. But what happens if 0 is the initial number. Then you will never enter the while loop and nothing is printed at all, which is obviously wrong. Even for 0 the output has to be 0. For 5 the output is 5. That’s why we have the extra condition at the beginning that checks whether x==0.

Here is my solution in Java:

public class BasicAlgorithm3_cutNumber {
	
	// Non-recursive
	void cutNumber(int x){
		System.out.println("cutting " + x + " from right to left");
		if(x==0){
			System.out.println(x);
		}

		while(x>0){
			System.out.println(x);
			x=x/10;
		}
		
		System.out.println();
	}
	
	
	// Recursive function
	// The actual recursive function is "cutNumberRecAux()",
	// where Aux stands for auxiliary.
	void cutNumberRecAux(int x){
		if(x>0){
			System.out.println(x);
			cutNumberRecAux(x/10);
		}
	}
	
	// This function uses the auxiliary function.
	// I needed it to handle the case x==0.
	void cutNumberRec(int x){
		System.out.println("cutting " + x + " from right to left");
		if(x==0){
			System.out.println(x);
		}
		else{
			cutNumberRecAux(x);
		}
		System.out.println();
	}
	
	
	// main method() -------------------------------------------------------
	public static void main(String[] args){
		int myNumber=31415926;
	    int thousand=1000;
	    int five=5;
	    int zero=0;
	    
	    // Creating object
	    BasicAlgorithm3_cutNumber myObj = new BasicAlgorithm3_cutNumber();
	    
	    System.out.println("Non-recursive:");
	    myObj.cutNumber(myNumber);
	    myObj.cutNumber(thousand);
	    myObj.cutNumber(five);
	    myObj.cutNumber(zero);
	    
	    System.out.println("Recursive:");
	    myObj.cutNumberRec(myNumber);
	    myObj.cutNumberRec(thousand);
	    myObj.cutNumberRec(five);
	    myObj.cutNumberRec(zero);
	    
	    System.out.println("End of program");
	}
}

Here is my solution in Python 3:

# Non-recursive function
def cutNumber(x):
    print("cutting", x, "from right to left...")
    if(x==0):
        print(x)
    while(x>0):
        print(x)
        x=x//10
        # Note for Python 3:
        # Use the double slash for integer division
    print()



# Recursive function
# The actual recursive function is "cutNumberRecAux()",
# where Aux stands for auxiliary. 
def cutNumberRecAux(x):
    if(x>0):
        print(x)
        cutNumberRecAux(x//10)
        # Note for Python 3:
        # Use the double slash for integer division


# this function uses the auxiliary function
# I needed it to handle the case x==0.
def cutNumberRec(x):
    print("cutting", x, "from right to left...")
    if(x==0):
        print(x)
    else:
        cutNumberRecAux(x)
    print()

#------------------------------------------------------

    
# main function
def main():
    myNumber=31415926
    thousand=1000
    five=5
    zero=0

    print("Non-recursive:")
    cutNumber(myNumber)
    cutNumber(thousand)
    cutNumber(five)
    cutNumber(zero)

    print("Recursive:")
    cutNumberRec(myNumber)
    cutNumberRec(thousand)
    cutNumberRec(five)
    cutNumberRec(zero)

    print("End of program")
Advertisements

One Response to “Basic Algorithm 3: cut the number”

  1. […] Basic Algorithm 3: cut the number […]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

 
%d bloggers like this: