Fibonacci Numbers

  1. In our current project, create a new application called fibonacci. At the command line, type:

    python manage.py startapp fibonacci
  2. Create a view that computes the n-th element of the Fibonacci sequence using the following recurrence relation:

    Fibonacci recurrence relation

    Edit the sigcse/fibonacci/views.py file so that it contains the following:

    from django.shortcuts import render_to_response
    
    def do_it(request, n):
        n = int(n)
        result = fib(n)
        return render_to_response('fibonacci.html', {'n': n, 'r': result})
        
    def fib(n):
        if n in [0, 1]:
            return n
        else:
            return fib(n - 1) + fib(n - 2)

    We can test our solution running the Django shell. At the command line type:

    python manage.py shell

    Now type the following at the interactive shell:

    >>> from sigcse.fibonacci.views import fib
    >>> fib(5)
    5
    >>> fib(10)
    55
    
  3. Create a template file called fibonacci.html and place it in the templates folder. Its contents should be:

    {% extends "base.html" %}
    
    {% block title %}Fibonacci Numbers{% endblock %}
    
    {% block main %}
      <h1>Fibonacci Numbers</h1>
      <p>
        Element #{{ n }} of the sequence is: {{ r }}
      </p>
    {% endblock %}
  4. Link the view function with a URL pattern. Edit the sigcse/urls.py file by adding the following highlighted line:

    urlpatterns = patterns('',
        # Example:
        # (r'^sigcse/', include('sigcse.foo.urls')),
    
        # Uncomment the admin/doc line below and add 'django.contrib.admindocs' 
        # to INSTALLED_APPS to enable admin documentation:
        # (r'^admin/doc/', include('django.contrib.admindocs.urls')),
    
        # Uncomment the next line to enable the admin:
        # (r'^admin/(.*)', admin.site.root),
        (r'^hello/(\w+)/$', 'sigcse.hello.views.say'),
        (r'^fibonacci/(\d{1,2})/$', 'sigcse.fibonacci.views.do_it'),
    )
  5. Using your web browser, visit the following URL: http://localhost:8000/fibonacci/10/

Exercises

  1. Modify the previous application, so that instead of displaying the n-th element of the Fibonacci sequence, it displays the first n elements of the sequence as an HTML unordered list (using the <ul> and <li> tags). For example, given the URL http://localhost:8000/fibonacci/10/ the output should look something like this:

    Fibonacci sequence output example.
  2. Write a new application called pascal that displays diagonals 0 to n of the Pascal triangle (using the <table>, <tr> and <td> tags).

    This is how the triangle should be built: the first row and column are composed of ones; all other elements are computed by adding the element immediately above plus the element immediately to the left. In the resulting table, all cells that are not part of the triangle should be left blank. For example, given the URL http://localhost:8000/pascal/5/ the output should look something like this:

    Pascal triangle output example.
© 2009-2010 by Ariel Ortiz. Except where otherwise noted, content on this site is licensed under a
Creative Commons Attribution-Noncommercial 3.0 License