(Integer Partition) |
|||
| (4 intermediate revisions by one other user not shown) | |||
| Line 1: | Line 1: | ||
| − | March 21, 2012 | + | [[Category:ECE264]] [[Category:Programming]] [[Category:C]] [[Category:lecture notes]] |
| + | |||
| + | =Lecture 21, [[ECE264]], Spring 2012, Prof. Lu= | ||
| + | ---- | ||
| + | March 21, 2012 - Tej Rajendran | ||
Comfortable topics | Comfortable topics | ||
| Line 33: | Line 37: | ||
for n = 3 | for n = 3 | ||
| + | |||
x _ _ | x _ _ | ||
| + | |||
x _ _ | x _ _ | ||
| + | |||
x _ _ | x _ _ | ||
| + | |||
x x _ | x x _ | ||
| + | |||
x _ _ | x _ _ | ||
| + | |||
_ _ _ | _ _ _ | ||
| + | |||
| + | |||
x _ _ | x _ _ | ||
| + | |||
| + | |||
x x _ | x x _ | ||
| + | |||
_ _ _ | _ _ _ | ||
| + | |||
| + | |||
x x x | x x x | ||
| + | |||
_ _ _ | _ _ _ | ||
| + | |||
_ _ _ | _ _ _ | ||
| + | |||
| Line 54: | Line 74: | ||
1 * * *-> 1 ** -> 1 * -> 1 | 1 * * *-> 1 ** -> 1 * -> 1 | ||
| + | |||
-> 2 | -> 2 | ||
| + | |||
-> 2 * -> 1 | -> 2 * -> 1 | ||
| + | |||
-> 3 | -> 3 | ||
| Line 80: | Line 103: | ||
} | } | ||
| + | ---- | ||
| + | [[2012_Spring_ECE_264_Lu|Back to ECE264 Prof. Lu]] | ||
Latest revision as of 05:01, 11 July 2012
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); }
}
