| Line 1: | Line 1: | ||
| − | [[Category:ECE264]] [[Category:Programming]] [[Category:C]] | + | [[Category:ECE264]] [[Category:Programming]] [[Category:C]] [[Category:lecture notes]] |
=Lecture 26, [[ECE264]], Spring 2012, Prof. Lu= | =Lecture 26, [[ECE264]], Spring 2012, Prof. Lu= | ||
Latest revision as of 04:28, 11 July 2012
Contents
Lecture 26, ECE264, Spring 2012, Prof. Lu
Sukhyun Hong Prof.Elmqvst Section 1 Lecture on IPA2-5 blokus.
- include <stdio.h>
- inlcude <stdlib.h>
- include <string.h>
- inlcude "Blokus.h"
void print_partition(int size, int *partition) { printf("["); int i; for (i = 0; i < size; i++){ printf(" %d", partition[i])); } printf("]\n"); }
int emptyFirstColumn(char *data, int dim) { int empty = 1; int i; for (i = 0; i < dim; i++){ if (data[i * dim] != '0') empty = 0; } return empty; }
Blokus *gen_row(int row, int prevCol, int size, int *partition, char *data, int dim) { // Base case : Gone through all rows if (row == size) { if (emptyFirstColumn(data, dim)) return NULL; return Blokus_create(data, dim); } // Recursive Case : We stil have not assigned all blocks in this partition in col; in start = 0; int stop = dim - partition[row] + 1;
if (row != 0){ start = prevCol - partition[row] + 1; if (start < 0) start = 0;
stop = prevCol + partition[row - 1] ; if (stop + partition[row] > dim) stop = dim - partition[row] + 1; }
Blokus *head = NULL; for (col = start; col < stop; col++){ memset(data + row * dim, '0', sizeof(char) * dim); memset(data + row * dim + col, '1', // 'a' + row <---------check sizeof(char) * partition[row]); Blokus *list = gen_row(row + 1, col, size, partition, data, dim); head = BlokusL_append(head, list); } return head; }
Blockus *gen_shifts(int *partition, int size, int dim) { char *data = malloc(sizeof(car) * dim * dim); memset(data, '0', sizeof(char) * dim * dim); Blokus *list = gen_row(0, 0, size, partition, data, dim); free(data); return list; }
Blokus *gen_partition(int budget, int pos, int *partition, int dim) { // Base case : no more budget if (budget == 0){ print_partition(pos, partition); Blokus *list = gen_shifts(partition, pos, dim); return list; }
// Recursive case : We have budget Blokus *head = NULL; int spending; for (spending = 1; spending <= budget; spending++){ partition[pos] = spending; Blokus *list = gen_partition(budget - spending, pos + 1, partition, dim); head = BlokusL_append(head, list); } return head; }
Blokus *make_unique(Blokus *head) // <---write { check for uniqueness going through and get rid of duplicates reteurn head; }
Blokus *generate_pieces(int n) { int *partition = malloc(sizeof(int) * n);
// Step 1 + 2 : Partitoin + shift Valid Blokus *head = gen_partition(n, 0, partition, n);
free(partition); // Step 3: Uniqueness
head = make_unique(head); return head; }
int main(int argc, char *argv[]) { if (argc != 2){ return EXIT_FAILURE; }
int n = strtol(argv[1], NULL, 10); Blokus *head = generate_pieces(n); BlokusL_print(head); // printf("generate %d pieces.\n" BlokusL_destroy(head);
return EXIT_SUCCESS;
}
--
- inlcude <stdio.h>
- include <stdlib.h>
- include "Blokus.h"
Blokus *Blokus_create(char *data, int dim) { Blokus *blokus = malloc(sizeof(Blokus)); blokus->data = malloc(sizeof(char) * dim * dim); memcpy(blokus->data, data, sizeof(char) * dim * dim); blokus->dim = dim; blokus->next = NULL; return blokus; }
void Blokus_destroy(Blokus *blokus)
{
free(blokus->data);
free(blokus);
}
void Blokus_print2d(Blokus *blokus) { int i, j; for (i = 0; i<blokus->dim; i++){ for (j=0; j<blokus->dim; j++){ printf("%c", blokus->data[(i * blokus->dim)]); } printf("\n"); } }
void Blokus_print(Blokus *blokus) { int i; for (i = 0; i < blokus->data * blokus->dim ; i++){ printf("%c", blokus->data[i]); } printf("\n"); }
void BlokusL_print2d(Blokus *head)
{
while (head != NULL){
Blokus_print(head);
head = head->next;
}
}
int BlokusL_getCount(Blokus *head) { int count = 0; while (head != NULL){ count++; head = head -> next; } return count;
}
Blokus *BlokusL_insert(char *data, int dim, Blokus *head); { Blokus *blokus = Blokus_create(data, dim); blokus->next = head; return head; }
Blokus *BlokusL_append(Blokus *head, Blokus *head2) //POSSIBLE EXAM QUESITON!!!!!! { if (head == NULL) return head2; Blokus *curr = head; while (curr->next != NULL){ curr = curr->next; } curr->next = head2; return head; }
void BlokuL_destroy(Blokus *head) { while (head != NULL){ Blokus *tmp = head; head = head->next; Blokus_destroy(tmp); } }
/*ECE 264 Lecture Wed Apr18 Peachanok Lertkajornkitti Professor Elmqvst (Section 1)
IPA2-5
need to use: ipa2-1 AND 2-3,2-4
Steps: 1.IPA2-1 2.IPA2-2 3.IPA2-4 4.Print list
- /
- include<stdio.h>
- include<stdlib.h>
- include<string.h>
- include"Blokus.h"
void print_partition(int size,int *partition) { printf("["); int i; for(i=0;i<size;i++) { printf(" %d",partition[i]); } printf("]\n");
Blokus *gen_partition(int budget,int pos,int *partition,int dim) { //Base case: no more budget if(budget==0) { print_partition(pos,partition); Blokus *list = gen_shifts(partition,pos,dim); return list; }
//Recursive case: have budget Blokus *head = NULL; int spending; int (spending = 1;spending<=budget;spending++) { partition(pos) = spending; Blokus *list = gen_partition(budget-spending,pos+1,partition,dim); head = BlokusL_append(head, list); //takes the head and add a new list to the end }
} Blokus *make_unique(Blokus *head) //takes in the head n make sure it's unique { //IPA2-4 return head; } Blokus *generate_pieces(int n) { int *partition = malloc(sizeof(int)*n); //Step 1+2 Blokus *head = gen_partition(n,0,partition,n); free(partition); //Step 3 head = make_unique(head); return head; }
int main(int argc,char *argv[]) { if(argc != 2) { return EXIT_FAILURE; } int n = strtol(argv[1],NULL,10);
Blokus *head = generate_pieces(n); BlokusL_printf(head); BlokusL_destroy(head);
return EXIT_SUCCESS; }
//Blokus.h
- ifndef BLOKUS_H
- define BLOKUS_H
typedef struct Blokus_t{ char *data; int dim; struct Blokus_t *next; }Blokus;
Blokus *Blokus_create(char *data,int dim); void Blokus_destroy(Blokus *blokus); void Blokus_print(Blokus *blokus);
Blokus BlokusL_insert(char *data,int dim,Blokus *head); void BlokusL_print(Blokus *head); void BlokusL_destroy(Blokus *head); Blokus *BlokusL_append(head, list);
- endif /*Blokus.h */
//Blokus.c
- include<stdio.h>
- include<stdlib.h>
- include<string.h>
- include"Blokus.h"
Blokus *Blokus_create(char *data,int dim) { Blokus *blokus = malloc(sizeof(Blokus)); blokus->data = malloc(sizeof(char) * dim * dim); memcpy(blokus->data,data,sizeof(char)*dim*dim); blokus->dim = dim; blokus->next = NULL;
return blokus; } void Blokus_destroy(Blokus *blokus) { free(blokus->data); free(blokus); }
void Blokus_print(Blokus *blokus); { int i; for(i=0;i<blokus->dim*blokus->dim;i++) { printf("%c",blokus->data[i]); } printf("\n");
}
Blokus BlokusL_insert(char *data,int dim,Blokus *head) { Blokus *blokus = Blokus_create(data,dim); blokus->next = head; return head; }
void BlokusL_print(Blokus *head)
{
while(head != NULL)
{
Blokus_piece(head);
head = head->next;
}
}
void BlokusL_destroy(Blokus *head)
{
while(head != NULL)
{
Blokus *tmp = head;
head = head->next;
Blokus_destroy(tmp);
}
}
Blokus *BlokusL_append(Blokus *head, Blokus *head2) //COULD COME OUT IN AN EXAM { if(head == NULL) return head2; Blokus *curr = head; while(curr->next != NULL) { curr = curr->next; }
curr->next = head2; return head; }
===================
Hanye Xu April 19th
Binary search tree v
/ \ left right
everything at left <v right >v integer partition generate piece by shift eliminate duplicates invalid piece 8 squares
how many ways can you shift: a squares & b squares b-1 distance to shift or a-1 distance to shift
for(shift = 1-b; shift<=a-1; shift++) { next two rows;
n= a new piece
p=head;
while('p' != NULL)&&checkDuplicate(P,n) == 0){
p=p->next;
}
if (p==NULL){insert(nth list);
}
binary tree
for any real number x you can find a real number y such that x = 2^y or x = -2^y
n steps to log n steps
suppose have n numbers array of n elements log n
===============================
Wudi Zhou, April 19th, Prof. Lu's section
Hints for last assignment: Steps: 1,Integer partition
2,Generate pieces by shifting
3,Eliminate duplicates
use for loop to shift two rows:
ie for(shift = 1 - b; shift <= a - b; shift ++)
p = head; while((p != NULL) && (checkDuplicate == 0)) { p = p -> next; } if(p == NULL) { insert(n); }
For binary tree: n step can be done by log(n) steps
===================
Kevin Tan(0023987592), section#2 notes 04/17
2-5:
1.integer patition
2.generate piece by shift
3.eliminate duplicates
4.invalid piece
for (shift = 1-b;shift<= a-1; shift++)
for(i=1;i<=n;i++) {
f(n-i);
}
n = a new piece; p=head;
while(('p' != NULL)&&(checkduplicate(p,n)==0)
{
p=p->next;
} if(p==NULL) {
insert(nth list);
}
for any real number x, you can find a real number y, such that x=2^y or x=-2^y
n step can be done by log(n) steps
Lecture Wed Apr18
Huayi Guo
Professor Elmqvst (Section 1)
/* Lecture 0418
Announcement;
Exam 3 - 8-10pm
(-need to take if not passed all outcomes)
ipa2-5 - Monday, Apr23 6pm
(extended!)
ex6 - sat, apr28 12pm(noon)
(no extensions)
Final exam - Sat, May5 8-10pm
(EE206/207,POTR360,MSEE189)
course survey - 0.5pt(email)
- /
//ipa2-5 /* N -> generate all valid and unique pieces of size N(# of cells used)
Need: ipa2-1: partition
ipa2-3: validity
ipa2-4: uniquness
Step 1: Step 2: Step 3:
- /
- include<stdio.h>
- include<stdlib.h>
- include<string.h>
void PartitionPrint(int, size, int *partition) {
printf("[");
int i;
for(i = 0;i<size ;i++){
printf("%d", partition[1]);
}
printf("]\n");
}
Blokus *GenPartition(int budget, int pos, int *partition, int dim) {
//Base case: no more budget
it(budget = 0){
PartitionPrint(pos, partition);
return GenShifts(partition,pos,dim);
}
//REcursive case: we have budget
Blokus *head = NULL;
int spending;
for(spending =1; spending <=budget; spending++){
partition[pos] = spending;
Blokus *list = GenPartition(budget-spending, pos+1,partition, dim);
Blokus *head = BlokusListappend(head, list);
}
return head;
}
int emptyFirstColumn(char *data,int dim) {
int empty = 1;
int i;
for(i= 0; i<dim;i++){
if(data[i*dim]!='0')empty = 0;
}
return empty;
}
Blokus *gen_row(int row, int prevCol int size, int *partition, char* data int dim) {
//base case
if(row == size){
if(emptyFirstColumn(data,dim)) return NULL;
return BlokusCreate(data, dim);
}
//Recursive case
int col;
int start = 0; int stop = dim - partition[row] + 1; if(row != 0){
start = prevCol - partition[row]+1; if(start < 0)start = 0;
stop = prevCol + partition[row -1]; if(stop + partition[row] > dim) stop = dim-partition[row]+1;
}
Blokus *head =NULL;
for(col =start; col <stop;co++){
memset(data + row *dim,'0',sizeof(char)*dim);
memset(dat+row*dim+col, '1',sizeof(char)*partition[row]);
Blokus *list = gen_row(row +1, col,size,partition,data,dim);
head = Blokus
}
}
Blokus * GenShift(int *partition, int size, int dim) {
char * data = malloc(sizeof(char)*dim*dim); memset(dat, '0', sizeof(char)*dim*dim); Blokus * list = gen_row(0,0,size,partition,data,dim); free(data); return list;
}
Blokus *BlokusListappend(Blokus *head, Blokus*list); {
if(head =NULL)return list;
Blokus * curr = head;
while(curr->next != NULL){
curr = curr->next;
}
curr->next = list;
return head;
}
Blokus *MakeUnique(Blokus * head)
{
}
Blokus * GeneratePiece(int n)
{
int *partition = malloc(sizeof(int)*n); //step 1and2 partition+shift valid Blokus * head = GenPartition(n,0, partition,n) free(partition); //step 3: uniqueness; head = MakeUnique(head); return head;
}
int main(int argc, char * argv[]) {
int n = strtol(argv[1], NULL, 10); Blokus * head = GeneratePiece(n); BlokusPrint(head); BlokusDestroy(head); return EXIT_SUCCESS;
}
_________________________________________________________
Shiyu Wang Lec26 April 22nd
Binary Search tree
v
/ \
Left(<v) Right(>v)
n= a new piece
p= head;
while((p!=NULL)&&checkduplite(p)==0) {
p=p->next;
}
if(p==NULL) {
insect(n+0,list);
}
binary tree for any real number x you can find a real number y such that x=2^y
or x=-2^y
n steps
logn steps
n numbers array of n elements
