Think of a positive whole number, and apply the following rules:
Do you always reach 1? Prove your answer.
The puzzle is known as the Collatz-Syracuse-Ulam problem (and has many other names).
No one knows if the sequence always reaches 1, but it is thought that it does.
Computer calculations show that every starting number up to at least 19 * 258 ≈ 5.48 * 1018 eventually hits 1. [Ian Stewart, Professor Stewart's Hoard of Mathematical Treasures].
In computability theory, the halting problem can be stated as:
Given a program and an input to the program, decide (yes or no) whether or not the program will eventually halt when run with that input.
In 1936, Alan Turing proved that the problem is undecidable: no general algorithm exists that can solve the problem for all possible program-input pairs.
See:
How Dr. Seuss would prove the halting problem
undecidable
CSE2001 Introduction to the Theory of Computation
In pseudocode:
while p is not equal to 1
if p is even
p = p / 2
else
p = 3 * p + 1
In Java:
while (p != 1)
{
if (???)
{
}
else
{
}
output.println(p);
}
In Java, the code inside the block of a loop runs if
a condition (logical expression) is true.
In while and for loops, the
condition is checked once (and only once) before the
loop runs the first time, and every time at the end
of the loop body.
A while (condition)
{
//
B // loop body
//
}
C // after loop
true the loop body B is run, otherwise
control flows to C.
true the loop body B is run, otherwise
control flows to C.
A gambler with finite wealth playing a fair game (equal odds of winning or losing) will eventually go broke against an opponent with infinite wealth (casino). However, it is possible for a disciplined gambler to make money if he stops gambling after he has accumulated a preset amount of wealth.
What are the odds of reaching the preset amount of wealth?
How many games will it take (on average)?
It is easy to simulate the gambler's ruin scenario. You need to know:
You also need to know how much it costs to play a game. To keep things simple, assume that it costs $1 to play a game.
import java.util.Scanner;
import java.io.PrintStream;
import java.util.Random;
public class GamblersRuin
{
public static void main(String[] args)
{
PrintStream output = System.out;
Scanner input = new Scanner(System.in);
output.print("Starts with $ ");
int dollars = input.nextInt();
output.print("Finish with $ ");
int target = input.nextInt();
Random game = new Random();
while (dollars > 0 && dollars < target)
{
if (game.nextBoolean())
{
dollars++;
}
else
{
dollars--;
}
}
if (dollars == 0)
{
output.println("Busted!");
}
else
{
output.println("Winner!");
}
}
}
Write a loop that repeatedly reads an integer number from the user until the user enters -1.
In pseudocode:
set number to zero while number is not -1 read number from user
In Java:
final int SENTINEL = -1;
int number = 0;
while (???)
{
}
Write a loop that repeatedly reads an integer number from the user until the user enters -1; the loop should compute and output the sum of the numbers entered so far.
In Java:
final int SENTINEL = -1;
int number = 0;
int sum = 0;
while (???)
{
}
Instead of using a sentinel, suppose you ask the user how many numbers they want to input. Write a loop that computes the total sum of the numbers input by the user.
output.print("How many numbers do you want to enter?: ");
int n = input.nextInt();
int sum = 0;
while (???)
{
}
for Loops
The idea of using a loop controlled by a counter is so
common that it has its own kind of loop, the for
loop.
The for loop is controlled by 3 expressions, all of which
are optional.
for (initial-expression; logical-expression; update-expression)
{
statements
}
The loop executes as follows:
true then:
output.print("How many numbers do you want to enter?: ");
int n = input.nextInt();
int sum = 0;
for (int count = 0; count < n; count++)
{
int number = input.nextInt();
sum += number;
}
When written this way, the variable count
is local to body of the loop; you cannot use
count after the loop body.
Traditionally, loop counter variables are named
i, j, and k.
Suppose we have the following loop that computes the sum 0 + 1 + 2:
int sum = 0;
for (int i = 0; i < 3; i++)
{
sum = sum + i;
}
You can think of this loop as being equivalent to:
int sum = 0;
{
int i = 0; // this only happens once
if (i < 3)
{
sum = sum + i; // sum is now 0
}
i++; // i is now 1
if (i < 3)
{
sum = sum + i; // sum is now 1
}
i++; // i is now 2
if (i < 3)
{
sum = sum + i; // sum is now 3
}
i++; // i is now 3
// i < 3 is false so the loop ends
}
You can put one loop inside another loop. For example, supposed you wanted to print this:
**** **** **** ****
1. for each row a. print 4 stars b. print a newline
final int N = 4;
for (int row = 0; row < N; row++)
{
for (int col = 0; col < N; col++)
{
output.print("*");
}
output.println();
}
Supposed you wanted to print this:
*
**
***
****
*****
1. for each row a. print some spaces b. print some stars c. print a new line
final int N = 5;
for (int row = 0; row < N; row++)
{
// how many spaces?
int spaces = ???;
for (???; ???; ???)
{
output.print(" ");
}
// how many stars?
int stars = ???;
for (???; ???; ???)
{
output.print("*");
}
output.println();
}
Supposed you wanted to print this:
*
***
*****
*******
*********
1. for each row a. print some spaces b. print some stars c. print a new line
final int N = 5;
for (int row = 0; row < N; row++)
{
// how many spaces?
int spaces = ???;
for (???; ???; ???)
{
output.print(" ");
}
// how many stars?
int stars = ???;
for (???; ???; ???)
{
output.print("*");
}
output.println();
}
Modify the GamblersRuin program so
that it simulates the gambler's ruin scenario
10,000 times.
Count the number of times the gambler wins (reaches the target amount); this gives the odds of reaching the target amount.
Count the total number of games played (the number
of times game.nextBoolean() for all
of the winning scenarios; this gives the average
number of games the gambler needs to play to
reach the target amount.