Lecture26ECE264Spring2012 - Rhea

/*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

• /

1. include<stdio.h>
2. include<stdlib.h>
3. include<string.h>

1. 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

1. ifndef BLOKUS_H
2. 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);

1. endif /*Blokus.h */

//Blokus.c

1. include<stdio.h>
2. include<stdlib.h>
3. include<string.h>

1. 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