10 replies to this topic

[YaGa]

Hi guys..

Please help me solving this problem by recursion even if you could just give me the idea i have been trying to do it for three days until now



The game of “Jump It” consists of a board with n positive integers in a row except for the first column, which always contains zero. These numbers represent the cost to enter each column. Here is a sample game board where n is 6:

0 3 80 6 57 10


The object of the game is to move from the first column to the last column in the lowest total cost. The number in each column represents the cost to enter that column. You always start the game in the first column and have two types of moves. You can either move to the adjacent column or jump over the adjacent column to land two columns over. The cost of a game is the sum of the costs of the visited columns.

In the board shown above, there are several ways to get to the end. Starting in the first column, our cost so far is 0. We could jump to 80, then jump to 57, then move to 10 for a total cost of 80+57+10 = 147. However, a cheaper path would be to move to 3, jump to 6, then jump to 10, for a total cost of 3+6+10 = 19.

Write a recursive solution to this problem that computes the cheapest cost of the game and outputs this value for an arbitrarily large game board represented as an array. Your program doesn’t have to output the actual sequence of jumps, only the cheapest cost of this sequence. After making sure that your solution works on small arrays, test your solution on boards of larger and larger values of n to get a feel for how efficient and scalable your solution is.


Pretty please :)

[WingedPanther]

I'll be nice and give you a hint:

The cost of a move is the cost to go into a column, plus the cost of all the following moves.

You will need a way to call the function with the current column. You will need a way to return the lowest cost of the next column to move into. You will need a way to store the column costs. You will need a way to access the column costs from your function.

You should be able to assemble the framework of a program with that information. Post your code and we can try to guide you to completing it :)

[YaGa]

WingedPanther said:

I'll be nice and give you a hint:

The cost of a move is the cost to go into a column, plus the cost of all the following moves.

You will need a way to call the function with the current column. You will need a way to return the lowest cost of the next column to move into. You will need a way to store the column costs. You will need a way to access the column costs from your function.

You should be able to assemble the framework of a program with that information. Post your code and we can try to guide you to completing it :)

thanks WingedPanther that was kind from you but up till now i havn't got any thing done but the main.. :(

God my brain stopped working :(

[WingedPanther]

If all you have is main, add an empty function for calculating the jumps and post that code.

[YaGa]

sorry for the delay i'll post it as soon as i get home :)

thanks

[YaGa]

Hi again this was my final try and i got a StackOverFlowError :(

import java.util.Scanner;

import java.util.Arrays;


public class JumpIt {


    public static void main(String[] args) 

    {

    	Scanner k = new Scanner(System.in);

    	System.out.println("Welcome to 'Jump It'. Please enter the required length of the board ");

      	int length = k.nextInt();

      	System.out.println("You have enterd " + length);

      	int[] board = new int[length];

      	int sumAll = 0;

      	board[0] = 0;

      	

      	for (int i = 1; i < length; i++)

      	{

      		System.out.print("Please enter the " );

      		System.out.print(i + 1);

      		System.out.println(" element for the board");

      		board[i] = k.nextInt();

      		

      		

      	}

      	

      		System.out.print(Arrays.toString(board) );

      		System.out.println(cheapWay(board,0) );

      	

    

    

    

    	

    }

    

    public static int cheapWay(int[] board, int n)

    {

    	if(cheapWay(board, n + 1) < cheapWay(board, n + 2))

    		return board[n] + cheapWay(board, n + 1);

    	else if(board.length - 1  == n)

    		return board[n];

		else if(board.length - 2 == n)    	

    			return board[0] + board[n];

    	else

    		return board[n] + cheapWay(board, n + 2);	


    		 	

     }

    	

    	

    }

[YaGa]

please help me the dead line is few hours away

[YaGa]

i've got i've got i think i did yeeeeeeeeeeeeeeey

import java.util.Scanner;

import java.util.Arrays;


public class JumpIt {


    public static void main(String[] args) 

    {

    	Scanner k = new Scanner(System.in);

    	System.out.println("Welcome to 'Jump It'. Please enter the required length of the board ");

      	int length = k.nextInt();

      	System.out.println("You have enterd " + length);

      	int[] board = new int[length];

      	int sumAll = 0;

      	board[0] = 0;

      	

      	for (int i = 1; i < length; i++)

      	{

      		System.out.print("Please enter the " );

      		System.out.print(i + 1);

      		System.out.println(" element for the board");

      		board[i] = k.nextInt();

      		

      		

      	}

      	

      		System.out.print(Arrays.toString(board) );

      		System.out.println(cheapWay(board,0) );

      	

    

    

    

    	

    }

    

    public static int cheapWay(int[] board, int n)

    {

    	if(board.length - 1  == n)

    		return board[n];

    	

    	else if(board.length - 2 == n)    	

    			return board[0] + board[n];

    		

		else if(cheapWay(board, n + 1) < cheapWay(board, n + 2))

    		return board[n] + cheapWay(board, n + 1);

    		

    	else

    		return board[n] + cheapWay(board, n + 2);	


    		 	

     }

    	

    	

    }

You just need to switch the if statements

[YaGa]

little correction
second if statement

import java.util.Scanner;

import java.util.Arrays;


public class JumpIt {


    public static void main(String[] args) 

    {

    	Scanner k = new Scanner(System.in);

    	System.out.println("Welcome to 'Jump It'. Please enter the required length of the board ");

      	int length = k.nextInt();

      	System.out.println("You have enterd " + length);

      	int[] board = new int[length];

      	board[0] = 0;

      	

      	for (int i = 1; i < length; i++)

      	{

      		System.out.print("Please enter the " );

      		System.out.print(i + 1);

      		System.out.println(" element for the board");

      		board[i] = k.nextInt();

      		

      		

      	}

      	

      		System.out.println(Arrays.toString(board) );

      		System.out.println(cheapWay(board,0) );

      	

    

    

    

    	

    }

    

    public static int cheapWay(int[] board, int n)

    {

    	if(board.length - 1  == n)

    		return board[n];

    	

    	else if(board.length - 2 == n)    	

    			return board[0] + board[board.length - 1];

    		

		else if(cheapWay(board, n + 1) < cheapWay(board, n + 2))

    		return board[n] + cheapWay(board, n + 1);

    		

    	else

    		return board[n] + cheapWay(board, n + 2);	


    		 	

     }

    	

    	

    }

[WingedPanther]

Congrats! I'm glad you were able to get it :)

[YaGa]

i've just submitted this was the other question that i spent seven hours on it

Write a program that uses an array of parameter type Contact to store a database of contacts. The Contact class should store the contact's name, birth date, phone number (7-digit integer), and email address. Add appropriate accessor and mutator methods.

Your database program should present a menu that allows the user to:

1. add a contact,

2. display all contacts in ascending order. Here contacts are sorted by name (ascending order of the String class). If the names of two contacts are same, then contacts are sorted by their phone number.

3. Search for a specific contact based on
a. name
b. phone number
c. email address

4. search for a specific contact and give the user the option to delete it, and

5. exit the program.

public class Contacts implements Comparable 
{
	
	private String name;
	private String DOB;
	private String number;
	private String email;

    public Contacts(String name, String DOB, String number, String email)
    {
    	this.name = name;
    	this.DOB =  DOB;
    	this.number = number;
    	this.email = email;
    }
    
    
        public Contacts() 
    {
    	this("No Name", "No DOB", "No Number", "No Email");
    }
    
    public String getName()
    {
    	return name;
    }
    
        public String getDOB()
    {
    	return DOB;
    }
    
        public String getNumber()
    {
    	return number;
    }
    
        public String getEmail()
    {
    	return email;
    }
    
    public String toString()
    {
    	return "\nName: " + getName() + "\nDOB: " + getDOB() + "\nTelephone Number: " + getNumber() + "\ne-mail: " + getEmail() + "\n";
    }
    
    	public int compareTo(Object other) {
		if(other == null)
			return -1;
		
		else if(this.getClass() != other.getClass()) 
			return -1;
		
		else {
			Contacts c1 = (Contacts) other;
			if(this.getName().compareTo(c1.getName()) < 0) 
				return -1;
			else if(this.getName().compareTo(c1.getName()) > 0) 
				return +1;
			else 
				return 0;
		}
	}
/*********************************************************/


import java.util.Arrays;
import javax.swing.JOptionPane;

public class contactsTest
{

    public static void main(String[] args)
    {
    	int counter = 0;
    	Contacts[] a = new Contacts[1000];
    	String user = JOptionPane.showInputDialog("Please enter your name.");
    	JOptionPane.showMessageDialog(null ,"Hi " + user + ". Please press ok to continue :)");
    	
    	while(true){
    	
    	int choise = Integer.parseInt(JOptionPane.showInputDialog("Please enter your choice "+ user +".\n1- Add Contact.\n2- Display all Contacts.\n3-Search a Contact.\n4- Delete a Contact.\n5- Exit.") );
    	
    	if(choise == 1)
    	{
    		for(int i = 0; i < a.length; i++)
    		{
    			if(a[i] != null) continue;
    			String name = JOptionPane.showInputDialog("Please enter your contact's name.");
    			String DOB = JOptionPane.showInputDialog("Please enter your contact's DOB.");
    			String phone = JOptionPane.showInputDialog("Please enter your contact's phone of 7 digits.");
    			phone = checkPhone(phone);
    			String email = JOptionPane.showInputDialog("Please enter your contact's email.");
    			a[i] = new Contacts(name, DOB, phone, email);
    			String cont = JOptionPane.showInputDialog("Do you want to add another contact. Enter y or n");
    			if(cont.equalsIgnoreCase("y")) 
    			continue;
    			
    			else
    			{
    				JOptionPane.showMessageDialog(null ,"Thanks " + user + ". You'll be redirected to Main Menu :)");
    				break;
    			}
    				
    		}
    	}
    	
    	else if(choise == 2)
    	{
    		counter = 0;
    		for(int i = 0; i < a.length; i++)
    		{
    			if (a[i] != null)
    				counter++;
    		}
    		Contacts[] b = new Contacts[counter];
    		for(int i = 0; i < b.length; i++)
    		{
    			b[i] = a[i];
    		}
    		Arrays.sort(b);
    		System.out.println(Arrays.toString(b));
    		JOptionPane.showMessageDialog(null, "You will be redirected to Main Menu");
    	}
    	
    	else if(choise == 3)
    	{
    		counter =0;
    		for(int i = 0; i < a.length; i++)
    		{
    			if (a[i] != null)
    				counter++;
    		}
    		Contacts[] b = new Contacts[counter];
    		for(int i = 0; i < b.length; i++)
    		{
    			b[i] = a[i];
    		}
    		Arrays.sort(b);
    		int choise2 = Integer.parseInt(JOptionPane.showInputDialog("Please enter your Searchin method choice "+ user +".\n1- By Name.\n2- By Phone.\n3-By Email.") );
    		
    		if(choise2 == 1)
    		{
    			String nameS = JOptionPane.showInputDialog("Please enter your contact's name you want to search for.");
    			Contacts c1 = new Contacts(nameS, "", "", "");
    			linearSearchName(b, c1);
			}
    		else if(choise2 == 2)
    		{
    			String phoneS = JOptionPane.showInputDialog("Please enter your contact's Phone number you want to search for.");
    			Contacts c2 = new Contacts("", "", phoneS, "");
				linearSearchPhone(b, c2);
			}
    		
    		 else if(choise2 == 3)
    		{
    			String emailS = JOptionPane.showInputDialog("Please enter your contact's Email you want to search for.");
    			Contacts c3 = new Contacts("", "", "", emailS);
				linearSearchEmail(b, c3);
    		}
    		
    		else
    			JOptionPane.showMessageDialog(null, "You have entered a wrong value and will be redirected to Main Menu");
    	
    	}//choise 3
    	
    	else if(choise == 4)
    	{
    		counter =0;
    		for(int i = 0; i < a.length; i++)
    		{
    			if (a[i] != null)
    				counter++;
    		}
    		Contacts[] b = new Contacts[counter];
    		for(int i = 0; i < b.length; i++)
    		{
    			b[i] = a[i];
    		}
    		Arrays.sort(b);
    		int choise2 = Integer.parseInt(JOptionPane.showInputDialog("Please enter your Searchin method choice "+ user +".\n1- By Name.\n2- By Phone.\n3-By Email.") );
    		
    		if(choise2 == 1)
    		{
    			String nameS = JOptionPane.showInputDialog("Please enter your contact's name you want to search for then delete.");
    			Contacts c1 = new Contacts(nameS, "", "", "");
    			deleteName(b, c1);
    			copy(a, b);
			}
    		else if(choise2 == 2)
    		{
    			String phoneS = JOptionPane.showInputDialog("Please enter your contact's Phone number you want to search for.");
    			Contacts c2 = new Contacts("", "", phoneS, "");
				deletePhone(b, c2);
    			copy(a, b);
			}
    		
    		 else if(choise2 == 3)
    		{
    			String emailS = JOptionPane.showInputDialog("Please enter your contact's Email you want to search for.");
    			Contacts c3 = new Contacts("", "", "", emailS);
				deleteEmail(b, c3);
    			copy(a, b);
    		}
    		
    		else
    			JOptionPane.showMessageDialog(null, "You have entered a wrong value and will be redirected to Main Menu");
    			
    			
    	}//Choise 4
    	
    	if(choise == 5) {
    			JOptionPane.showMessageDialog(null, "Bye " + user);
    		System.exit(0);
    		
    	}
    	
    	}//while
    	
    	
    	
    }//main
    public static String checkPhone(String phone)
    {
    	while(true)
    	{
    	if(phone.length() == 7)
    		return phone;
    	
    	else
    		phone = JOptionPane.showInputDialog("Please make sure that phone number is of 7 digits");	
    }
    }
    
    public static void linearSearchName(Contacts[] c, Contacts key) 
    	{
		for(int i = 0; i < c.length; i++)
			if(c[i].getName().equals(key.getName()))
				JOptionPane.showMessageDialog(null, c[i].toString() );
				JOptionPane.showMessageDialog(null, "Contact was not found any more. You'll be redirected to Main Menu");
		}
	
	public static void linearSearchPhone(Contacts[] c, Contacts key) 
		{
		for(int i = 0; i < c.length; i++)
			if(c[i].getNumber().equals(key.getNumber()))
				JOptionPane.showMessageDialog(null, c[i].toString() );
				JOptionPane.showMessageDialog(null, "Contact was not found any more. You'll be redirected to Main Menu");
		}
	
	public static void linearSearchEmail(Contacts[] c, Contacts key) 
		{
		for(int i = 0; i < c.length; i++)
			if(c[i].getEmail().equals(key.getEmail())) 
				JOptionPane.showMessageDialog(null, c[i].toString() );
				JOptionPane.showMessageDialog(null, "Contact was not found any more. You'll be redirected to Main Menu");
		 }
    
    public static void deleteName(Contacts[] b, Contacts key) 
    	{
    		String answer = "";
		for(int i = 0; i < b.length; i++){
			if(b[i].getName().equals(key.getName())){
			
				answer = JOptionPane.showInputDialog(b[i].toString() + "\nDo you want to delete it. Enter y or n.");
				
			if(answer.equalsIgnoreCase("y")){
			b[i] = null;
			JOptionPane.showMessageDialog(null, "Contact was Deleted. You'll be redirected to Main Menu");
			}
			  else
			  	continue;
				
					}
				}
			
		}
		
		    public static void deletePhone(Contacts[] b, Contacts key) 
    	{
    		String answer = "";
		for(int i = 0; i < b.length; i++){
			if(b[i].getNumber().equals(key.getNumber())){
			
				answer = JOptionPane.showInputDialog(b[i].toString() + "\nDo you want to delete it. Enter y or n.");
				
			if(answer.equalsIgnoreCase("y")){
			b[i] = null;
			JOptionPane.showMessageDialog(null, "Contact was Deleted. You'll be redirected to Main Menu");
			}
			  else
			  	continue;
				
					}
				}
			
		}
		
		    public static void deleteEmail(Contacts[] b, Contacts key) 
    	{
    		String answer = "";
		for(int i = 0; i < b.length; i++){
			if(b[i].getEmail().equals(key.getEmail())){
			
				answer = JOptionPane.showInputDialog(b[i].toString() + "\nDo you want to delete it. Enter y or n.");
				
			if(answer.equalsIgnoreCase("y")){
			b[i] = null;
			JOptionPane.showMessageDialog(null, "Contact was Deleted. You'll be redirected to Main Menu");
			}
			  else
			  	continue;
				
					}
				}
			
		}
		
		public static void copy(Contacts[] a, Contacts[] b)
		{
			for(int i = 0; i < b.length; i++)
			{
				if(b[i] != null)
					a[i] = b[i];
			}
			for(int i = b.length - 1; i < a.length; i++)
			{
				a[i] = null;
			}
		}
    
}
    
}

Edited by YaGa, 21 April 2009 - 12:24 PM.