Lecture 21, ECE264, Spring 2012, Prof. Lu
March 21, 2012 - Tej Rajendran
Comfortable topics -Recursion -File Management -Structures
Upcoming Topics -Dynamic Memory -Data Structures -Linked Lists -Binary Trees
IPA2-1
Rules for blocks - arrangement cant have holes - no diagonal blocks
ELIMINATE ROTATIONS/ MIRRORS/ TRANSLATIONS
-Store in a 2D array
Integer Partitions
n = 3
1,1,1 2,1 1,2 3
- Useful for generation of tetris pieces b/c given number of blocks in each piece, helps
determine how many blocks in each row (use as a budget)
for n = 3
x _ _
x _ _
x _ _
x x _
x _ _
_ _ _
x _ _
x x _
_ _ _
x x x
_ _ _
_ _ _
n = 4
1 * * *-> 1 ** -> 1 * -> 1
-> 2
-> 2 * -> 1
-> 3
Code for generation of Integer Partitions
void intPart(int budget, int pos, int *data) { int i;
//Base case: no more budget if(budget == 0) { //print the partition return; }
//Recursive case: figure out how to spend the budget for ( i = 1; i< budget; i ++) { data [pos] = i; intPart( budget-1, pos +1, data); }
}
