Programming - Recursion & Arrays(7)

Administrivia

Practice Web Page - http://www.cs.tau.ac.il/~efif/courses/Programming_Fall_04

Riddle

Find three ways to change one character in the code bellow so that the resulting code will print 20 times the minus sign ('-').
- Remember, you can change one character only for each solution.
int i, n=20; for (i = 0; i < n; i--) printf("-");

Top-down recursive I/O

A recursive program that reads a sequence of characters until new line is reached one at a time and prints it out

#include <stdio.h>

void rch();

int main()
{
  printf("Input a line\n");
  rch();
  return 0;
}

void rch()
{
  char ch;
  scanf("%c", &ch);
  printf("%c", ch);
  if (ch != '\n')
    rch();
}

rch.c

Bottom-up recursive I/O

A recursive program that reads a sequence of characters until new line is reached one at a time and prints it out

#include <stdio.h>

void rch();

int main()
{
  printf("Input a line\n");
  rch();
  printf("\n");
  return 0;
}

void rch()
{
  char ch;
  scanf("%c", &ch);
  if (ch != '\n')
    rch();
  printf("%c", ch);
}

rrch.c

stdlib.h - standard library definitions

A program that reads a number n, forllowed by a number X, followed by a sequence of n numbers, and prints out the number m of the sequence, hwose absolute difference from x is the maximum among all the numbers of the sequence

#include <stdio.h>
#include <stdlib.h>
int main()
{
  int x, n;
  int num, max_num, max = 0;
  printf("Enter number n and x: ");
  scanf("%d %d", &n, &x);
  while (n > 0)	{
    scanf("%d", &num);
    if (max < abs(num - x)) {
      max_num = num;
      max = abs(num - x);
    }
    n--;
  }
  printf("Output: %d\n", max_num);
  return 0;
}

Example:

inpute: 5 3 4 7 8 1 2
output: 8
max_dabs.c

stdlib.h - standard library definitions

A program that reads a sequence of integers and prints them out. It stops when the input sequence diverts from the Fibonacci sequence.

#include <stdio.h>
int main()
{
  int a1 = 1, a2 = 1, temp, input;

  scanf("%d", &input);
  printf("%d ",input);
  if (a1 != input)
    return 0;
  scanf("%d", &input);
  while (input ==  a2) {
    printf("%d ",input);
    temp = a1;
    a1 = a2;
    a2 = temp + a2;
    scanf("%d", &input);
  } 
  printf("%d\n",a2);
}

Example:

inpute: 1 1 2 3 5 8 13 23
output: 1 1 2 3 5 8 13 21
tfib.c

Computing log₂(`n`)

How many times n is divided by 2

Iterative

Recursive

int log2(int n)
{
  int count = 0;
  while (n != 1) {
    n = n / 2;
    count++;
  }
  return count;
}

int log2(int n)
{
  if (n == 1)
    return 0;
  return 1 + log2(n / 2);
}

Computing log_x(`n`)

How many times n is divided by x

Iterative

Recursive

int log(int x, int n)
{
  int count = 0;
  while (n != 1) {
    n = n / x;
    count++;
  }
  return count;
}

int log(int x, int n)
{
  if (n == 1)
    return 0;
  return 1 + log(x, n / x);
}

Arrays

a variable that can hold several elements (values)
not limited to any particular type
- can have arrays of int, char, double, etc.
int a[10]; float temperatures[10];
You specify which of the several values you're referring to by using a numeric subscript
the subscript is an integer expression in square brackets

arrays are zero-based array

a[0] = 10;
a[1] = 20;
a[2] = a[0] + a[1];

cannot set all elements of an array at once
a = 0; /* WRONG */
cannot assign one array to another
int b[10]; b = a;/* WRONG */

one by one

int b[10];

for(i = 0; i < 10; i++)
  b[i] = a[i];

Simple array

A program that reads 10 characters into an array and prints them out in reverse order.

#include <stdio.h>

int main()
{
  int i;
  char a[10];
  for (i = 0; i < 10; i++)
    scanf("%c",&a[i]);
  for (i = 9;i >= 0; i--)
    printf("%c",a[i]);
  printf("\n");
  return 0;
}

sarr.c

random number generator

int rand() - returns a pseudo-random integer between 0 and RAND_MAX
srand(unsigned int seed) - sets seed as the seed for a new sequence of pseudo-random integers to be returned by rand(). These sequences are repeatable by calling srand() with the same seed value.

dice.c

/*
 * The behavior of rolling a pair of dice.
 *
 * The total roll can be anywhere from 2 to. We want to count how often each
 * roll comes up. We use an array to keep track of the counts: a[2] will count
 * how many times we've rolled 2, etc.
 *
 * We simulate the roll of a die by calling C's random number generation
 * function, rand(). Each time rand() is called, it returns a different,
 * pseudo-random integer. The values that rand() returns typically span a large
 * range. We use C's modulus (or ``remainder'') operator % to produce random
 * numbers in the range we want. The expression rand() % 6 produces random
 * numbers in the range 0 to 5, and rand() % 6 + 1 produces random numbers in
 * the range 1 to 6.
 */

#include <stdio.h>
#include <stdlib.h>

main ()
{
  int i;
  int d1, d2;
  int a[13];			/* uses [2..12] */

  /* Initialize: */
  for (i = 2; i <= 12; i++)
    a[i] = 0;

  /* Compute: */
  for (i = 0; i < 1000; i++) {
    d1 = rand() % 6 + 1;
    d2 = rand() % 6 + 1;
    a[d1 + d2] = a[d1 + d2] + 1;
  }

  /* Print out: */
  for (i = 2; i <= 12; i++)
    printf ("%2d: %3d\n", i, a[i]);

  return 0;
}