//FibonacciSteps.java
// climb steps one or two at a time: the ways to climb n steps

import java.awt.*;
import javax.swing.*;

public class FibonacciSteps  extends JApplet  {   

    String [] FN;
    int maxF;

    public void init() {
    	String []FN1 = new String[1];
        String []FN2 = new String[1];
 	int Fn=0, Fn1=1, Fn2=1;
        double phi= (1.0 + Math.sqrt(5)) / 2;

        String input = JOptionPane.showInputDialog("Number of steps ","8");
        maxF = Integer.parseInt(input);
        maxF++;
 	
	FN1[0] = "1";
	FN2[0] = "";

 	System.out.printf("%2d %6d   \n",1,Fn2);
 	System.out.printf("%2d %6d                                %s\n",2,Fn1,FN1[0]);
	
 	for (int n=3; n<=maxF; n++) {
 	    Fn = Fn1 + Fn2;
 	    System.out.printf("%2d %6d   %12.4f     %8.6f   ",
 	                      n,Fn,(Math.pow(phi,n)/Math.sqrt(5)),((double)Fn/Fn1));
 	    
 	    FN = new String[Fn];
 	    for (int j=0; j<Fn1; j++)
 	    	FN[j] = FN1[j] + "1";   //append 1  to each from previous F1
 	    for (int j=0; j<Fn2; j++)
 	    	FN[j+Fn1] = FN2[j] + "2"; //append 2 to each from two previous F2
 	    for (int j=0; j<Fn; j++)
 	    	System.out.print(" "+FN[j]);
 	    System.out.println();	
	    FN2 = FN1;
	    FN1 = FN;
	    
 	    Fn2 = Fn1;
 	    Fn1 = Fn;
 	}
        
        System.out.print("\nphi="+phi);
        System.out.println("    phi^2="+(phi*phi));
        System.out.println("1/phi="+(1/phi));
    }
  
    public void paint (Graphics g) {
    	int w = getWidth();
    	int h = getHeight();  
    	int steps = maxF - 1;
    	int stepsize = 5;
    	int blocksize = steps*stepsize;
    	int gapsize = 2*stepsize;
    	int x, y, s;
    	int horizBlocks = w / (blocksize+gapsize);
    		
    	for (int i=0; i<FN.length; i++) {
    	    y = (i / horizBlocks) * (blocksize + gapsize) + blocksize;
    	    x = (i % horizBlocks) * (blocksize + gapsize);
    	    for (int j=0; j<FN[i].length(); j++) {    //each char 1 or 2
    	        s = Integer.parseInt(Character.toString(FN[i].charAt(j)));
    	        g.drawLine(x,y, x,y-s*stepsize);    //up stroke
    	        g.drawLine(x,y-s*stepsize, x+s*stepsize,y-s*stepsize);    //right stroke
    	        x += s*stepsize;
    	        y -= s*stepsize; 
    	        
    	    }
    	}
    		
    }  
}